I.
Generate and
Test
A.
Pengertian
GT adalah metode yang paling sederhana dalam teknik
pencarian heuristik. Jika pembangkitan sebuah solusi yang mungkin (a possible
solution) dikerjakan secara sistematis, maka prosedur ini menjamin akan
menemukan solusinya. Tetapi jika ruang masalahnya sangat luas, mungkin
memerlukan waktu yang sangat lama. Di dalam GT, terdapat dua prosedur penting
yaitu pembangkit (membangkitkan sebuah solusi yang mungkin) dan tes (menguji solusi
yang dibangkitkan tersebut). Dengan penggunaan memori yang sedikit, DFS bisa digunakan
sebagai prosedur pembangkit untuk menghasilkan suatu solusi. Prosedur Tes bisa menggunakan
fungsi heuristik. Metode Generate-and-Test (GT) adalah metode yang paling sederhana
dalam teknik pencarian heuristic.
Di
dalam GT, terdapat dua prosedur penting:
1. Pembangkit
(generate), yang membangkitkan semua solusi yang mungkin.
2. Test, yang
menguji solusi yang dibangkitkan tersebut.
Algoritma GT menggunakan prosedur Depth First Search karena suatu solusi
harus dibangkitkan secara lengkap sebelum dilakukan Test. Dengan penggunaan
memori yang sedikit, DFS bisa digunakan sebagai prosedur pembangkit yang
menghasilkan suatu solusi. Prosedur Test bisa menggunakan fungsi heuristik.
B.
Algoritma
1. Bangkitkan
sebuah solusi yang mungkin. Solusi bisa berupa suatu keadaan (state) tertentu.
Solusi juga bisa berupa sebuah jalur dari satu posisi asal ke posisi tujuan,
seperti dalam kasus pencarian rute dari satu kota asal ke kota tujuan.
2. Uji untuk
melihat apakah node tersebut benar-benar merupakan solusinya dengan cara
membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih
merupakan tujuan yang di harapkan.
3. Jika solusi
telah ditemukan, keluar. Jika belum, kembali ke langkah 1.
C.
Ilustrasi
Algoritma
Studi Kasus: Traveling Salesman Problem (TSP)
Seorang salesman ingin mengunjungi sejumlah n kota. Akan dicari rute
terpendek di mana setiap kota hanya boleh dikunjungi tepat 1 kali. Jarak antara
tiap-tiap kota sudah diketahui.
Penyelesaian :
Penyelesaian dengan menggunakan Generate-and-Test dilakukan dengan membangkitkan
solusi-solusi yang mungkin dengan menyusun kota-kota dalam urutan abjad, yaitu:
ü A-B-C-D
ü A-B-D-C
ü A-C-B-D
ü A-C-D-B
ü dan seterusnya
1.
Misalkan kita mulai dari node A. Kita pilih sebagai
keadaan awal adalah lintasan ABCD dengan panjang lintasan = 19.
2.
Kemudian kita lakukan backtracking untuk mendapatkan
lintasan ABDC dengan panjang lintasan = 18.
3.
Lintasan ini kita bandingkan dengan lintasan ABCD,
ternyata ABDC < ABCD, sehingga lintasan terpilih adalah ABDC.
4.
Kita lakukan lagi backtracking untuk mendapatkan
lintasan ACBD (=12), ternyata ACBD < ABDC, maka lintasan terpilih sekarang
adalah ACBD.
5.
Demikian seterusnya hingga ditemukan solusi yang
sebenarnya.
D. Kelebihan dan Kelemahan
Salah satu kelemahan dari
metode ini adalah perlunya dibangkitkan semua kemungkinan solusi sehingga
membutuhkan waktu yang cukup besar dalam pencariannya.
II.
Hill Climbing
A. Pengertian
Metode Hill-climbing merupakan variasi dari depth-first
search. Dengan metoda ini, eksplorasi terhadap keputusan dilakukan dengan cara
depth-first search dengan mencari path yang bertujuan menurunkan cost untuk
menuju kepada goal/keputusan. Sebagai contoh kita mencari arah menuju Tugu
Monas, setiap kali sampai dipersimpangan jalan kita berhenti dan mencari arah
mana yang kira-kira akan mengurangi jarak menuju Tugu Monas, Dengan cara
demikian sebetulnya kita berasumsi bahwa secara umum arah tertentu semakin dekat
ke Tugu Monas.
Terdapat dua jenis HC yang
sedikit berbeda, yakni :
1.
Simple HC (HC Sederhana)
a.
Algoritma akan berhenti kalau mencapai nilai optimum lokal
b.
Urutan penggunaan operator akan sangat berpengaruh pada
penemuan solusi.
c.
Tidak diijinkan untuk melihat satupun langkah selanjutnya.
2.
Steepest-Ascent HC (HC dengan memilih kemiringan yang
paling tajam /curam)
a.
Hampir sama dengan Simple HC, hanya saja gerakan
pencarian tidak dimulai dari paling kiri. Gerakan selanjutnya dicari
berdasarkan nilai heuristik terbaik.
B. Algoritma
Ø
Simple HC
1.
Evaluasi initial state. Jika state ini adalah goal state,
maka kembalikan state ini sebagai solusi dan keluar dari program. Jika state
ini bukan goal state, lanjutkan proses dengan initial state sebagai current
state.
2.
Ulangi sampai solusi ditemukan atau sampai tidak ada
operator baru yang dapat diaplikasikan terhadap current state:
a.
Pilih sebuah operator yang belum diaplikasikan
terhadap current state dan aplikasikan operator tersebut sehingga menghasilkan
new state.
b.
Evaluasi new state:
ü
Jika state ini adalah goal state, maka kembalikan
state ini sebagai solusi dan keluar dari program.
ü
Jika state ini bukan goal state tetapi lebih baik dari
pada current state, maka jadikan state ini sebagai current state.
ü
Jika state ini tidak lebih baik daripada current
state, kembali ke langkah 2.a.
Ø
Steepest-Ascent
HC
1.
Evaluasi initial state. Jika state ini adalah goal
state, maka kembalikan state ini sebagai solusi dan keluar dari program. Jika
state ini bukan goal state, lanjutkan proses dengan initial state sebagai
current state.
2.
Ulangi sampai solusi ditemukan atau sampai tidak ada
perubahan terhadap current state:
a.
Misalkan SUK adalah suatu state yang menjadi suksesor
dari current state.
b.
Untuk setiap operator yang bisa dilakukan terhadap
current state, kerjakan:
ü
Aplikasikan operator tersebut dan bangkitkan new
state.
ü
Evaluasi new state. Jika merupakan goal state,
kembalikan state ini sebagai solusi dan keluar dari program. Jika bukan goal
state, bandingkan new state dengan SUK. Jika new state lebih baik daripada SUK,
maka ganti SUK dengan new state. Jika tidak lebih baik, SUK tidak perlu
diganti.
c.
Jika SUK lebih baik dari current state, maka ganti
current state dengan SUK.
C. Ilustrasi Algoritma
Ø
Simple HC
Studi Kasus : Game 8- Puzzle
Terdapat 4 operator yang
dapat kita gunakan untuk menggerakkan dari satu keadaan ke keadaan yang baru.
1.
Ubin kosong digeser ke kiri
2.
Ubin kosong digeser ke kanan
3.
Ubin kosong digeser ke atas
4.
Ubin kosong digeser ke bawah
1.
Jumlah heuristic h(n)= 5 merupakan intial state,
sedangkan heuristic h(n)= 0 menyatakan goal state.
2.
Jumlah heuristic h(n) setiap state menyatakan jumlah langkah
dari state tersebut untuk mencapai goal state.
3.
Simple HC langsung memilih berpindah ke bawah pada
iterasi I sebagai next state karena nilai h(n) pada state tersebut lebih kecil
dibandingkan nilai h(n) pada initial state, begitupun seterusnya hingga
mencapai goal state.
4.
Jadi urutan penyelesaian game 8-puzzle diatas dengan
menggunakan metode Simple Hill Climbing dan menghitung nilai heuristik berupa
jumlah langkah yang diperlukan untuk mencapai goal state adalah ubin kosong
bergeser ke BAWAH, KIRI, ATAS KANAN, BAWAH dengan nilai heuristik terakhir
adalah 0.
Ø
Steepest-Ascent
HC
Studi Kasus : Game 8- Puzzle
Terdapat 4 operator yang
dapat kita gunakan untuk menggerakkan dari satu keadaan ke keadaan yang baru.
1.
Ubin kosong digeser ke kiri
2.
Ubin kosong digeser ke kanan
3.
Ubin kosong digeser ke atas
4.
Ubin kosong digeser ke bawah
D.
Kelebihan dan
Kelemahan
Ø
Simple HC
Kelebihan : Metode Hill Climbing proses pencarian lebih mudah karena proses
pencarian selalu mendekati tujuan.
Kelemahan : Pada metode Hill
Climbing bila ditemukannya satu solusi, kita harus mencari solusi yang lain
untuk dibandingkan, karena kita harus mencari node awal yang dekat dengan node
tujuan.
Ø
Steepest-Ascent HC
Kelebihan : Steepest-Ascent HC
bisa jadi lebih kecil untuk waktu komputasi dan memori yang digunakan juga
lebih kecil dibandingkan metode Hamilton.
Kelemahan : keterbatasan di dalam
menemukan solusi optimal. Sangat besar kemungkinan Steepest-Ascent HC terjebak
dalam solusi optimal lokal.
No comments:
Post a Comment