Hill Climbing

Hill Climbing
Metode ini hampir sama dengan metode generate and test dan merupakan salah satu
variasi dari metode tersebut. Yang membedakan kedua metode ini adalah umpan balik
(feed back) yang berasal dari prosedur pengujian digunakan untuk memutuskan arah
gerak dalam pencarian.
Ada dua macam metode hill climbing, yaitu simple hill climbing dan steepest ascent
hill climbing.

Simple Hill Climbing
Algoritma untuk simple hill climbing adalah sebagai berikut.

1. Mulai dari keadaan awal, lakukan pengujian. Jika merupakan tujuan maka
berhenti. Jika sebaliknya, lanjutkan dengan keadaan sekarang sebagai keadaan
awal.

2. Ulangi langkah – langkah berikut hingga solusi ditemukan, atau sampai tidak ada
operator baru yang akan diaplikasikan pada keadaan sekarang.

a. Pilih operator yang belum pernah digunakan, gunakan operator ini untuk
mendapatkan keadaan yang baru.

b. Evaluasi keadaan yang baru tersebut. Jika keadaan baru merupakan tujuan maka keluar
. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang,
maka jadikan keadaan baru tersebut menjadi keadaan sekarang. Jika keadaan baru tidak lebih baik daripada keadaan sekarang maka lanjutkan iterasi.

Sebagai ilustrasi pencarian solusi dengan simple hill climbing, kita gunakan contoh
masalah TSP pada generate and test. Operator yang digunakan adalah operator yang
bisa menghasilkan kombinasi lintasan kota yang berbeda – beda, yaitu dengan cara
menukar posisi masing – masing kota. Untuk mempermudah penukaran posisi, kita
cukup menukar posisi 2 kota, operator untuk kombinasi lintasan dengan menukar
posisi 2 kota dapat dihitung dengan rumus 2! ( 2 )!!
n −n
sehingga operator yang kita
peroleh untuk masalah ini adalah 2! ( 4 2 )!4!

kombinasi operator, yaitu :
1. (1,2) : Menukar posisi kota kesatu dengan kota kedua
2. (1,3) : Menukar posisi kota kesatu dengan kota ketiga
3. (1,4) : Menukar posisi kota kesatu dengan kota keempat
4. (2,3) : Menukar posisi kota kedua dengan kota ketiga
5. (2,4) : Menukar posisi kota kedua dengan kota keempat
6. (3,4) : Menukar posisi kota ketiga dengan kota keempat
Pada pencarian dengan menggunakan simple hill climbing, penggunaan urutan
operator harus konsisten, tidak boleh berbeda dalam setiap level. Urutan penggunaan
operator juga sangat menentukan kecepatan dalam menemukan solusi.

Setelah urutan operator ditentukan, gunakan algoritma pengerjaan sesuai aturan
metode simple hill climbing. Keadaan awal yang dibangkitkan, misalnya kita pilih
ABCD, sesuai dengan gambar berikut ini.

Pencarian pada simple hill climbing mulai dilihat dari anak kiri. Apabila nilai
heuristik anak kiri lebih baik maka dibuka untuk pencarian selanjutnya. Jika tidak,
barulah kita dapat melihat tetangga dari anak kiri tersebut, dan seterusnya.
Pada gambar di atas, terlihat bahwa pada level satu BACD nilai heuristiknya lebih
baik daripada ABCD (ABCD = 10 < BACD = 9) sehingga yang dibuka untuk
pencarian selanjutnya adalah BACD tanpa harus mengecek nilai heuristik tiap node
yang selevel BACD. Pada level dua untuk operator (1,2), lintasan yang ditemui adalah
ABCD. Oleh karena lintasan tersebut telah dilalui dan dicek sebelumnya maka tidak
perlu dilakukan pengecekan lagi. Kemudian, dipilih node CBAD yang ternyata nilai
heuristiknya sama dengan BACD sehingga pengecekan dilanjutkan pada tetangga
CABD yaitu DACB, yang ternyata nilai heuristiknya juga lebih jelek dari BACD
(BACD = 8 < DACB = 10). Cek node tetangganya, yaitu BCAD, yang nilai
heuristiknya juga lebih jelek dibandingkan BACD (BACD = 8 < BCAD = 10).
Lakukan pengecekan untuk node selanjutnya, yaitu BDCA, yang ternyata nilai
heuristiknya juga lebih jelek dibandingkan BACD (BACD = 8 < BDCA = 10).
Pengecekan terakhir dilakukan pada node BADC yang ternyata nilai heuristiknya
ABCD
(10)
BACD
(9)
CBAD
(8)
DBCA
(12)
ACBD
(12)
ADCB
(9)
ABDC
(8)
ABCD
(10)
CABD
(9)
DACB
(10)
BCAD
(10)
BDAC
(8)
BADC
(6)
CADB
(8)
BDAC
(8)
BCDA
(9)
BACD
(9)
DABC
(8)
ABDC
(8)
(1,2) (1,3)
(1,4)
(2,4)
(2,3)
(3,4)
(1,2)
(1,2)
(1,3)
(1,3)
(1,4)
(1,4)
(2,3)
(2,3)
(2,4)
(2,4)
(3,4)
(3,4)
23
lebih baik dari BACD (BACD = 8 > BADC = 6) sehingga untuk pencarian
selanjutnya, yang dibuka adalah node BADC.
Node yang dibuka untuk level tiga adalah BADC, setelah dieksplorasi dengan urutan
operator yang telah ditentukan, secara berturut – turut diperoleh node berikut : node
ABDC yang nilai heuristiknya lebih jelek dari BADC (BADC = 6 < ABDC = 8),
DABC yang juga nilai heuristiknya lebih jelek dari BADC (BADC = 6 < DABC = 8),
CADB yang nilai heuristiknya juga jelek (BADC = 6 < CADB = 8), BDAC yang nilai
heuristiknya juga jelek (BADC = 6 < BDAC = 8), BCDA yang nilai heuristiknya juga
lebih jelek dari BADC (BADC = 6 < BCDA = 9), selanjutnya pengecekan pada node
terakhir BACD yang ternyata nilai heuristiknya juga lebih jelek dari BDAC (BDAC =
6 < BCAD = 9). Oleh karena pada level tiga tidak ada node yang menghasilkan nilai
heuristik yang lebih baik dari BDAC maka pencarian solusi dihentikan. Solusi yang
ditemukan dari metode simple hill climbing tersebut adalah BADC dengan panjang
lintasan adalah 6. Berbeda apabila kita menggunakan metode generate and test di
mana semua solusi dapat diperoleh yaitu BADC atau CDBA. Pada metode simple hill
climbing, tidak semua solusi dapat kita temukan.

