5. Metode Pencarian dan Pelacakan 2 (Heuristik)

Metode Pencarian dan Pelacakan 2 (Heuristik)

Hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian.

• Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space).

• Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

• Untuk mengukur perfomansi metode pencarian, terdapat 4 kriteria yang dapat digunakan :

1. Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?
2. Time complexity : berapa lama waktu yang diperlukan? [semakin cepat, semakin baik]
3. Space complexity : berapa banyak memori yang diperlukan
4. Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?
   
   
   Dua teknik pencarian dan pelacakan
   – Pencarian buta (blind search)
   • Pencarian melebar pertama (Breadth – First Search)
   • Pencarian mendalam pertama (Depth – First Search)
   – Pencarian terbimbing (heuristic search)
   • Pendakian Bukit (Hill Climbing)
   • Pencarian Terbaik Pertama (Best First Search)
   5.1 Pencarian Melebar Pertama (Breadth-First Search)
   
   
   • Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1
   • Mulai dari akar terus ke level 1 dari kiri ke kanan
   • Kemudian ke level selanjutnya hingga solusi ditemukan
   
   
   
   
   
   • Keuntungan
   – Tidak akan menemui jalan buntu
   – Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti
   yang paling baik
   – Jika ada satu solusi maka bread-first search akan menemukannya
   • Kelemahannya
   – Membutuhkan memori yang cukup banyak
   – Membutuhkan waktu yang cukup lama
   
   

   5.2 Pengurangan (kompleksitas) atau Problem Reduction Dalam Teknik Pencarian Heuristik 

   • 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)!  atau sebanyak 6 kombinasi. Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi

    

   

   5.3 Constraint Satisfaction
   
   
   • Problem search standard :
     – state adalah "black box“
     – setiap struktur data yang mendukung fungsi successor, fungsi heuristik dan tes goal.
   • CSP:
   – state didefinisikan sebagai variabel Xi dengan nilai dari domain Di – Tes goal adalah sekumpulan constraint yang menspesifikasikan kombinasi dari nilai subset variabel.
   • Contoh sederhana adalah bahasa representasi formal.
   • CSP ini merupakan algoritma general-purpose dengan kekuatan lebih daripada algoritma pencarian standar.
   • Contoh : Pewarnaan Peta 
    
    
   • Variabel WA, NT, Q, NSW, V, SA, T
   • Domain Di = {red,green,blue}
   • Constraints : daerah yang bertetangga dekat harus memiliki warna yang berbeda.
   • Contoh WA ≠ NT, atau (WA,NT) {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}
   • Solusi lengkap dan konsisten, contoh : WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green
     
     
     Constraint Graf
   • Binary CSP biner : setiap constraint merelasikan dua variabel
   • Graf Constraint : node adalah variabel, arc adalah constraint

5.4  MEA (Means-Ends Analysis)

• MEA adalah strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General Problem Solver) [Newell & Simon, 1963].
• Proses pencarian berdasarkan ruang masalah yang menggabungkan aspek penalaran forward dan backward.
• Perbedaan antara state current dan goal digunakan untuk mengusulkan operator yang mengurangi perbedaan itu.
• Keterhubungan antara operator dan perbedaan tsb disajikan sebagai pengetahuan dalam sistem (pada GPS dikenal dengan Table of Connections) atau mungkin ditentukan sampai beberapa pemeriksaan operator jika tindakan operator dapat dipenetrasi.
• Contoh OPERATOR first-order predicate calculus dan operator2 tertentu mengijinkan perbedaan korelasi task-independent terhadap operator yang menguranginya.
• Kapan pengetahuan ada tersedia mengenai pentingnya perbedaan, perbedaan yang paling utama terpilih pertama lebih lanjut meningkatkan rata-rata capaian dari MEA di atas strategi pencarian Brute-Force.
• Bagaimanapun, bahkan tanpa pemesanan dari perbedaan menurut arti penting, MEA meningkatkan metode pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata antara current state dengan goal-nya.

sumber:  https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/
             http://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html