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:
0 komentar:
Posting Komentar