Strategi Pencarian Berbentuk (heuristic search stragegy)

TUGAS PENG. TEKNOLOGI SISTEM CERDAS

 

Nama :Inka Riesty Gunadi

Npm    :13115384

Kelas   :3KA10

Dosen   :Essy Malays Sari Sakti

  

UNIVERSITAS GUNADARMA

2017

Strategi pencarian berbentuk(heuristic search stragegy)

1. Greedy 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)

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

Fungsi Heuristik

Fungsi heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state,yang dinyatakan dengan :

Ket:

f’ = Fungsi evaluasi

g  = cost dari initial state ke current state

h’ = prakiraan cost dari current state ke soal state

Algoritma Pencarian Local dan Masalah Optimisasi

1.Hill Climbing (Pendaki Bukit)

Hill Climbing (mendaki bukit) merupakan salah satu variasi metode buat dan uji (generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search).Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah iya atau tidak. Dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).

2.SimulatedAnnealingSearch
adalah salah satu 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. 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.
contoh :
1. Simulated Annealing padaTSP digunakan untuk menelusuri dan mencari setiap rute yang mungkin, kemudian mendapatkan rute yang jaraknya paling pendek.
2. Model Simulated Annealing untuk menyelesaikan TSP adalah model state yang dibangun untuk menyatakan rute yang mungkin dan definisi energi yang dinyatakan dengan total jarak yang ditempuh.

3. Berapa besarnya pengurangan temperature dalam setiap waktu

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.

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

3.4Agen 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:

http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/

hendrik.staff.gunadarma.ac.id/Downloads/files/23065/teknik-pencarian-heuristik.pdf

https://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Iterative_Improvement/Hill_Climbing

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

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