STEEPEST-ASCENT HILL CLIMBING

Steepest Ascent Hill Climbing melakukan pencarian berdasarkan nilai heuristic terbaik. Dalam hal ini penggunaan operator tidak menentukan penemuan solusi.  Steepest ascent hill climbing merupakan metode algoritma yang banyak digunakan untuk permasalahan optimasi. Salah satu penerapannya adalah untuk mencari rute yang terpendek dengan cara memaksimumkan atau meminimumkan nilai fungsi optimasi yang ada. Secara harafiah steepest berarti paling tinggi, sedangkan ascent berarti kenaikan. Dengan demikian steepest ascent berarti kenaikan paling tinggi. Jadi prinsip dasar metode ini adalah mencari kenaikan paling tinggi keadaan sekitar untuk mencapai nilai yang paling optimal.

            Metode steepest ascent hill climbing ini merupakan pengembangan dari metode simple hill climbing. Bedanya adalah simple hill climbing menentukan next state dengan membandingkan current state dengan satu successor dan successor pertama yang lebih baik akan dipilih menjadi next state.Sedangkan steepest ascent akan membandingkan current state dengan semua succesors yang ada didekatnya sehingga dalam steepest ascent hill climbing, next statenya merupakan successor yang paling baik atau paling mendekati tujuan.

Algoritma Steepest-Ascent hill climbing

1.        Mulai dari keadaan awal, lakukan pengujian : jika merupakan tujuan maka akan berhenti; dan jika tidak, lanjutkan dengan  keadaan sekarang sebagai keadaan awal

2.        Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang.

a.         Tentukan SUCC sebagai nilai heuristik terbaik dari successor – successor

b.         Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:

i.          Gunakan operator tersebut dan bentuk keadaan baru

ii.        Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar.                                               Jika bukan, bandingkan nilai heuristiknya denngan SUCC. Jika lebih baik, jadikan nilai keadaan heuristik baru tersebut sebagai SUCC. Namun, jika tidak lebih baik, nilai SUCC tidak berubah

iii.      Jika SUCC lebih baik dri pada nilai heuristik keadaan sekarang, ubah   node    SUCC  menjadi keadaan sekarang.

Pada Steepest- Ascent Hill Climbing ada 3 masalah yang mungkin yaitu:

1.        Local optimum: keadaan semua tetangga lebih buruk atau sama dengan     

       keadaan dirinya

2.        Plateau : Keadaan semua tetangga sama dengan dirinya

3.        Ridge : Local optimum yang lebih disebabkan karena ketidakmampuan untuk

       menggunakan 2 operator sekaligus.

            Penyelesaian Travelling Salesman Problem dengan Steepest-Ascent Hill Climbing yaitu dengan menentukan ruang keadaan yang berisi semua kemungkinan lintasan 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  Sehingga kalau ada 5 kota, kita bisa memperoleh  yaitu sebanyak 10 kombinasi. Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi. Maka dengan operator tukar kita dapat menentukan lintasan yang mungkin. Operator tukar yang akan kita gunakan adalah 10 kombinasi yaitu sbb:

1.  Operator 1,2 (menukar posisi kota-1 dengan kota-2)

2.  Operator 1,3 (menukar posisi kota-1 dengan kota-3)

3.  Operator 1,4 (menukar posisi kota-1 dengan kota-4)

4.  Operator 1,5 (menukar posisi kota-1 dengan kota-5)

5.  Operator 2,3 (menukar posisi kota-2 dengan kota-3)

6.  Operator 2,4 (menukar posisi kota-2 dengan kota-4)

7.  Operator 2,5 (menukar posisi kota-2 dengan kota-5)

8.  Operator 3,4 (menukar posisi kota-3 dengan kota-4)

9.  Operator 3,5 (menukar posisi kota-3 dengan kota-5)

10.Operator 4,5 (menukar posisi kota-4 dengan kota-5)

Penyelesaian Travelling Salesman Problem dengan Steepest Ascent Hill Climbing :