Heuristic Beam Search

Heuristic Beam Search

Hill Climbing

Hill Climbing berbeda Generate-and-Test, yaitu pada feedback dari prosedur test untuk membantu pembangkit menentukan yang langsung dipindahkan dalam ruang pencarian. Dalam prosedur Generate & test , respon fungsi pengujian hanya ya atau tidak. Tapi jika pengujian ditambahkan dengan atauran fungsi-fungsi yang menyediakan estimasi dari bagaimana mendekati state yang diberikan ke state tujuan, prosedur pembangkit dapat mengeksplorasi ini sebagaimana ditunjukkan di bawah. HC sering digunakan jika terdapat fungsi heuristic yang baik untuk mengevaluasi state. Sebagai contoh, anda berada di sebuah kota yang tidak dikenal, tanpa peta dan anda ingin menuju ke pusat kota. Cara sederhana adalah
gedung yang tinggi. Fungsi heuristics-nya adalah jarak antara lokasi sekarang dengan gedung yang tinggi dan state yang diperlukan adalah jarak yang terpendek.

Simple HC

Algorithm: Simple HC

1. Evaluate the initial state. If it is also a goal state, then return it and quit. Otherwise,

continue with the initial state as the current state.

2. Loop until a solution is found or until there are no new operators left to be applied in

the current state:

a). Select an operator that has not yet been applied to the current state and apply it to

produce a new state.

b). Evaluate the new state:

(i) If it is a goal state, then return it and quit.

(ii) If it is not a goal state but it is better than the current state, then make it the

current state.

(iii) If it is not better than the current state, then continue in the loop.

Gambar 3.1 Pencarian jalur menggunakan Simple Hill Climbing.

Steepest-Ascent HC
 

Gambar 3.2 Pencarian jalur menggunakan Steepest-Ascent Hill Climbing.

Pada gambar 3.2 di atas, terjadi ambiguitas dimana fungsi heuristik node E dan node F adalah sama. Misalkan dipilih F dan ternyata menemukan solusi di level 8. Padahal terdapat solusi lain yang lebih optimal di level 2. Hal ini dikatakan bahwa Steepest-Ascent Hill Climbing terjebak pada solusi lokal (local minima).

Algoritma Steepest-Ascent HC:

1. Evaluate initial state. If it is also a goal state, then return it and quit. Otherwise,

continue with the initial state as the current state.

2. Loop until a solution is found or until a complete iteration produces no change to

current state:

a). Let SUCC be a state such that any possible successor of the current state will be

better than SUCC.

b). For each operator that applies to the current state do:

(i) Apply the operator and generate a new state.

(ii) Evaluate the new state. If it is a goal state, return it and quit. If not, compare

it to SUCC. If it is better, then set SUCC to this state. If it is not better, leave

SUCC alone.

c). If the SUCC is better than current state, then set current state to SUCC.

Best-First Search

Merupakan metode yang membangkitkan suksesor dengan mempertimbangkan harga (didapat dari fungsi heuristik tertentu) dari setiap node, bukan dari aturan baku seperti DFS maupun BFS. Gambar 3.4 mengilustrasikan langkah-langkah yang dilakukan oleh algoritma Best First Search. Pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node D terpilih

karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node

B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya

akan dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node Tujuan.

Gambar 3.4 Langkah-langkah yang dilakukan oleh algoritma Best First Search.

Untuk mengimplementasikan algoritma pencarian ini, diperlukan dua buah senarai, yaitu: OPEN untuk mengelola node-node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola node-node yang pernah dibangkitkan dan sudah dievaluasi. Algoritma selengkapnya adalah sebagai berikut:

Algoritma Best-Fisrt Search:

1. Start with OPEN containing just the initial state.

2. Until a goal is found or there are no nodes left on OPEN do:

a) Pick the best node on OPEN.

b) Generate its successors.

c) For each successor do:

i. If it has not been generated, evaluate it, add it to OPEN, and record its parent.

ii. If it has been generated, change the parent if this new path is better than the previous one. In that case, update the cost of getting to this node and to any successors that this node may already have.

Posted in: AI