TEKNIK
PENCARIAN HEURISTIK
Heuristik adalah sebuah teknik yang
mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan
mengorbankan kelengkapan ( completeness ).
Fungsi Heuristik digunakan untuk
mengevaluasi keaadaan – keadaan problema individual dan menentukan seberapa
jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis – jenis Pencarian Heuristik :
Ø Generate and 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 Generate dan Test:
·
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 pertaama.
Kelemahan
·
Perlu membangkitkan semua kemungkinan
sebelum dilakukan pengujian
·
Membutuhkan waktu yang cukup lama dalam
pencariannya
Contoh :
o
Seorang salesman ingin mengunjungi kota
o
Jarak antara tiap – tiap kota sudah
diketahui
o
Kita ingin mengetahui rute terpendek
dimana setiap kota hanya boleh dikunjungi tepat 1 kali
o
Misal ada 4 kota dengan jarak antara
tiap – tiap kota seperti berikut ini :
Ø Hill Climbing
Hampir
sama Generate and Test, perbedaan terjadi pada feedback dari prosedur test
untuk pembangkitan keadaan berikutnya.
Tes yang
berupa fungsi heuristik akan menunjukkan seberapa baik nilai terkaan yang
diambil terhadap keadaan lain yang mungkin.
Menyelesaikan masalah yang
mempunyai beberapa solusi. Ada solusi yang lebih baik daripada solusi lain.
·
Simple Hill Climbing
Algoritma Simple Hill Climbing:
o
Evaluasi state awal, jika state awal
sama dengan tujuan, maka proses berhenti. Jika tidak sama dengan tujuan maka
lanjutkan proses dengan membuat state awal sebagai state sekarang.
o
Kerjakan langkah berikut sampai solusi
ditemukan atau sampai tidak ada lagi operator baru yang dapat digunakan dalam
state sekarang :
-
Cari sebuah operator yang belum pernah
digunakan dalam state sekarang dan gunakan operator tersebut untuk membentuk
state baru
-
Evaluasi state baru
§ Jika
state baru adalah tujuan, maka proses berhenti
§ Jika
state baru tersebut bukan tujuan tetapi state baru lebih baik daripada state
sekarang, maka buat state baru menjadi state sekarang
§ Jika
state baru tidak lebih baik daripada state sekarang, maka lanjutkan kelangkah
sebelumnya
·
Steepest Ascent Hill Climbing
Mirip dengan simple hill climbing.
Perbedaannya dengan simple hill climbing :
- Semua
suksesor
dibandingkan, dan yang paling dekat dengan solusi yang dipilih
- Pada
simple hill climbing, node pertama yang jaraknya terdekat dengan solusi yang
dipilih
Algoritma Steepest Ascent Hill
Climbing:
o
Evaluasi keadaan awal ( Intial State ),
jika keadaan awal sama dengan tujuan ( Goal State )maka kembali pada initial
state dan berhenti berproses. Jika tidak maka initial state tersebut jadikan
sebagai current state.
o
Mulai dengan current state = intial
state
o
Dapatkan semua pewaris ( successor )
yang dapat dijadikan next state pada current statenya dan evaluasi successor
tersebut dengan fungsi evaluasi dan beri nilai pada setiap successor tersebut
o
Jika salah satu dari successor tersebut
mempunyai nilai yang lebih baik dari current state maka jadikan successor
dengan nilai yang paling baik tersebut sebagai new current state
o
Lakukan operasi ini terus menerus hingga
tercapai current state = goal state atau tidak ada perubahan pada current
statenya
Ø Best First Search
Teknik Best – First – Search adalah
teknik search yang menggabungkan kebaikan yang ada dari teknik Depth – First –
Search dan Breadth – First – Search.
Tujuan menggabungkan dua teknik
search ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat
berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang
ditelusuri. Untuk mendapatkan jalur yang menjajikan adalah dengan memberikan
skala prioritas pada setiap state saat dihasilkan dengan fungsi heuristik.
o
Pada best first search, pencarian
diperbolehkan mengunjungi node di lebih rendah, jika ternyata node di level
lebih tinggi memiliki nilai heuristik lebih buruk.
o
Fungsi
Heuristik yang digunakan merupakan prakiraan ( estimasi ) cost dari initial
state ke goal state, yang
dinyatakan dengan :
- f’(n)
= g(n) + h’(n)
- f’
= Fungsi evaluasi
- g
= cost dari initial state ke current
state
- h’
= prakiraan cost dari current state ke goal state
Untuk menggunakan Best – First –
Search, kita memerlukan dua daftar simpul, yaitu :
OPEN
Berisi simpul yang dihasilkan dari
fungsi heuristik tapi belum di evaluasi, memiliki antrian prioritas dimana
elemen dengan prioritas tertinggi adalah yang memiliki nilai paling baik yang
dihasilkan fungsi heuristik.
CLOSED
Berisi simpul yang sudah di
evaluasi. Kita perlu tatap menyimpan simpul – simpul ini dalam memori jika kita
ingin melakukan search pada Graph, sehingga jika kita menemui suatu simpul kita
bisa memeriksa apakah simpul ini sudah pernah di evaluasi atau belum.
Algoritma Best First Search:
§ Mulai
dengan OPEN hanya berisi initial state
§ Sampai
goal ditemukan atau tidak ada lagi simpul yang tersisa dalam OPEN, lakukan:
- Pilih
simpul terbaik dalam OPEN
- Telusuri
successor-nya
- Untuk
tiap successor, lakukan :
v Jika
belum pernah ditelusuri sebelumnya, evaluasi simpul ini, tambahkan kedalam OPEN
dan catat parentnya.
v Jika
sudah pernah ditelusuri, ganti parent nya jika jalur baru lebih baik dari
sebelumnya.
Ø Alpha Beta Prunning, Means – End –
Anlysis, Constraint Satisfaction, Simulated Annealing, etc.
Sumber:
