ARTIFICIAL INTELEGENCE - METODE PENCARIAN SIMPLE HILL CLIMBING

METODE PENCARIAN SIMPLE HILL CLIMBING

Metode pencarian & pelacakan 

• Teknik Search menentukan simpul mana yang dibuat lebih dulu dan mana yang kemudian sampai ditemukannya simpul solusi
• Dari proses search dihasilkan diagram tree, sehingga perlu penjelasan beberapa terminologi diagram tree seperti berikut :

Simpul

Level/Cabang

Path

Parent

Child

Root

Leave

Jumlah Ruang Simpul

Langkah solusi (Solusi)

Pencarian Buta (Blind Search)

Breadth-First Search

Depth-First Search

Pencarian Terbimbing (Heuristics Search)

Generate & Test

Hill Climbing

Best-First Search

Tabu Search

Simulated Annealing

Uniformed Cost Search (UCS)

Greedy Algorithm

A/A* Algorithm

Pendakian Bukit (Hill Climbing)

• Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. 
• Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. 
• Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

Simple Hill Climbing

Algoritma

• Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
• Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
• Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
• Evaluasi keadaan baru tersebut.
• Jika keadaan baru merupakan tujuan, 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.

Operator --> Tukar kota ke-i dengan kota ke-j (Tk i,j)

Kasus: TSP

Untuk 4 kota:

Tk 1,2 : tukar kota ke-1 dengan kota ke-2.

Tk 1,3 : tukar kota ke-1 dengan kota ke-3.

Tk 1,4 : tukar kota ke-1 dengan kota ke-4.

Tk 2,3 : tukar kota ke-2 dengan kota ke-3.

Tk 2,4 : tukar kota ke-2 dengan kota ke-4.

Tk 3,4 : tukar kota ke-3 dengan kota ke-4.

Untuk N kota, akan ada operator sebanyak: 

Kasus: Traveling Salesman Problem (TSP). 

Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali. 

Apabila hanya digunakan 4 operator saja:

Pada simple hill climbing, ada 3 masalah yang mungkin:

Algoritma akan berhenti kalau mencapai nilai optimum local.

Urutan penggunaan operator akan sangat berprngaruh pada penemuan solusi.

Tidak diijinkan untuk melihat satupun langkah sebelumnya.