Teknik Pencarian Hill Climbing

Nama : Fat’hiyyah Nuswantari

NPM : 12118579

Kelas : 3KA21

Teknik Hill Climbing adalah pengembangan dari teknik Generate-and-Test, dengan penambahan adanya umpan balik dari prosedur test yang sudah digunakan untuk membantu memilih arah mana yang harus ditelusuri pada setiap area search.

Pada prosedur Generate-and-Test yang murni, fungsi test hanya ditanggapi dengan Ya atau Tidak. Tetapi pada Hill-Climbing fungsi test ditambahkan dengan fungsi heuristic atau fungsi objectif yang memungkinkan perkiraan seberapa dekat simpul yang ditelusuri terhadap goal state.

Hill-climbing sering kali digunakan jika fungsi heuristic yang baik tersedia untuk mengevaluasi stata, tapi ketika tidak ada lagi pengetahuan yang dapat digunakan.

Sebagai contoh, anda berada disuatu kota yang belum pernah anda kunjungi tanpa memiliki peta. Tujuannya menuju gedung tertinggi yang terlihat dari tempat anda berada.

Fungsi heuristic adalah hanya masalah jarak antara lokasi anda berada dengan letak gedung tertinggi dan bagaimana menemukan jarak yang terdekat atau cara tercepat menuju gedung tertinggi.

Algoritma Simple Hill Climbing :

1. Evaluasi initial state. Jika ini goal state maka return dan keluar. Jika bukan maka lanjutkan dengan initial state sebagai current state.
2. Ulangi langkah berikut sampai menemukan solusi atau sampai tidak ada lagi operator yang dapat digunakan pada current state

Sebagai ilustrasi teknik pencarian simple hill climbing digunakan contoh masalah TSP pada masalah generate and test . Operator yang digunakan adalah operator yang dapat 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 kalkulasi 

yaitu:

1. (1,2) menukar posisi kota kesatu dan kedua

2. (1,3) menukar posisi kota kesatu dan ketiga

3. (1,4) menukar posisi kota kesatu dengan keempat

4. (2,3) menukar posisi kota kedua dengan kota ketiga

5. (2,4) menukar posisi kota kedua dengan keempat

6. (3,4) menukar posisi kota ketiga dengan keempat

Penggunaan pengurutan operator harus konsisten, tidak boleh berbeda tiap levelnya.

urutan penggunaan operator juga sangat menentukan kecepatan dalam menemukan solusi.