Pertemuan Ke-3 : Pencarian Berbentuk/ Heuristik Search Dan Eksplorasi

Nama  : Rezky Audiansyah Putra
Kelas  : 3KA12
NPM   : 18116161

Hasil PPT : https://drive.google.com/open?id=1cB1XbmcKjU2DJlwazSyUdLZBXkn4sUF8 

Strategi pencarian berbentuk / heuristik 

search strategy  

      Teknik Dasar Pencarian  Pencarian adalah proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Teknik pencarian terbagi atas dua teknik, yaitu pencarian buta (blind search) dan pencarian heuristik (heuristic search).

      Penelitian yang pernah dilakukan mengenai permainan pergeseran angka dalam bentuk bintang yaitu dengan menggunakan algoritma breadth first search. Pada penelitian ini penulis menggunakan algoritma Best First Search untuk penyelesaian permainan pergeseran angka pada bentuk bintang ini. Algoritma best first search adalah salah satu algoritma pencarian heuristik yang merupakan kombinasi dari dua algoritma pencarian buta (blind search), yaitu breadth first search dan depth first.

•      Pencarian Heuristik (Heuristic Search)

     Pencarian terbimbing (heuristic search) dibutuhkan karena pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, hal ini dikarenakan waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan.

      Kelemahan ini dapat diatasi jika ada informasi tambahan (fungsi heuristik) dari domain yang bersangkutan. Pada pencarian heuristik, sebuah fungsi heuristik digunakan untuk mengevaluasi keadaan permasalahan tersendiri dan menentukan bagaimana fungsi ini diperlukan dalam memecahkan suatu permasalahan. Sebuah fungsi heuristik adalah sebuah fungsi yang memetakan keadaan permasalahan, yang menjelaskan daya tarik dan digambarkan dalam sebuah angka.

      

      Beberapa heuristik lebih baik dari pada heuristik lainnya, dan semakin baik suatu heuristik, maka semakin sedikit node yang diperlukan untuk diperiksa dalam pohon pencarian untuk menemukan solusi. Oleh karena itu, seperti memilih representasi yang tepat, memilih heuristik yang tepat dapat membuat perbedaan yang signifikan dalam membantu kita untuk memecahkan masalah.

     

      Dalam tugas akhir ini, fungsi heuristik yang akan dipakai sebagai fungsi evaluasi untuk menuntun arah pencarian solusi, adalah Gaschnig’s heuristic. Gaschnig’s heuristic mengukur jumlah pergeseran (swap) dengan tempat/ubin kosong untuk menghasilkan keadaan tujuan (goal state).

•       Algoritma Best First Search

      Apabila pada pencarian dengan algoritma hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node di level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya pada algoritma best first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai heuristik yang lebih buruk.Setiap sebuah node dikembangkan, algoritma akan menyimpan setiap successor node n sekaligus dengan harga (cost) dan petunjuk pendahulunya (parent). Algoritma akan berakhir pada node tujuan, dan tidak ada lagi pengembangan node. “Best first” mengacu pada algoritma mengeksplorasi node dengan "nilai" terbaik pertama. Sebuah fungsi evaluasi digunakan untuk menetapkan nilai untuk setiap calon node. Dalam algoritma ini, ruang pencarian dievaluasi menurut fungsi heuristik yang dinyatakan dengan persamaan berikut:

f(n) = h(n) (1.1)

dimana:

f(n) = fungsi heuristik

h(n) = fungsi evaluasi yang dipakai untuk mengestimasi seberapa baik setiap node dibangkitkan.

•       Memory-bounded A* (SMA)

      adalah salah satu algoritma searching yang menjanjikan solusi yang optimal jika memori yang tersedia setidaknya sebesar jumlah node pada jalur solusi optimal. Heuristic additive digunakan sebagai biaya perkiraan agar algoritma ini dapat diimplementasikan ke dalam planning. Ada dua strategi dalam Planning, yaitu Forward Planning dan Backward Planning. Pada Forward Planning, pencarian jalur solusi akan dilakukan dari initial state menuju goal state, sementara pada Backward Planning pencarian jalur solusi akan dilakukan terbalik dari goal state menuju initial state. Planning sebagai heuristic search adalah cara yang menggabungkan heuristic search dengan planning untuk menemukan jalur solusi.

Dalam tugas akhir ini algoritma SMA dengan menggunakan heuristic additive sebagai biaya estimasi digunakan untuk menyelesaikan permasalahan planning pada studi kasus dunia balok. Pembatasan memori pada algoritma ini aka disimulasikan dalam array of node. Sistem ini akan menampilkan output berupa aksi-aksi yang dilakukan oleh sistem untuk mencapai goal state, menampilkan jumlah aksi yang dilakukan, menghitung jumlah iterasi yang diperlukan, serta menampilkan waktu proses yang dibutuhkan sistem untuk menyelesaikan problem.

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

1.  Jika h(n) = 0, sehingga hanya g(n) yang terlibat maka A* akan bekerja seperti halnya algoritma Dijkstra.

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

3.  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*.

4.  Jika h(n) > h*(n), maka A* tidak menjamin pencarian rute terpendek, tetapi berjalan dengan cepat.

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

Fungsi Heuristik

      Dalam metode pencarian heuristik, digunakan suatu metode yang digunakan untukmengevaluasi keadaan-keadaan masalah individual dan menentukan seberapa jauhhal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Fungsi heuristik berbeda untuk setiap tujuan, sehingga fungsi ini sering dijadikan sebagai parameter penting dalam menyelesaikan fungsi heuristik diimplementasikan untuk mencari jarak dari dua buah verteksyang biasanya menggunakan euclidean dan manhattan distance.

      Suatu fungsi heuristik dapat dikatan baik, apabila dapat memberikan biaya perkiraan yang mendekati biaya sebenarnya. semakin mendekati biaya sebenarnya, fungsi heuristik tersebut semakin baik. Dalam masalah pencarian rute terpendek dengan graph, fungsi heuristik yang dapat digunakan adalah Manhattan Distance.

Algoritma pencarian lokal dan masalah 

optimisasi

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

1.   Simple Hill Climbing ,

2.   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.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.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.3.4 Genetic Algorithm

Genetic Algorithm(atau 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:

Representasi genetis dari domain solusi

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

Agen pencarian online dan lingkungan 

yang tidak diketahui.

Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian

Pencarian melebar pertama (Breadth – First Search) 

Pencarian mendalam pertama (Depth – First Search)

Referensi :

https://stackoverflow.com/questions/32909833/what-is-the-difference-between-local-beam-search-and-stochastic-beam-search

https://piptools.net/algoritma-sa-simulated-annealing/