Pencarian Berbentuk /heuristik search dan Eksplorasi (MATERI 3)

1. Strategi pencarian berbentuk

Dengan menggunakan Uninformed Search Algorithm, beberapa permasalahan dapat dipecahkan, namun tidak semua algoritma dapat menyelesaikan permasalahan dengan efektif serta efisien.

Informed Search Algorithm, disebut juga dengan Heuristic Search. Pencarian dengan algoritma ini menggunakan pengetahuan yang spesifik kepada permasalahan yang dihadapi selain dari definisi masalahnya itu sendiri.

Pada pencarian dengan metode UCS(Salah satu bagian dai Uninformed Search Algorithm), kita membandingkan nilai pada path yang ada lalu kemudian melakukan ekspansi pertama kali pada path dengan nilai yang terkecil. Nilai path ini biasanya dilambangkan dengan g(n). lebih lanjut lagi, dari metode pencarian tsb, pada Informed Search Algorithm, kita akan mengenal nilai estimasi(prediksi) dari satu node ke node yang lainnya. Nilai estimasi ini biasanya dilambangkan dengan h(n). Jika n adalah goal node, maka nilai h(n) adalah nol.

Metode metode pada Informed Search Algorithm :

• Greedy Best First Search

Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal node. 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)

• A * Search (A-Star Search)

Bentuk dari Best First Search yang paling dikenal adalah algorima pencarian A(Dibaca dengan A-Star). Tidak jauh 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)

• Heuristic Best First Search

Fungsi heuristic h(n) merupakan estimasi cost dari n ke simpul tujuan. Sangat penting untuk memilih fungsi heuristic yang baik. Misalkan h(n) merupakan cost sebenarnya dari simpul n ke simpul tujuan, maka pada algoritma A terdapat beberapa kemungkinan yang terjadi pada pemilihan fungsi heuristic yang digunakan, yaitu (Amit Gaming) :

• Jika h(n) = 0, sehingga hanya g(n) yang terlibat maka A* akan bekerja seperti halnya algoritma Dijkstra.
• Jika h(n) < h*(n), maka A* akan mengembangkan titik dengan nilai paing rendah dan algoritma A* menjamin ditemukannya lintasan terpendek. Nilai h(n) terendah akan membuat algoritma mengembangkan lebih banyak simpul. Jika h(n) < h*(n), maka h(n) dikatakan heuristicyang admissible.
• Jika h(n) = h*(n), maka A* akan mengikuti lintasan terbaik dan tidak akan mengembangkan titik-titik yang lain sehingga akan berjalan cepat. Tetapi hal ini tidak akan terjadi pada semua kasus. Informasi yang baik akan mempercepat kinerja A*.
• Jika h(n) > h*(n), maka A* tidak menjamin pencarian rute terpendek, tetapi berjalan dengan cepat.

Jika h(n) terlalu tinggi relative dengan g(n) sehingga hanya h(n) yang bekerja maka A* berubah jadi Greedy Best First Search.

2. 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).

Ada dua macam metode Hill

• Climbing Search, yaitu Simple Hill Climbing , Steepest-ascent Hill Climbing (Sri Kusumadewi 2003, h. 39).

Algoritma untuk Hill Climbing Search adalah sebagai berikut :

1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada node baru yang akan diaplikasikan pada keadaan sekarang :

• Cari node yang belum pernah digunakan; gunakan node ini untuk mendapatkan keadaan yang baru.
• Evaluasi keadaan baru tersebut.

– Jika keadaan baru merupakan tujuan, keluar.

– Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.

– Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan pencarian.

• Simulated Annealing Search

Merupakan ialah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir keristal/logam. Algoritma unt untuk optimalisasi yang bersifat generic. Berbasiskan probabilitas dan mekanika statistic,algoritma ini dapat dipakai untmencari pendekatan terhadap solusi optimum global dari suatu permasalahn. Masalah yang membutuhkan pendekatan simulated annealing ialah masalah-masalah optimisasi kombinatorial, dimana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahn itu.

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

Local 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 :

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.

Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori daripencarian ini jauh lebih sedikit daripada metode yang mendasari metode 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.

• 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.

Dalam GA biasanya ada 2 hal yang harus didefinisikan:

1. Representasi genetis dari domain solusi
2. Fungsi fitness untuk mengevaluasi solusi domain.

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.

3. Agen pencarian online dan lingkungan yang tidak diketahui.

1. Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian.
2. Pencarian melebar pertama (Breadth – First Search).
3. Pencarian mendalam pertama (Depth – First Search).

Link PPT:

https://drive.google.com/open?id=1GMj05p3t6NkHAJxjkVWvfOp7QbB6k6rk

Sumber : 

https://adiazep.wordpress.com/2017/11/12/pencarian-berbentuk-heuristik-search-dan-eksplorasi/

https://shabri-prayogi.blogspot.com/2013/08/teknik-pencarian-heuristik-heuristic.html