modul 3 - pencarian heuristik

Masalah, Ruang Masalah dan Pencarian

Ir. Ahmad Haidaroh, M.Kom.

PENGENALAN KECERDASAN PENGENALAN KECERDASAN BUATAN BUATAN

( / AI )(2 SKS)

Ir. Ahmad Haidaroh, M.Kom.STIKOM Artha Buana.

Artificial Intelligence

Pencarian HeuristikPencarian HeuristikHeuristic seacrching

2STIKOM Artha Buana

Ir. Ahmad Haidaroh, M.Kom.

Pencarian Heuristik• Kelemahan blind search :

– Waktu akses lama– Memori yang dibutuhkan besar– Ruang masalah besar – tidak cocok – karena keterbasan

kecepatan komputer dan memori

• Solusi - Pencarian heuristik• Pencarian heuristik

– sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dg kemungkinan mengorbankan kelengkapan (completeness).

– menggunakan suatu fungsi yang menghitung biaya perkiraan / estimasi dari suatu simpul tertentu menuju ke simpul tujuan (disebut fungsi heuristik)

3STIKOM Artha Buana

Contoh• Kasus 8-puzzle

– Ada 4 operator :• Ubin kosong digeser ke kiri • Ubin kosong digeser ke kanan • Ubin kosong digeser ke bawah • Ubin kosong digeser ke atas

4STIKOM Artha Buana

Contoh

• Diberikan informasi khusus :– Untuk jumlah ubin yang menempati posisi

(urutan) yang benar (h)– Jumlah yang lebih banyak adalah yang lebih

diharapkan (lebih baik)

5STIKOM Artha Buana

6STIKOM Artha Buana

JumlahUbin Yg BenarJumlahUbin Yg Benar

Contoh

• Diberikan informasi khusus :– Untuk jumlah ubin yang menempati posisi

yang salah – Jumlah yang lebih kecil adalah yang

diharapkan (lebih baik)

7STIKOM Artha Buana

8STIKOM Artha Buana

Jumlah Ubin Yg SalahJumlah Ubin Yg Salah

Contoh

• Menghitung total gerakan yang diperlukan untuk mencapai tujuan

• Jumlah yang lebih kecil adalah yang diharapkan (lebih baik)

9STIKOM Artha Buana

10STIKOM Artha Buana

Pencarian Heuristik

Berikut ini, sekilas metode yang tergolong heuristic search :

a. Generate and Test (Pembangkitan dan Pengujian)

b. Best First Search

c. Hill Climbing (Pendakian Bukit)

1.Simple HC

2.Steepest-Ascent HC


Generate and Test (GT)• Metode ini merupakan penggabungan antara

depth-first search dg pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

• Algoritma :– Bangkitkan suatu kemungkinan solusi

(membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).

– Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dg cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dg kumpulan tujuan yang diharapkan.

– Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.


Contoh Kasus• Contoh : Traveling Salesman Problem (TSP)

– Seorang salesman ingin mengunjungi n kota.– Jarak antara tiap-tiap kota sudah diketahui. – Kita ingin mengetahui rute terpendek dimana setiap

kota hanya boleh dikunjungi tepat 1 kali. – Misal ada 4 kota dg jarak antara tiap-tiap kota seperti

berikut ini :


Contoh Kasus• Penyelesaian dg metode Generate and Test

DA B C

C DB

B D C BC D

D B B CD C


Semua diisi dg lintasan yg kurang

Contoh Kasus

Pencarian ke- Lintasan Panjang Lintasan

Lintasan Terpilih Panjang Lintasan Terpilih

1 ABCD 19 ABCD 19

2 ABDC 18 ABDC 18

3 ACBD 12 ACBD 12

4 ACDB 13 ACBD 12

5 ADBC 16 ACBD 12

Dst…


Hill Climbing (HC)

• Menyelesaikan masalah yang mempunyai beberapa solusi

• Ada solusi yang lebih baik daripada solusi lain


Hill Climbing• Contoh : Traveling Salesman Problem (TSP)

– Seorang salesman ingin mengunjungi n kota.– Jarak antara tiap-tiap kota sudah diketahui. – Kita ingin mengetahui rute terpendek dimana setiap

kota hanya boleh dikunjungi tepat 1 kali. – Misal ada 4 kota dg jarak antara tiap-tiap kota seperti

berikut ini :


Hill Climbing

• Solusi – solusi yang mungkin dg menyusun kota-kota dalam urutan abjad, misal : – A – B – C – D : dg panjang lintasan (=19) – A – B – D – C : (=18) – A – C – B – D : (=12) – A – C – D – B : (=13) – A – D – B – C : (=16)– A – D – C – B : (=18)


STIKOM Artha Buana 19

No. lintasan panjang

1 B A C D 17

2 B A D C 21

3 B C A D 15

4 B C D A 18

5 B D A C 14

6 B D C A 13

1 C A B D 15

2 C A D B 14

3 C B A D 20

4 C B D A 16

5 C D A B 21

6 C D B A 18

1 D A B C 20

2 D A C B 15

3 D B A C 15

4 D B C A 12

5 D C A B 17

6 D C B A 15

Simple Hill Climbing• Ruang keadaan berisi semua kemungkinan lintasan

yang mungkin. • Operator digunakan untuk menukar posisi kota-kota

yang bersebelahan. • Fungsi heuristik yang digunakan adalah panjang lintasan

yang terjadi. • Operator yang akan digunakan adalah menukar urutan

posisi 2 kota dalam 1 lintasan. Bila ada n kota, dan ingin mencari kombinasi lintasan dg menukar posisi urutan 2 kota, maka akan didapat sebanyak :


