Pertemuan 3

Metode Pencarian Heuristik

• Pencarian buta tidak selalu dapat diterapkan dengan baik
  – Waktu aksesnya yang cukup lama
  – Besarnya memori yang diperlukan
• Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar.
• Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan ➔ disebut fungsi heuristic
• Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine
• Contoh pada masalah 8 puzzle:

Keadaan Awal: Tujuan:

• Operator
  – Ubin kosong geser ke kanan
  – Ubin kosong geser ke kiri
  – Ubin kosong geser ke atas
  – Ubin kosong geser ke bawa
• Langkah Awal

• Langkah Awal hanya 3 operator yang bisa digunakan:
  – Ubin kosong digeser ke kiri, ke kanan dan ke atas.
• Jika menggunakan pencarian buta, tidak perlu mengetahui operasi apa yang akan dikerjakan (sembarang).
• Pada pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut.

Informasi yang diberikan dalam domain tersebut adalah sebagai berikut:

• Untuk jumlah ubin yang menempati posisi yang benar jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik)

• Untuk jumlah ubin yang menempati posisi yang salah jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

• Menghitung total gerakan yang diperlukan untuk mencapai tujuan jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Pencarian Heuristik

Pembangkit & Pengujian (Generate and Test)

Pendakian Bukit (Hill Climbing)

Pencarian Terbaik Pertama (Best First Search)

Simulated Annealing

Pembangkit & Pengujian (Generate and Test)

- Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan
pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan-

awal.
- Algoritmanya:

Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).

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.

Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.

Contoh Traveling Salesman Problem (TSP)

• Seorang salesman ingin mengunjungi n kota. Jarak antara tiaptiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali.
  

- Contoh Traveling Salesman Problem (TSP) pada gambar di atas menggunakan Generate & test
dan akan membangkitkan semua solusi yang mungkin sebagai berikut:

A – B – C – D

A – B – D – C

A – C – B – D

A – C – D – B, dll

- Dan contoh gambar berupa tree adalah sebagai berikut:

• Lintasannya sebagai berikut:

- Kelemahan dari Pembangkit & Pengujian (Generate and Test) adalah sebagai berikut:

Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian

Membutuhkan waktu yang cukup lama dalam pencariannya

Pendakian Bukit (Hill Climbing)

- Metode yang digunakan dalam pendakian Bukit (Hill Climbing) adalah sebagai berikut:

Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses
pengujian dilakukan dengan menggunakan fungsi heuristik.

Pembangkitan keadaan berikutnya sangat 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.

Simple Hill Climbing

- Algoritma yang digunakan dalam Simple Hill Climbing

Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:

• Cari operator yang belum pernah digunakan; gunakan operator 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 iterasi.

Contoh Dalam Traveling Salesman Problem (TSP)

- Operator : Tukar kota ke-i dengan kota ke-j (Tk i,j)
- Untuk 4 kota sebagai berikut:

Tk 1,2 : tukar kota ke-1 dengan kota ke-2.

Tk 1,3 : tukar kota ke-1 dengan kota ke-3.

Tk 1,4 : tukar kota ke-1 dengan kota ke-4.

Tk 2,3 : tukar kota ke-2 dengan kota ke-3.

Tk 2,4 : tukar kota ke-2 dengan kota ke-4.

Tk 3,4 : tukar kota ke-3 dengan kota ke-4.

- Cara Pencarian dengan menggunakan tree sebagai berikut:

Steepest Ascent Hill Climbing

- Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri.
- Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.
- Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.
- Algoritmanya sebagai berikut:

Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang.

Tentukan SUCC sebagai nilai heuristic terbaik dari successor - successor.

Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang

Gunakan operator tersebut dan bentuk keadaan baru.

Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah.

Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang, ubah node SUCC menjadi keadaan sekarang.

- Contoh Pencarian dalamm tree sebagai berikut:

Lebih lengkap semua silakan download di bagian "Download Materi"