HEURISTIC SEARCH

Pencarian berbentuk Heuristik (Heuristic Search)

• Heuristik adalah 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.
• Jenis-jenis Heuristic Searching:
– Generate and Test.
– Hill Climbing.
– Best First Search.
– Means-EndAnlysis, Constraint Satisfaction, dll.


Strategi pencarian berbentuk / heuristik search strategy   


Teknik Dasar Pencarian adalah proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Teknik pencarian terbagi atas dua teknik, yaitu pencarian buta (blind search) dan pencarian heuristik (heuristic search).


Penelitian yang pernah dilakukan mengenai permainan pergeseran angka dalam bentuk bintang yaitu dengan menggunakan algoritma breadth first search. Pada penelitian ini penulis menggunakan algoritma Best First Search untuk penyelesaian permainan pergeseran angka pada bentuk bintang ini. Algoritma best first search adalah salah satu algoritma pencarian heuristik yang merupakan kombinasi dari dua algoritma pencarian buta (blind search), yaitu breadth first search dan depth first.




Fungsi Heuristik


Dalam metode pencarian heuristik, digunakan suatu metode yang digunakan untukmengevaluasi keadaan-keadaan masalah individual dan menentukan seberapa jauhhal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Fungsi heuristik berbeda untuk setiap tujuan, sehingga fungsi ini sering dijadikan sebagai parameter penting dalam menyelesaikan fungsi heuristik diimplementasikan untuk mencari jarak dari dua buah verteksyang biasanya menggunakan euclidean dan manhattan distance.
Suatu fungsi heuristik dapat dikatan baik, apabila dapat memberikan biaya perkiraan yang mendekati biaya sebenarnya. semakin mendekati biaya sebenarnya, fungsi heuristik tersebut semakin baik. Dalam masalah pencarian rute terpendek dengan graph, fungsi heuristik yang dapat digunakan adalah Manhattan Distance.

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 :

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

3). PENCARIAN TERBAIK PERTAMA (Best-First Search)

Metode ini merupakan kombinasi dari metode depthfirst search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.

Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan : 

f’(n) = g(n) + h’(n)
• f’ = Fungsi evaluasi
• g = cost dari initial state ke current state
• h’ = prakiraan cost dari current state ke goal state
• Contoh: Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.

Memory-bounded A* (SMA)

adalah salah satu algoritma searching yang menjanjikan solusi yang optimal jika memori yang tersedia setidaknya sebesar jumlah node pada jalur solusi optimal. Heuristic additive digunakan sebagai biaya perkiraan agar algoritma ini dapat diimplementasikan ke dalam planning. Ada dua strategi dalam Planning, yaitu Forward Planning dan Backward Planning. Pada Forward Planning, pencarian jalur solusi akan dilakukan dari initial state menuju goal state, sementara pada Backward Planning pencarian jalur solusi akan dilakukan terbalik dari goal state menuju initial state. Planning sebagai heuristic search adalah cara yang menggabungkan heuristic search dengan planning untuk menemukan jalur solusi.

Dalam tugas akhir ini algoritma SMA dengan menggunakan heuristic additive sebagai biaya estimasi digunakan untuk menyelesaikan permasalahan planning pada studi kasus dunia balok. Pembatasan memori pada algoritma ini aka disimulasikan dalam array of node. Sistem ini akan menampilkan output berupa aksi-aksi yang dilakukan oleh sistem untuk mencapai goal state, menampilkan jumlah aksi yang dilakukan, menghitung jumlah iterasi yang diperlukan, serta menampilkan waktu proses yang dibutuhkan sistem untuk menyelesaikan problem.

Genetic Algorithm

Genetic Algorithm(atau GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

Dalam GA biasanya ada 2 hal yang harus didefinisikan:

Representasi genetis dari domain solusi

Fungsi fitness untuk mengevaluasi solusi domain.

Hal-hal yang harus dilakukan untuk menggunakan algoritma genetika

1. Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat
2. Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan
3. Menentukan proses pembangkitan solusi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random walk.
4. Menentukan proses seleksi yang akan digunakan
5. Menentukan proses perkawinan silang (cross over) dan mutasi gen yang akan digunakan

Agen pencarian online dan lingkungan yang tidak diketahui.

Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian

Pencarian melebar pertama (Breadth – First Search) 

Pencarian mendalam pertama (Depth – First Search)



PPT:
https://drive.google.com/open?id=13kXVR3_hRoRL4d324Sfl82N0KVB06zUI

sumber:

https://shabri-prayogi.blogspot.com/2013/08/teknik-pencarian-heuristik-heuristic.html