1. Strategi Pencarian
Berbentuk
Dengan menggunakan Uninformed Search Algorithm,
beberapa permasalahan dapat dipecahkan, namun tidak semua algoritma dapat
menyelesaikan permasalahan dengan efektif serta efisien.
Informed Search Algorithm, disebut juga dengan
Heuristic Search. Pencarian dengan algoritma ini menggunakan pengetahuan yang
spesifik kepada permasalahan yang dihadapi selain dari definisi masalahnya itu
sendiri.
Pada pencarian dengan metode UCS(Salah satu bagian dai
Uninformed Search Algorithm), kita membandingkan nilai pada path yang ada lalu
kemudian melakukan ekspansi pertama kali pada path dengan nilai yang terkecil.
Nilai path ini biasanya dilambangkan dengan g(n). lebih lanjut lagi, dari
metode pencarian tsb, pada Informed Search Algorithm, kita akan mengenal nilai
estimasi(prediksi) dari satu node ke node yang lainnya. Nilai estimasi ini
biasanya dilambangkan dengan h(n). Jika n adalah goal node, maka nilai h(n)
adalah nol.
Algoritma yang menggunakan metode best-first search,
yaitu :
§ 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). pada Greedy
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.
§ Sejarah
Algoritma A*
Penggunaan informasi heuristic untuk meningkatkan
efisiensi pencarian telah dipelajari dalam berbagai bidang. Penggunaan fungsi
evaluasi pada masalah pencarian pada graf dikemukakan oleh Lin (1965) yang
digunakan pada masalah Traveling Salesman Problem (TSP). Doran dan Michie
(1966) merumuskan dan mencoba dengan algoritma best-first search yang
menggunakan perkiraan jarak dari current node ke simpul tujuan. Hart, Nilsson
dan Raphael memperkenalkan penggunaan sebuah algoritma dalam masalah optimasi
yaitu algoritma A* (A Star). Versi bi-directional algoritma A*, yang sevara
bersamaan mencari dari simpul awal dan simpul tujuan diperkenalkan oleh Pohl
(1971), yang selanjutnya diteliti oleh de Champeaux dan Sint (1977).
§ Algoritma A*
dalam Pencarian Rute Terpendek
Beberapa strategi best-first search berbeda hanya pada
bentuk fungsi evaluasi yang digunakan. Pada strategi best-first search, simpul
yang terpilih untuk dikembangkan adalah simpul dengan nilai fungsi evaluasi
terendah dan ketika dua lintasan mengarah pada simpul yang sama, simpul dengan
nilai paling besar akan dibuang. Secara matematis, nilai fungsi evaluasi
heuristic sebuah simpul pada algoritma A* diberikan oleh :
f(n) = h(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 search yang 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.
§ Heuristic Best
First Search
Fungsi heuristic h(n) merupakan estimasi cost dari n
ke simpul tujuan. Sangat penting untuk memilih fungsi heuristic yang baik.
Misalkan h(n) merupakan cost sebenarnya dari simpul n ke simpul tujuan, maka
pada algoritma A terdapat beberapa kemungkinan yang terjadi pada pemilihan
fungsi heuristic yang digunakan, yaitu (Amit Gaming) :
Jika h(n) = 0, sehingga hanya g(n) yang terlibat maka
A* akan bekerja seperti halnya algoritma Dijkstra.
Jika h(n) < h*(n), maka A* akan mengembangkan titik
dengan nilai paing rendah dan algoritma A* menjamin ditemukannya lintasan
terpendek. Nilai h(n) terendah akan membuat algoritma mengembangkan lebih
banyak simpul. Jika h(n) < h*(n), maka h(n) dikatakan heuristicyang
admissible.
Jika h(n) = h*(n), maka A* akan mengikuti lintasan
terbaik dan tidak akan mengembangkan titik-titik yang lain sehingga akan
berjalan cepat. Tetapi hal ini tidak akan terjadi pada semua kasus. Informasi
yang baik akan mempercepat kinerja A*.
Jika h(n) > h*(n), maka A* tidak menjamin pencarian
rute terpendek, tetapi berjalan dengan cepat.
Jika h(n) terlalu tinggi relative dengan g(n) sehingga
hanya h(n) yang bekerja maka A* berubah jadi Greedy Best First Search.
2. 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 :
Mulai dari keadaan awal, lakukan pengujian: jika
merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan
sekarang sebagai keadaan awal.
Kerjakan langkah-langkah berikut sampai solusinya
ditemukan, atau sampai tidak ada node baru yang akan diaplikasikan pada keadaan
sekarang :
·
Cari node yang
belum pernah digunakan; gunakan node ini untuk mendapatkan keadaan yang baru.
·
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 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:
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.
Kriteria : Yang dipakai unt memutuskan apakah
temperature sistem seharusnya dikurangi.
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 :
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.
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.
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 metode
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:
·
Representasi
genetis dari domain solusi
·
Fungsi fitness
untuk mengevaluasi solusi domain.
Hal-hal yang harus dilakukan untuk menggunakan
algoritma genetika:
Mendefinisikan individu, dimana individu menyatakan
salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.
Mendefinisikan nilai fitness, yang merupakan ukuran
baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan.
Menentukan proses pembangkitan solusi awal. Hal ini
biasanya dilakukan dengan menggunakan pembangkitan acak seperti random walk.
Menentukan proses seleksi yang akan digunakan.
Menentukan proses perkawinan silang (cross over) dan
mutasi gen yang akan digunakan.
3. 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).
Link:
Tidak ada komentar:
Posting Komentar