HEURISTIC SEARCH
ì
Irvanizam Zamanhuri, M.Sc Dr. Taufiq A. Gani, M.EngSc Jurusan Informatika Universitas Syiah Kuala http://informatika.unsyiah.ac.id/irvanizam
Travelling Salesmen Problem ì Seorang salesman ingin mengunjungi sejumlah n
kota. Akan dicari rute terpendek di mana se7ap kota hanya boleh dikunjungi tepat 1 kali.
Heuristic Search Pencarian buta 7dak selalu dapat diterapkan dengan baik,
hal ini disebabkan waktu aksesnya yang cukup lama serta besarnya memori yang dibutuhkan Kelemahan ini dapat diatasi jika ada informasi tambahan (fungsi heuris7k) dari domain yang bersangkutan Heuris7c adalah
Suatu proses yang mungkin dapat menyelesaikan suatu masalah tetapi 7dak ada jaminan bahwa solusi yang dicari selalu dapat ditemukan
Fungsi Heuris7k adalah fungsi yang melakukan pemetaan
(mapping) dari diskripsi keadaan masalah (problema) ke pengukur kebutuhan, umumnya direpresentasikan berupa angka.
Heuristic Search AI menggunakan heuris7k dalam 2 situasi dasar : Persoalan/problema yang mungkin memiliki solusi eksak, namun biaya perhitungan untuk menemukan solusi tersebut sangat 7nggi dalam kebanyakan persoalan (seper7 catur), ruang keadaan bertambah secara luar biasa seiring dengan jumlah Persoalan yang mungkin 7dak memiliki solusi eksak karena ambiquitas (ke7dakpas7an) mendasar dalam pernyataan persoalan atau data yang tersedia, diagnosa medis merupakan salah satu contohnya. Heuris7k hanyalah sebuah cara menerka langkah
berikutnya yang harus diambil dalam memecahkan suatu persoalan berdasarkan informasi yang ada/tersedia.
Metode Pencarian Heuristic ì Bangkitkan dan Uji (Generate and Test) ì HILL CLIMBING ì Simple Hill Climbing ì Steepest = Ascent Hill Climbing
ì BEST FIRST SEARCH ì Greedy Best First Search ì Algoritma A*
Generate dan Test (1/2) ì Metode Generate-‐and-‐Test (GT) adalah
metode yang paling sederhana dalam teknik pencarian heuris7k.
ì Di dalam GT, terdapat dua prosedur pen7ng: ì Pembangkit (generate), yang membangkitkan semua
solusi yang mungkin. ì Test, yang menguji solusi yang dibangkitkan tersebut.
ì Algoritma GT menggunakan prosedur Depth
First Search karena suatu solusi harus dibangkitkan secara lengkap sebelum dilakukan Test.
Generate dan Test (2/2) ì Dengan penggunaan memori yang sedikit, DFS
bisa digunakan sebagai prosedur pembangkit yang menghasilkan suatu solusi.
ì Prosedur Test bisa menggunakan fungsi
heuris7k.
Algoritma Generate dan Test 1.
2. 3.
Bangkitkan suatu kemungkinan solusi. Solusi bisa berupa suatu keadaan (state) tertentu. Solusi juga bisa berupa sebuah jalur dari satu posisi asal ke posisi tujuan, seper7 dalam kasus pencarian rute dari satu kota asal ke kota tujuan. Tes apakah solusi yang dibangkitkan tersebut adalah sebuah solusi yang bisa diterima sesuai dengan kriteria yang diberikan. Jika solusi telah ditemukan, keluar. Jika belum, kembali ke langkah 1.
CONTOH KASUS TSP (Travelling Salesmen Problem) ì Seorang salesman ingin mengunjungi sejumlah n
kota. Akan dicari rute terpendek di mana se7ap kota hanya boleh dikunjungi tepat 1 kali. ì Jarak antara 7ap-‐7ap kota sudah diketahui. Misalkan ada 4 kota dengan jarak antara 7ap-‐7ap kota seper7 terlihat pada gambar berikut.
CONTOH KASUS TSP(Travelling Salesmen Problem) ì Membangkitkan solusi-‐solusi yang mungkin dengan
menyusun kota-‐kota dalam urutan abjad, yaitu : ì A – B – C – D ì A – B – D – C ì A – C – B – D ì A – C – D – B ì Dst
ì Untuk mengetahui jumlah seluruh kombinasi abjad
yang mungkin menjadi sebuah solusi à n!
CONTOH KASUS TSP(Travelling Salesmen Problem) ì Pilih keadaaan awal, misal ABCD dengan panjang
lintasan 19
ì Lakukan backtracking untuk mendapatkan lintasan
ABDC, misal panjang lintasan 18
ì Bandingkan lintasan ABDC dengan sebelumnya,
lintasan terpendek akan dipilih untuk dilakukan backtracking lagi.
ì Solusi terbaik adalah menemukan lintasan
terpendek dari kota yang dilewa7.
CONTOH KASUS TSP(Travelling Salesmen Problem) ì Dibuat Tabel
CONTOH KASUS TSP(Travelling Salesmen Problem)
Generate dan Test ì Kelemahan : ì Membangkitkan semua kemungkinan sebelum dilakukan pengujian ì Membutuhkan waktu yang cukup besar dalam pencariannya
Hill Climbing ì Terdapat 2 jenis HC yang sedikit berbeda, yaitu
Simple Hill Climbing (HC sederhana) dan Steepest-‐ Ascent Hill Climbing (HC dengan memilih kemiringan yang paling tajam/curam).
ì Simple HC, langsung memilih new state yang
memiliki jalur yang lebih baik (“curam”) daripada jalur-‐jalur sebelumnya tanpa memperhitungkan jalur-‐jalur lain yang lebih “curam”.
ì Sedangkan Steepest-‐Ascent HC, akan mengevaluasi
semua state yang berada di bawah current state dan memilih state dengan jalur yang paling “curam”.
Simple Hill Climbing Algoritma Mulai dari keadaan awal, (ini*al state) lakukan pengujian,
Ulangi langkah berikut hingga solusi ditemukan atau sampai 7dak ada operator baru yang diaplikasikan pada keadaan sekarang
jika state (keadaan) merupakan goal state (tujuan) à berhen7 jika state (keadaan) bukan merupakan goal state (tujuan) à lanjutkan dengan keadaan sekarang sebagai keadaan awal. Pilih operator yang belum pernah digunakan Gunakan operator untuk mendapatkan keadaan yang baru
Evaluasi keadaan baru tersebut :
Jika keadaan baru adalah tujuan à keluar Jika 7dak tetapi nilainya lebih baik dari keadaan sekarang, à jadikan keadaan baru tersebut menjadi keadaan sekarang Jika keadaan baru 7dak lebih baik dari keadaan sekarang à lanjutkan iterasi
Simple Hill Climbing Contoh Kasus : TSP Operator yg digunakan adalah operator yang bisa menghasilkan
kombinasi lintasan kota yang berbeda, yaitu dengan menukar urutan posisi 2 kota dalam suatu lintasan. Bila ada n kota maka kombinasi lintasan : n!
2!( n ! 2 )! Jika dari soal terdapat 4 kota maka kombinasi ada 6 yaitu :
1. (1,2) tukar urutan posisi kota ke-‐1 dg kota ke-‐2 2. (2,3) tukar urutan posisi kota ke-‐2 dg kota ke-‐3 3. (3,4) tukar urutan posisi kota ke-‐3 dg kota ke-‐4 4. (4,1) tukar urutan posisi kota ke-‐4 dg kota ke-‐1 5. (2,4) tukar urutan posisi kota ke-‐2 dg kota ke-‐4 6. (1,3) tukar urutan posisi kota ke-‐1 dg kota ke-‐3
Simple Hill Climbing Contoh Kasus : TSP ì Pada pencarian ini, penggunaan urutan dari
kombinasi harus konsisten. Setelah kombinasi ditentukan, gunakan algoritma pengerjaan sesuai aturan metode simple hill climbing. Misalnya keadaan awal adalah ABCD
Simple Hill Climbing Contoh Kasus : TSP dengan 6 operator 8
A 3
7 D
B 4
6
5 C
Penjelasan (1/2) ì Keadaan awal, lintasan ABCD (=19). ì Level pertama, hill climbing mengunjungi BACD (=17), BACD
(=17) < ABCD (=19), sehingga ì BACD menjadi pilihan selanjutnya dengan 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 ke7ga, 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)
Penjelasan (2/2) ì 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 7dak ada node yang memiliki nilai heuris7k yang lebih
kecil dibanding nilai heuris7k DBCA, maka node DBCA (=12) adalah lintasan terpendek (SOLUSI)
Simple Hill Climbing Contoh Kasus : TSP dengan 6 operator §
Pencarian dilihat dari anak kiri, bila nilai heuris7k anak kiri lebih baik, maka dibuka untuk pencarian selanjutnya, bila 7dak baru melihat tetangga dari anak kiri tersebut.
§
Solusi yang dihasilkan adalah node DBCA (=12) à lintasan terpendek dibanding yang lain.
§
Kelemahannya : 1. 7dak semua solusi dapat ditemukan seper7 pada metode generate and test (2 solusi). 2. pembatasan kombinasi operator à penemuan solusi yang 7dak maksimal
Simple Hill Climbing §
Masalah-‐masalah yang mungkin 7mbul pada prosedur Hill Climbing : §
Maksimum Lokal §
§
Daratan (Plateau) §
§
Suatu keadaaan yang lebih baik daripada semua tetangganya namum masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya. Suatu daerah datar dari ruang pencarian (search) dimana semua himpunan keadaan tetangganya memiliki nilai yang sama.
Punggung (Ridge) §
Suatu daerah ruang pencarian (search) yang lebih 7nggi daripada daerah sekitarnya, namun 7dak dapat dibalikkan oleh langkah-‐langkah tunggal ke arah manapun.
Simple Hill Climbing ì Solusinya : ì Melakukan langkah balik (tracking) 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 kebeberapa arah sekaligus.
STEEPEST – ASCENT HILL CLIMBING ì Hampir sama dengan simple hill climbing, hanya saja
gerakan pencarian 7dak dimulai dari kiri, tetapi berdasarkan nilai heuris7k terbaik.
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)
BEST FIRST SEARCH §
Merupakan kombinasi kelebihan teknik depth first search dan breadth first search dengan mengambil kelebihan dari kedua metode tersebut.
§
Pencarian diperkenankan mengunjungi node yang ada di level yg lebih rendah jika ternyata node pada level yg lebih 7nggi ternyata memiliki nilai heuris7k yg buruk.
§
Untuk mengimplementasikan metode ini, dibutuhkan 2 antrian yang berisi node-‐node, yaitu : § §
OPEN à berisi simpul-‐simpul yang masih memiliki peluang (peluangnya masih terbuka) untuk terpilih sebagai simpul terbaik. CLOSED à berisi simpul-‐simpul yang 7dak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup).
BEST FIRST SEARCH §
Best First Search akan membangkitkan node berikutnya dari semua node yang pernah dibangkitkan.
§
Pertanyaannya : Bagaimana menentukan sebuah node terbaik saat ini?
Dilakukan dengan menggunakan biaya perkiraan
Bagaimana caranya menentukan biaya perkiraan? Biaya perkiraan dapat ditentukan dengan fungsi heuris*c
Best First Search Fungsi Heuristic ì Suatu fungsi heuris7c dikatakan baik jika bisa
memberikan biaya perkiraan yang mendeka7 biaya sebenarnya.
ì Semakin mendeka7 biaya sebenarnya, fungsi
heuris7c tersebut semakin baik.
Contoh 100 16 A ( 20 , 10 )
B ( 35 , 10 )
10 C ( 55 , 10 )
D ( 65 , 10 )
Dalam kasus pencarian rute terpendek, biaya sebenarnya adalah panjang jalan raya yang sebenarnya. Sedangkan fungsi heuristiknya adalah garis lurus dari 1 kota ke kota lainnya. Untuk itu, bisa digunakan rumus berikut :
dab =
( y b – y a )2 + ( x b – x a )2
dAB = 15 dBC = 20 dCD = 10
Algoritma Best First Search ì Greedy Best First Search ì Algoritma A*
Greedy Best First Search ì Algoritma ini merupakan jenis algoritma Best First
Search yg paling sederhana
ì Algoritma ini hanya memperhitungkan biaya
perkiraan saja
f(n) = h’(n)
ì Karena hanya memperhitungkan biaya perkiraan
yang belum tentu kebenarannya, maka algoritma ini menjadi Bdak opBmal
90 A
10
25
S
10 E
35 15
10
F
5
40
B
30
C
D
K
50
30
25
H
40
25 L
52
20
G
40
J
40
80
M
n
S
A
B
C
D
E
F
G
H
J
K
L
M
h (n)
80
80
60
70
85
74
70
0
40
100
30
20
70
A
10
25 S
B
30 C
35
10
D E
LANGKAH 1
n
S
A
B
C
D
E
h (n)
80
80
60
70
85
74
A
10
5
25 S 10
F K
50
B
30 C
35 D
LANGKAH 2
E
n
A
C
D
E
F
K
h (n)
80
70
85
74
70
30
A
10
F
5
25 B S
30
30 C
35
10
K
50
LANGKAH 3
D E
n
A
C
D
E
F
G
h (n)
80
70
85
74
70
0
G
10
A
5
25 B S 10
F 50
30
30 35
K
G
C
SOLUSI
D
Dengan Total Jarak = 105
E
S -‐ B -‐ K -‐ G
PENJELASAN ì Dari contoh di atas, Greedy akan menemukan
solusi S-‐B-‐K-‐G dengan total jarak 105
ì Padahal ada solusi lain yg lebih op7mal, yakni
S-‐A-‐B-‐F-‐K-‐G dengan total jarak hanya 95 ì Dari situ bisa disimpulkan bahwa Greedy Best First
Search 7dak bisa menemukan solusi yang op7mal
ALGORITMA A* ì Berbeda dengan Greedy, algoritma ini akan menghitung
fungsi heuris7c dengan cara menambahkan biaya sebenarnya dengan biaya perkiraan. Sehingga didapatkan rumus :
f(n) = g(n) + h’(n)
g(n) = Biaya sebenarnya dari Node Awal ke Node n ì h’(n) = Biaya perkiraan dari Node n ke Node Tujuan ì
ì Dengan perhitungan biaya seper7 ini, algoritma A* adalah
complete dan opBmal
ALGORITMA A* ì Algoritma A* juga menggunakan dua senarai,
yaitu :
ì OPEN ì CLOSED
ì Terdapat 7ga kondisi bagi se7ap suksessor yang
dibangkitkan, yaitu :
ì Sudah berada di OPEN ì Sudah berada di CLOSE ì Tidak berada di OPEN maupun CLOSE
ALGORITMA A* §
Jika Suksessor sudah pernah berada di OPEN, maka : §
§ § §
Dilakukan pengecekan apakah perlu pengubahan parent atau 7dak tergantung pada nilai g nya melalui parent lama atau parent baru Jika melalui parent baru memberikan nilai g yang lebih kecil, maka dilakukan pengubahan parent. Jika pengubahan parent dilakukan, maka dilakukan perbaruan (update) nilai g dan f pada suksessor tersebut. Dengan perbaruan ini, suksessor tersebut memiliki kesempatan yang lebih besar untuk terpilih sebagai simpul terbaik
ALGORITMA A* ì Jika Suksessor sudah pernah berada di CLOSED,
maka:
ì Dilakukan pengecekan apakah perlu pengubahan
parent atau 7dak. ì Jika ya, maka dilakukan perbaruan(update) nilai g dan nilai f pada suksessor tersebut pada semua anak cucunya yang sudah pernah berada di OPEN. ì Dengan perbaruan ini, maka semua anak cucunya memiliki kesempatan lebih besar untuk terpilih sebagai simpul terbaik.
ALGORITMA A* ì Jika suksessor 7dak berada di OPEN maupun di
CLOSED, maka :
ì Suksessor tersebut dimasukkan ke dalam OPEN ì Tambahkan suksessor tersebut sebagai
suksessornya best node. ì Hitung biaya suksessor tersebut dengan rumus f=g+h
90 A
10
10
25 S
30
K
50
30
40
C
G
25
D
40
25
H
15
E
40
B
35
10
F
5
L
52
20
J
40
80
M
n
S
A
B
C
D
E
F
G
H
J
K
L
M
h (n)
80
80
60
70
85
74
70
0
40
100
30
20
70
A
10 25 S
B
30 C
35
10
D E
LANGKAH 1
n
S
A
B
C
D
E
h (n)
80
80
60
70
85
74
g(n)
0
10
25
30
35
10
f(n)
80
90
85
100
120
84
A
10
25 S
B
30 C
35
10
E
D
15 20
LANGKAH 2
J
n
A
B
C
D
J
h (n)
80
60
70
85
100
g(n)
10
25
30
25
30
f(n)
90
85
100
110
130
A
10
10
F
5
25 B S
30 C
35
10
K
50
D 15 E 20
J
LANGKAH 3
n
A
C
D
J
F
K
h (n)
80
70
85
100
70
30
g(n)
10
30
25
30
30
75
f(n)
90
100
110
130
100
105
90
A
10
10
25 S
F K
50
B
30
G
C
35
10
5
D E
15 20
J
LANGKAH 4
n
C
D
J
F
K
G
h (n)
70
85
100
70
30
0
g(n)
30
25
30
25
70
100
f(n)
100
110
130
95
100
100
90
A
10
10
25 S 10
5
F
40 K
50
B
30
G
C
35 D
E
15 20
J
LANGKAH 5
n
C
D
J
K
G
h (n)
70
85
100
30
0
g(n)
30
25
30
65
100
f(n)
100
110
130
95
100
90
A
10
10
25 S
F
40 K
50
B
30
30
G
C
35
10
5
D E
15 20
J
LANGKAH 6
n
C
D
J
G
h (n)
70
85
100
0
g(n)
30
25
30
95
f(n)
100
110
130
95
90
A
10
10
25 S 10
5 B
F
40 50
30
30
G
C
35 D
E
15 20
K
J
SOLUSI : S -‐ A -‐ B -‐ F -‐ K -‐ G Dengan Total Jarak = 95
KESIMPULAN ì Algoritma A* lebih baik dalam melakukan
pencarian heuris7c daripada Greedy Best First Search karena dapat mengasilkan solusi yang op7mal.
