A. Metode
Pencarian Buta
Pencarian buta merupakan sekumpulan prosedur yang digunakan
dalam melacak ruang keadaan. Pencarian berlangsung sampai solusi terakhir
ditemukan. Idenya adalah menguji seluruh kemungkinan yang ada untuk menemukan
solusi.
Pencarian Melebar
Pertama (Breadth-First Search)
Pada metode Breadth-First Search, semua node pada level n
akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1.
Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan,
kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan sampai
ditemukannya solusi.
Algoritma :
- Buat sebuah antrian, inisialisasi node pertama
dengan Root dari tree
- Bila node pertama, jika ≠ GOAL, diganti dengan
anak-anaknya dan diletakkan di belakang per level
- Bila node pertama = GOAL, selesai
Keuntungan :
- Tidak akan menemui jalan buntu
- Jika ada satu solusi, maka breadth first search
akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum
akan ditemukan.
Kelemahan :
- Membutuhkan memori yang cukup banyak, karena
menyimpan semua node dalam satu pohon
- Kemungkinan ditemukan optimal local
Pencarian Mendalam
Pertama (Depth-First Search)
Pada Depth First Search, proses pencarian akan dilaksanakan
pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel.
Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini
diulangi terus hingga ditemukannya solusi.
Algoritma :
- Buat sebuah antrian, inisialisasi node pertama
dengan Root dari tree
- Bila node pertama, jika ≠ GOAL, node dihapus
diganti dengan anak-anaknya dengan urutan LChild
- Bila node pertama = GOAL, selesai
Keuntungan :
- Membutuhkan memori yang relatif kecil, karena
hanya node-node pada lintasan yang aktif saja yang disimpan
- Menemukan solusi tanpa harus menguji lebih
banyak lagi dalam ruang keadaan
Kelemahan :
- Kemungkinan terjebak pada optimal local
- Hanya akan mendapatkan 1 solusi pada setiap
pencarian
Pencarian dengan
Mendaki Bukit (Hill Climbing Search)
Algoritma :
- Buat sebuah antrian, inisialisasi node pertama
dengan Root dari tree
- Bila node pertama, jika ≠ GOAL, node dihapus
diganti dengan anak-anaknya dengan urutan yang paling kecil jaraknya
- Bila node pertama = GOAL, selesai
Keuntungan :
- Membutuhkan memori yang relatif kecil, karena
hanya node-node pada lintasan yang aktif saja yang disimpan
- Metode hill climbing search akan menemukan
solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan
Kerugian :
- Algoritma akan berhenti kalau mencapai nilai
optimum local
- Perlu menentukan aturan yang tepat
Pencarian dengan
Best-First Search
Algoritma :
- Bila sebuah antrian, inisialisasi node pertama
dengan Root dari tree
- Bila node pertama, jika ≠ GOAL, node dhapus dan
diganti dengan anak-anaknya. Selanjutnya keseluruhan node yang ada di Queu
di-sort Ascending
- Bila node pertama = GOAL, selesai
Keuntungan :
- Membutuhkan memori yang relatif kecil, karena
hanya node-node pada lintasan aktif saja yang dismpan
- Secara kebetulan, metode best first
search akan menemukan solusi tanpa harus menguji lebih banyak
lagi dalam ruang keadaan
Kerugian :
- Algoritma akan berhenti kalau mencapai nilai
optimum local
- Tidak diijinkan untuk melihat satupun langkah
sebelumnya
B. Metode
Pencarian Heuristik
Heuristik adalah sebuah teknik yang mengembangkan efisiensi
dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga
dapat mengngorbankan kelengkapan (complateness).
Fungsi Heuristik
Heuristic digunakan untuk mengevaluasi keadaan-keadaan
problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan
untuk mendapatkan solusi yang diinginkan.
Jenis-jenis Pencarian Heuristik
- Generate and Test.
- Hill Climbing.
- Best First Search.
- Alpha Beta Prunning
- Simulated Annealing
Pembangkitan dan
Pengujian (Generate and Test)
Metode ini merupakan penggabungan antara depth-first
search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang
menuju pada suatu keadaan awal.
Algoritma:
1.
Bangkitkan suatu kemungkinan
solusi(membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan
awal).
2.
Uji untuk melihat apakah node tersebut
benar-benar merupakan solusinya dengan cara membandingkan node terebut atau
node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang
diharapkan.
3.
Jika solusi ditemukan, keluar. Jika tidak,
ulangi kembali langkah pertama.
Pendakian Bukit (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
lain yang mungkin.
Algoritma:
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 :
1. Jika keadaan baru merupakan tujuan,
keluar
2. Jika bukan tujuan, namun nilainya
lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut
menjadi keadaan sekarang.
3.
Jika keadaan baru tidak lebih baik daripada
keadaan sekarang, maka lanjutkan iterasi.
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)
f’ = Fungsi evaluasi
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke goal state
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 alphaadalah 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.
Referensi :
Comments
Post a Comment