Metode Pencarian (Heuristik)
Metode Pencarian (Heuristik)
1. Best First
Search
Best-First Search merupakan sebuah metode yang membangkitkan
simpul dari simpul sebelumnya. Best-first search memilih simpul baru yang
memiliki biaya terkecil diantara semua
leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan.
Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang
disebut fungsi evaluasi f(n).fungsi evaluasi best-first search dapat berupa
biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya
sebenarnya dan biaya perkiraan tersebut.
Pada setiap langkah proses pencarian terbaik pertama, kita
memilih node - node dengan menerapkan fungsi heuristik yang memadai pada setiap
node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk
menghasilkan penggantinya. Fungsi heuristic merupakan suatu strategi untuk
melakukan proses pencarian ruang keadaan suatu problema secara selektif, yang
memandu proses pencarian yang kita lakukan sepanjang jalur yang memiliki
kemungkinan sukses paling besar.
Ada beberapa istilah yang sering digunakan pada metode
best-first search, yaitu:
1. Start node adalah sebuah terminology untuk posisi awal
sebuah pencarian
2. Curret node adalah simpul yang sedang dijalankan dalam
algoritma pencarian jalan terpendek
3. Suksesor adalah simpul-simpul yang yang akan diperiksa
setelah current node
4. Simpul (node)
merupakan representasi dari area pencarian
5. Open list adalah tempat menyimpan data simpul yang
mungkin diakses dari starting node maupun simpul yang sedang dijalankan
6. Closed list adalah tempat menyimpan data simpul yang juga
merupakan bagian dari jalur terpendek yang telah berhasil didapatkan
7. Goal node yaitu simpul tujuan
8. Parent adalah curret node dari suksesor.
o Algoritma Best-first Search
Pertama kali, dibangkitkan node
A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada
langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3,
semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga
node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E,
dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkan semua suksesor B.
Demikian seterusnya sampai ditemukan node tujuan. Ilustrasi algoritma
best-first search dapat dilihat pada gambar dibawah ini.
Untuk mengimplementasikan
algoritma pencarian ini, diperlukan dua buah senarai, yaitu: OPEN untuk
mengelola node-node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE
untuk mengelola node-node yang pernah dibangkitkan dan sudah dievaluasi.
Algoritma selengkapnya adalah sebagai berikut:
· OPEN berisi
initial state dan CLOSED masih kosong.
· Ulangi sampai
goal ditemukan atau sampai tidak ada di dalam OPEN
a. Ambil simpul
terbaik yang ada di OPEN
b. Jika simpul
tersebut sama dengan goal, maka sukses
c. Jika tidak,
masukkan simpul tersebut ke dalam CLOSED
d. Bangkitkan semua
aksesor dari simpul tersebut
e. Untuk setiap
suksesor kerjakan:
· Jika suksesor
tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke
OPEN, dan catat parent.
· Jika suksesor
tersebut sudah pernah dibangkitkan, ubah parent-nyajika jalur melalui parent
ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya
perbarui biaya untuk suksesor tersebut dn nodes lain yang berada di level
bawahnya.
Algoritma yang menggunakan metode best-first search, yaitu:
a. Greedy Best-First
Greedy Best-First adalah algoritma best-first yang paling
sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja,
yakni f(n) = h(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan.
Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya,
maka algoritma ini menjadi tidak optimal.
b. A*
A* adalah algoritma best-first search yang menggabungkan
Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan
didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi
matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan perhitungan biaya
seperti ini, algoritma A* adalah complete dan optimal.
2. Problem
Reduction
Problem reduction adalah dasar teknik pemecahan masalah AI
dimana dilakukan dengan cara mengurangi masalah dalam satu set sub masalah yang
lebih mudah pemecahannya. Intinya adalah berusaha mengurangi masalah dengan
harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Ide utama
teknik problem reduction adalah mendekomposisi masalah ke dalam skala yang
lebih kecil.
Problem Reduction dibagi dalam dua metode yaitu :
a) Graf AND OR
Graf AND OR atau tree merupakan graf yang digunakan untuk memperlihatkan solusi
dari permasalahan yang dapat diselesaikan dengan cara mendekomposisikan masalah
tersebut menjadi sekumpulan masalah yang lebih kecil, dimana semuanya harus
dapat diselesaikan. Pereduksian ini membangkitkan arc(busur) AND. Satu busur
AND akan menghasilkan beberapa nomor dari simpul setelahnya dimana semua simpul
harus diselesaikan supaya pancaran menghasilkan solusi. Hanya saja pada graf OR
banyak pancaran akan muncul dari beberapa node, mengindikasikan beberapa jalan
yang dapat menyelesaikan masalah. Untuk
menemukan solusi dari sebuah graf AND OR kita memerlukan sebuah algoritma yang
serupa dengan algoritma BFS(Best First Search) tetapi dengan kemampuan untuk
menangani pancaran AND dengan tepat. Algoritma ini harus menemukan bagian dari
simpul awal dari graf untuk menghimpun simpul-simpul yang menggambarkan state
solusi. Perlu diketahui bahwa hal ini
mungkin diperlukan untuk mendapatkan lebih dari solusi dalam setiap pancaran
AND. Untuk mendeskripsikan algoritma
Graph AND-OR kita menggunakan nilai F_UTILITY, yaitu biaya solusi. Algoritma :
· Inisialisasi
graph ke node awal.
· Kerjakan
langkah-langkah di bawah ini hingga node awal SOLVED atau sampai biayanya lebih
tinggi dari F_UTILITY
Pada Gambar di atas, pada langkah-1 semula hanya ada satu
node yaitu A. Node A diekspansi hasilnya adalah node B, C, dan D. Node D memiliki biaya yang lebih rendah (6)
jika dibandingkan dengan B dan C (9). Pada langkah-2 node D terpilih untuk
diekspansi, menjadi E dan F dengan biaya estimasi sebesar 10. Sehingga kita
harus memperbaiki nilai f’ dari D menjadi 10. Kembali ke level sebelumnya, node
B dan C memiliki biaya yang lebih rendah daripada D (9 < 10). Pada
langkah-3, kita menelusuri arc dari node A, ke B dan C bersama-sama. Jika B
dieksplore terlebih dahulu, maka akan menurunkan node G dan H. Kita perbaiki
nilai f’ dari B menjadi 6 (nilai G=6 lebih baik daripada H=8), sehingga biaya
AND-arc B-C menjadi 12 (6+4+2). Dengan demikian nilai node D kembali menjadi
lebih baik (10 < 12). Sehingga ekspansi dilakukan kembali terhadap D.
Demikian seterusnya.
b) Graf
AO*(Algorithm Optimized) Algoritma AO* menggunakan struktur Graph dimana
tiap-tiap node pada graph tersebut akan memiliki nilai h’ yang merupakan biaya
estimasi jalur dari node itu sendiri sampai suatu solusi Algoritma .
-
Diketahui GRAPH yang hanya
berisi node awal (sebut saja node INIT).
Hitung h’(INIT).
- Kerjakan langkah-langkah di bawah ini
hingga INI bertanda SOLVED atau samoai nilai h’(INIT) menjadi lebih besar
daripada F_UTILITY:
- Ekspand
INIT dan ambil salah satu node yang belum pernah diekspand (sebut NODE).
-
Bangkitkan successor-successor NODE. Jika tida
memiliki successor maka set FUTULITY dengan nilai h’(NODE). Jika ada successor,
maka untuk setiap successor (sebut sebagai SUCC) yang bukan merupakan ancestor
dari NODE
-
Kirimkan informasi baru tersebut ke graph,
dengan cara: tetapkan S adalah node yang ditandai dengan SOLVED atau node yang
nilai h’-nya baru saja diperbaiki, dan sampaikan nilai ini ke parent-nya.
Inisialisasi S = NODE. Kerjakan langkah-langkah berikut ini hingga S kosong.
-
Jika mungkin, seleksi dari S suatu node yang
tidak memiliki descendant dalam GRAPH yang terjadi pada S. Jika tidak ada,
seleksi sebarang node dari S (sebut: CURRENT) dan hapus dari S.
-
Hitung
biaya tiap-tiap arc yang muncul dari CURRENT. Biaya tiap-tiap arc ini sama
dengan jumlah h’ untuk tiaptiap node pada akhir arc ditambah dengan biaya arc
itu sendiri. Set h’(CURRENT) dengan biaya minimum yang baru saja dihitung dari
stiap arc yang muncul tadi.
-
Tandai
jalur terbaik yang keluar dari CURRENT dengan menandai arc yang memiliki biaya
minimum.
-
Tandai
CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga arc
yang baru saja ditandai tadi telah ditandai dengan SOLVED.
-
Jika
CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah,
maka status baru ini harus disampaikan ke GRAPH. Kemudian tambahkan semua
ancestor dari CURRENT ke S.
Sebagai contoh, pada Gambar di atas, jelas bahwa jalur
melalui C selalu lebih baik daripada melalui B. Tetapi jika biaya node E
muncul, dan pengaruh perubahan yang diberikan ke node B tidak sebesar
pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik. Sebagai
contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11 (10+1),
dengan demikian biaya node A apabila memilih jalur lewat C adalah 12 (11+1).
Tentu saja akan lebih baik memilih jalur melalui node B (11). Tapi tidak
demikian halnya apabila kemudian node D diekspan. Bisa jadi jalur dengan
melalui node B akan lebih buruk lagi ketimbang jalur dengan melalui node C.
3. Constraint
Satisfaction
·
Problem search standard :
State adalah "black box“ setiap struktur data yang
mendukung fungsi successor, fungsi heuristik dan tes goal.
·
CSP :
State didefinisikan sebagai variabel Xi dengan nilai dari
domain, di Tes goal adalah sekumpulan constraint yang menspesifikasikan
kombinasi dari nilai subset variabel. Contoh sederhana adalah bahasa
representasi formal
CSP ini merupakan algoritma general-purpose dengan kekuatan
lebih daripada algoritma pencarian standar.
Contoh : Pewarnaan Peta
· Variabel WA,
NT, Q, NSW, V, SA, T
· Domain Di =
{red,green,blue}
· Constraints
: daerah yang bertetangga dekat harus memiliki warna yang berbeda.
· Contoh WA ≠
NT, atau (WA,NT) {(red,green), (red,blue), (green,red), (green,blue),
(blue,red), (blue,green)}
· Solusi lengkap dan konsisten, contoh : WA =
red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green
4. Means End
Analysis(MEA)
MEA adalah strategi penyelesaian masalah yang diperkenalkan
pertama kali dalam GPS (General Problem Solver) [Newell & Simon, 1963].
Proses pencarian berdasarkan ruang masalah yang menggabungkan aspek penalaran
forward dan backward. Perbedaan antara state current dan goal digunakan untuk
mengusulkan operator yang mengurangi perbedaan itu. Keterhubungan antara operator
dan perbedaan tsb disajikan sebagai pengetahuan dalam sistem (pada GPS dikenal
dengan Table of Connections) atau mungkin ditentukan sampai beberapa
pemeriksaan operator jika tindakan operator dapat dipenetrasi.
Contoh OPERATOR first-order predicate calculus dan operator2
tertentu mengijinkan perbedaan korelasi task-independent terhadap operator yang
menguranginya. Kapan pengetahuan ada tersedia mengenai pentingnya perbedaan,
perbedaan yang paling utama terpilih pertama lebih lanjut meningkatkan rata-rata
capaian dari MEA di atas strategi pencarian Brute-Force. Bagaimanapun, bahkan
tanpa pemesanan dari perbedaan menurut arti penting, MEA meningkatkan metode
pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan
masalah pada perbedaan yang nyata antara current state dengan goal-nya.
Sumber :
- http://deisyamalia.blogspot.co.id/2012/03/best-first-search.html
-http://www.academia.edu/4865567/Teknik_Pencarian_Heuristik_1_25_Pengantar_Kecerdasan_Buatan_AK045218_Generate_and_Test_Hill_Climbing_Best_First_Search_Problem_Reduction_Constraint_Satisfaction_Means_End_Analysis
- http://nailil-hidayah.blogspot.co.id/2013/11/kecerdasan-buatan.html
Komentar
Posting Komentar