Simple Hill Climbing

• 6 kombinasi tsb digunakan sbg operator :

– Tukar 1,2 = menukar urutan posisi kota ke – 1 dg kota ke – 2







22

Node paling kiri dibandingkan panjang lintasannya dengan level di atasnya. Kalau lebih kecil, maka diambil lintasan tersebut. Klau tidak tidak bergeser ke sebelah kanannya dan bandingkan. Begitu seterusnya. Kalau level dibawahnya tidak ada yg lebih kecil, berarti node itulah yg diambil (SOLUSI)

Simple Hill Climbing• Keadaan awal, lintasan ABCD (=19). • Level pertama, hill climbing mengunjungi BACD (=17), BACD (=17)

< ABCD (=19), sehingga BACD menjadi pilihan selanjutnya dg operator Tukar 1,2

• Level kedua, mengunjungi ABCD, karena operator Tukar 1,2 sudah dipakai BACD, maka pilih node lain yaitu BCAD (=15), BCAD (=15) < BACD (=17)

• Level ketiga, mengunjungi CBAD (=20), CBAD (=20) > BCAD (=15), maka pilih node lain yaitu BCDA (=18), pilih node lain yaitu DCAB (=17), pilih node lain yaitu BDAC (=14), BDAC (=14) < BCAD (=15)

• Level keempat, mengunjungi DBAC (=15), DBAC(=15) > BDAC (=14), maka pilih node lain yaitu BADC (=21), pilih node lain yaitu BDCA (=13), BDCA (=13) < BDAC (=14)

• Level kelima, mengunjungi DBCA (=12), DBCA (=12) < BDCA (=13) • Level keenam, mengunjungi BDCA, karena operator Tukar 1,2

sudah dipakai DBCA, maka pilih node lain yaitu DCBA, pilih DBAC, pilih ABCD, pilih DACB, pilih CBDA

• Karena sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding nilai heuristik DBCA, maka node DBCA (=12) adalah lintasan terpendek (SOLUSI)


Algoritma Simple Hill Climbing• Evaluasi state awal, jika state awal sama dg tujuan,

maka proses berhenti. Jika tidak sama dg tujuan maka lanjutkan proses dg membuat state awal sebagai state sekarang.

• Kerjakan langkah berikut sampai solusi ditemukan atau sampai tidak ada lagi operator baru yang dapat digunakan dalam state sekarang: – Cari sebuah operator yang belum pernah digunakan dalam state

sekarang dan gunakan operator tersebut untuk membentuk state baru.

– Evaluasi state baru. • Jika state baru adalah tujuan, maka proses berhenti • Jika state baru tersebut bukan tujuan tetapi state baru lebih baik

daripada state sekarang, maka buat state baru menjadi state sekarang.

• Jika state baru tidak lebih baik daripada state sekarang, maka lanjutkan kelangkah sebelumnya.


Steepest Hill Climbing

• Mirip dg simple hill climbing

• Perbedaannya dg simple hill climbing :– semua suksesor dibandingkan, dan yang

paling dekat dg solusi yang dipilih– Pada simple hill climbing, node pertama yang

jaraknya terdekat dg solusi yang dipilih


• Keadaan awal, lintasan ABCD (=19). • Level pertama, hill climbing memilih nilai heuristik terbaik yaitu

ACBD (=12) sehingga ACBD menjadi pilihan selanjutnya. • Level kedua, hill climbing memilih nilai heuristik terbaik,

karena nilai heuristik lebih besar dibanding ACBD, maka hasil yang diperoleh lintasannya tetap ACBD (=12)


Algoritma Steepest Hill Climbing• Evaluasi keadaan awal (Initial State). Jika keadaan awal

sama dg tujuan (Goal state) maka kembali pada initial state dan berhenti berproses. Jika tidak maka initial state tersebut jadikan sebagai current state.

• Mulai dg current state = initial state. • Dapatkan semua pewaris (successor) yang dapat

dijadikan next state pada current statenya dan evaluasi successor tersebut dg fungsi evaluasi dan beri nilai pada setiap successor tersebut.

• Jika salah satu dari successor tersebut mempunyai nilai yang lebih baik dari current state maka jadikan successor dg nilai yang paling baik tersebut sebagai new current state.

• Lakukan operasi ini terus menerus hingga tercapai current state = goal state atau tidak ada perubahan pada current statenya.


Best First Search• Kombinasi dari metode depth first search dan

breadth first search • Pada best first search, pencarian diperbolehkan

mengunjungi node di lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristik lebih buruk.

• Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dg :

– f’(n) = g(n) + h’(n)– f’ = Fungsi evaluasi– g = cost dari initial state ke current state– h’ = prakiraan cost dari current state ke goal state



Best First Search


Contoh UCS


A

Step 1

(1)

A

CB D(3) (5)

Step 2

(6)

A

CB D(3) (1)(5)

E F(4)

Step 3

(6)

A

CB D(3) (1)(5)

E F(4)G H(6) (5)

Step 4

(6)

A

CB D(3) (1)(5)

E F(4)G H(6) (5)

Step 5

I J (1)(2)

Algoritma

• Buat sebuah antrian, inisialisasi node pertama dg root dari tree

• Bila node pertama, jika ≠ GOAL, node dihapus dan diganti dg anak-anaknya. Selanjutnya keseluruhan node yang ada diurutkan

• Bila node pertama = GOAL, selesai


Tugas

• Buat suatu contoh kasus

• Representasikan dg tree

• Pilih salah satu metode di bawah untuk menyelesaikan kasus tersebut :– Simple Hill climbing – Steepest Hill climbing– Best First Search


modul 3 - pencarian heuristik

Documents