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)
