Heuristik Search dan Eksplorasi ( Perteuan ke 3 )

Pencarian Berbentuk Heuristik dan Eksplorasi

Pada strategi best-forst search, cost sebenarnya yaitu dari simpul awal ke simpul n, dinotasikan dengan g(n) dan fungsi heuristic yang digunakan yaitu perkiraan/etimasi nilai dari simpul n ke simpul tujuan dinotasikan dengan h(n). Algoritma yang menggunakan metode best-first search, yaitu  :

• Greedy Best-First Search
• Algoritma A*

Beberapa istilah yang sering digunakan pada metode best-first search :

1. Start node, adalah sebuah terminology untuk posisi awal sebuah pencarian.
2. Current node, adalah simpul yang sedang dijalankan (yang sekarang) dalam algoritma pencarian jalan terpendek.
3. Kandidat (successor), adalah simpul-simpul yang berjasen dengan current node, dengan kata lain simpul-simpul yang akan diperiksa berikutnya.
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, yaitusimpul tujuan.
8. Parent, adalah current node dari suksesor/kandidat.

Greedy Best First Search

Greedy Best First Search fungsi evaluasi tidak bergantung pada cost sebelumnya, tetapi hanya bergantung pada fungsi heuristic itu sendiri.jika pada algoritma pencarian yang dilakukan bergantung pada cost sebenarnya dari sebuah simpul yaitu g(n), pada Greedy Best First Search fungsi evaluasi hanya bergantung pada fungsi heuristic h(n) yang mengestimasikan arah yang benar, sehingga pencarian jalur dapat berlangsung dengan sangat secapt. Secara matematis fungsi evaluasi pada greedy search diberikan oleh :

f(n) = h(n)

Salah satu algoritma yang termasuk kedalam kategori informed search adalah Greedy Best First Search yang dikenal juga dengan Greedy Search. Secara harfiah greedy artinya rakus atau tamak, sifat yang berkonotasi negative. Sesuai dengan arti tersebut, prinsip greedy adalah mengambil keputusan yang dianggap terbaik hanya untuk saat itu saja yang diharapkan dapat memberikan solusi terbaik secara keseluruhan. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.

Algoritma A* (A Star)

Algoritma A* adalah algoritma yang menggabungkan Dijkstra dan algoritma Greedy Best First Search. Selain menghitung biaya yang diperlukan untuk berjalan dari simpul satu ke simpul lainnya, algoritma A* juga menggunakan fungsi heuristicuntuk memprioritaskan pemeriksaan simpul-simpul pada arah yang benar, sehingga algoritma A* mempunyai efisiensi waktu yang baik dengan tidak mengorbankan perhitungan biaya sebenarnya.

 Algoritma Pencarian Lokal dan Masalah Optimisasi

• Metode Hill Climbing Search

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin (Sri Kusumadewi 2003, h. 34).

• Simulated Annealing Search

Suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir keristal/logam. Algoritma unt untuk optimalisasi yang bersifat generic.

Secara umum ada 3 hal pokok pada simulated annealing, yaitu:

1. Nilai awal Unt temperature (T0). Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati 0), karena jika T mendekati 0 maka gerakan simulated annealing akan sama dengan hill climbing. Biasanya temperature awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak.
2. Kriteria Yang dipakai unt memutuskan apakah temperature sistem seharusnya dikurangi.
3. Berapa besarnya pengurangan temperature dalam setiap waktu.

• Local Beam Search

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 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 Search membutuhkan tiga komponen sebagai inputnya, yaitu :

1. 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.
2. 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.
3. 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.

• Genetic Algorithm

Genetic Algorithm (GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

Hal-hal yang harus dilakukan untuk menggunakan algoritma genetika:

1. Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.
2. Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan.
3. Menentukan proses pembangkitan solusi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random walk.
4. Menentukan proses seleksi yang akan digunakan.
5. Menentukan proses perkawinan silang (cross over) dan mutasi gen yang akan digunakan.

Referensi : https://bellavira.blogspot.com