Greedy Best First Search
Salah satu algoritma yang termasuk kedalam kategori informed
search adalah Greedy Best First Search yang dikenal juga
dengan Greedy Search. Secara harfiah greedy artinya
rakus atau tamak, sifat yang berkonotasi negative. Sesuai dengan arti tersebut,
prinsip greedy adalah mengambil keputusan yang dianggap
terbaik hanya untuk saat itu saja yang diharapkan dapat memberikan solusi
terbaik secara keseluruhan. Oleh karena itu, pada setiap langkah harus dibuat
keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil
pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.
Greedy Best First Search seperti
halnya algoritma yang menggunakan strategi best-first search lainnya
mempuyai sebuah fungsi yang menjadi acuan kelayakan sebuah simpul yaitu fungsi
evaluasi f(n). padaGreedy Best First Search fungsi evaluasi tidak
bergantung pada cost sebelumnya, tetapi hanya bergantung pada
fungsi heuristic itu sendiri.jika pada algoritma pencarian
yang dilakukan bergantung pada cost sebenarnya dari sebuah simpul yaitu g(n),
pada Greedy Best First Search fungsi evaluasi hanya bergantung
pada fungsi heuristic h(n) yang mengestimasikan arah yang
benar, sehingga pencarian jalur dapat berlangsung dengan sangat secapt. Secara
matematis fungsi evaluasi pada greedy search diberikan oleh :
f(n) = h(n)
dengan :
g(n) = estimasi biaya dari simpul n ke simpul tujuan
(goal node).
Berikut langkah-langkah pencarian lintasan terpendek yang
dilakukan Greedy Best First Search :
- Masukan simpul awal ke dalam Open List.
- Open berisi simpul awal dan Closed List masih kosong.
- Masukkan simpul awal ke Closed List dan suksesornya pada Open List.
- Ulangi langkah berikut sampai simpul tujuan ditemukan dan tidak ada lagi simpul yang akan dikembangkan.
- Hitung nilai f simpul-simpul yang ada pada Open List, ambil simpul terbaik (f paling kecil).
- Jika simpul terbesar sama dengan simpul tujuan, maka sukses.
- Jika tidak, masukkan simpul tersebut ke dalam Closed.
- Bangkitkan semua suksesor dari simpul tersebut.
Untuk setiap suksesor kerjakan :
a. Jika suksesor tersebut belum pernah
dibangkitkan, evaluasi suksesor tersebut, tambahkan ke Open dan catat “parent”nya.
b. Jika suksesor tersebut sudah pernah
dibangkitkan, ubah parent-nya jika jalur parent ini lebih baik daripada jalur
melalui parent yang sebelumnya. Selanjutnya, perbarui biaya untuk suksesor
tersebut.
Algoritma A* (A Star)
Terdapat banyak algoritma pencarian lintasan terpendek,
algoritma Dijsktra merupakan salah satu dari algoritma tersebut. Dengan
menggunakan fungsi biaya g(n) setiap simpul, algoritma
Dijkstra memeriksa kelayakan biaya yang diperlukan untuk mencapai suatu simpul
dari sebuah simpul lain. Proses ini dilakukan berulang sampai simpul tujuan
diperiksa.
Algoritma Dijkstra memang menjamin didapatkannya jalur
optimal, tetapi algoritma ini mempunyai kelemahan. Pemeriksaan simpul akan
dilakukan ke segala arah yang dimungkinkan dan pada akhirnya seluruh simpul
pada sebuah graf akan diperiksa. Hal ini menyebabkan algoritma ini bekerja
dengan lambat, sehingga waktu yang dibutuhkan untuk menemukan solusi akan
semakin besar pula.
Algoritma A* adalah algoritma yang menggabungkan Dijkstra
dan algoritma Greedy Best First Search. Selain menghitung biaya
yang diperlukan untuk berjalan dari simpul satu ke simpul lainnya, algoritma A*
juga menggunakan fungsi heuristic untuk memprioritaskan
pemeriksaan simpul-simpul pada arah yang benar, sehingga algoritma A* mempunyai
efisiensi waktu yang baik dengan tidak mengorbankan perhitungan biaya
sebenarnya.
A* Search
Bentuk
dari Best First Search yang paling dikenal adalah algoritma pencarian A*
(dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat
kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari
pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).
f(n) = g(n) + h(n)
dengan,
g(n) = biaya dari simpul awal (start node) ke simpul n.
h(n) = estimasi biaya dari simpul n ke simpul tujuan
(goal node).
Algoritma A* menggunakan dua buah list yaitu Open
List dan Closed List. Seperti halnya best-first
searchyang lain kedua list mempunyai fungsi yang sama. Pada awalnya Open
List hanya berisi satu simpul awal dan Closed List masih
kosong. Perlu diperhatikan setiap simpul akan menyimpan petunjuk “parent”nya
sehingga stelah pencarian berakhir lintasan juga akan didapatkan. Berikut
adalah langkah-langkah algoritma A* (A Star) :
- Masukkan simpul awal ke Open List.
- Ulangi langkah berikut sampai pencarian berakhir.
a. Cari node n dengan
nilai f(n) paling rendah, dalam Open List. Node ini akan menjadi current node.
b. Keluarkan current node
dari Open List dan masukkan ke Closed List.
c. Untuk setiap suksesor
dari current node lakukan langkah berikut :
- Jika sudah dalam terdapat dalam Closed List,
abaikan, jika tidak lanjutkan.
- Jika belum ada pada Open List, masukkan ke Open
List. Simpan current node sebagai “parent” dari suksesor ini. Simpan cost masing-masing
simpul.
- Jika sudah ada dalam Open List, periksa jika
simpul suksesor ini mempunyai nilai lebih disbanding suksesor sebelumnya. Jika
lebih kecil, jadikan sebagai current node dang anti “parent” node ini.
d. Walaupun telah mencapai simpul tujuan,
jika masih ada suksesor yang memiliki nilai lebih kecil, maka simpul tersebut
akan terus dipilih sampai bobotnya jauh lebih besar atau mencapai simpul akhir
dengan bobot yang lebih kecil disbanding dengan simpul sebelumnya yang telah
mencapai simpul tujuan.
e. Pada setiap pemilihan simpul
berikutnya, nilai f(n) akan dievaluasi dan jika terdapat nilai f(n) yang sama
akan dipilih berdasarkan nilai g(n) terbesar.
Memory-Bounded
Heuristic Search
1. Fungsi Heuristik
Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan
menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi
yang diinginkan.
2. Algoritma pencarian lokal dan masalah optimisasi
yaitu meliputi :
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.
B) Simulated Annealing Search
Simulated
Annealing adalah suatu algoritma optimasi yang mensimulasikan
proses annealing pada pembuatan materi yang terdiri dari butir
kristal atau logam. 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
Berikut
ini adalah pemetaan dari Physical Annealing ke Simulated Annealing :
Fisika (termodinamika)
|
Simulated Annealing
|
Keadaan sistem
|
Solusi yang mungkin
|
Energi
|
Biaya
|
Perubahan keadaan
|
Solusi tetangga
|
Temperatur
|
Parameter kontrol
|
Keadaan beku
|
Solusi heuristik
|
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.
Secara umum ada 3 hal pokok pada simulated annealing, yaitu:
a. Nilai awal untuk temperatur (T0).
Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati
nol), karena jika T mendekati 0 maka gerakan simulated annealing akan sama
dengan hill climbing. Biasanya temperatur awal ini ditetapkan sebesar 2 kali
panjang suatu jalur yang dipilih secara acak.
b. Kriteria yang digunakan untuk memutuskan
apakah temperatur sistem seharusnya dikurangi.
c. Berapa besarnya pengurangan temperatur
dalam setiap waktu.
Algoritma Pencarian Lokal dan Masalah Optimisasi
Metode Hill Climbing Search
Metode ini hampir sama dengan metode pembangkitan dan
pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi
heuristik.
Pembangkitan keadaan berikutnya sangat tergantung pada
feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan
menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap
keadaan-keadaan lainnya yang mungkin(Sri Kusumadewi 2003, h. 34).
Ada dua macam metode Hill
* Climbing Search, yaitu Simple Hill Climbing
, Steepest-ascent Hill Climbing (Sri Kusumadewi 2003, h. 39).
Algoritma untuk Hill Climbing Search adalah sebagai
berikut :
1. Mulai dari keadaan awal, lakukan pengujian: jika
merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan
sekarang sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut sampai solusinya
ditemukan, atau sampai tidak ada node baru yang akan diaplikasikan pada keadaan
sekarang :
a. Cari node yang belum pernah digunakan;
gunakan node 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 pencarian.
Simulated Annealing Search
Merupakan ialah suatu algoritma optimasi yang
mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir
keristal/logam. Algoritma unt untuk optimalisasi yang bersifat generic.
Berbasiskan probabilitas dan mekanika statistic,algoritma ini dapat dipakai
untmencari pendekatan terhadap solusi optimum global dari suatu permasalahn.
Masalah yang membutuhkan pendekatan simulated annealing ialah masalah-masalah
optimisasi kombinatorial, dimana ruang pencarian solusi yang ada terlalu besar,
sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahn itu.
Secara umum ada 3 hal pokok pada simulated annealing,
yaitu:
1. Nilai awal
Unt temperature (T0). Nilai T0 biasanya ditetapkan cukup
besar (tidak mendekati 0), karena jika T mendekati 0 maka gerakan simulated
annealing akan sama dengan hill climbing. Biasanya temperature awal ini
ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak.
2. Kriteria
Yang dipakai unt memutuskan apakah temperature sistem
seharusnya dikurangi.
3. Berapa besarnya pengurangan temperature dalam setiap
waktu.
Local Beam Search
Local beam search adalah algoritma pencarian heuristik
yangmerupakan optimasi dari pencarian best-first search yang
mengurangikebutuhan memorinya. Dalam Beam Search, hanya jumlah solusiparsial
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
daripencarian 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 optimaldan bahkan mungkin
tidak mencapai tujuan sama sekali. Padakenyataannya, algoritma beam search
berakhir untuk dua kasus: nodetujuan yang diperlukan tercapai, atau node
tujuan tidak tercapai dantidak ada node tersisa untuk dieksplorasi.
Genetic Algorithm
Genetic Algorithm (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:
1. Representasi genetis dari domain solusi
2. 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.
1. Pencarian buta (uninformed/blind search) :
tidak ada informasi awal yang digunakan dalam proses pencarian.
2. Pencarian melebar pertama (Breadth – First
Search).
3. Pencarian mendalam pertama (Depth – First
Search).
Sumber:
Buku "Perpustakaan Universitas Pendidikan
Indonesia". Hal 20-27.
http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html
https://bellavira.blogspot.co.id/2017/10/pencarian-berbentuk-heuristic-search.html
http://aditya291296.blogspot.co.id/2017/09/pencarian-berbentuk-dan-eksplorasi.html
0 komentar :
Posting Komentar