Kamis, 28 September 2017
PENCARIAN BERBENTUK DAN EKSPLORASI
1. Strategi Pencarian Berbentuk
yaitu meliputi :
A) Greddy Best First Search
Metode
pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal.
Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya
dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan
untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja.
f(n) = h(n)
B) A* Search
Bentuk dari Best First Search
yang paling dikenal adalah algoritma pencarian A* (dibaca dengan “A-star”).
Sedikit berbeda dengan Greedy yang hanya melihat kepada nilai h(n), pencarian
dengan A* melihat kepada kombinasi nilai dari pathnya yaitu g(n) dengan nilai
estimasi yaitu h(n).
f(n) = g(n) +
h(n)
C) Memory-Bounded Heuristic Search
2. Fungsi Heuristik
Heuristic digunakan untuk
mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh
hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
3. Algoritma pencarian lokal dan masalah optimisasi
yaitu meliputi :
A) 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.
B) Simulated Annealing Search
Simulated Annealing adalah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir kristal atau logam. Algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu
Berikut
ini adalah pemetaan dari Physical Annealing ke Simulated Annealing :
Fisika (termodinamika)
|
Simulated Annealing
|
Keadaan sistem
|
Solusi yang mungkin
|
Energi
|
Biaya
|
Perubahan keadaan
|
Solusi tetangga
|
Temperatur
|
Parameter kontrol
|
Keadaan beku
|
Solusi heuristik
|
Annealing
adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam
mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk
susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat
tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan
terkendali dari materi tersebut. Pemanasan materi di awal proses annealing,
memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara
bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses
pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak
bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal
yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.
Secara
umum ada 3 hal pokok pada simulated annealing, yaitu:
a. Nilai awal untuk temperatur (T0).
Nilai T0 biasanya ditetapkan cukup
besar (tidak mendekati nol), karena jika T mendekati 0 maka gerakan simulated
annealing akan sama dengan hill climbing. Biasanya temperatur awal ini
ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak.
b. Kriteria yang digunakan untuk
memutuskan apakah temperatur sistem seharusnya dikurangi.
c. Berapa besarnya pengurangan
temperatur dalam setiap waktu.
Contoh Simulated Annealing
C) Local Beam Search
Beam Search adalah algoritma
pencarian heuristik yangmerupakan optimasi dari
pencarian best-first search yang mengurangikebutuhan memorinya. Dalam
Beam Search, hanya jumlah solusiparsial terbaik yang telah
ditetapkan yang disimpan sebagai kandidat.
Beam Search membutuhkan tiga komponen
sebagai inputnya, yaitu :
a. Masalah yang akan di selesaikan
Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang
tiap satu atau lebih node mengarah ke goal/hasil.
b. Kumpulan aturan-aturan heuristik untuk pemangkasan
Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas
node yang tidak menguntungkan dari memori yang berhubungan dengan ruang
masalah.
c. Memori dengan kapasitas yang terbatas
Adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh
dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang
dihapus, jadi tidak akan melebihi memori yang tersedia.
Beam Search memiliki keuntungan yang berpotensi
mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian
memori daripencarian ini jauh lebih sedikit daripada metode yang
mendasari mtode pencarian ini. Kelemahan utama Beam Search adalah metode
pencarian ini mungkin tidak dapat mencapai tujuan/hasil
yang optimaldan bahkan mungkin tidak mencapai tujuan sama
sekali. Padakenyataannya, algoritma beam search berakhir untuk dua kasus: nodetujuan yang
diperlukan tercapai, atau node tujuan tidak tercapai dantidak ada node tersisa untuk dieksplorasi.
Beam A*
Algoritma ini memberikan sedikit variasi pada A*,
yaitu dengan membatasi simpul yang bisa disimpan di dalam OPEN.
Ketika jumlah simpul di OPEN sudah melebihi batas tertentu,
maka simpul dengan nilai f terbesar akan dihapus. Sedangkan
jumlah simpul yang di dalamCLOSED tetap dibiarkan tanpa batasan
karena simpul yang di dalamCLOSED memang tidak mungkin dihapus.
Dengan membatasi jumlah simpul di OPEN, maka pencarian menjadi
lebih terfokus seperti sinar (beam). Sehingga variasi ini
dinamakan Beam A*.
Implementasi algoritma BA* sama dengan A* tetapi
ada sedikit fungsi tambahan untuk pengecekan dan penghapusan simpul terburuk
di OPEN.
Algoritma Beam A* menggunakan dua senarai
: OPEN danCLOSED. OPEN adalah adalah
senarai (list) yang digunakan untuk menyimpan simpul-simpul yang pernah
dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih
sebagai simpul terbaik (best node). Dengan kata lain, OPEN berisi
simpul-simpul yang masih memiliki peluang (peluangnya masih terbuka)
untuk terpilih sebagai simpul terbaik. Sedangkan CLOSED adalah
senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan dan sudah
pernah terpilih sebagai simpul terbaik. Artinya, CLOSED berisi
simpul-simpul yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk
terpilih sudah tertutup).
Terdapat tiga kondisi bagi setiap sukseror yang dibangkitkan,
yaitu : sudah berada di OPEN, sudah berada di CLOSED,
dan tidak berada di OPEN maupun CLOSED. Pada
ketiga kondisi tersebut diberikan penanganan yang berbeda-beda.
Jika suksesor sudah pernah berada di OPEN,
maka dilakukan pengecekan apakah perlu pengubahan parent atau
tidak tergantung pada nilai g-nya melalui parent lama
atau parent baru. Jika melaluiparent baru
memberikan nilai g yang lebih kecil, maka dilakukan pengubahan parent.
Jika pengubahan parent dilakukan, maka dilakukan pula
perbaruan (update) nilai g dan f pada
suksesor tersebut. Dengan perbaruan ini, suksesor tersebut memiliki kesempatan
yang lebih besar untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor sudah pernah berada di CLOSED,
maka dilakukan pengecekan apakah perlu pengubahan parent atau
tidak. Jika ya, maka dilakukan perbaruan nilai g dan f pada
suksesor tersebut serta pada semua “anak cucunya” yang sudah pernah berada
di OPEN. Dengan perbaruan ini, maka semua anak cucunya tersebut
memiliki kesempatan lebih besar untuk terpilih sebagai simpul terbaik (best
node).
Jika suksesor tidak berada di OPEN maupun CLOSED,
maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor
tersebut sebagai suksesornya best node. Hitung biaya suksesor
tersebut dengan rumus f = g + h.
