Heuristic Search: Optimize Your Problem-Solving Process

Slide1HEURISTIC  S EARCH Dr. Kusrini, M.Kom

Slide2HEURISTIC  S EARCH  merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan ( state space)  suatu problema secara selektif, yang memandu  proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling  besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu  sebuah teknik yang mengem bangkan efisiensi dalam proses pencarian,  namum dengan kemungkinan mengorbankan kelengkapan ( completeness)

Slide3Untuk dapat menerapkan heuristik dengan baik dalam suatu domain tertentu, diperlukan suatu Fungsi Heuristik.  Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual  dan menentukan seberapa jauh hal tersebut  dapat digunakan untuk mendapatkan solusi yang diinginkan

Slide4JENIS  H EURISTIC  S EARCH  Generate and Test  Pendakian Bukit (Hill Climbing)  Pencarian Terbaik Pertama (Best First Search)  Tabu Search  Simulated Anealing  Cheapest Insertion Heuristic

Slide5GENERATE  A ND  T EST  Metode ini merupakan penggabungan antara  depth first search dengan pelacakan mundur (backtracking) yaitu bergerak ke belakang menuju pada suatu keadaan awal.  Algoritma: 1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal). 2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang  diharapkan. 3. Jika solusi ditemukan, keluar. Jikatidak, ulangi kembali langkah pertama.

Slide6CONTOH  Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana setaip kota hanya boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini :

Slide8HILL  C LIMBING  (P ENDAKIAN  B UKIT )  Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja  proses pengujian dilakukan dengan menggunakan fungsi heuristic .  Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan.  Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

Slide9ALGORITMA  H ILL  C LIMBING 1. Buatlah solusi usulan pertama dengan cara yang  sama seperti yang dilakukan dalam prosedur buat dan uji ( generate and test). Periksalah  apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita  lanjutkan ke langkah berikutnya. 2. Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru. 3. Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini : a. Kirimkanlah elemen ini ke fungsi uji. Jika  elemen ini merupakan sebuah solusi,  berhentilah. b. Jika tidak, periksalah apakah elemen ini  merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah. 4. Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan. 5. Kembalilah ke langkah 2.

Slide11GREEDY  B EST  F IRST  S EARCH  Lakukan node expansion terhadap node di fringe yang nilai h(n)-nya paling kecil  Greedy best-first search selalu memilih node yang kelihatannya paling dekat ke goal.

Slide12A* SEARCH  Hindari node yang berada di path yang “mahal”

Slide13PENGGUNAAN  T EKNIK  P ENCARIAN  D ALAM G AME  P UZZLE  Goal State  Initial State  Kemungkinan Langkah  Aplikasi

Slide14CHEAPEST  I NSERTION  H EURISTICS 1. Penelusuran dimulai dari sebuah kota pertama yang dihubungkan dengan sebuah kota terakhir. 2. Dibuat sebuah hubungan  subtour  antara 2 kota tersebut. Yang dimaksud  subtour  adalah perjalanan dari kota pertama dan berakhir di kota pertama, misal (1,3)    (3,2)    (2,1)

Slide153. Ganti salah satu arah hubungan (arc ) dari dua kota dengan kombinasi dua  arc , yaitu  arc  (i,j) dengan  arc  (i,k) dan  arc  (k,j), dengan k diambil dari kota yang belum masuk  subtour  dan dengan tambahan jarak terkecil. Jarak diperoleh dari : c ik  + c kj  – c ij c ik  adalah jarak dari kota i ke kota k, c kj  adalah jarak dari kota k ke kota j dan c ij  adalah jarak dari kota i ke kota j 4. Ulangi langkah 3 sampai seluruh kota masuk dalam  subtour

Slide16CONTOH 1. Ambil perjalanan dari kota 1 ke 5 2. Buat  subtour     (1,5)    (5,1) 3. Buat tabel yang menyimpan kota yang bisa disisipkan dalam  subtour beserta tambahan jaraknya

Slide174. selanjutnya dibuat tabel yang menyimpan kota yangbisa disisipkan dalam  subtour  beserta tambahan jaraknya

Slide19SUMBER  Russel, S.J., dan Norvig, P., 1995, Artificial Intelligence a Modern Aproach  Winston, P.H., 1992, Artificial Intelligence  Narama, T., 2008, Sliding puzzle n x n dengan algoritma fixed heuristic, Sliding_puzzle_n_x_n_dengan_algoritma_fixed_h euristic.htm

Slide20TUGAS Buat Paper tentang penggunaan salah satu metode pencarian dalam suatu aplikasi  Ingat!  Sumber harus dicantumkan  Dijelaskan langkah-langkahnya