Pencarian berbentuk/heuristik search dan eksplorasi

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

3.1 Strategi pencarian berbentuk/heuristic search stragegy

PENCARIAN TERBAIK PERTAMA(Best-First Search)

Metode ini merupakan kombinasi dari metode depth-first 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) 

dimana f’ = Fungsi evaluasi 

g = cost dari ini tial state ke current state

h’ = prakiraan cost dari current state ke goal state 

Contoh : 

Misalkan kita memiliki ruang pencarian seperti pada gambar dibawah. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengan node 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 mengurut nilai untuk setiap node.

Terdapat dua jenis algoritma Best First Search, yaitu:
-          Greddy Best yang hanya memperhitungkan biaya perkiraan saja.
-          A* yang memperhitungkan gabungan dua biaya, biaya sebenarnya dan biaya perkiraan.

a. Greddy Best
Greedy Best First Search hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni:
f(n) = h(n)
dimana h(n)= perkiraan biaya dari simpul n ke goal.
Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya maka algoritma ini menjadi tidak optimal.
Algoritma greddy best ini membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

b. A* Search

Algoritma ini merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search danGreddy Best First Search.
Algoritma ini memperhitungkan biaya dari biaya sebenarnya ditambah dengan biaya perkiraan.
Dalam notasi matematika dituliskan sebagai:
f(n) = g(n) + h(n)

g(n) = biaya sebenarnya untuk mencapai simpul n

h(n) = perkiraan biaya dari simpul n ke goal.

f(n) = perkiraan total biaya jalur yang melalui simpul n ke goal.

Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.

Memory-bounded heuristic search

SMA* atau Simplified Memory Bounded A* adalah algoritma pencarian jalur terpendek berdasarkan dari algoritma A*. Keuntungan utama dari algo SMA* adalah dia menggunakan bounded memory, sementara algo A* mungkin membutuhkan memori exponensial. Semua karakteristik di algo SMA* diturunkan dari A*.

Proses

Seperti A *, algoritma SMA* memperluas cabang yang paling menjanjikan menurut heuristik. Apa yang membuat SMA * terpisah adalah SMA* memangkas simpul yang ekspansinya telah diungkapkan kurang menjanjikan dari yang diharapkan. Pendekatan ini memungkinkan algoritma untuk mengeksplorasi cabang dan backtrack untuk mengeksplorasi cabang lain.

Ekspansi dan pemangkasan simpul didorong karena SMA* menjaga dua nilai f untuk setiap simpul. Simpul x menyimpan nilai f(x) yang memperkirakan biaya mencapai tujuan dengan mengambil jalan melalui simpul tersebut. Semakin rendah nilai, semakin tinggi prioritas. Seperti di A * nilai ini diinisialisasi dengan h (x) + g (x), tetapi kemudian akan diperbarui untuk mencerminkan perubahan estimasi ketika anak-anaknya diperluas. Sebuah simpul yang sudah diperluas sepenuhnya akan memiliki nilai f setidaknya setinggi dari suksesornya. Selain itu, simpul menyimpan nilai f dari suksesor terbaik yang telah dilupakan. Nilai ini dikembalikan jika suksesor yang telah dilupakan itu dinyatakan sebagai suksesor paling menjanjikan.

Dimulai dengan simpul pertama, ia mempertahankan OPEN, memerintahkan dengan leksikografi oleh f dan kedalaman. Ketika memilih simpul untuk diperluas, ia memilih yang terbaik sesuai dengan urutan itu. Ketika memilih sebuah simpul untuk dipangkas, ia memilih yang terburuk.

b. Memory bounded heuristik search

SMA* merupakan algoritma yang bekerja dengan heuristic, seperti A*

Selesai jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi terdangkal

Optimal jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi optimal terdangkal, jika tidak dia akan mengembalikan solusi terbaik yang ada di memori

Menjauhi pernyataan yang diulang-ulang selama batas memori memperbolehkannya

