HILL CLIMBING(Jenis Metode Pencarian Heuristik)

HILL CLIMBING(Jenis Metode Pencarian Heuristik)

· Hill climbing (mendaki bukit) merupakan salah
satu variasi metode buat dan uji (generate and
test) dimana umpan balik yang berasal dari
prosedur uji digunakan untuk memutuskan arah
gerak dalam ruang pencarian (search).

· Dalam prosedur buat dan uji yang murni, respon
fungsi uji hanyalah ya atau tidak.

· Dalam prosedur Hill Climbing, fungsi uji
dikombinasikan dengan fungsi heuristik yang
menyediakan pengukuran kedekatan suatu
keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :

1. Buatlah solusi usulan pertama dengan cara yang
sama seperti yang dilakukan dalam prosedur
buat dan uji (generate and test). Periksalah
apakah solusi usulan itu merupakan sebuah
solusi. Jika ya, berhentilah. Jika tidak, kita
lanjutkan ke langkah berikutnya.
Pengantar Inteligensia Buatan – Heuristic Searching 3/8

2.Dari solusi ini, terapkan sejumlah aturan yang
dapat diterapkan untuk membuat sekumpulan
solusi usulan yang baru.

3.Untuk setiap elemen kumpulan solusi tersebut,
lakukanlah hal-hal berikut ini :

    1.Kirimkanlah elemen ini ke fungsi uji. Jika
    elemen ini merupakan sebuah solusi,
    berhentilah.

    2.Jika tidak, periksalah apakah elemen ini
    merupakan yang terdekat dengan solusi yang
    telah diuji sejauh ini. Jika tidak, buanglah.

    3.Ambilah elemen terbaik yang ditemukan di atas
    dan pakailah sebagai solusi usulan berikutnya.
    Langkah ini bersesuaian dengan langkah dalam
    ruang problema dengan arah yang muncul
    sebagai yang tercepat dalam mencapai tujuan.

    4.Kembalilah ke langkah 2.

Masalah-masalah yang mungkin timbul pada
prosedur Hill Climbing :

- Maksimum lokal adalah suatu keadaan yang
lebih baik daripada semua tetangganya namun
masih belum lebih baik dari suatu keadaan lain
yang jauh letaknya darinya.

- Daratan (Plateau) adalah suatu daerah datar dari
ruang pencarian (search) dimana semua
himpunan keadaan tetangganya memiliki nilai
yang sama.

- Punggung (Ridge) adalah suatu daerah ruang
pencarian (search) yang lebih tinggi daripada
daerah sekitarnya, namun tidak dapat dibalikkan
oleh langkah–langkah tunggal ke arah manapun.

Solusinya:

- Melakukan langkah balik (backtracking) ke
simpul yang lebih awal dan mencoba bergerak
ke arah yang lain.

- Melakukan lompatan besar ke suatu arah untuk
mencoba bagian ruang pencarian yang baru.

- Menerapkan dua atau lebih aturan sebelum
melakukan uji coba. Ini bersesuaian dengan
bergerak ke beberapa arah sekaligus.