Beam Search adalah algoritma pencarian heuristik yang merupakan optimasi dari pencarian best-first search yang mengurangi kebutuhan memorinya. Dalam Beam Search, hanya jumlah solusi parsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.
Beam Search membutuhkan tiga komponen sebagai inputnya, yaitu :
a. Masalah yang akan di selesaikan
Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang tiap satu atau lebih node mengarah ke goal/hasil.
b. Kumpulan aturan-aturan heuristik untuk pemangkasan
Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan ruang masalah.
c. Memori dengan kapasitas yang terbatas
Adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus, jadi tidak akan melebihi memori yang tersedia.
Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori dari pencarian ini jauh lebih sedikit daripada metode yang mendasari mtode pencarian ini. Kelemahan utama Beam Search adalah metode pencarian ini mungkin tidak dapat mencapai tujuan/hasil yang optimal dan bahkan mungkin tidak mencapai tujuan sama sekali. Pada kenyataannya, algoritma beam search berakhir untuk dua kasus: node tujuan yang diperlukan tercapai, atau node tujuan tidak tercapai dan tidak ada node tersisa untuk dieksplorasi.
Beam A*
Algoritma ini memberikan sedikit variasi pada A*, yaitu dengan membatasi simpul yang bisa disimpan di dalam OPEN. Ketika jumlah simpul di OPEN sudah melebihi batas tertentu, maka simpul dengan nilai f terbesar akan dihapus. Sedangkan jumlah simpul yang di dalam CLOSED tetap dibiarkan tanpa batasan karena simpul yang di dalam CLOSED memang tidak mungkin dihapus. Dengan membatasi jumlah simpul di OPEN, maka pencarian menjadi lebih terfokus seperti sinar (beam). Sehingga variasi ini dinamakan Beam A*.
Implementasi algoritma BA* sama dengan A* tetapi ada sedikit fungsi tambahan untuk pengecekan dan penghapusan simpul terburuk di OPEN.
Algoritma Beam A* menggunakan dua senarai : OPEN dan CLOSED. OPEN adalah adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih sebagai simpul terbaik (best node). Dengan kata lain, OPEN berisi simpul-simpul yang masih memiliki peluang (peluangnya masih terbuka) untuk terpilih sebagai simpul terbaik. Sedangkan CLOSED adalah senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik. Artinya, CLOSED berisi simpul-simpul yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup).
Terdapat tiga kondisi bagi setiap sukseror yang dibangkitkan, yaitu : sudah berada di OPEN, sudah berada di CLOSED, dan tidak berada di OPEN maupun CLOSED. Pada ketiga kondisi tersebut diberikan penanganan yang berbeda-beda.
Jika suksesor sudah pernah berada di OPEN, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak tergantung pada nilai g-nya melalui parent lama atau parent baru. Jika melalui parent baru memberikan nilai g yang lebih kecil, maka dilakukan pengubahan parent. Jika pengubahan parent dilakukan, maka dilakukan pula perbaruan (update) nilai g dan f pada suksesor tersebut. Dengan perbaruan ini, suksesor tersebut memiliki kesempatan yang lebih besar untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor sudah pernah berada di CLOSED, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak. Jika ya, maka dilakukan perbaruan nilai g dan f pada suksesor tersebut serta pada semua “anak cucunya” yang sudah pernah berada di OPEN. Dengan perbaruan ini, maka semua anak cucunya tersebut memiliki kesempatan lebih besar untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor tidak berada di OPEN maupun CLOSED, maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor tersebut sebagai suksesornya best node. Hitung biaya suksesor tersebut dengan rumus f = g + h.
Referensi :
http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Beam_search
Suryanto ST. 2007. Artificial Intelligence. Bandung : Penerbit Informatika
1 komentar:
Posting Komentar