3.1.
Strategi pencarian berbentuk/heuristic search stragegy
Pencarian
Heuristik adalah salah satu teknik pencarian pada sistem kecerdasan buatan yang
mengembangkan efisiensi dalam proses pencarian. Pada fungsinya, Heuristic akan
melihat dan mengevaluasi algoritma pencarian. Pada setiap percabangan
pengambilan keputusan, Fungsi heuristic ini akan menilai ketersediaan informasi
dan menentukan cabang mana yang akan dipilih dan dapat digunakan untuk
mendapatkan solusi yang diinginkan. Heuristic search ini memiliki beragam jenis
seperti greedy best first search, A* search, dan memory bounded heuristic
search.
3.1.1.
Greedy best-first search
Metode
best first search menggunakan fungsi evaluasi yang terdiri atas dua bagian,
yaitu fungsi heuristik h(n) dan perkiraan biaya g(n), dimana
f(n) = g(n) + h(n)
Algoritma Greedy Best First Search
atau disingkat algoritma greedy merupakan metode yang cukup populer untuk
memecahkan masalah optimasi. Secara harfiah, greedy berarti tamak atau rakus.
Algoritma greedy menggunakan fungsi evaluasi dengan meniadakan perkiraan biaya
g(n), dimana
f(n) = h(n)
Prinsip dari algoritma greedy (Russel
dan Norvig, 2003) adalah mengambil setiap kesempatan yang ada saat itu juga,
tanpa memperhatikan konsekuensi
kedepannya. Algoritma greedy membentuk solusi dari langkah demi langkah, dan pada setiap langkah harus dibuat
keputusan yang terbaik dalam menentukan pilihan. Di
setiap langkahnya algoritma greedy mengambil pilihan yang terbaik yang
dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan. Setiap
keputusan yang diambil diharapkan merupakan langkah optimum pada langkah
tersebut, dikenali sebagai solusi optimum lokal, kemudian dengan setiap langkah
yang ditempuh diharapkan dapat memperoleh solusi optimum di akhir proses, yaitu
solusi optimum global. Skema umum algoritma greedy adalah:
a. himpunan kandidat, himpunan ini berisi seluruh
elemen pembentuk solusi;
b. himpunan solusi, berisi kandidat-kandidat yang
terpilih sebagai solusi persoalan;
c. fungsi
seleksi, fungsi yang
pada setiap langkah
memilih kandidat yang
paling memungkinkan mencapai
solusi optimal;
d. fungsi kelayakan, fungsi yang memeriksa apakah
suatu kandidat yang terpilih dapat memberikan solusi yang layak, yaitu kandidat
bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar
kendala yang ada;
e. fungsi objektif, fungsi yang memaksimumkan atau
meminimumkan nilai solusi.
3.1.2.
A* Search
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.
Algoritma A juga membutuhkan dua
antrian, yaitu OPEN dan CLOSED. Selain itu, ada juga fungsi heuristik yang
memprediksi keuntungan tiap node yang di buat. Yang akan memungkinkan algoritma
untuk melakukan pencarian-pencarian lintasan yang lebih di harapkan. Fungsi ini
di sebut f’(n) sebagai pendekatan dari fungsi f(n) yang merupakan fungsi
evaluasi yang sebenarnya terhadap node n. dalam banyak penarapan, akan lebih
baik jika fungsi di definisikan sebagai kombinasi atau jumlah dua komponen
yaitu g(n) dan h(n). Fungsi g(n) merupakan ukuran biaya yang di keluarkan dari
keadaan awal sampai ke node n. Nilai yang didapat g(n) merupakan jumlahan biaya
penerapan setiap aturan yang dilakukan pada sepanjang lintasan trbaik menuju
suatu simpul dan bukan merupakan hasil estimasi.
Fungsi h(n) merupakan pengukur biaya
tambahan yang harus dikeluarkan dari node n sampai mendapatkan tujuan. Perlu
diketahui bahwa g(n), tidak negatif karena bila negatif maka lintasan yang
membalik siklus pada graf akan tampak lebih baik dengan semakin panjangnya
lintasan.
Secara matematis, fungsi F sebagai
estimasi fungsi evaluasi terhadap node
ndapat di tuliskan :
f’(n) = g(n) + h’(n)
Dengan f’(n) =
fungsi evaluasi, g(n) = biaya yang sudah di keluarkan dari keadaan awal sampai keadaan
n, h’(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n. Dari
fungsi di atas maka ada beberapa kondisi yang perlu diperhatikan, yaitu:
Jika h = h’, berarti proses pencarian telah sampai ke
tujuan ( goal ).
Jika g = h’ = 0 maka f’ random, artinya system tidak
dapat di kendalikan.
Jika g = k, k adalah konstanta dan biasanya bernilai
1, h’ = 0, artinya system menggunakan breadth first search.
3.1.3.
Memory-bounded heuristic search
SMA* atau
Simplified Memory Bounded A* adalah algoritma pencarian jalur terpendek
berdasarkan dari algoritma A*. Keuntungan utama dari algoritma SMA* adalah dia
menggunakan bounded memory, sementara algoritma A* mungkin membutuhkan memori
exponensial. Semua karakteristik di algoritma SMA* diturunkan dari A*.
3.2.
Fungsi Heuristic
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 local dan masalah optimisasi
Algoritma
pencarian lokal untuk masalah optimisasi kombinatorik biasanya digunakan pada
pseudopolynomial running time dan algoritma polynomial-time sering tidak dapat
menemukan solusi optimum lokal untuk masalah optimisasi NP −hard. Penelitian
ini bertujuan mengenalkan konsep optimalitas ε-lokal dan menunjukkan bahwa
optimum ε-lokal dapat diidentifikasi dengan waktu polynomial pada masalah
ukuran dan 1/ε bilamana hubungan ketetanggan dapat dicari dengan polynomial
time untuk ε > 0. Akibatnya, masalah optimisasi kombinatorial memiliki
banyak pola pendekatan polynomial-time jika dan hanya jika memiliki fully
polynomial-time pola tambahan (augmentation).
3.3.1.
Hill Climbing Search
Hill Climbing ( HC
) atau pendakian bukit merupakan salah satu metode yang masuk dalam kategori
metode pencarian heuristik. Dinamakan Hill Climbing ( HC ) atau pendakian bukit
karena mempunyai aturan produksi dengan cara menukar dua posisi kota yang
saling berdekatan seperti orang yang mendaki bukit. Hill Climbing ( HC ) dibagi
menjadi dua jenis yaitu Simple HC ( HC sederhana ) dan Steepest-Ascent HC ( HC
dengan memilih kemiringan yang paling tajam/curam ).
Simple HC ( SHC ) bekerja dengan cara
memilih secara langsung new state yang memiliki keadaan lebih baik dari pada
keadaan sebelumnya tanpa memperhitungkan
keadaan lain yang lebih “curam”.
3.3.2.
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.
3.3.3.
Local Beam Search
Dalam
ilmu komputer, beam search adalah
algoritma pencarian heuristik yang mengeksplorasi grafik dengan memperluas
simpul yang paling menjanjikan dalam rangkaian terbatas. Penelusuran beam
adalah optimalisasi pencarian terbaik pertama yang mengurangi kebutuhan memori.
Pencarian terbaik-pertama adalah pencarian grafik yang memerintahkan semua
solusi parsial (goal). Tapi dalam pencarian balok, hanya sejumlah solusi
parsial terbaik yang telah ditentukan dijaga sebagai kandidat.
3.3.4.
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 dancrossover.
GA diimplementasikan sebagai proses
simulasi yang dijabarkan sebagai berikut: Populasi dari representasi abstrak
(disebut kromosom, genotip, atau genom) dari candidate solution(disebut
individual, atau fenotip) dari optimasi yang berevolusi ke solusi yang lebih baik.
Biasanya solusi direpresentasikan ke dalam string biner. Evolusi dimulai dari
populasi dari individu yang dihasulkan secara random dan terjadi dalam
generasi. Di setiap generasi, fitnessdari setiap individu dalam populasi
dievaluasi, beberapa individu dipilih secara stokastik(berdasarkan fitness) dan
dimodifikasi(crossover dan kemungkinan mutasi) untuk membentuk populasi baru.
Populasi baru lalu dimanfaatkan untuk iterasi selanjutnya. Secara umum,
algoritma selesai jika telah menghasilkan generasi maksimum atau hasil dalam
populasi dirasa memuaskan (berdasarkan berbagai parameter).
3.4.
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)
Sumber :
Tidak ada komentar:
Posting Komentar