Menggunakan semua memori yang ada

Memperbesar batas memori dari algoritma hanya akan mempercepat perhitungan

Ketika memori cukup ada untuk memuat  seluruh pohon pencarian, maka perhitungan mempunyai kecepatan yang optimal

Implementasi

Implementasi dari SMA* sangat mirip dengan implementasi A*, hanya perbedaannya adalah ketika tidak ada ruang yang tersisa, simpul dengan nilai f tertinggi akan dipangkas dari antrian. Karena simpul-simpul tersebut dihapus, SMA* juga harus mengingat nilai f terbaik dari anak yang dilupakan dengan simpul orangtua. Ketika terlihat jika semua jalur yang dieksplorasi lebih buruk dari jalur yang telah dilupakan, maka jalur meregenerasi.

3.2 Fungsi Heuristik

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

3.3 . Algoritma pencarian lokal dan masalah optimisasi

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

b. Simmulated anneling search

Simulated annealing adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas  dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu. Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.

c. local beam search

Beam Search  adalah algoritma pencarian heuristik yang merupakan optimasi dari pencarian best-first search yang mengurangi kebutuhan memorinya. Dalam Beam Search, hanya jumlah solusi parsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.

Beam Search membutuhkan tiga komponen sebagai inputnya, yaitu :

a.    Masalah yang akan di selesaikan

Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang    tiap satu atau lebih node mengarah ke goal/hasil.

b.    Kumpulan aturan-aturan heuristik untuk pemangkasan

Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan ruang masalah.

c.      Memori dengan kapasitas yang terbatas

Adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus, jadi  tidak  akan melebihi memori yang tersedia.

Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori dari pencarian ini jauh lebih sedikit daripada metode yang mendasari mtode pencarian ini.  Kelemahan utama Beam Search adalah metode pencarian ini mungkin  tidak dapat mencapai tujuan/hasil yang optimal dan bahkan mungkin tidak mencapai tujuan sama sekali. Pada kenyataannya, algoritma beam search berakhir untuk dua kasus:  node tujuan yang diperlukan tercapai, atau node tujuan tidak tercapai dan tidak ada node tersisa untuk dieksplorasi.

d. Algoritma Genetika / Genetic Algorithm

Algoritme genetik adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritme genetik adalah kelas khusus dari algoritme evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)

Algoritme Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritme Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritme.

Prosedur Algoritme Genetik

                Algoritme genetik yang umum menyaratkan dua hal untuk didefinisikan: (1) representasi genetik dari penyelesaian, (2) fungsi kemampuan untuk mengevaluasinya.

Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan representasi bentuk bebas diselidiki di dalam HBGA.

Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda (objek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang tetap. Representasi penyelesaian mungkin berbentuk larik bits, dimana tiap bit mewakili objek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah objek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini valid, karena ukuran objek dapat melebihi kapasitas ransel. Kemampuan penyelesaian adalah jumlah nilai dari semua objek di dalam ransel jika representasi itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini digunakan IGA.

Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan, algoritme genetik akan memproses inisialisasi populasi penyelesaian secara acak, dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator-operator mutasi, persilangan, dan seleksi.

Secara sederhana, algoritme umum dari algoritme genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu:

Membentuk suatu populasi individual dengan keadaan acak

Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan

Memilih individual dengan kecocokan yang tertinggi

Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi

Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang diinginkan

Daftar Pustaka
http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html 
http://najibzot.blogspot.co.id/p/teknik-searching-kecerdasan-buatan-di.html 
https://id.wikipedia.org/wiki/Algoritma_genetik
https://rinnooberta.wordpress.com/2013/10/29/pencarian-heuristik/

TUGAS PENGETAHUAN TEKNOLOGI SISTEM CERDAS

MINGGU KE-3

HERI JULIYANTO

13115135

3KA12

UNIVERSITAS GUNADARMA