TEKNIK SEARCHING
Kecerdasan Buatan di ciptakan untuk memecahkan masalah di berbagai bidang yaitu :
- Masalah AI adalah masalah yang dapat dikonversikan kedalam ruang keadaan ( Ruang Masalah ) , mempunyai keadaan awal ( Initial State) , dan keadaan akhir (Goal).
- Mendeskripsikan Masalah
- Ruang Keadaan
- Yaitu suatu ruang yang berisi semua keadaan yang mungkin.
- Keadaan Awal
- Keadaan dimulainya pencarian
- Keadaan Akhir/Goal
- Keadaan diakhirinya suatu pencarian
- Kumpulan Aturan
- Aturan yang dapat digunakan untuk mengubah suatu keadaan(state)ke keadaan lainya
ANALISA TEKNIK SEARCHING DALAM ARTIFICIAL INTELLIGENCE
Pada moment kali ini kita akan coba belajar tentang metode searching dalam Artificial Intelligence 
Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:
Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
- Membangkitkan simpul berdasarkan urutan
- Kalau ada solusi maka solusi akan ditemukan
- Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).
Blind Searching sendiri dibagi menjadi tiga macam yaitu :
1.1.BFS (Breadth First Search)
Breadth First Search yaitu model pencarian yang memakai metode melebar. Untuk mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara membuka node (titik) pada tiap levelnya.
Lebih jelasnya dapat dilihat pada gambar dibawah ini :
1.2.DFS (Depth-first Search)
DFS (Depth-first Search) sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemuakn “goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target/goal.
Dengan menggunakan permasalahan yang sama dengan penjelasan di awal tadi, maka pada model DFS akan di dapatkan solusi seperti gambar di bawah ini.
Jadi, solusi node yang di lalui pada DFS adalah a,b,e,h.
DFS memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node.
1.3.UCS (Uniform Cost Search)
UCS (Uniform Sost Search) adalah perpaduan antara BFS dan DFS. Pada UCS, teknik pencariannya memperhatikan cost/jarak antara 1 node ke node lain.
Berikut ini adalah ilustrasinya :
2. Heuristic Searching
Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan).
Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).
Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis Heuristic Searching :
2.1.Generate and Test
Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan.
Pendekatan ini meliputi langkah–langkah sebagai berikut :
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.
2.2.Hill Climbing
Hill Climbing (mendaki bukit) merupakan salah satu variasi metode buat dan uji (generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search).
Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak. Dalam prosedurHill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :
- Maksimum lokal adalah suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya.
- Daratan (Plateau) adalah suatu daerah datar dari ruang pencarian (search) dimana semua himpunan keadaan tetangganya memiliki nilai yang sama.
- Punggung (Ridge) adalah suatu daerah ruang pencarian (search) yang lebih tinggi daripada daerah sekitarnya, namun tidak dapat dibalikkan oleh langkah–langkah tunggal ke arah manapun.
Solusinya:
- Melakukan langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak ke arah yang lain.
- Melakukan lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru.
- Menerapkan dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah sekaligus.
2.3.Best First Search
Pencarian terbaik pertama (Best First Search) merupakan suatu cara yang menggabungkan keuntungan atau kelebihan dari pencarian Breadth-First Search dan Depth-First Search.
Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya.
Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :
f’ = g + h’
dimana f’ = prakiraan cost dari initial ke goal
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke goal state
Terdapat dua jenis algoritma Best First Search, yaitu:
- Greddy Best yang hanya memperhitungkan biaya perkiraan saja.
- A* yang memperhitungkan gabungan dua biaya, biaya sebenarnya dan biaya perkiraan.
1. Greddy Best
Greedy Best First Search hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni:
f(n) = h(n)
dimana h(n)= perkiraan biaya dari simpul n ke goal.
Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya maka algoritma ini menjadi tidak optimal.
Algoritma greddy best ini membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.
2. A*
Algoritma ini merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search danGreddy Best First Search.
Algoritma ini memperhitungkan biaya dari biaya sebenarnya ditambah dengan biaya perkiraan.
Dalam notasi matematika dituliskan sebagai:
f(n) = g(n) + h(n)
3. Kesimpulan
Berikut ini adalah Tabel Identifikasi dan Analisa tentang perbandingan Teknik Searching.
Referensi : Sumber 1 , Pengantar Inteligensia Buatan – Heuristic Searching (Anonymous Writer)
Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:
- Blind searching
- Heuristic searching
Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
- Membangkitkan simpul berdasarkan urutan
- Kalau ada solusi maka solusi akan ditemukan
- Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).
Blind Searching sendiri dibagi menjadi tiga macam yaitu :
1.1.BFS (Breadth First Search)
Breadth First Search yaitu model pencarian yang memakai metode melebar. Untuk mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara membuka node (titik) pada tiap levelnya.
Lebih jelasnya dapat dilihat pada gambar dibawah ini :
Dalam persoalan pada gambar di atas, urutan node yang dilalui pada pencaian BFS adalah a, b, c, d, e, f, g, h. Seperti pada gambar di bawah ini.
1.2.DFS (Depth-first Search)DFS (Depth-first Search) sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemuakn “goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target/goal.
Dengan menggunakan permasalahan yang sama dengan penjelasan di awal tadi, maka pada model DFS akan di dapatkan solusi seperti gambar di bawah ini.
Jadi, solusi node yang di lalui pada DFS adalah a,b,e,h.DFS memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node.
1.3.UCS (Uniform Cost Search)
UCS (Uniform Sost Search) adalah perpaduan antara BFS dan DFS. Pada UCS, teknik pencariannya memperhatikan cost/jarak antara 1 node ke node lain.
Berikut ini adalah ilustrasinya :
Pada permasalahan diatas telah ditentukan jarak antara node. Maka pada model UCS, teknik yang akan dilakukan adalah membuka node yang memiliki nilai/cost antar node yang terendah.
pada gambar diatas jika kita buka :
c = 10
b = 20
a = 10
Karena nilai c dan a sama maka teserah mau membuka yang mana lebih dahulu.
Seandainya kita membuka c maka kita teruskan pencariannya, lalu kita buka :
d = 10+5 =15
e = 10+40 = 50 (mencapai goal, namun nilai cost nya dirasa masih terlalu besar)
Maka kita buka node d, lalu akan diperoleh hasil :
e = 10+5+30 = 45 (nilai pada pencarian ini pun terasa masih terlau besar) maka dari itu kita buka node yang kecil di awal tadi yaitu node a.
Setelah kita buka node a, maka akan di dapat hasil :
e = 10 + 20 = 30 (di dapatkan goal dengan solusi terbaik)
Dari kasus diatas, dapat kita lihat bahwa ada banyak cara unuk mendapatkan solusi. Namun dari berbagai macam penyelesaian kasus, kita dapat mencari solusi yang paling optimal dan ini lah ke unggulan dari model UCS.2. Heuristic Searching
Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan).
Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).
Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis Heuristic Searching :
- Generate and Test
- Hill Climbing
- Best First Search
- Alpha Beta Prunning
- Means-End-Anlysis
- Constraint Satisfaction
2.1.Generate and Test
Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan.
Pendekatan ini meliputi langkah–langkah sebagai berikut :
- Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.
- Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).
- Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.
2.2.Hill Climbing
Hill Climbing (mendaki bukit) merupakan salah satu variasi metode buat dan uji (generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search).
Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak. Dalam prosedurHill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :
- Buatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya.
- Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.
- Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :
- Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.
- Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.
- Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.
- Kembalilah ke langkah 2.
- Maksimum lokal adalah suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya.
- Daratan (Plateau) adalah suatu daerah datar dari ruang pencarian (search) dimana semua himpunan keadaan tetangganya memiliki nilai yang sama.
- Punggung (Ridge) adalah suatu daerah ruang pencarian (search) yang lebih tinggi daripada daerah sekitarnya, namun tidak dapat dibalikkan oleh langkah–langkah tunggal ke arah manapun.
Solusinya:
- Melakukan langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak ke arah yang lain.
- Melakukan lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru.
- Menerapkan dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah sekaligus.
2.3.Best First Search
Pencarian terbaik pertama (Best First Search) merupakan suatu cara yang menggabungkan keuntungan atau kelebihan dari pencarian Breadth-First Search dan Depth-First Search.
Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya.
Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :
f’ = g + h’
dimana f’ = prakiraan cost dari initial ke goal
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke goal state
Terdapat dua jenis algoritma Best First Search, yaitu:
- Greddy Best yang hanya memperhitungkan biaya perkiraan saja.
- A* yang memperhitungkan gabungan dua biaya, biaya sebenarnya dan biaya perkiraan.
1. Greddy Best
Greedy Best First Search hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni:
f(n) = h(n)
dimana h(n)= perkiraan biaya dari simpul n ke goal.
Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya maka algoritma ini menjadi tidak optimal.
Algoritma greddy best ini membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.
2. A*
Algoritma ini merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search danGreddy Best First Search.
Algoritma ini memperhitungkan biaya dari biaya sebenarnya ditambah dengan biaya perkiraan.
Dalam notasi matematika dituliskan sebagai:
f(n) = g(n) + h(n)
- g(n) = biaya sebenarnya untuk mencapai simpul n
- h(n) = perkiraan biaya dari simpul n ke goal.
- f(n) = perkiraan total biaya jalur yang melalui simpul n ke goal.
3. Kesimpulan
Berikut ini adalah Tabel Identifikasi dan Analisa tentang perbandingan Teknik Searching.
| No | Teknik Searching | Space |
Time
| Completeness | Optimility | |
| 1. | Blind Searching | BFS | Sedikit | Lama | Lengkap | Kurang |
| DFS | Sedikit | Cepat | Kurang | Kurang | ||
| UCS | Sedikit | Lama | Kurang | Kurang | ||
| 2. | Heuristic Searching |
Generate & Test
| Cukup | Lama | Kurang | Cukup Optimal |
| Hill Climbing | Cukup | Cepat | Lengkap | Cukup Optimal | ||
Best First Search
| Cukup | Cepat |
Lengkap dan Jelas
|
Sangat Optimal
| ||
Referensi : Sumber 1 , Pengantar Inteligensia Buatan – Heuristic Searching (Anonymous Writer)
Sumber 2 , http://adamspahalerang.blogspot.com/2012/10/analisa-teknik-searching-dalam.html
makasih banyak min
BalasHapusobeng plus samsung