Heuristic Search (kecerdasan buatan)

Teknik Generate dan Test

Generate dan Test adalah cara yang paling sederhana dalam proses pencarian.

Algoritma generate dan test adalah :

• Begin

• Repeat

• Bangkitkan suatu keadaan baru dan namakan dia sebagai current-state;

• Until current-state = Tujuan

• End

C. Teknik Generate dan Test

Contoh :

Kasus 4 puzzle (kotak permainan)

b. Kasus 8 puzzle (kotak permainan)

c. Kasus Travelling Salesman Problem (TSP)

D. Teknik Hill Climbing

Sama halnya dengan teknik generate dan test, Hill Climbing juga melakukan suatu pembangkitan keadaan dan pengujian. Bedanya pengujian pada Hill Climbing menggunakan fungsi heuristik (fx) yang akan memberikan suatu perkiraan ukuran jarak tujuan dari node x.

• Dua teknik Hill Climbing adalah :

• à Simple Hill Climbing

• Algoritmanya :

Begin

1. Tentukan keadaan awal, lakukan pengujian;

If current_state = tujuan

Return

Sukses dan stop

Else do

Current_state=new_current_state

Begin

2. Jadikan new_current_state sebagai keadaan sekarang

Until current_state = tujuan atau current_state dalam keadaan tak ada

operator cari operator baru untuk mendapatkan keadaan yang baru

Evaluasi keadaan baru tersebut;

If new_current_state=tujuan

Return

Sukses dan keluar

Else if nilai new_current_state > current_state

Begin

Repeat

Jadikan new_current_state=current_state

Until current_state=tujuan

End

If nilai new_current_state <>

Lanjutkan iterasi berikutnya

End

End

D. Teknik Hill Climbing

à Simple Hill Climbing

Contoh :

• Kasus Traveling Salesman Problem(TSP)

à Steepest-Ascent Hill Climbing

• Pencarian dengan teknik Steepest-Ascent Hill Climbing lebih cepat karena berdasarkan nilai heuristik terbaik. Pencariannya tidak selalu dimulai dari kiri.

• Hal inilah yang membedakan teknik ini dengan teknik Hill Climbing. Dalam hal ini, urutan penggunaan operator tidak menentukan penemuan solusi.

Contoh :

Diketahui keadaan awal dan tujuan dari suatu permainan kotak 8 puzzle, sebagai berikut :

E. Best First Search

• Teknik pencarian Best First Search merupakan kombinasi antara Depth First Search dan Breadth First Search.

• Teknik ini memperbolehkan pencarian dengan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node yang lebih tinggi memiliki nilai heuristik yang lebih buruk.

• Tak seperti Hill Climbing, teknik Best First Search mempunyai kemampuan melakukan koreksi terhadap suatu langkah yang salah yang telah dipilih lebih dulu.

• Ini merupakan salah satu keuntungan utama Best First Search daripada teknik Hill Climbing.

E. Best First Search

Best First Search bisa dijalankan dengan dua cara, yakni : OR Graph dan Algoritma A*.

à OR Graph

Untuk menjalankan cara ini, dibutuhkan 2 antrian, yakni OPEN dan CLOSED.

– Suatu node disebut open apabila node tersebut telah dibangkitkan dan sudah memiliki fungsi heuristik tetapi belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi.

– Suatu node disebut closed jika node tersebut telah diperluas untuk membangkitkan turunannya.

E. Best First Search

à Algoritma A*

– Untuk mengukur kebaikan dari suatu node dalam algoritma A*, diperlukan dua fungsi biaya, yakni biaya heuristik dan biaya pembangkitan. Biaya heuristik mengukur jarak dari node x yang sekarang menuju ke tujuan dan dinyatakan dengan h(x). Sedangkan biaya pembangkitan node x yang dinyatakan dengan g(x) adalah untuk mengukur jarak dari node x ke node awal dalam graph. Total fungsi biaya yang dinyatakan dengan f(x) adalah jumlah g(x) tambah h(x).

– G(x) dapat diukur dengan mudah saat node x dibangkitkan melalui beberapa transisi keadaan. Misalnya, jika node x dibangkitkan dari node awal melalui transisi keadaan m, biaya g(x) akan menjadi proporsional ke m. Lalu, bagaimana mengevaluasi h(x)? Kemungkinan bahwa h(x) adalah biaya yang keluarkan untuk mencapai tujuan. Jelasnya, biaya apapun dapat dinyatakan sebagai h(x) melalui prediksi. Biaya yang diprediksi untuk h(x) dinyatakan dengan h’(x). Oleh karena itu, biaya total yang diprediksikan dinyatakan dengan f’(x) di mana:

F’(x) = g(x) + h’(x)