Hill Climbing dalam AI

1.                  Artificial Intelegence ( AI )

Sejak pertama kali dikemukan pada tahun 1956 di konferensi Darthmuoth  Artificial Intelegence ( AI ) terus berkembang dengan pesat. Diawali dengan kesuksesan Newell dan Simon dengan sebuah program yang disebut General Problem Solver yang dirancang untuk menyelesaikan masalah secara manusiawi. Selanjutnya pada tahun 1958 Mc Carthy di MIT AI Lab Memo No.1 mendefinisikan bahasa pemrograman tingkat tinggi yaitu LISP yang sekarang mendominasi pembuatan program-program AI. Perkembangan AI
dari tahun ke tahun juga mengalami pasang surut sampai akhirnya mulai diminati lagi ketika munculnya konsep jaringan saraf tiruan dan algoritma genetika yang diaplikasikan ke dalam software-software ( Suyanto,2007 : 3-6 ).

Artificial Intelegence ( AI ) itu sendiri merupakan cabang ilmu pengetahuan yang beruasaha memahami kecerdasan manusia. Seiring dengan perkembangan ilmu pengetahuan serta berbagai penelitian yang mengkaji teori-teori dan prinsip-prinsip AI maka dikenal empat teknik penyelesaian masalah menggunakan AI yaitu Searching, Reasoning, Planning, dan Learnig. Ke empat teknik tersebut memiliki kelebihan dan kelemahan masing-masing tergantung bagaimana cara kita menggunakannya ( Suyanto,2007 : 11 ).

2.                  Searching Metode atau Metode Pencarian

Searching atau Pencarian merupakan salah satu teknik dalam AI yang mengajarkan cara menyelesaikan masalah dengan mencari solusi terbaik dari semua kemungkinan solusi yang ada. Dalam menyelesaikan masalah menggunakan teknik ini terdapat tiga langkah awal sebagai modal awal untuk mencapai tujuan yaitu mencari solusi yang paling tepat dari masalah yang dihadapi, yaitu:

1.      Mendefinisikan ruang masalah untuk suatu masalah yang dihadapi. Ruang masalah itu sendiri dapat didefinisikan sebagai himpunan keadaan awal ( initial state ) menuju keadaan tujuan ( goal state ).

2.      Mendefinisikan aturan yang akan dilakukan untuk mengubah suatu state ke state lainnya yang biasa disebut dengan aturan produksi.

3.      Memilih metode yang paling tepat untuk mencari solusi terbaik dari semua kemungkinan solusi yang ada.

Namun, secara umum langkah-langkah yang bisa digunakan untuk mengidentifikasi masalah adalah sebagai berikut ( Suyanto, 2007 : 11 ):

1.      Seberapa besar ruang masalahnya?

2.      Berapakah faktor percabangan dan kedalaman solusinya?

3.      Bearapa kecepatan prosesor dan memori yang tersedia?

4.      Apakah solusinya harus optimal?

5.      Dapatkah ditemukan fungsi heuristiknya?

6.      Terdapat satu macam goal atau lebih?

Secara garis besar searching dibagi ke dalam dua jenis yaitu metode pencarian buta/tanpa informasi atau blind/un-informed search dan metode pencarian heuristik/dengan informasi atau heuristic/informed search. Hal yang membedakan kedua jenis teknik pencarian tersebut adalah adanya informasi awal dan aturan produksinya. Terdapat beberapa teknik pencarian yang masuk ke dalam metode pencarian buta/blind yaitu Breadth First Search ( BFS ), Uniform Cost Search ( UCS ), Depth First Search ( DFS ), Depth-Limited Search ( DLS ), Interative Deepening Search ( IDS ), dan Bi-directorial Search ( BDS ). Kelemahan dari metode pencarian buta adalah dibutuhkannya memori yang sangat besar untuk menyesaikan masalah yang cukup sederhana karena harus menyimpan semua solusi yang telah dibangkitkan. Pada jenis ke-2 metode yaitu metode pencarian heuristik/informed, pencarian solusi dilakukan menggunakan keadaan awal  ( initial state ) dan aturan produksi berupa fungsi heuristik ( suatu fungsi untuk menghitung nilai atau biaya perkiraan dari suatu solusi permasalah yang dicari ) sebagai modal untuk melakukan iterasi menuju goal state. Beberapa metode yang masuk dalam  jenis ini antara lain Generate and Test ( GT ), Hill Climbing ( HC ), Simulated Annealing ( SA ), Best First Search ( Greedy Best First Search dan A* ). Dengan mempunyai modal awal berupa initial state dan fungsi heuristik sebagai aturan produksinya maka metode pencarian heuristik lebih efisien dalam mencari solusi dibandingkan dengan metode pencarian buta/blind. Namun, untuk mendapatkan solusi terbaik dari suatu permasalahan harus lebih cermat dalam memilih metode dan fungsi heuristik yang akan digunakan.

