INTELEGENSI BUATANPertemuan 2,3
Problem, Space, Search
M. Miftakul Amin, M. Eng.e mail: mmiftakulamin@gmail come-mail: [email protected]
website : http://mafisamin.web.ugm.ac.id
Jurusan Teknik KomputerJurusan Teknik KomputerPoliteknik Negeri Sriwijaya Palembang
2014
Tujuan
Mahasiswa mampu merepresentasikan masalah dalam ruang keadaan dan gmelakukan memahami berbagai metode pencarian.
Pokok BahasanPokok BahasanPokok BahasanPokok Bahasan
Mendefinisikan Masalah dalam Ruang KeadaanRepresentasi Ruang KeadaanRepresentasi Ruang KeadaanMetode Pencarian & Pelacakan
Artificial IntelligenceArtificial Intelligence
ARTIFICIAL INTELLIGENCEARTIFICIAL INTELLIGENCE
Knowledge Inference
Input:MASALAH
Output:SOLUSI
Knowledge Base
InferenceEngine
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 seseorangcatur 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 yangsuatu ruang yang berisi semua keadaan yang mungkin
Penyelesaian masalah secara umum
Mendefinisikan suatu ruang keadaan;Mendefinisikan suatu ruang keadaan;Menetapkan satu atau lebih keadaan awal;Menetapkan satu atau lebih tujuan;Menetapkan satu atau lebih tujuan;Menetapkan kumpulan aturan.
Lintasan dari M ke T:M-A-B-C-E-TM-A-B-C-E-H-TM D C E TM-D-C-E-TM-D-C-E-H-T
Lintasan yang menemui jalan buntu (tidakLintasan yang menemui jalan buntu (tidak sampai ke T):
M-A-B-C-E-F-GM A B C E F GM-A-B-C-E-I-JM-D-C-E-F-GM-D-C-E-I-JM-D-I-J
Pohon PelacakanM
A D
Level-0
Level-1A
B CI
e e
Level-2
C E
E F HI
J Level-3Buntu
E F THI
F THI JG T
Level-4
Level-5Tujuan
JG T Level-6TujuanTujuan
Tujuan
BuntuBuntu
BuntuBuntuTujuan
Contoh: Masalah Teko AirAda 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 b ttersebut. Ada sebuah pompa air yang akan digunakan untuk mengisikan air pada kedua teko tersebut. Permasalahannya: Bagaimanakah kita dapat mengisikan tepat 2 galon y g p g p gair ke dalam teko yang berkapasitas 4 galon?
3 galon(t k B)
4 galon(teko A)
Airtak terbatas
(teko B)
Penyelesaian …Identifikasi ruang keadaan:
Permasalahan ini dapat direpresentasikan dengan 2Permasalahan 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∈{0,1,2,3}.y { , , , }
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.
(0,0) (1,0) (2,0) (3,0) (4,0)
Keadaan Awal Tujuan
( , )
(0,1)
( , )
(1,1)
( , )
(2,1)
( , )
(3,1)
( , )
(4,1)( , )
(0,2)
( , )
(1,2)
( , )
(2,2)
( , )
(3,2)
( , )
(4,2)(0,2)
(0,3)
(1,2)
(1,3)
(2,2)
(2,3)
(3,2)
(3,3)
(4,2)
(4,3)(0,3) (1,3) (2,3) (3,3) (4,3)
Aturan-aturan
Aturan ke- Jika Maka
1. (x,y) (4,y)x < 4 Isi teko A.
2. (x,y)y < 3
(x,3)Isi teko B.
3 (x y) (x d y)3. (x,y)x > 0
(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)+ ≥ 4 d > 0
(4,y-(4-x))T k i d i t k B k t k A x+y ≥ 4 dan y > 0 Tuangkan air dari teko B ke teko 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 x+y ≥ 3 dan x 0 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 Ateko A.
10. (x,y)x+y ≤ 3 dan x > 0
(0,x+y)Tuangkan seluruh air dari teko A ke teko B.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 ruang keadaan dengan pohon p g g ppelacakan.
(0,0)
(4,0) (0,3)
(0,0) (1,3)(4,3) (0,0) (3,0)(4,3)
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 petani akan menyeberangkan seekor g p y gkambing, seekor serigala, dan sayur-sayuran dengan sebuah boat yang melalui sungai. B h bi i dBoat hanya bisa memuat petani 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
Permasalahan ini dapat dilambangkan dengan (J l hK bi J l hS i l J l hS(JumlahKambing, JumlahSerigala, JumlahSayuran, JumlahBoat). Sebagai contoh: Daerah asal (0,1,1,1) berarti pada daerah asal tidak ada kambing ada serigala ada sayuran danasal tidak ada kambing, ada serigala, ada sayuran, dan ada boat.
Keadaan AwalDaerah asal: (1 1 1 1)Daerah asal: (1,1,1,1)Daerah seberang: (0,0,0,0)
TujuanD h l (0 0 0 0)Daerah asal: (0,0,0,0)Daerah seberang: (1,1,1,1)
Aturan-aturan
Aturan Aturanke- Aturan
1. Kambing menyeberang
b2. Sayuran menyeberang
3. Serigala menyeberang
4 K bi k b li4. Kambing kembali
5. Sayuran kembali
6 Serigala kembali6. Serigala kembali
7. Boat kembali
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) (0 1 0 0) 2(1,0,1,1) (0,1,0,0) 2
(1,0,0,0) (0,1,1,1) 7
(1 0 0 1) (0 1 1 0) 1(1,0,0,1) (0,1,1,0) 1
(0,0,0,0) (1,1,1,1) solusi
Metode Pencarian & pelacakanPencarian Buta (Blind Search)
Breadth First SearchBreadth-First SearchDepth-First Search
Pencarian Terbimbing (Heuristics Search)Pencarian Terbimbing (Heuristics Search)Generate & TestHill Cli biHill ClimbingBest-First SearchTabu SearchTabu SearchSimulated Annealing
Breadth-First Search
Pada metode Breadth-First Search, semua nodePada metode 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 solusihingga ditemukannya solusi
Keuntungan:Tidak akan menemui jalan buntu.Jika ada satu solusi, maka breadth-first search
k k D jik d l bih d i takan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahan:Kelemahan:Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satukarena menyimpan semua node dalam satu pohon.Membutuhkan waktu yang cukup lama, karena y g pakan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)
Depth-First Search
Pada Depth-First Search, proses pencarianPada Depth 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
KeuntunganKeuntunganMembutuhkan 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 labihmenemukan solusi tanpa harus menguji labih banyak lagi dalam ruang keadaan.
KelemahanMemungkinkan tidak ditemukannya tujuan yang diharapkan.H k d tk 1 l i d tiHanya akan mendapatkan 1 solusi pada setiap pencarian.
OperatorUbin kosong geser ke kanang gUbin kosong geser ke kiriUbin kosong geser ke atasUbin kosong geser ke bawah
Langkah awal
Tujuan
1 2 3
8 4
7 6 5
1 2 3
7 4
6 5
8
7 6 5 6 5
kananataskiri
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 8 56 5 6 5 6 8 5
Nilai heuristik …Nilai heuristik …
Untuk jumlah ubin yang menempati posisi yang benar jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik)diharapkan (lebih baik)
1 2 3 1 2 3
Tujuan
1 2 3
8 4
7 6 5
1 2 3
7 4
6 5
8
ataskiri
1 2 31 2 3 1 2 3
kananataskiri
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 8 5h=6h=6 h=4h=4 h=h=55
Untuk jumlah ubin yang menempati posisi yang l h j l h l bih k il d l hsalah jumlah yang lebih kecil adalah yang
diharapkan (lebih baik).
1 2 3
8 4
1 2 3
7 48
Tujuan
7 6 5 6 5
kananataskiri
1 2 3
7 48
1 2 3
7 48
1 2 3
7 4
6 5 6 5 6 8 5h=2h=2 h=4h=4 h=3h=3
Menghitung total gerakan yang diperlukan untuk i j j l h l bih k il d l hmencapai tujuan jumlah yang lebih kecil adalah
yang diharapkan (lebih baik).
1 2 3
8 4
1 2 3
7 48
Tujuan
7 6 5 6 5
kananataskiri
1 2 3
7 48
1 2 3
7 48
1 2 3
7 4
6 5 6 5 6 8 5h=2h=2 h=4h=4 h=4h=4
Generate & TestPada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awalyaitu bergerak ke belakang menuju pada suatu keadaan awal.Algoritma:
1. Bangkitkan suatu kemungkinan solusi (membangkitkan t titik t t t t li t t t t d i k dsuatu titik tertentu atau lintasan tertentu dari keadaan
awal).2. Uji untuk melihat apakah node tersebut benar-benar
k l i d b di k dmerupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.Jik l i dit k k l Jik tid k l i k b li3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
Kasus: Kasus: Traveling Salesman ProblemTraveling Salesman Problem (TSP).(TSP).
Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungiterpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali.
A B8
3 4
D C
7 53
D C6
Generate & test akan membangkitkan semua solusi yang mungkin:y g g
A – B – C – DA – B – D – CA – C – B – DA – C – B – DA – C – D – B, dll
A B C DA B C D
B C D
C D B D C B
D C D B B C
Alur pencarian
Pencarian ke- Lintasan Panjang
Lintasan Lintasan terpilihPanjang 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 1212. BDCA 13 ACBD 12
Pencarian Li t Panjang Li t t ilihPanjang Li t Pencarian
ke- Lintasan Panjang Lintasan Lintasan terpilih Lintasan
terpilih
13. CABD 15 ACBD 12
14 CADB 14 ACBD 1214. 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 t DBCA 1222. 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 i i d l h l b ki kini adalah perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang cukup besar d l idalam pencariannya.
Pendakian Bukit (Hill Climbing)
Metode ini hampir sama dengan metode p gpembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristikheuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur
tpengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yangmenunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.
Simple Hill ClimbingAlgoritma
Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan,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, atauKerjakan 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 p y g p g ; g pmendapatkan 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.j
Kasus: TSP
Operator Tukar kota ke-i dengan kota ke-j (Tk i,j)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 4Tk 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:
)!2N(!2!N− )(
ABCD
Tk 1,2 Tk 1,3
(19)
BACD ACBD ABDC DBCA
Tk 2,3 Tk 3,4 Tk 4,1
ABDC CBAD
Tk 2,4
(17)Tk 1,2
Tk 2,3 Tk 3,4 Tk 4,1 Tk 2,4 Tk 1,3(15)ABCD BCAD BADC DACB
, ,
BDCA CABD
, ,(15)
Tk 1,2 Tk 2,3 Tk 4,1 Tk 2,4 Tk 1,3Tk 3,4(20) (18) (19) (14)
CBAD BACD BCDA DCAB BDAC ACBD(20) (18) (19) (14)
DBAC BADC BDCA CDAB
Tk 1,2 Tk 3,4 Tk 4,1
BCAD ADBC
Tk 2,4 Tk 1,3(15)
Tk 2,3(21) (13)
DBAC BADC BDCA CDAB BCAD ADBC
DBCA BCDA BDAC BDAC
Tk 1,2 Tk 3,4 Tk 4,1
CBAD ADCB
Tk 2,4(12)
Tk 2,3 Tk 1,3
BDCA DCBA DBAC ACDB DACB CBDA
Tk 1,2 Tk 2,3 Tk 4,1 Tk 2,4 Tk 1,3Tk 3,4(19) (15) (13) (16)(15)
Apabila hanya digunakan 4 operator saja:
ABCD(19)
BACD ACBD ABDC DBCA
Tk 1,2
Tk 2,3 Tk 3,4 Tk 4,1
(17)
ABCD BCAD BADC DACB
Tk 1,2 Tk 2,3Tk 3,4
Tk 4,1(15)
ABCD BCAD BADC DACB
Tk 1,2 Tk 2,3Tk 3,4
Tk 4,1(20) (17) (18) (17)
CBAD BACD BCDA DCAB
,(20) (17) (18) (17)
Pada simple hill climbing ada 3 masalahPada simple hill climbing, ada 3 masalah yang mungkin:
Algoritma akan berhenti kalau mencapai nilaiAlgoritma akan berhenti kalau mencapai nilai optimum local.Urutan penggunaan operator akan sangat p gg p gberprngaruh 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 heuristikGerakan selanjutnya dicari berdasarkan nilai heuristik terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.
AlgoritmaMulai 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:
G k t t b t d b t k k d bGunakan 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 sekarangsekarang, ubah node SUCC menjadi keadaan sekarang.
Kasus: TSP
ABCD
Tk 1 2 Tk 1 3
(19)
ACBD ABDC DBCA
Tk 1,2Tk 3,4
Tk 4,1
ADCB CBAD
Tk 2,4Tk 1,3
(17)Tk 2,3
(12) (18) (12) (18) (20)BACD
CABD ABCD ACDB DCBA
Tk 2,3Tk 3,4
Tk 4,1
ADBC BCAD
Tk 2,4 Tk 1,3(15) (13)
Tk 1,2
(19) (16) (15)(19)CABD ABCD ACDB DCBA ADBC BCAD
Pada steepest-ascent hill climbing ini ada 3Pada steepest ascent hill climbing ini, ada 3 masalah yang mungkin, yaitu:
Local optimum: keadaan semua tetangga lebihLocal 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 k tid k t k k 2karena ketidakmampuan untuk menggunakan 2 operator sekaligus.
Best-First Search
Metode best-first search ini merupakan kombinasi dari metode depth-first search dan metode breadth-first search dengandepth 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 d pe bo e a u tu e ba e ode pada e e ya g ebrendah 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 burukheuristik 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;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 OPENA [A]
[D,C,B]A
3 5 7
[C,F,B,E]
B C D
A
3 5B C D
E F
2 4
[G,F,B,E,H]A
B C D
5 1 2 4
3B C D
E FG H
Tabu SearchTabu Search merupakan suatu metode optimasi yang menggunakan short-term memory untuk menjaga agar proses pencarian tidak terjebak pada nilai optimum lokalpencarian 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 akanSelama 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 p p ,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 y g jmerupakan 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)BestSoFar = FCost(S).BestMove = S.Kerjakan dari i=1 sampai (n-1):j p ( )
Kerjakan dari j=i sampai n:L = Tukar(S[i] S[j])L = Tukar(S[i],S[j]).Cost = FCost(L).Jika (L ∉TabuList) atau (Cost < GlobalMin), kerjakan:
Jika (Cost < BestSoFar), kerjakanBestSoFar = Cost.BestMove = L.
S = BestMove.Tambahkan S ke TabuList.Jik B tS F Gl b lMi k j kJika BestSoFar < GlobalMin, kerjakan:
GlobalMin = BestSoFar.Best = BestMove.
Contoh …
Simulated AnnealingIde dasar simulated annealing terbentuk dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) dalamAnnealing (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 permutasimisalkan perubahan gerakan dengan menggunakan permutasi pada masalah Travelling Salesman Problem.Pada simulated annealing, ada 3 parameter yang sangat menentukan yaitu: tetangga gain temperatur pembangkitanmenentukan, yaitu: tetangga, gain, temperatur, pembangkitan bilangan random.
AlgoritmaEvaluasi keadaan awal. Jika keadaan awal merupakan tujuan, maka pencarian berhasil dan KELUAR. Jika tidak demikian, lanjutkan denganpencarian 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 baruKerjakan 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 il i k il i k d b∆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:
Langkah ini biasanya dikerjakan dengan membangkitkan suatu bilangan
T/Ee'p ∆−=
g y j g g grandom 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 adalah jawaban yang dimaksudkan.
Secara umum ada 3 hal pokok pada p psimulated 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 g g ghill climbing. Biasanya temperatur awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acakdipilih secara 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): real;Function PjgJalur(L,X,Y): real;Panjang = 0;For i=1 to (NC-1) doFor 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;LMax 0;For i=1 to MTemp do
LA = ambil jalur sembarangLen = PjgJalur(LA)If Len > LMax then LMax = Len
T0 2*LMT0 = 2*LMax
Function JalurBaru(L): arrayNC;Bangkitkan 2 bilangan random N1 dan N2 antara 1 sampai NC dengan N1 < N2Depan = L(1) sampai L(N1 1);Depan = L(1) sampai L(N1-1);Tengah = L(N1) sampai L(N2);Belakang = L(N2+1) sampai L(NC);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]
elseSementara = [Depan Belakang]; dengan M elemen.Bangkitkan bilangan random r dengan nilai antara 1 sampai M.DepanBaru = Sementara(1..r).p ( )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;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;Sukses = 1;While Sukses > 0
Sukses = 0;Mi Pj J l Pj J l (L)MinPjgJalur = PjgJalur(L);For i=1 to MaxIterasi do
Jalur = JalurBaru(L);Pj Pj J l (J l )Pjg = PjgJalur(Jalur);
If Pjg < MinPjgJalur thenMi Pj J l PjMinPjgJalur = Pjg;Lbaru = Jalur;Sukses = Sukses +1;If MinPjgJalur < PjgJalurTerpendek then
PjgJalurTerpendek = MinPjgJalur;JalurTerpendek = Lbaru;JalurTerpendek Lbaru;
If Sukses = MaxSukses then BREAK;else
Bangkitkan bilangan random r;Bangkitkan bilangan random r;If r < e-(Pjg-MinPjgJalur)/T then Lbaru=Jalur;
L = Lbaru;T = decT * T;
Kasus: TSPOperator 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.p pBangkitkan 2 bilangan random antara 1 sampai NC, misalkan kedua bilangan itu adalah N1 dan N2 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, apabila r < 0,5; maka:DepanBaru = Depan.TengahBaru = Tengah dengan urutan dibalik.B l k B B l kBelakangBaru = 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 MBangkitkan bilangan random r dengan nilai antara 1 sampai M.DepanBaru = Sementara(1:r).TengahBaru = Tengah.BelakangBaru = Sementara(r+1:M).Lbaru = [DepanBaru TengahBaru BelakangBaru]Lbaru [DepanBaru TengahBaru BelakangBaru]
Misalkan jalur yang ada adalah:L = [4 3 6 9 11 2 5 1 7 8 12 10] NC=12L = [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 = [4 3 6].Tengah = [9 11 2 5 1 7 8].Belakang = [12 10].
Bangkitkan bilangan random r, apabila r < 0,5; maka:DepanBaru = [4 3 6].DepanBaru [4 3 6].TengahBaru = [8 7 1 5 2 11 9].BelakangBaru = [12 10].Lbaru = [4 3 6 8 7 1 5 2 11 9 12 10]
Jika r ≥ 0 5; maka kerjakan:Jika r ≥ 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 Contoh …