Penggunaan operator sangat mempengaruhi penemuan solusi pada metode simple hill
climbing, begitu juga apabila penggunaan operator dibatasi misalnya untuk masalah
TSP sebelumya. Pada masalah TSP tersebut, diperlukan penggunaan 6 operator, tetapi
kita batasi hanya menggunakan 4 operator. Dengan demikian, solusi yang dihasilkan
belum tentu merupakan solusi optimal karena tidak semua kemungkinan solusi
dilakukan pengecekan yang disebabkan oleh kurangnya penggunaan operator yang
diperlukan untuk membangkitkan kemungkinan solusi yang ada.

Steepest Ascent Hill Climbing

Steepest Ascent Hill Climbing hampir sama dengan simple hill climbing, dan yang
membedakan keduanya adalah pada gerakan pencarian yang bila menemukan satu
node tidak langsung berhenti tetapi dilanjutkan dengan mencari apakah ada node lain
yang memiliki nilai heuristik yang lebih baik. Dalam hal ini, urutan penggunaan
operator tidak menentukan penemuan solusi.

solusi bagi masalah TSP tersebut adalah CDAB dengan panjang
lintasan sebesar 6. Metode Steepest Ascent Hill Climbing tidak harus melihat naka kiri
pertama kali, tetapi dengan mencari semua nilai heuristik yang lebih baik pada node –
node selevel. Gambar di atas menunjukkan bahwa pada level satu, yang memiliki nilai
heuristik yang lebih baik dari lintasan ABCD yang panjangnya 10 adalah lintasan
CBAD dan ABDC dengan lintasan sama dengan 8. Oleh karena ada dua node yang
nilainya sama dan lebih baik dibandingkan node tetangganya yang lain maka kita
dapat memilih salah satu node yang ingin dibuka untuk melanjutkan pencarian solusi
selanjutnya. Pada gambar, dipilih node CBAD untuk pencarian selanjutnya. Pada
level dua, diperoleh node CDAB dengan panjang lintasan adalah 6 sebagai lintasan
yang lebih baik nilai heuristiknya dibandingkan node lintasan sebelumnya dan juga
bila dibandingkan dengan node – node tetangganya. Pada level tiga tidak ditemukan
nilai heuristik yang lebih baik dibandingkan lintasan CDAB sehingga pencarian
berhenti dan solusi yang diperoleh untuk lintasan terpendek adalah CDAB dengan
panjang lintasan adalah 6.
ABCD
(10)
BACD
(9)
CBAD
(8)
DBCA
(12)
ACBD
(12)
ADCB
(9)
ABDC
(8)
(1,2) (1,3)
(1,4)
(2,4)
(2,3)
(3,4)
BCAD
(10)
ABCD
(10)
DBAC
(9)
CABD
(9)
CDAB
(6)
DCAB
(9)
ADCB
(9)
BDAC
(8)
CADB
(8)
CBAD
(8)
CDBA
(8)
CBDA
(9)
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)
(1,2)
(1,3) (1,4) (2,3) (2,4) (3,4).


http://ibbi.ac.id/ibbiacid/bahan/kecerdasan-buatan.pdf