Heuristik adalah sebuah teknik yang mengembangkan efisiensi
dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan
(completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan
problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan
untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:
1.
Generate and Test.
2.
HillClimbing.
3.
Best First Search.
4.
Alpha
Beta Prunning,Means-End-Anlysis,Constraint
Satisfaction, Simulated Anealing, dll
PEMBANGKITAN dan
PENGUJIAN (Generate and Test)
Metode ini merupakan penggabungan antara depth-first search
dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada
suatu keadaan awal. Algoritma:
·
Bangkitkan suatu kemungkinan solusi
(membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
·
Uji untuk melihat apakah node tersebut
benar-benar merupakan solusinya dengan cara membandingkan node terebut atau
node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang
diharapkan.
·
Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.
Contoh:
“Travelling Salesman
Problem (TSP)” Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap
kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota
hanya boleh dikkunjungi tepat 1 kal i.
Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah
ini:
Penyelesaian dengan metode Generate and Test
PENDAKIAN BUKIT (Hill
Climbing)
Metode ini hampir sama dengan metode pembangkitan dan
pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi
heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari
prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan
seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya
yang mungkin.
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
PENCARIAN TERBAIK
PERTAMA(Best-First Search)
Metode ini merupakan kombinasi dari metode depth-first
search dan breadth-first search. Pada metode best-first search, pencarian
diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika
ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic
yang lebih buruk.
Fungsi Heuristik yang digunakan merupakan prakiraan
(estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :
f’(n) = g(n)+ h’(n)
dimana f’ = Fungsi evaluasi
g = cost dari ini tial state ke current state
h’ = prakiraan cost dari current state ke goal state
Contoh :
Misalkan kita memiliki ruang pencarian seperti pada gambar
dibawah. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya
edge yang menghubungkan node M dengan node A adalah biaya yang dikeluarkan
untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge
minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya
yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah
jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita
bisa mengurut nilai untuk setiap node.
TEST TURING
Turing Test yang dicetuskan oleh Alan Turing pada tahun 1950
bertujuan untuk menguji apakah sebuah program komputer itu cerdas. Tes tersebut
dilakukan dengan membiarkan seorang penguji (C) melakukan sesi tanya-jawab
(dengan text) dengan sebuah mesin (A) dan manusia (B), dan pada akhir sesi
tersebut C diharuskan untuk menentukan diantara A dan B manakah yang sebuah
mesin (program komputer). Jika C dapat membedakan dengan mudah maka AI tersebut
tidak begitu “cerdas”, sedangkan jika C tidak dapat menentukan dengan benar
yang mana yang mesin dan yang mana manusia maka dapat disimpulkan bahwa program
komputer tersebut “cerdas” karena dapat meniru kemampuan manusia menjawab
pertanyaan seperti layaknya manusia.
Sumber :
