INTELEGENSI BUATAN Pertemuan 2,3 Problem, Space, Search
M. Miftakul Amin, M. Eng. e-mail: e mail:
[email protected] mmiftakulamin@gmail com website : http://mafisamin.web.ugm.ac.id
Jurusan Teknik Komputer Politeknik Negeri Sriwijaya Palembang 2014
Tujuan z
Mahasiswa mampu merepresentasikan masalah dalam ruang g keadaan dan melakukan memahami berbagai metode pencarian.
Pokok Bahasan
Mendefinisikan Masalah dalam Ruang Keadaan Representasi Ruang Keadaan Metode Pencarian & Pelacakan
Artificial Intelligence ARTIFICIAL INTELLIGENCE Output: SOLUSI
Input: MASALAH
Knowledge Base
Inference Engine
Permainan Catur
Keadaan awal :
Aturan-aturan untuk melakukan gerakan secara legal
IF Bidak putih pada Kotak(e,2), And Kotak(E,3) Kosong, And Kotak(E,4) Kosong Then Gerakkan bidak dari (E,2) ke (E,4)
Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya. Kemenangan ini ditandai dengan posisi Raja yang sudah tidak dapat bergerak lagi.
Ruang Keadaan
suatu ruang yang berisi semua keadaan yang mungkin
Penyelesaian masalah secara umum
Mendefinisikan suatu ruang keadaan; Menetapkan satu atau lebih keadaan awal; Menetapkan satu atau lebih tujuan; Menetapkan kumpulan aturan.
Representasi Ruang Keadaan
Graph Keadaan Pohon Pelacakan Pohon AND/OR Kasus …
Graph Keadaan A
3 B
4
2
C 8 5
H
3 I D
2
G
1
E
6
M
F
4
4
J
7 T 6
Lintasan dari M ke T:
M-A-B-C-E-T M-A-B-C-E-H-T MDCET M-D-C-E-T M-D-C-E-H-T
Lintasan yang menemui jalan buntu (tidak sampai ke T):
MABCEFG M-A-B-C-E-F-G M-A-B-C-E-I-J M-D-C-E-F-G M-D-C-E-I-J M-D-I-J
Pohon Pelacakan M
Level-0 e e Level-1
D
A B
I
C
Level-2
C
J
E
Level-3
Buntu
E
F
I
H
T
Level-4
Tujuan
F G
I J
Buntu Buntu
H
T Tujuan
T Tujuan
G
J
T
Buntu Buntu Tujuan
Level-5 Level-6
Pohon AND/OR
M
A
B
(a)
M
C
A
arc yang terletak antara busur berarti AND
(b)
B
C
M A
B
H
D
E
C
T
Level-0
T
C
H
E
T
Level-1
T
Level-2
Contoh: Masalah Teko Air
Ada 2 buah teko masing-masing berkapasitas 4 galon (teko A) dan 3 galon (teko B). Tidak ada tanda yang menunjukkan batas ukuran pada kedua teko t tersebut. b t Ada sebuah pompa air yang akan digunakan untuk mengisikan air pada kedua teko tersebut. Permasalahannya: y Bagaimanakah g kita dapat p mengisikan g tepat p 2g galon air ke dalam teko yang berkapasitas 4 galon?
Air tak terbatas 4 galon (teko A)
3 galon (t k B) (teko
Penyelesaian …
Identifikasi ruang keadaan:
Permasalahan ini dapat direpresentasikan dengan 2 bilangan integer, yaitu x dan y:
x = air yang diisikan pada teko 4 galon (teko A); y = air yang diisikan pada teko 3 galon (teko B);
Ruang keadaan: (x,y) sedemikian hingga x∈{0,1,2,3,4} dan y { , , , } y∈{0,1,2,3}.
Keadaan awal & tujuan:
Keadaan awal, kedua teko dalam keadaan kosong: (0,0); Tujuan, keadaan dimana pada teko 4 galon berisi tepat 2 galon air: (2,n) untuk sembarang n.
Keadaan Awal
Tujuan
((0,0) , )
((1,0) , )
((2,0) , )
((3,0) , )
((4,0) , )
((0,1) , )
((1,1) , )
((2,1) , )
((3,1) , )
((4,1) , )
(0,2)
(1,2)
(2,2)
(3,2)
(4,2)
(0,3)
(1,3)
(2,3)
(3,3)
(4,3)
Aturan-aturan
Aturan ke-
Jika
Maka
1.
(x,y) x<4
(4,y) Isi teko A.
2.
(x,y) y<3
(x,3) Isi teko B.
3 3.
(x,y) (x y) x>0
(x-d,y) (x d y) Tuangkan sebagian air keluar dari teko A.
4.
(x,y) y>0
(x,y-d) Tuangkan sebagian air keluar dari teko B.
5.
(x,y) x>0
(0,y) Kosongkan teko A dengan membuang airnya ke tanah.
6.
(x,y) y>0
(x,0) Kosongkan teko B dengan membuang airnya ke tanah.
7.
(x,y) x+y + ≥ 4 dan d y>0
(4,y-(4-x)) T Tuangkan k air i d darii tteko k Bk ke tteko k A sampai teko A penuh.
8.
(x,y) x+y ≥ 3 dan x > 0
(x-(3-y),3) Tuangkan air dari teko A ke teko B sampai teko B penuh.
9.
(x,y) x+y ≤ 4 dan y > 0
(x+y,0) Tuangkan seluruh air dari teko B ke t k A. teko A
10.
(x,y) x+y ≤ 3 dan x > 0
(0,x+y) Tuangkan seluruh air dari teko A ke teko B.
11.
(0,2)
(2,0) Tuangkan 2 galon air dari teko B ke teko A.
12.
(2,y)
(0,y) Kosongkan 2 galon air di teko A dengan membuang airnya ke tanah.
Representasi p ruang g keadaan dengan g p pohon pelacakan. (0,0)
(4,0)
(4,3)
(0,0)
(0,3)
(1,3)
(4,3)
(0,0)
(3,0)
Salah satu solusi: Isi Teko A (gallon)
Isi Teko B (gallon)
Aturan yang dipakai
0
0
2
0
3
9
3
0
2
3
3
7
4
2
5
0
2
9
2
0
solusi
Contoh: Petani, Sayur, dan Kambing
Seorang gp petani akan menyeberangkan y g seekor kambing, seekor serigala, dan sayur-sayuran dengan sebuah boat yang melalui sungai. B Boat h hanya bi bisa memuat petanii d dan satu penumpang yang lain (kambing, serigala atau sayur sayuran). sayur-sayuran) Jika ditinggalkan oleh petani tersebut, maka sayur-sayuran akan dimakan oleh kambing, dan kambing akan dimakan oleh serigala.
Penyelesaian …
Identifikasi ruang keadaan
Keadaan Awal
Permasalahan ini dapat dilambangkan dengan (J l hK bi (JumlahKambing, JJumlahSerigala, l hS i l JJumlahSayuran, l hS JumlahBoat). Sebagai contoh: Daerah asal (0,1,1,1) berarti pada daerah asal tidak ada kambing kambing, ada serigala serigala, ada sayuran sayuran, dan ada boat. Daerah asal: (1,1,1,1) (1 1 1 1) Daerah seberang: (0,0,0,0)
Tujuan
Daerah D h asal: l (0 (0,0,0,0) 0 0 0) Daerah seberang: (1,1,1,1)
Aturan-aturan Aturan ke1.
Kambing menyeberang
2.
Sayuran menyeberang b
3.
Serigala menyeberang
4 4.
K Kambing bi k kembali b li
5.
Sayuran kembali
6 6.
Serigala kembali
7.
Boat kembali
Aturan
Salah satu solusi: Daerah Asal
Daerah Seberang
Aturan yang dipakai
(1,1,1,1)
(0,0,0,0)
1
(0,1,1,0)
(1,0,0,1)
7
(0,1,1,1)
(1,0,0,0)
3
(0,0,1,0)
(1,1,0,1)
4
(1 0 1 1) (1,0,1,1)
(0 1 0 0) (0,1,0,0)
2
(1,0,0,0)
(0,1,1,1)
7
(1 0 0 1) (1,0,0,1)
(0 1 1 0) (0,1,1,0)
1
(0,0,0,0)
(1,1,1,1)
solusi
Metode Pencarian & pelacakan
Pencarian Buta (Blind Search)
Breadth-First Breadth First Search Depth-First Search
Pencarian Terbimbing (Heuristics Search)
Generate & Test Hill Cli Climbing bi Best-First Search Tabu Search Simulated Annealing
Breadth-First Search
Pada metode Breadth-First Breadth First Search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan hingga ditemukannya solusi
A
E
F
D
C
B
G
H
I
J
K
L
M
Keuntungan:
Tidak akan menemui jalan buntu. Jika ada satu solusi, maka breadth-first search akan k menemukannya. k Dan D jik jika ada d llebih bih d darii satu t solusi, maka solusi minimum akan ditemukan.
Kelemahan:
Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon. Membutuhkan waktu y yang g cukup p lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)
Depth-First Search
Pada Depth Depth-First First Search, proses pencarian akan dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi
A B C
Keuntungan
Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan. Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji labih banyak lagi dalam ruang keadaan.
Kelemahan
Memungkinkan tidak ditemukannya tujuan yang diharapkan. H Hanya akan k mendapatkan d tk 1 solusi l i pada d setiap ti pencarian.
Pencarian Heuristik
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 gg 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
Nilai heuristik …
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 h= 5
5
Untuk jumlah ubin yang menempati posisi yang salah l h Æ jumlah j l h yang llebih bih kkecilil adalah d l h 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
Menghitung total gerakan yang diperlukan untuk mencapaii tujuan j Æ jumlah j l h yang llebih bih kkecilil adalah d l h 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
Generate & Test
Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal awal. Algoritma: 1.
2.
3.
Bangkitkan suatu kemungkinan solusi (membangkitkan suatu t titik ttertentu t t atau t lintasan li t tertentu t t t dari d i keadaan k d awal). Uji untuk melihat apakah node tersebut benar-benar merupakan k solusinya l i d dengan cara membandingkan b di k node d tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan. Jik solusi Jika l i dit ditemukan, k kkeluar. l Jik Jika tid tidak, k ulangi l i kkembali b li langkah yang pertama.
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. A 7 D
B
8 3
4
6
5 C
Generate & test akan membangkitkan semua solusi yyang g mungkin: g 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 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
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
Pencarian ke-
Li t Lintasan
Panjang Lintasan
Li t Lintasan terpilih t ilih
Panjang Li t Lintasan terpilih
13.
CABD
15
ACBD
12
14 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 22.
DBCA
12
ACBD atau t DBCA
12
23.
DCAB
17
ACBD atau DBCA
12
24.
DCBA
19
ACBD atau DBCA
12
Pencarian ke-
Salah satu kelemahan dari metode generate & test i i adalah ini d l h perlu l membangkitkan b ki k semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang cukup besar d l dalam pencariannya. i
Pendakian Bukit (Hill Climbing)
Metode ini hampir p sama dengan g metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. heuristik Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. t 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 langkah langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
Cari operator p yyang g belum p pernah digunakan; g ;g gunakan operator p 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 j iterasi.
Kasus: TSP
Operator Æ Tukar kota ke-i dengan kota ke-j (Tk i,j) Untuk 4 kota:
Tk 1,2 Tk 1,3 Tk 1,4 14 Tk 2,3 Tk 2,4 Tk 3,4
: tukar kota ke-1 dengan kota ke-2. : tukar kota ke-1 dengan kota ke-3. : tukar kota ke-1 ke 1 dengan kota ke-4. 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.
Untuk 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 climbing, ada 3 masalah yang mungkin:
Algoritma akan berhenti kalau mencapai nilai optimum local. Urutan p penggunaan gg operator p akan sangat g berprngaruh pada penemuan solusi. Tidak diijinkan untuk melihat satupun langkah sebelumnya.
Steepest Ascent Hill Climbing
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 successor-successor. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:
Gunakan G k operator t tersebut t b t dan d bentuk b t k keadaan k d baru. b 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. sekarang, sekarang
Kasus: TSP (19) ABCD
(17) BACD
(15) CABD
Tk 1 1,2 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 13 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 steepest-ascent ascent hill climbing ini, 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 k karena kketidakmampuan tid k untuk t k menggunakan k 2 operator sekaligus.
Best-First Search
Metode best-first search ini merupakan kombinasi dari metode depth-first depth first search dan metode breadth-first breadth first search dengan mengambil kelebihan dari kedua metode tersebut. Apabila pada pencarian dengan metode hill climbing tidak diperbolehkan d pe bo e a u untuk tu kembali e ba ke e node ode pada level e e ya yang g lebih eb 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. 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
A
[C,F,B,E] 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
Tabu Search merupakan suatu metode optimasi yang menggunakan short-term memory untuk menjaga agar proses pencarian tidak terjebak pada nilai optimum lokal lokal. Metode ini menggunakan Tabu List untuk menyimpan sekumpulan solusi yang baru saja dievaluasi. Selama proses optimasi, optimasi pada setiap iterasi iterasi, solusi yang akan dievaluasi akan dicocokkan terlebih dahulu dengan isi Tabu List untuk melihat apakah solusi tersebut sudah ada pada Tabu List. Apabila p solusi tersebut sudah ada p 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 yyang g baru saja j diperoleh merupakan solusi yang sebenarnya.
Algoritma:
Tetapkan:
X = Matriks input berukuran nxm. MaxItr = maksimum iterasi.
S = bangkitkan solusi secara random. GlobalMin = FCost(S). Best = S. T b Li t = [] TabuList []. Kerjakan dari k=1 sampai MaxItr:
BestSoFar = FCost(S). FCost(S) BestMove = S. Kerjakan j dari i=1 sampai p ((n-1): )
Kerjakan dari j=i sampai n:
L = Tukar(S[i] Tukar(S[i],S[j]). 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. Jik B Jika BestSoFar tS F < GlobalMin, Gl b lMi kerjakan: k j k
GlobalMin = BestSoFar. Best = BestMove. Contoh …
Simulated Annealing
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 menentukan, tetangga, gain gain, temperatur 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 E = nilai il i sekarang k – nilai il i keadaan k d baru. b
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: p' = e− ∆E / T
g ini biasanya y dikerjakan j dengan g membangkitkan g suatu bilangan g Langkah 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. BEST_SO_FAR
Secara umum ada 3 hal p pokok p 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 g g akan sama dengan g hill climbing. Biasanya temperatur awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak acak. b. Kriteria yang digunakan untuk memutuskan apakah temperatur sistem seharusnya dikurangi. c. Berapa besarnya pengurangan temperatur dalam setiap waktu.
Pseudocode Function PjgJalur(L,X,Y): PjgJalur(L X Y): real;
Panjang = 0; For i=1 i 1 to (NC-1) (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 2*LM
Function JalurBaru(L): arrayNC; Bangkitkan 2 bilangan random N1 dan N2 antara 1 sampai NC dengan N1 < N2 Depan = L(1) sampai L(N1 L(N1-1); 1); Tengah = L(N1) sampai L(N2); Belakang = L(N2 L(N2+1) 1) sampai L(NC); Bangkitkan bilangan random r. If r < 0,5 then
DepanBaru = Depan. TengahBaru(1..NT) = Tengah(NT..1); dengan NT=N2N1+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 p = 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; 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; Mi Pj J l = PjgJalur(L); MinPjgJalur Pj J l (L) For i=1 to MaxIterasi do
Jalur = JalurBaru(L); Pj = PjgJalur(Jalur); Pjg Pj J l (J l )
If Pjg < MinPjgJalur then Mi Pj J l = Pj 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;
Kasus: TSP
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 p p 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. B l k BelakangBaru B = Belakang. B l k 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 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:
= [4 3 6]. = [9 11 2 5 1 7 8]. = [12 10].
Bangkitkan bilangan random r, apabila r < 0,5; maka:
Depan Tengah Belakang DepanBaru TengahBaru BelakangBaru Lbaru
= = = =
[4 3 6]. [8 7 1 5 2 11 9]. [12 10]. [4 3 6 8 7 1 5 2 11 9 12 10]
Jika r ≥ 0,5; 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 …
