Pencarian Berbentuk /heuristik search dan Eksplorasi

Nama          : Safira Regia Tama Basmalah

Kelas          : 3KA10

NPM           : 16115327

Dosen         : Essy Malays Sari Sakti

Strategi pencarian berbentuk

A* Search

Pencarian A*, seperti best-first search, mengevaluasi ruang pencarian menggunakan fungsi heuristik. Tapi A * menggunakan kedua biaya untuk mendapatkan dari keadaan awal ke keadaan saat ini (g (n)), serta perkiraan biaya (heuristik) dari jalur dari simpul saat ini ke tujuan (h (n)). Ini dijumlahkan ke fungsi biaya f (n). Pencarian A *, tidak seperti yang terbaik-pertama, optimal dan lengkap. Daftar OPEN dan CLOSED digunakan lagi untuk mengidentifikasi perbatasan untuk pencarian (daftar OPEN) dan nodul yang dievaluasi sejauh ini (TERTUTUP). Daftar OPEN diimplementasikan sebagai antrian prioritas yang dipesan dengan urutan f terendah (n). Apa yang membuat A * menarik adalah bahwa ia terus mengevaluasi ulang fungsi biaya untuk node saat ia menemukannya kembali. Hal ini memungkinkan A * untuk secara efisien menemukan jalur minimal dari keadaan awal ke keadaan sasaran. Sekarang mari kita lihat A * pada tingkat tinggi dan kemudian kita akan menggali lebih jauh dan menerapkannya pada masalah yang terkenal.

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

Fungsi Heuristik

Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Algoritma pencarian lokal dan masalah optimisasi

Hill Climbing Search

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.

Simulated Annealing Search

Simulated Annealing (SA) adalah algoritma
peningkatan iteratif lainnya dimana keacakan digabungkan untuk memperluas ruang
pencarian dan menghindari terjebak dalam minimum lokal. Sesuai dengan namanya,
algoritma mensimulasikan proses anil. Annealing adalah teknik dalam pengecoran
logam dimana logam cair dipanaskan dan kemudian didinginkan secara bertahap
untuk mendistribusikan molekul secara merata ke dalam struktur kristal. Jika
logam didinginkan terlalu cepat, struktur kristal tidak berakibat, dan padatan logam
lemah dan rapuh (telah dipenuhi dengan gelembung dan retakan). Jika didinginkan
secara bertahap dan terkendali, struktur kristal terbentuk pada tingkat
molekuler sehingga menghasilkan integritas struktural yang hebat. Algoritma
dasar untuk simulasi anil ditunjukkan pada. Kita mulai dengan kandidat solusi
awal dan loop sementara suhunya lebih besar dari nol. Dalam lingkaran ini, kita
menciptakan solusi kandidat yang berdekatan dengan mempertimbang solusi kita
saat ini. Ini mengubah solusi untuk solusi tetangga, tapi secara acak. Kami
kemudian menghitung energi delta antara solusi baru (berdekatan), dan solusi
kami saat ini. Jika energi delta ini kurang dari nol, solusi baru kita lebih
baik daripada yang lama, dan kita menerimanya (kita memindahkan solusi baru
yang berdekatan ke solusi kita saat ini).

Referensi

http://www.mediafire.com/file/sq6k4qs4tsz6sx2/buku12.pdf