Pencarian berbentuk heuristik search dan eskplorasi

Materi 3 Pencarian berbentuk heuristik search dan eskplorasi

)    Strategi pencarian berbentuk(heuristik search strategy)

1.1)            Greedy Best First Search

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.

Greedy Best First Search seperti halnya algoritma yang menggunakan strategi best-first search lainnya mempuyai sebuah fungsi yang menjadi acuan kelayakan sebuah simpul yaitu fungsi evaluasi f(n). pada 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 Searchfungsi 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)

dengan :

g(n) = estimasi biaya dari simpul n ke simpul tujuan (goal node).

Berikut langkah-langkah pencarian lintasan terpendek yang dilakukan Greedy Best First Search :

§  Masukan simpul awal ke dalam Open List.

§  Open berisi simpul awal dan Closed List masih kosong.

§  Masukkan simpul awal ke Closed List dan suksesornya pada Open List.

§  Ulangi langkah berikut sampai simpul tujuan ditemukan dan tidak ada lagi simpul yang akan dikembangkan.

§  Hitung nilai f simpul-simpul yang ada pada Open List, ambil simpul terbaik (f paling kecil).

§  Jika simpul terbesar sama dengan simpul tujuan, maka sukses.

§  Jika tidak, masukkan simpul tersebut ke dalam Closed.

§  Bangkitkan semua suksesor dari simpul tersebut.

§  Untuk setiap suksesor kerjakan :

a.    Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke Open dan catat “parent”nya.

b.   Jika suksesor tersebut sudah pernah dibangkitkan, ubah parent-nya jika jalur parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya, perbarui biaya untuk suksesor tersebut.

1.2)             Algoritma A* (A Star)

Terdapat banyak algoritma pencarian lintasan terpendek, algoritma Dijsktra merupakan salah satu dari algoritma tersebut. Dengan menggunakan fungsi biaya g(n) setiap simpul, algoritma Dijkstra memeriksa kelayakan biaya yang diperlukan untuk mencapai suatu simpul dari sebuah simpul lain. Proses ini dilakukan berulang sampai simpul tujuan diperiksa.

Algoritma Dijkstra memang menjamin didapatkannya jalur optimal, tetapi algoritma ini mempunyai kelemahan. Pemeriksaan simpul akan dilakukan ke segala arah yang dimungkinkan dan pada akhirnya seluruh simpul pada sebuah graf akan diperiksa. Hal ini menyebabkan algoritma ini bekerja dengan lambat, sehingga waktu yang dibutuhkan untuk menemukan solusi akan semakin besar pula.

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.

2)    Fungsi Heuristic

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 heuristic yang 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.

3)    Algoritma Pencarian Lokal dan Masalah Optimisasi

3.1) 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 :

a.  Cari node yang belum pernah digunakan; gunakan node ini untuk mendapatkan keadaan yang baru.

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

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

3.3) 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 :

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.

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

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

Referensi
Buku "Perpustakaan Universitas Pendidikan Indonesia". Hal 20-27.

PPT : https://drive.google.com/open?id=1dQbRnzABtMrq_q-E6GSwsrVEXaRoCHkN