2. HEURISTIC SEARCH
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. Atau 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.
Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Ø GENERATE dan TEST, Pada prinsipnya
metode ini merupakan penggabungan antara depth-first search dengan pelacakan
mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan
awal.
Algoritma:
– Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu
atau lintasan tertentu dari keadaan awal).
– Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya
dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan
yang dipilih dengan kumpulan tujuan yang diharapkan.
– Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang
pertama.
Contoh : Traveling Salesman Problem (TSP) Seorang salesman ingin
mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Ingin
diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1
kali.
Contoh : Traveling Salesman Problem (TSP)
• Generate & test akan membangkitkan semua solusi yang mungkin:
– A – B – C – D
– A – B – D – C
– A – C – B – D
– A – C – D – B, dll
Kelemahan dari Pembangkit & Pengujian (Generate and Test) yaitu ;
– Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian
– Membutuhkan waktu yang cukup lama dalam pencariannya
Ø
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.
Algoritma Simple HillClimbing.
Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai
tidak ada operator baru yang akan diaplikasikan pada keadaan
sekarang:
- Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
- Evaluasi keadaan baru tersebut :
- Jika keadaan baru merupakan tujuan, keluar
- Jika bukan tujuan, namun nilainya lebih baik dari pada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
- Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
Pada simple hill climbing, ada 3 masalah yang mungkin:
- Algoritma akan berhenti kalau mencapai nilai optimum local
- Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi
- Tidak diijinkan untuk melihat satupun langkah sebelumnya.
Contoh: TSP dengan Simple Hill Climbing :
Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin.
Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila
ada n kota, dan kita ingin mencari kombinasi l intasan dengan menukar posisi
urutan 2 kota, maka kita akan mendapatkan sebanyak:
atau sebanyak 6 kombinasi (lihat gambar dibawah). Fungsi heuristic yang
digunakan adalah panjang lintasan yang terjadi
Referensi:
Tidak ada komentar:
Posting Komentar