Heuristik adalah sebuah teknik
yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan
mengorbankan kelengkapan (completeness).
Fungsi heuristik digunakan
untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa
jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Ada 4 metode
Heuristic Searching:
a)
Generate
and Test.
b)
Hill
Climbing.
c)
Best
First Search.
d)
Simulated
Anealing
A.
PEMBANGKITAN dan PENGUJIAN (Generate and Test)
Metode ini merupakan
penggabungan antara depth-first search dengan pelacakan mundur (backtracking),
yaitu bergerak ke belakang 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.
Contoh : Pada Traveling Salesman Problem (TSP)
Seorang salesman ingin mengunjungi n kota. Jarak
antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek
dimana setaip kota hanya boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota
dengan jarak antara tiap-tiap kota seperti gambar di bawah ini :
Penyelesaian dengan metode Generate and Test :
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-D
·
dan
seterusnya
Dari gambar diatas dapat dijelakan sebagai berikut :
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.
6.
Salah
satu kelemahan dari metode ini adalah perlunya dibangkitkan semua kemungkinan
solusi sehingga membutuhkan waktu yang cukup besar dalam pencariannya.
Alur pencarian dengan Generate and Test
B.
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 lainnya yang mungkin.
Algoritma Simple Hill Climbing :
1.
Cari
operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan
keadaan yang baru.
2.
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.
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.
Pada simple hill climbing, ada 3 masalah yang mungkin:
·
Algoritma
akan berhenti kalau mencapai nilai optimum local
·
Urutan
penggunaan operator akan sangat berpengaruh pada penemuan solusi.
·
Tidak
diijinkan untuk melihat satupun langkah sebelumnya.
Contoh : TSP dengan Simple Hill Climbing
Disini ruang keadaan berisi semua kemungkinan
llintasan yang mungkin. Operator
digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota,
dan kita ingin mencari kombinasi lintasan
dengan menukar posisi urutan
2 kota, maka
kita akan mendapatkan sebanyak :
Contoh Penerapan Algoritma Simple Hill Climbing :
Salah satu
contoh dari penerapan
Algoritma Simple Hill Climbing adalah Traveling Salesman Problem.
Disini ruang keadaan berisi semua
kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi
kota-kota yang bersebelahan. Fungsi heuristik yang digunakan adalah panjang
lintasan yang terjadi.
Operator yang akan kita gunakan, adalah
menukar urutan posisi 2 kota dalam suatu lintasan. Apabila ada n kota, dan kita
ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita
akan mendapatkan
Sehingga kalau ada 4 kota, kita bisa memperoleh :
kombinasi. Keenam kombinasi ini akan kita
pakai semuanya sebagai operator, yaitu:
*
Tukar 1, 2
(menukar urutan posisi kota ke-1 dengan kota
ke-2).
*
Tukar 2, 3
(menukar urutan posisi kota ke-2 dengan kota
ke-3).
*
Tukar 3, 4
(menukar urutan posisi kota ke-3 dengan kota
ke-4).
*
Tukar 4, 1
(menukar urutan posisi kota ke-4 dengan kota
ke-1).
*
Tukar 2, 4
(menukar urutan posisi kota ke-2 dengan kota
ke-4).
*
Tukar 1, 3
(menukar urutan posisi kota ke-1 dengan kota
ke-3).
Pada Gambar 2.22 terlihat bahwa, pada
keadaan awal, lintasan terpilih adalah ABCD (=19). Pada level pertama, hill climbing akan mengunjungi BACD
(=17) yang ternyata memiliki nilai heuristik lebih kecil dibandingkan dengan
ABCD (17<19), sehingga BACD menjadi pilihan selanjutnya dengan operator
terpakai Tukar1,2. Pada level kedua, hill
climbing akan mengunjungi ABCD. Karena
operator Tukar 1, 2 sudah
digunakan oleh BACD,
maka dipilih node yang lain yaitu BCAD (=15). Karena nilai heuristik
BCAD lebih kecil dibanding dengan BACD (15<17), maka node BCAD akan menjadi
pilihan selanjutnya dengan operator Tukar2,3. Kemudian hill climbing akan
mengunjungi CBAD (=20). Karena nilai heuristik CBAD lebih besar jika dibanding
dengan BCAD (20>17), maka dipilih node lain. Pencarian menuju ke node BACD,
karena operator Tukar2,3 sudah pernah digunakan oleh BCAD, maka dipilih node
lain. Kunjungan berikutnya ke node BCDA (=18). Nilai inipun masih lebih besar
dari nilai heuristik BCAD, sehingga dipilih node lain. Node vang dikunjungi
berikutnya adalah DCAB (=19). Nilai heuristic DCAB ternyata juga lebih besar
dibanding dengan BCAD, sehingga pencarian dilanjutkan di node lainnya lagi,
yaitu BDAC (=14). Nilai heuristik ini sudah lebih kecil daripada nilai
heuristik node BCAD (14<15), maka sekarang node ini yang akan diekplorasi.
Pencarian pertama ditemukan node DBAC (=21), yang lebih besar daripada nilai
BDAC. Nilai heuristik yang lebih kecil diperoleh pada node BDCA (=13). Sehingga
node BDCA ini akan diekplorasi. Pencarian pertama sudah mendapatkan node
dengan nilai heuristik yang lebih kecil,
yaitu DBCA (=12). Sehingga node ini diekplorasi juga. Dari hasil ekplorasi
dengan pemakaian semua operator, ternyata sudah tidak ada node yang memiliki
nilai heuristik yang lebih kecil dibanding dengan nilai heuristik DBCA,
sehingga sebenarnya node DBCA (=12) inilah lintasan terpendek yang kita cari
(SOLUSI). Misalkan kita tidak menggunakan semua operator, melainkan kita hanya
menggunakan 4 operator pertama saja, yaitu :
* Tukar 1,2 (menukar
urutan posisi kota ke'1 dengan kota ke'2).
* Tukar 2, 3 (menukar
urutan posisi kota ke-2 dengan kota ke'3).
* Tukar 3,4 (menukar
urutan posisi kota ke-3 dengan kota ke'4).
* Tukar 4, 1 (menukar
urutan posisi kota ke-4 dengan kota ke'l).
Maka pencarian dengan simple hill climbing ini dapat dilihat pada
Gambar 2.23. Lintasan terpendek yang diperoleh adalah B-C-A-D yaitu sebesar 15.
Disini kita akan terjebak pada nilai minimum local yang disebabkan oleh
kurangnya operator yang kita gunakan. Kita tidak dapat memperoleh nilai minimum
globalnya yaitu sebesar 12.
Contoh TSP di atas adalah contoh pertama yang dibahas dalam makalah
ini. Untuk contoh kedua adalah game Number Puzzle Slider dengan langkah-
langkah menggunakan Simple Hill Climbing.
Berikut adalah contoh menyelesaikan Number Puzzle Slider dengan
kondisi tertentu menggunakan Simple Hill Climbing;
h(n) adalah nilai total heuristik dari kondisi puzzle. Bernilai 0
untuk posisi yang benar dan untuk posisi yang salah nilainya adalah jarak
terpendek menuju posisi benar. Proses
evaluasi yang dilakukan selalu mengambil nilai heuristik terkecil.
References :
-
elib.unikom.ac.id/download.php?id=191397
-
viska.web.id/wp-content/uploads/2012/03/Modul-Pertemuan-2-7.pdf
-
web.unair.ac.id/admin/file/f_22572_2_Simple_Hill_Climbing.pdf
-
http://www.academia.edu/9820429/Generate-and-Test_GT
0 comment:
Post a Comment