Metode Pencarian Buta dan Heuristik

Pada postingan kali ini, saya akan membahas metode pencarian (searching) dalam Artificial Intelligence.

Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.

Metode searching sendiri terbagi menjadi dua, yaitu :

Pencarian Buta (blind search)
Pencarian Heuristik (heuristic search)

1. Metode Pencarian Buta

Metode pencarian buta adalah metode pencarian yang tidak memiliki informasi awal dan juga merupakan sekumpulan prosedur yang digunakan dalam melacak ruang keadaan. Pencarian berlangsung sampai solusi terakhir ditemukan.

model pencarian ini memiliki tiga ciri – ciri utama yaitu:

Membangkitkan simpul berdasarkan urutan

Kalau ada solusi maka solusi akan ditemukan

Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

Pencarian buta ada 2 metode yang umum digunakan yaitu :

1. BFS (Breadth First Search)

Diagram Pohon dari BFS

Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan sampai ditemukannya solusi.

contoh :

Mencari jalur angkutan umum dari terminal senen ke terminal Kp. Rambutan

* Initial State : Senen

* Goal State : Kp. Rambutan

Rute Perjalanan

Penjelasan Gambar :

1. Membangkitkan anak dari terminal Senen = Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai

2. Karena goal state (Terminal Kp. Rambutan) belum tercapai maka kita bangkitkan anak dari terminal senen

Terminal Blok M = Terminal Grogol, Terminal Lebak Bulus

Terminal Lebak Bulus = Terminal Ciputat, Terminal Kp. Rambutan.

Terminal Pulo Gadung = Terminal bekasi

Terminal Manggarai = Terminal Cililitan, Terminal Harmoni

3. Akhirnya tercapai Goal State (Terminal Kp. Rambutan).

2. DFS (Depth-first Search)

Pada metode Depth-First Search, proses pencarian akan dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi.

Contoh :

Penjelasan :

Pencarian dimulai dari simpul sebelah kiri yaitu ABD karena D tidak memiliki anak maka lanjut ke sebelah kanan yaitu E lalu FG. Anak-anak dari simpul B sudah habis maka lanjut ke simpul C dan di teruskan ke HIJK. K merupakan goal state dari pohon tersebut

Pada prinsipnya, DFS ini menggunakan tumpukan untuk menyimpan seluruh state yang ditemukan atau bisa dikatakan bahwa DFS menggunakan metode LIFO (Last In First Out).

2. Metode Pencarian Heuristik

Metode pencarian heuristik merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan). Teknik pencarian heuristik (heuristic searching) 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. Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).

Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik). Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Jenis-jenis Heuristic Searching :

Generate and Test

Hill Climbing

Best First Search

Alpha Beta Prunning

Means-End-Anlysis

Constraint Satisfaction

Kali ini yang akan dibahas adalah metode Generate and Test dan Hill Climbing.

1. Generate and Test

Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan.Pendekatan ini meliputi langkah–langkah sebagai berikut :

Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.

Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).

Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.

Jika pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya (bila ada). Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama. Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.

Contoh :

“Travelling Salesman Problem (TSP)” Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana setiap kota hanya boleh dikunjungin tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar dibawah ini :

Penyelesaian dengan menggunakan metode Generate and Test :

2. Hill Climbing

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 ya atau tidak. Dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).

Prosedur Hill Climbing :

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.

Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.

Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :

1. Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.

2. Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.

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

4. Kembalilah ke langkah 2.