3.                  Hill Climbing ( Pendakian Bukit )

Hill Climbing ( HC ) atau pendakian bukit merupakan salah satu metode yang masuk dalam kategori metode pencarian heuristik. Dinamakan Hill Climbing ( HC ) atau pendakian bukit karena mempunyai aturan produksi dengan cara menukar dua posisi kota yang saling berdekatan seperti orang yang mendaki bukit. Hill Climbing ( HC ) dibagi menjadi dua jenis yaitu Simple HC ( HC sederhana ) dan Steepest-Ascent HC ( HC dengan memilih kemiringan yang paling tajam/curam ).

Simple HC ( SHC ) bekerja dengan cara memilih secara langsung new state yang memiliki keadaan lebih baik dari pada keadaan sebelumnya  tanpa memperhitungkan keadaan lain yang lebih “curam”. Berikut adalah algoritma dari SHC ( Suyanto, 2007 : 24 ) :

1.      Evaluasi initial state (keadaan awal). Jika initial state adalah goal state maka jadikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, lanjutkan proses dengan initial state sebagai current state.

2.      Ulangi sampai solusi ditemukan atau sampai tidak ada operator ( aturan produksi ) baru yang dapat diaplikasikan terhadap current state :

a.       Pilih operator yang belum diaplikasikan terhadap current state dan aplikasikan operator tersebut sehingga menghasilkan new state.

b.      Evaluasi new state :

                                      i.      Jika state ini merupakan goal state maka jadikan state ini sebagai solusi dan keluar dari program.

                                    ii.      Jika state ini bukan goal state tetapi lebih baik dari current state maka jadikan state ini sebagai current state baru.

                                  iii.      Jika state ini tidak lebih baik dari current state maka kembali ke langkah 2.a.

Berikut ini adalah gambar proses penyelesaian solusi dengan menggunakan SHC.

Sedikit berbeda dengan SHC, Steepest-Ascent HC ( SAHC ) lebih menekankan pada aturan produksinya yaitu SHC akan mengevaluasi semua state yang berada dibawah current state dan memilih state dengan keadaan paling “curam”. Berikut adalah algoritma dari SAHC :

1.      Evaluasi initial state. Jika initial state adalah goal state maka jadikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, lanjutkan proses dengan initial state sebagai current state.

2.      Ulangi sampai solusi ditemukan atau sampai tidak ada perubahan terhadap current state :

a.       Misalkan SUK adalah suatu state yang menjadi suksesor dari current state.

b.      Untuk setiap operator yang bisa dilakukan terhadap current state, kerjakan :

                                      i.            Aplikasikan semua operator yang ada dan bangkitkan new state.

                                    ii.            Evaluasi new state. Jika merupakan goal state, jadikan ini sebagai solusi dan keluar dari program. Jika bukan goal state, bandingkan dengan new state  dengan SUK. Jika new state lebih baik dari SUK maka ganti SUK dengan new state. Jika new state tidak lebih baik dari SUK, tidak perlu diganti.

c.       Jika SUK lebih baik dari current state maka ganti current state dengan SUK.

Berikut ini adalah gambar proses penyelesaian solusi dengan menggunakan SAHC.

Sedikit berbeda dengan SHC, Steepest-Ascent HC ( SAHC ) lebih menekankan pada aturan produksinya yaitu SHC akan mengevaluasi semua state yang berada dibawah current state dan memilih state dengan keadaan paling “curam”. Berikut adalah algoritma dari SAHC :

1.      Evaluasi initial state. Jika initial state adalah goal state maka jadikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, lanjutkan proses dengan initial state sebagai current state.

2.      Ulangi sampai solusi ditemukan atau sampai tidak ada perubahan terhadap current state :

a.       Misalkan SUK adalah suatu state yang menjadi suksesor dari current state.

b.      Untuk setiap operator yang bisa dilakukan terhadap current state, kerjakan :

                                      i.            Aplikasikan semua operator yang ada dan bangkitkan new state.

                                    ii.            Evaluasi new state. Jika merupakan goal state, jadikan ini sebagai solusi dan keluar dari program. Jika bukan goal state, bandingkan dengan new state  dengan SUK. Jika new state lebih baik dari SUK maka ganti SUK dengan new state. Jika new state tidak lebih baik dari SUK, tidak perlu diganti.

c.       Jika SUK lebih baik dari current state maka ganti current state dengan SUK.

Berikut ini adalah gambar proses penyelesaian solusi dengan menggunakan SAHC.