HEURISTIC
SEARCH STRATEGY
Rizka Andriani M
(16115120)
3KA12
UNIVERSITAS
GUNADARMA
FAKULTAS
ILMU KOMPUTER DAN TEKNOLOGI INFORMASI
TAHUN
AJARAN 2017/2018
Heuristik adalah sebuah teknik
yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan
mengorbankan kelengkapan (completeness).
A. 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)
o f’
= Fungsi evaluasi
o g
= cost dari initial state ke current state
o 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.
v
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.
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
v
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.
B. Fungsi Heuristik
Dalam metode pencarian heuristik,
digunakan suatu metode yang digunakan untuk mengevaluasi keadaan-keadaan
masalah individual dan menentukan seberapa jauh hal tersebut dapat digunakan
untuk mendapatkan solusi yang diinginkan. Fungsi heuristik berbeda untuk setiap
tujuan, sehingga fungsi ini sering dijadikan sebagai parameter penting dalam menyelesaikan
permasalahan. Fungsi heuristik diimplementasikan untuk mencari jarak dari dua
buah verteks, yang biasanya menggunakan euclidean dan manhattan distance.
(Funge, 2009) Suatu fungsi heuristik dapat dikatakan 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 Man
a. Hill Climbing Search
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 lainnya yang mungkin.
Algoritma Simple Hill Climbing
Kerjakan langkah-langkah berikut
sampai solusinya ditemukan atau sampai
tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
• Cari
operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan
keadaan yang baru.
• Evaluasi
keadaan baru tersebut :
• Jika
keadaan baru merupakan tujuan, keluar
• Jika
bukan tujuan, namun nilainya lebih baik dari pada keadaan sekarang, maka
jadikan keadaan baru tersebut menjadi keadaan sekarang.
• Jika
keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan
iterasi.
Pada simple hill climbing, ada 3
masalah yang mungkin:
• Algoritma
akan berhenti kalau mencapai nilai optimum local
• Urutan
penggunaan operator akan sangat berpengaruh pada penemuan solusi
• Tidak
diijinkan untuk melihat satupun langkah sebelumnya.
b. Simulated Annealing
Search
Merupakan metode searching yang
memanfaatkan teori probabilitas untuk mencari global minimum dari suatu
permasalahan optimasi. Simulated annealing umumnya digunakan untuk variabel
yang bersifat categorical. Target dari metode ini adalah menemukan solusi bagus
yang bisa diterima, bukan untuk mencari solusi yang terbaik. Nama annealing
berasal dari keilmuan metallurgy, di mana proses tersebut akan berusaha mencari
suatu posisi suhu tertentu yang optimal untuk mengurangi kerusakan dan menambah
ukuran kristal di dalam suatu material.
Analogi dengan proses tersebut,
metode Simulated Annealing ini juga berusaha untuk mencari solusi dengan
berpindah dari solusi yang satu ke solusi yang lainnya, dan apabila solusi baru
yang diuji mempunyai nilai fungsi ‘energy’ yang lebih kecil, maka solusi yang
sedang diuji akan menggantikan solusi yang lama. Umumnya solusi baru yang
dipilih merupakan solusi yang ada di dekat/sekitar solusi yang lama. Fungsi
energi ini sangat bergantung pada parameter-parameter seperti parameter T (yang
sering disebut dengan parameter “Temperature”). Metode ini merupakan adaptasi
dari algoritma Metropolis-Hasting, yang merupakan suatu jenis metode Monte
Carlo, untuk menciptakan sample state yang diperlukan.
Dalam metode ini, beberapa
parameter terkait harus didefinisikan termasuk, the state space (umumnya berupa
vector yang terdiri dari beberapa karakteristik), fungsi energy, prosedur untuk
menciptakan solusi baru, fungsi probabilitas untuk menerima atau menolak, dan
fungsi jadwal annealing dengan keterangan sebagai berikut:
– The state space umumnya
ditentukan dengan melihat pada objek yang menjadi domain space pencarian.
– Fungsi energy umumnya
menyesuaikan pada state space dan beberapa parameter kaitan lainnya.
– Prosedur untuk menciptakan
solusi baru harus ditentukan seefisien mungkin dengan memikirkan karakteristik
yang menjadi objek optimasi. Metode swapping antar karakteristik juga menjadi
salah satu solusinya.
– Fungsi probabilitas untuk
menerima atau menolak umumnya mempunyai bentuk tertentu dan bergantung pada
apakah objek optimasi dapat merupakan fungsi probabilitas atau tidak. Fungsi
probabilitas yang sering digunakan adalah fungsi probabilitas yang terkait
dengan algoritma Metropolis-Hastings.
– Sedangkan untuk rate jadwal
annealing umumnya ditentukan dengan melihat permasalahan yang ada pada objek
optimasi dan ditentukan secara empiris hattan Distance.
c. 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 :
i.
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.
ii. 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.
iii. 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.
Beam A*
Algoritma ini memberikan sedikit
variasi pada A*, yaitu dengan membatasi simpul yang bisa disimpan di dalam
OPEN. Ketika jumlah simpul di OPEN sudah melebihi batas tertentu, maka simpul
dengan nilai f terbesar akan dihapus. Sedangkan jumlah simpul yang di dalam
CLOSED tetap dibiarkan tanpa batasan karena simpul yang di dalam CLOSED memang
tidak mungkin dihapus. Dengan membatasi jumlah simpul di OPEN, maka pencarian
menjadi lebih terfokus seperti sinar (beam). Sehingga variasi ini dinamakan
Beam A*.
Implementasi algoritma BA* sama
dengan A* tetapi ada sedikit fungsi tambahan untuk pengecekan dan penghapusan
simpul terburuk di OPEN.
Algoritma Beam A* menggunakan dua
senarai : OPEN dan CLOSED. OPEN adalah adalah senarai (list) yang digunakan
untuk menyimpan simpul-simpul yang pernah dibangkitkan dan nilai heuristiknya
telah dihitung tetapi belum terpilih sebagai simpul terbaik (best node). Dengan
kata lain, OPEN berisi simpul-simpul yang masih memiliki peluang (peluangnya
masih terbuka) untuk terpilih sebagai simpul terbaik. Sedangkan CLOSED adalah
senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan dan sudah
pernah terpilih sebagai simpul terbaik. Artinya, CLOSED berisi simpul-simpul
yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih
sudah tertutup).
Terdapat tiga kondisi bagi setiap
sukseror yang dibangkitkan, yaitu : sudah berada di OPEN, sudah berada di
CLOSED, dan tidak berada di OPEN maupun CLOSED. Pada ketiga kondisi tersebut
diberikan penanganan yang berbeda-beda.
Jika suksesor sudah pernah berada
di OPEN, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak
tergantung pada nilai g-nya melalui parent lama atau parent baru. Jika melalui
parent baru memberikan nilai g yang lebih kecil, maka dilakukan pengubahan
parent. Jika pengubahan parent dilakukan, maka dilakukan pula perbaruan (update)
nilai g dan f pada suksesor tersebut.
Dengan perbaruan ini, suksesor tersebut memiliki kesempatan yang lebih besar
untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor sudah pernah berada
di CLOSED, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak.
Jika ya, maka dilakukan perbaruan nilai g dan f
pada suksesor tersebut serta pada semua “anak cucunya” yang sudah pernah
berada di OPEN. Dengan perbaruan ini, maka semua anak cucunya tersebut memiliki
kesempatan lebih besar untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor tidak berada di
OPEN maupun CLOSED, maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan
suksesor tersebut sebagai suksesornya best node. Hitung biaya suksesor tersebut
dengan rumus f = g + h.
d. Simulated Annealing
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.
Alpha-Beta Pruning
Alpha beta pruning adalah
prosedur untuk mengurangi jumlah perhitungan dan mencari selama minimax.
Minimax adalah pencarian dua-pass, satu lulus digunakan untuk menetapkan
nilai-nilai heuristik ke node pada kedalaman ply dan yang kedua digunakan untuk
menyebarkan nilai-nilai sampai pohon.
Alpha-beta hasil pencarian secara
mendalam-pertama. Sebuah nilai alpha adalah nilai awal atau sementara terkait
dengan node MAX. Karena MAX node diberi nilai maksimum antara anak-anak mereka,
nilai alpha tidak dapat menurunkan, hanya bisa naik.
Sebuah nilai beta adalah nilai
awal atau sementara terkait dengan node MIN. Karena node MIN diberi nilai
minimum antara anak-anak mereka, nilai beta tidak pernah dapat meningkatkan,
hanya bisa turun.
C. Agen yang berupa perangkat lunak atau biasa
disebut agen cerdas, adalah perangkat lunak yang dapat bertindak seperti orang
yang mampu berinteraksi dengan pencarian online dan lingkungan. Contohnya yang
sedang banyak digunakan :
Ø
Agen Spreadsheet
Agen spreadsheet digunakan untuk
membuat program spreadsheet menjadi lebih mudah digunakan oleh pemakai. Contoh
: Office Assistant pada Excel dapat “mengamati” pemakai dan jika terjadi
sesuatu yang dipandang perlu untuk dibantu, agen cerdas ini akan memberikan
saran.
Ø
Agen Perdagangan Elektronis
Agen untuk perdagangan elektronis
digunakan untuk membantu pemakai yang akan melakukan belanja secara online.
Perangkat lunak seperti ini dapat membantu pemakai dengan berbagai cara berikut
:
o Membantu
pemakai menetukan produk yang dibeli.
o Mencarikan
spesifikasi dan mengkajiny.
o Membantu
rekomendasi.
o Membandingkan
belanjaan untuk mendapatkam harga terbaik untuk produk yang dikehendaki.
o Mengamati
dan mengenalkan kepad pemakai penawaran dan diskon khusus.
Ø
Agen Sitem Operasi
Agen sistem operasi digunkan
untuk membantu penggunaan sistem operasi. Contoh, Microsoft memiliki sejumlah
agen yang dinamakan Wizard pada sistem operasi yang dibuatnya, misalnya Windows
NT. Agen ini digunakan antara lain untuk menambah nama pemakaki, mengelola grup
pemakai, dan manajemen berkas.
Berbagai aplikasi yang lain antara lain
untuk menyortir surat elektronis dan mengamati hasil perbandingan suatu
olahraga tertentu (misalnya sepakbola) dari berbagai situs Web dan kemudian
melaporkan hasilnya dalam bentuk surat elektronis ke para anggota yang
menginginkan hasil tersebut.
Sumber :
http://principessaprincipe.blogspot.co.id/2011/05/beam-search.htmlhttps://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html
Tidak ada komentar:
Posting Komentar