Heuristic Search

1.1. Pencarian Heuristik

Heuristic search adalah suatu istilah yang berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu.

George Poyla (dalam Kristanto. A, 2003) mendefinisikan heuristik sebagai ”studi tentang sebuah metode dan aturan discovery serta invention” dalam pencarian state space, heuristik didefinisikan sebagai aturan untuk memilih cabang-cabang dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima .

Pemecahan masalah AI menggunakan heuristik dalam dua situasi dasar (Setiawan. S, 1993), yaitu :

1.    Permasalahan yang mungkin tidak mempunyai solusi yang pasti disebabkan oleh ambiguitas (keraguan/ketidakpastian) mendasar dalam pernyataan permasalahan atau data yang tersedia, contohnya diagnosa kedokteran.

2.    Permasalahan yang boleh jadi memiliki solusi pasti, tetapi biaya komputasinya untuk mendapatkan solusi tersebut mungkin sangat tinggi. Dalam banyak problema (misalnya saja catur), pertumbuhan state space adalah secara kombinatorial eksplosif dengan bayak state yang mungkin meningkat secara eksponensial atau faktorial dengan kedalaman pencarian. Dalam hal ini, exhaustive, yakni teknik pencarian brute force seperti pencarian mendalam pertama dan pencarian meluas pertama mungkin gagal menemukan solusi sehingga heuristik akan menangani kerumitan permasalahan ini dengan panduan pencarian pada sepanjang lintasan yang memeberi harapan melewati state. Dengan mengeliminasi state yang tidak memberi harapan dan turunannya dari ruang tersebut maka algoritma heuristik dapat mengalahkan ledakan kombinatorial dan menemukan penyelesaian yang dapat diterima.

Pencarian terbimbing (heuristic search) dibutuhkan karena pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, hal ini disebabkan waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan. Dalam pencarian ruang keadaan, heuristik dinyatakan sebagai aturan untuk melakukan pemilihan cabang-cabang dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima.

Heuristik dapat digunakan pada beberapa kondisi berikut ini (Siswanto, 2010):

1.      Mengatasi combinatorial explosion.

Ada masalah yang kemungkinan arah penyelesaiannya berkembang pesat (bersifat faktorial) sehingga menimbulkan combinatorial explosion. Heuristik merupakan cara untuk menentukan kemungkinan arah penyelesaian masalah secara efisien.

2.      Solusi paling optimal mungkin tidak diperlukan.

Dalam suatu keadaan, mungkin lebih baik mendapatkan solusi yang mendekati optimal dalam waktu yang singkat daripada solusi yang paling optimal dalam waktu yang lama.

3.      Pada umumnya hasilnya cukup baik.

Sekalipun tidak optimal, tetapi biasanya mendekati optimal.  Membantu pemahaman bagi orang yang menyelesaikan persoalan.

4.      Banyak alternatif heuristik yang dapat diterapkan dalam suatu percobaan. Orang yang menyelesaikan persoalan tersebut akan lebih mengerti persoalannya jika mencoba heuristik yang diterapkannya.

Salah satu contoh dari heuristik yang baik untuk tujuan umum yang berguna untuk beragam kombinasi permasalahan adalah the nearest neighbour heuristic, yang bekerja dengan cara menyeleksi alternatif yang paling tinggi secara lokal pada setiap langkahnya. Untuk permasalahan perjalanan salesman, prosedur-prosedur yang harus dilakukan adalah sebagai berikut :

1.      Memilih sebuah kota awal (starting cities)

2.      Melihat kota berikutnya, kemudian melihat semua kota yang belum dikunjungi dan memilih salah satu kota yang paling dekat dengan kota yang dipilih pada saat itu.

3.      Ulangi langkah 2 sampai semua kota dikunjungi.

Sebuah fungsi heuristik mengevaluasi keadaan permasalahan tersendiri dan menentukan bagaimana diperlukan fungsi ini dalam memecahkan suatu permasalahan. Sebuah fungsi heuristik adalah sebuah fungsi yang memetakan keadaan permasalahan, yang mendeskripsikan daya tarik dan digambarkan dalam sebuah angka (Pearl, 1984).

Fungsi heuristik yang dirancang dengan baik dapat berperan dalam sebuah bagian yang penting untuk memandu secara efisien proses pencarian menuju ke sebuah solusi. Tabel 2.1 menunjukkan beberapa fungsi heuristik sederhana untuk beberapa permasalahan.

Kadang kala sebuah nilai tinggi dari fungsi heuristik mengindikasikan sebuah posisi yang baik secara relatif (terlihat pada catur dan tic tac toe), di lain waktu sebuah nilai rendah mengindikasikan sebuah situasi yang menguntungkan (terlihat pada perjalanan salesman). Program yang menggunakan nilai (value) dari fungsi dapat mengusahakan minimal atau maksimal secara tepat.

Tujuan dari sebuah fungsi heuristik adalah untuk memandu proses pencarian tujuan yang menguntungkan dengan menganjurkan jalur yang mana yang diikuti pertama kali ketika tersedia lebih dari satu tujuan. Setelah proses berlangsung, akan bisa dihitung sebuah fungsi heuristik yang sempurna dengan cara melakukan sebuah pencarian yang lengkap dari simpul dalam pertanyaan dan menentukan apakah fungsi ini menuju ke sebuah solusi yang baik.

Sayangnya, seperti semua kaidah penemuan lainnya, heuristik juga dapat salah. Heuristik hanyalah panduan informasi untuk menebak langkah berikutnya yang harus diambil dalam menyelesaikan suatu permasalahan, dan sering dilakukan berdasarkan eksperimen/percobaan atau secara intuisi. Oleh karena menggunakan informasi yang terbatas, heuristik jarang dapat memprediksi tingkah laku yang eksak dari ruang keadaan saat dilakukan pencarian. Heuristik dapat membimbing algoritma pencarian untuk mendapatkan solusi suboptimal atau gagal menemukan solusi apapun, karena tidak ada solusi yang dapat menuju keadaan akhir.

Heuristik dan perancangan algoritma untuk mengimplementasikan pencarian heuristik telah menjadi inti permasalahan penelitian AI. Game playing dan pemecahan teorema (theorem solving) adalah dua aplikasi paling tua dari AI, kedua-duanya memerlukan heuristik untuk memangkas ruang dari solusi yang mungkin.

1). PEMBANGKITAN dan PENGUJIAN (Generate and Test)

• 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 tititk tertentu atau lintasan tertentu dari keadaan awal).
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang  dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.
• Contoh : “Travelling Salesman Problem (TSP)”
*) Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya  boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota  dengan jarak antara tiap-tiap kota seperti berikut ini :

Alur pencarian dengan Generate and Test


Pencarian ke-	Lintasan	Panjang Lintasan	Lintasan terpilih	Panjang Lintasan terpilih
1	ABCD	19	ABCD	19
2	ABDC	18	ABDC	18
3	ACBD	12	ACBD	12
4	ACDB	13	ACBD	12
5	ADBC	16	ACBD	12
Dst…..

2) PENDAKIAN BUKIT (Hill Climbing)

• 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 lainnyayang mungkin.
• Algoritma:
1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator 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 iterasi.
• Contoh: TSP dengan Simple Hill Climbing Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak n!/2!(n-2)

Sumber : http://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html