Metode Pencarian (II)

Metode Pencarian

(Bagian II)

Pencarian dapat diartikan sebagai sebush proses pelacakan yang merupakan teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan teknik yang penting dalam AI (Artificial Inteligen). Hal penting dalam menentukan keberhasilan sebuah sistem berdasarkan kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Pencarian adalah suatu proses mencari solusi dari suatu permasalahan agar dapat mendapat solusi melalui sekumpulan pencarian yang sudah diperoleh dengan semua kemungkinan keadaan. Untuk mengukur performansi metode pencarian, terdapat empat kriteria yang dapat digunakan:

·         Completeness (Kelengkapan)

·         Time compexity (Kekompleksan waktu)

·         Space complexity (Kekompleksan ruang)

·         Optimality (Optimal)

Ada beberapa teknik pelacakan :

·         Heuristic Search

Heuristic Search disebut sebagai model pencarian terbimbing atau sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).

Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Ada beberapa metode yang tesedia di dalam Heuristic Search diantaranya:

1.      Pembangkitan dan Pengujian (Generate And Test)

Generate And Test yaitu model pencarian dengan car pembangkitan dan pengujian dan merupakan pendekatan yang paling sederhana dari semua pendekatan yang lainnya.

Sebagai Contoh:

“Travelling Salesman Problem (TSP)” 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. Misalnya ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini: 

Sehingga penyelesaian dengan menggunakan metode Generate and Test akan seperti ini

Pendekatan ini meliputi langkah–langkah sebagai berikut :

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

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

o   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 kurang efisien untuk masalah yang besar atau kompleks.

                Sehingga alur pencarian dari persoalan diatas akan menjadi seperti ini:

      Contoh diatas pada pencarian ke-1 terdapat lintasan ABCD dengan panjang lintasan 19  dan lintasan yang terpilih ABCD ddengan panjang lintasan terpilih 19. Pada pencarian ke-2 terdapat lintasan ABDC dengan panjang lintasan 18  dan lintasan yang terpilih ABDC dengan panjang lintasan terpilih 18. Dan pada pencarian ke-3 terdapat lintasan ACBD dengan panjang lintasan 12  dan lintasan yang terpilih ACBD dengan panjang lintasan terpilih pun 12. Dan seterusnya.

2.      Hill Climbing

Hill Climbing disebut sebagai pencarian Pendakian Bukit. Hill Climbing merupakan salah satu variasi dari metode generate and test. Dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search).

Dalam prosedur generate and test, respon fungsi uji hanyalah ya atau tidak. Tetapi di dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan/target.

                        Berikut ini adalah contoh dari Hill Climbing:

Prosedur Hill Climbing :

o   Membuatlah 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.

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

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

o   Kembalilah ke langkah 2.

Sumber:

http://www.ziddu.com/download/23183192/MetodePencariandanPelacakan.docx.html

Pengantar Inteligensia Buatan – Heuristic Searching