Metode
Pencarian & Pelacakan dengan Heuristik
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
Kasus
8-puzzle Tujuan
Keadaan Awal
1
2
3
1
7
8
4
8
5
7
6
2
3 4
6
5
Operator
Ubin kosong geser ke kanan Ubin kosong geser ke kiri Ubin kosong geser ke atas Ubin kosong geser ke bawah
Langkah
awal Tujuan 1
2
8 7
6
3
1
2
3
4
7
8
4
5
6
kiri
5
atas
kanan 1
2
3
1
2
3
1
7
8
4
7
8
4
7
6
5
6
5
6
2
3 4
8
5
Untuk
jumlah ubin yang menempati posisi yang benar jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik) Tujuan 1
2
8 7
6
3
1
2
3
4
7
8
4
5
6
kiri
5
atas
kanan 1
2
3
1
2
3
1
7
8
4
7
8
4
7
6
5
6
5
h=6
h=4
6
2
3 4
8 h=5
5
Untuk
jumlah ubin yang menempati posisi yang salah jumlah yang lebih kecil adalah yang diharapkan (lebih baik). Tujuan 1
2
8 7
6
3
1
2
3
4
7
8
4
5
6
kiri
5
atas
kanan 1
2
3
1
2
3
1
7
8
4
7
8
4
7
6
5
6
5
h=2
h=4
6
2
3 4
8 h=3
5
MMenghitung
total gerakan yang diperlukan untuk mencapai tujuan jumlah yang lebih kecil adalah yang diharapkan (lebih baik). Tujuan 1
2
8 7
6
3
1
2
3
4
7
8
4
5
6
kiri
5
atas
kanan 1
2
3
1
2
3
1
7
8
4
7
8
4
7
6
5
6
5
h=2
h=4
6
2
3 4
8 h=4
5
Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal. Algoritma:
1.
2.
3.
Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal). Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
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. A 7 D
B
8
3
4
6
5 C
Generate
& test akan membangkitkan semua solusi yang
mungkin: A–B–C–D A–B–D–C A–C–B–D A – C – D – B, dll
A
B
C
D
B
C
C
D
B
D
C
B
D
C
D
B
B
C
D
Alur
pencarian
Pencarian ke-
Lintasan
Panjan g Lintasa n
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
6.
ADCB
18
ACBD
12
7.
BACD
17
ACBD
12
8.
BADC
21
ACBD
12
9.
BCAD
15
ACBD
12
10.
BCDA
18
ACBD
12
11.
BDAC
14
ACBD
12
12.
BDCA
13
ACBD
12
Lintasan terpilih
Panjang Lintasan terpilih
Pencaria n ke-
Lintasa n
Panjang Lintasa n
Lintasan terpilih
Panjang Lintasan terpilih
13.
CABD
15
ACBD
12
14.
CADB
14
ACBD
12
15.
CBAD
20
ACBD
12
16.
CBDA
16
ACBD
12
17.
CDAB
21
ACBD
12
18.
CDBA
18
ACBD
12
19.
DABC
20
ACBD
12
20.
DACD
15
ACBD
12
21.
DBAC
15
ACBD
12
22.
DBCA
12
ACBD atau DBCA
12
23.
DCAB
17
ACBD atau DBCA
12
24.
DCBA
19
ACBD atau DBCA
12
Salah
satu kelemahan dari metode generate & test ini adalah perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang cukup besar dalam pencariannya.
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.
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.
Tukar kota ke-i dengan kota ke-j (Tk i,j) Untuk 4 kota: Operator
Tk 1,2 Tk 1,3 Tk 1,4 Tk 2,3 Tk 2,4 Tk 3,4
Untuk
: tukar kota ke-1 dengan kota ke-2. : tukar kota ke-1 dengan kota ke-3. : tukar kota ke-1 dengan kota ke-4. : tukar kota ke-2 dengan kota ke-3. : tukar kota ke-2 dengan kota ke-4. : tukar kota ke-3 dengan kota ke-4.
N kota, akan ada operator sebanyak: N! 2!( N 2)!
(19)
ABCD
Tk 1,2
Tk 1,3
Tk 2,3 BACD
(17)
ACBD
Tk 3,4
Tk 4,1
ABDC
DBCA
Tk 2,4 ABDC
CBAD
Tk 1,2
ABCD
Tk 3,4 (15) Tk 2,3 BCAD BADC Tk 1,2
Tk 4,1
Tk 2,4
DACB
Tk 1,3
BDCA
Tk 1,3 Tk 2,4 (18) (19) BCDA DCAB
CABD
Tk 2,3 Tk 3,4 Tk 4,1
(20) CBAD
BACD
Tk 1,2 (21) BADC
(15) DBAC
(12) DBCA
Tk 1,2 BCDA
(14) BDAC
ACBD
Tk 2,3 Tk 3,4 Tk 4,1 Tk 2,4 Tk 1,3 (13) BDCA CDAB BCAD
Tk 2,3 Tk 3,4 Tk 4,1 Tk 2,4 BDAC
BDAC
Tk 1,3 CBAD
ADCB
Tk 1,2
Tk 1,3 Tk 2,3 Tk 3,4 Tk 4,1 Tk 2,4 (19) (15) (13) BDCA DCBA DBAC ACDB
(15) DACB
(16) CBDA
ADBC
Apabila
hanya digunakan 4 operator saja: (19)
ABCD
Tk 1,2 Tk 2,3 (17)
BACD
ACBD
Tk 3,4 Tk 2,3 (15)
Tk 1,2 ABCD
BCAD
Tk 4,1 BADC
DACB
Tk 3,4 (20)
Tk 1,2
CBAD
Tk 2,3 (17) BACD
(18) BCDA
Tk 4,1 (17) DCAB
Tk 3,4 ABDC
Tk 4,1 DBCA
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.
Steepest-ascent
hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.
Algoritma
Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang. Tentukan SUCC sebagai nilai heuristic terbaik dari successorsuccessor. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:
Gunakan operator tersebut dan bentuk keadaan baru. Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah.
Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang, ubah node SUCC menjadi keadaan sekarang.
(19) ABCD
(17) BACD
(15) CABD
Tk 1,2 Tk Tk 2,3 (12) (18) 3,4 ACBD ABDC
Tk 1,2 Tk Tk 2,3(13) 3,4 (19) ABCD ACDB
Tk 1,3 Tk Tk 2,4 4,1 (12) (18) DBCA
Tk Tk 2,4 Tk 1,3 4,1(19) (16) DCBA ADBC
ADCB
(15) BCAD
(20) CBAD
Pada
steepest-ascent hill climbing ini, ada 3 masalah yang mungkin, yaitu: Local optimum: keadaan semua tetangga lebih buruk atau sama dengan keadaan dirinya. Plateau: keadaan semua tetangga sama dengan keadaan dirinya. Ridge: local optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2 operator sekaligus.
Metode best-first search ini merupakan kombinasi dari metode depth-first search dan metode breadth-first search dengan mengambil kelebihan dari kedua metode tersebut. Apabila pada pencarian dengan metode hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya dengan metode best-first search ini. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada lebih yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk.
Algoritma:
Tempatkan node awal A pada antrian OPEN. Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong:
Ambil node terbaik dari OPEN; Bangkitkan semua successornya; Untuk tiap-tiap successor kerjakan: Jika node tersebut belum pernah dibangkitkan sebelumnya, evaluasi node tersebut dan masukkan ke OPEN; Jika node tersebut sudah pernah dibangkitkan sebelumnya, ubah parent jika lintasan baru lebih menjanjikan. Hapus node tersebut dari antrian OPEN.
Antrian OPEN A
[A]
A
[D,C,B]
C 5
B 3
D 7 [C,F,B,E]
A D
C 5
B 3
E
F
2
4
[G,F,B,E,H]
A
C
B 3 G 5
D H
E
F
1
2
4
Tabu Search merupakan suatu metode optimasi yang menggunakan short-term memory untuk menjaga agar proses pencarian tidak terjebak pada nilai optimum lokal. Metode ini menggunakan Tabu List untuk menyimpan sekumpulan solusi yang baru saja dievaluasi. Selama proses optimasi, pada setiap iterasi, solusi yang akan dievaluasi akan dicocokkan terlebih dahulu dengan isi Tabu List untuk melihat apakah solusi tersebut sudah ada pada Tabu List. Apabila solusi tersebut sudah ada pada Tabu List, maka solusi tersebut tidak akan dievaluasi lagi pada iterasi berikutnya. Apabila sudah tidak ada lagi solusi yang tidak menjadi anggota Tabu List, maka nilai terbaik yang baru saja diperoleh merupakan solusi yang sebenarnya.
Tetapkan:
X = Matriks input berukuran nxm. MaxItr = maksimum iterasi.
S
= bangkitkan solusi secara random. GlobalMin = FCost(S). Best = S. TabuList = []. Kerjakan dari k=1 sampai MaxItr: BestSoFar = FCost(S). BestMove = S. Kerjakan dari i=1 sampai (n-1):
Kerjakan dari j=i sampai n: L = Tukar(S[i],S[j]). Cost = FCost(L). Jika (L TabuList) atau (Cost < GlobalMin), kerjakan:
Jika (Cost < BestSoFar), kerjakan BestSoFar = Cost. BestMove = L.
S = BestMove. Tambahkan S ke TabuList. Jika BestSoFar < GlobalMin, kerjakan: GlobalMin = BestSoFar. Best = BestMove.
Contoh …
Ide dasar simulated annealing terbentuk dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) dalam pemrosesan logam ini adalah suatu proses bagaimana membuat bentuk cair berangsur-angsur menjadi bentuk yang lebih padat seiring dengan penurunan temperatur. Simulated annealing biasanya digunakan untuk penyelesaian masalah yang mana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat luas, misalkan perubahan gerakan dengan menggunakan permutasi pada masalah Travelling Salesman Problem. Pada simulated annealing, ada 3 parameter yang sangat menentukan, yaitu: tetangga, gain, temperatur, pembangkitan bilangan random.
Algoritma Evaluasi keadaan awal. Jika keadaan awal merupakan tujuan, maka pencarian berhasil dan KELUAR. Jika tidak demikian, lanjutkan dengan menetapkan keadaan awal sebagai kondisi sekarang. Inisialisasi BEST_SO_FAR untuk keadaan sekarang. Inisialisasi T sesuai dengan annealing schedule. Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi akan diaplikasikan ke kondisi sekarang.
Gunakan operator yang belum pernah digunakan tersebut untuk menghasilkan kondisi baru. Evaluasi kondisi yang baru dengan menghitung:
E = nilai sekarang – nilai keadaan baru. Jika kondisi baru merupakan tujuan, maka pencarian berhasil dan KELUAR. Jika bukan tujuan, namun memiliki nilai yang lebih baik daripada kondisi sekarang, maka tetapkan kondisi baru sebagai kondisi sekarang. Demikian pula tetapkan BEST_SO_FAR untuk kondisi yang baru tadi. Jika nilai kondisi baru tidak lebih baik dari kondisi sekarang, maka tetapkan kondisi baru sebagai kondisi sekarang dengan probabilitas: E/T
p'
e
Langkah ini biasanya dikerjakan dengan membangkitkan suatu bilangan random r pada range [0 1]. Jika r < p’, maka perubahan kondisi baru menjadi kondisi sekarang diperbolehkan. Namun jika tidak demikian, maka tidak akan dikerjakan apapun.
Perbaiki T sesuai dengan annealing scheduling.
BEST_SO_FAR adalah jawaban yang dimaksudkan.
Secara
umum ada 3 hal pokok pada simulated annealing,
yaitu: a. Nilai awal untuk temperatur (T0). Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati nol), karena jika T mendekati 0 maka gerakan simulated annealing akan sama dengan hill climbing. Biasanya temperatur awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak. b.Kriteria yang digunakan untuk memutuskan apakah temperatur sistem seharusnya dikurangi. c. Berapa besarnya pengurangan temperatur dalam setiap waktu.
Function PjgJalur(L,X,Y): real; Panjang = 0; For i=1 to (NC-1) do
Panjang = Panjang + ((XL(i+1) – XL(i))2 + (YL(i+1) – YL(i))2);
PjgJalur = Panjang;
Function T0(MTemp:integer): real; LMax = 0; For i=1 to MTemp do
LA = ambil jalur sembarang Len = PjgJalur(LA) If Len > LMax then LMax = Len
T0 = 2*LMax
Function JalurBaru(L): arrayNC; Bangkitkan 2 bilangan random N1 dan N2 antara 1 sampai NC dengan N1 < N2 Depan = L(1) sampai L(N1-1); Tengah = L(N1) sampai L(N2); Belakang = L(N2+1) sampai L(NC); Bangkitkan bilangan random r. If r < 0,5 then
DepanBaru = Depan. TengahBaru(1..NT) = Tengah(NT..1); dengan NT=N2-N1+1. BelakangBaru = Belakang. Lbaru = [DepanBaru TengahBaru BelakangBaru]
else
Sementara = [Depan Belakang]; dengan M elemen. Bangkitkan bilangan random r dengan nilai antara 1 sampai M. DepanBaru = Sementara(1..r). TengahBaru = Tengah. BelakangBaru = Sementara(r+1..M). Lbaru = [DepanBaru TengahBaru BelakangBaru]
JalurBaru =
LBaru
Procedure
SimulatedAnneal (MTemp:integer; NC:integer; X,Y:real; MItr:integer; MSukses:integer; decT:real);
T = T0(MTemp); L = [1 2 3 … NC]; MaxIterasi = MItr*NC; MaxSukses = MSukses*NC; JalurTerpendek = L; PjgJalurTerpendek = PjgJalur(L); Sukses = 1; While Sukses > 0 Sukses = 0; MinPjgJalur = PjgJalur(L); For i=1 to MaxIterasi do
Jalur = JalurBaru(L); Pjg = PjgJalur(Jalur);
If Pjg < MinPjgJalur then MinPjgJalur
= Pjg; Lbaru = Jalur; Sukses = Sukses +1; If MinPjgJalur < PjgJalurTerpendek then PjgJalurTerpendek = MinPjgJalur; JalurTerpendek = Lbaru; If Sukses = MaxSukses then BREAK; else Bangkitkan
bilangan random r; If r < e-(Pjg-MinPjgJalur)/T then Lbaru=Jalur;
L = Lbaru; T = decT * T;
Operator Ada beberapa operator yang bisa digunakan. Berikut ini adalah salah satu contoh operator untuk menentukan jalur. Misalkan jumlah kota yang akan dikunjungi adalah NC. Kota-kota disimpan pada larik L. Bangkitkan 2 bilangan random antara 1 sampai NC, misalkan kedua bilangan itu adalah N1 dan N2 dengan N1 < N2.
= L(1) sampai L(N1-1). = L(N1) sampai L(N2). = L(N2+1) sampai L(NC).
Bangkitkan bilangan random r, apabila r < 0,5; maka:
Depan Tengah Belakang
DepanBaru = Depan. TengahBaru = Tengah dengan urutan dibalik. BelakangBaru = Belakang. Lbaru = [DepanBaru TengahBaru BelakangBaru]
Jika r
0,5; maka kerjakan:
Sementara = [Depan Belakang], misalkan memiliki M elemen. Bangkitkan bilangan random r dengan nilai antara 1 sampai M. DepanBaru = Sementara(1:r). TengahBaru = Tengah. BelakangBaru = Sementara(r+1:M). Lbaru = [DepanBaru TengahBaru BelakangBaru]
Misalkan jalur yang ada adalah: L = [4 3 6 9 11 2 5 1 7 8 12 10] NC=12
Bangkitkan bilangan random, misal: N1=4 dan N2=10. Didapatkan: Depan Tengah Belakang
Bangkitkan bilangan random r, apabila r < 0,5; maka: DepanBaru TengahBaru BelakangBaru Lbaru
= [4 3 6]. = [9 11 2 5 1 7 8]. = [12 10].
Jika r
= = = =
[4 3 6]. [8 7 1 5 2 11 9]. [12 10]. [4 3 6 8 7 1 5 2 11 9 12 10]
0,5; maka kerjakan:
Sementara = [4 3 6 12 10], M=5. Bangkitkan bilangan random r, misal r=2. DepanBaru = [4 3]. TengahBaru = [9 11 2 5 1 7 8]. BelakangBaru = [6 12 10]. Lbaru = [4 3 9 11 2 5 1 7 8 6 12 10]
Contoh …
