Metode Hill Climbing

Penyusun Denny Agustiawan

PENDAKIAN BUKIT (HILL CLIMBING)

Metode Hi l l C lambing hampir sama dengan metode pembangk i tan & penguj ian,hanya sa ja proses penguj ian d i lakukan dengan meng gunakan fungs i heur istik . Pembangk itan keadaan ber ikutnya sangat tergantung padafeedback dar i prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

B.L. Simple Hill Climbing

Metode ini biasanya digunakan untuk traveling salesman problem

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 sebanyak : n! 2t(n-2)lSehingga 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).

SteepesLAscent Hill Climbing

Steepest-ascenhti II climbing sebenarnya hampir sama dengan sirnple hitt ctimbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristic terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.

Contoh permasalahannya adalah

Penyelesaian contoh soalnya dalahP a d a G a m b a t 2 . 2 4 , t e r l i h a t b a h w a , k e a c l a a n a w a l , i i n t a s a n t e r p i i i h a d a l a h A B C D ( 1 9 ) . P a d a l e v e l p e r t a m a , h i l i c l i m b i n g a k a n r n e m i i i h n i l a i h e u r i s ti k t e r b a i k d a r i k e e n a m s u c c e s o r y a n g a d a , y a i t u : B A C D ( 1 7 ) , A C B D ( 1 2 ) , A B D C ( I 8 ) , D B C A ( 1 2 ) , A D C B ( 1 8 ) a t a u C B A D ( 2 0 ) . Te n t u s a j a y a n g t e r p i l i h a d a l a h A C B D , k a r e n a m e m i l i k i n i l a i h e u r i s ti k p a l i n g k e c i l ( = 1 2 ; . D a r i A C B D i n i a k a n d i p i l i h n i l a i h e u r i s ti k t e r b a i k d a r i s u c c e s o r n y a y a i t u : C A B D ( 1 5 ) , A B C D ( 1 9 ) , A C D B ( 1 3 ) , D C B A ( 1 9 ) , A D B C ( 1 6 ) a t a u B C A D ( 1 5 ) . Te r n y a t a d a r i k e e n a m s u c c e s s o r t e r s e b u t m e m i l i k i n i l a i h e u r i s ti k y a n g l e b i h b e s a r d i s b a n d i n g d e n g a n A C B D . S e h i n g g a ti d a k a k a n a d a p e r u b a h a n n i l a i k e a d a a n ( t e t a p A C B D ) . H a s i l y a n g d i p e r o l e h , l i n t a s a n n y a a d a l a h A C B D ( 1 2 ) .

Contoh soal puzzle:

Operator yang digunakan untuk menggerakkan dari satu keadaan kekeadaan berikutnya adalah:* Ubin kosongkekanan* Ubin kosong ke kiri* Ubin kosong ke atas* Ubin kosong ke bawah

Penyelesaian soal puzzle:

Diskripsi penyelesaian soal puzzle:

P a d a G a m b a r 2 . 2 6 t e r l i h a t b a h w a s e m u l a a d a 3 o p e r a t o r y a n g b i a s d i g u n a k a n , y a i t u u b i n k o s o n g d i g e s e r k e k a n a n , k i r i d a n b a w a h . M a s i n g - r n a s i n g k o n d i s i h a s i l d a r i i m p l e m e n t a s i o p e r a t o r m e m b e r i k a n n i l a i h e u r i s ti k 4 , 6 , d a n 5 . N i l a i h e u r i s ti k t e r b e s a r a d a l a h 6 , s e h i n g g a k o n d i s i k e d u a y a n g d i p i l i h . P a d a t a h a p k e d u a , o p e r a t o r y a n g b i a s d i g u n a k a n h a n y a 2 , y a i t u u b i n k o s o n g d i g e s e r k e k a n a n d a n k e b a w a h . m a s i n g - m a s i n g d e n g a n n i l a i h e u r i s ti k 5 d a n 7 . N i l a i h e u r i s ti c y a n g d i h a s i l k a n a d a l a h 7 , d a n k o n d i s i i n i d i p i l i h . P a d a t a h a p k e ti g a , a d a 3 o p e r a t o r y a n g d i g u n a k a n , y a i b u u b i n k o s o n g d i g e s e r k e a t a s , k a n a n , d a n b a w a h . M a s i n g - m a s i n g k o n d i s i m e m i l i k i n i l a i h e u r i s ti k 6 , 8 , d a n 6 . K a r e n a n i l a i 8 m e r u p a k a n s o l u s i , m a k a p e n c a r i a n t e l a h b e r a k h i r.