[AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010
KI091322 Kecerdasan Buatan Materi 5: Pencarian dengan Optimasi (Local Search & Optimization ) Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2012 Pengembangan Bahan Ajar sebagai Pendukung Student Centered-Learning (SCL) melalui e-Learning : Share ITS
Variasi Teknik Pencarian 1. 2. 3. 4. 5.
Pencarian tanpa informasi (uninformed search) Pencarian dengan informasi (informed search) Pencarian dengan optimasi (local search & optimization) Pencarian dengan informasi status lawan (adversarial search) Pencarian dengan batasan kondisi (constraint satisfaction problems)
Teknik 1 dan Teknik 2 mencari jalur (path) status solusi dari initial state sampai goal state. Teknik 3 hanya membutuhkan state yang memenuhi kondisi final. 2
Pencarian dengan Optimasi (local search & optimization) • hanya butuh state yang memenuhi kondisi final – Solusi problem 8-queen = posisi 8 bidak dengan jumlah bidak tidak saling menyerang minimal • Solusi adalah konfigurasi akhir 8 bidak • Tidak perlu tahu urutan bidak yang diletakkan di papan
– Berbeda dengan problem pencarian jarak terpendek yang membutuhkan urutan jalur dari kota awal ke kota akhir • Path: initial state … state antara … goal state 3
Pencarian dengan Optimasi (local search & optimization) • Pilih initial state dan mulai mencari solusi dari state terdekat • Algoritma untuk pencarian dengan optimasi: – Hill-Climbing Search • Pemilihan state berdasarkan nilai objektifnya
– Genetic Algorithm • Pemilihan state berdasarkan aturan seleksi alam yang diterapkan pada state collection (sering disebut sebagai populasi) 4
Algoritma Hill-Climbing Search function Hill-Climbing(problem) returns a state that is a local maximum current <- Make-Node(problem.Initial-State) loop do neighbor <- a highest-valued successor of current if neighbor.Value <= current.Value then return current.State current <- neighbor
Hill-Climbing Search disebut juga Greedy Local Search -> ambil state terdekat yang terlihat baik saat itu Sumber: [AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010 5
Persiapan untuk Hill-Climbing Search • Cara untuk menentukan initial state – Random?? State dengan nilai objektif terkecil??
• Fungsi Objektif untuk hitung nilai state • Problem: 8-queens – Pilih initial state • Posisi bidak random dari 1-8; posisi teratas
– Fungsi Objektif • Heuristic cost function h = jumlah pasangan bidak ratu yang dapat saling menyerang 6
Contoh Heuristic Cost Function h untuk Problem 8-queens 1
2
3
4
5
6
7
8 a b c
h = 1 pasangan bidak ratu yang dapat saling menyerang
d e
Yaitu 1a-8h
f g h
7
Contoh 8-queens dengan Hill-Climbing Secara random, state current = 1e 2f 3g 4d 5e 6f 7g 8f Nilai h(current)=17 pasangan saling menyerang 1e-2f; 1e-3g; 1e-5e; 2f-3g; 2f-4d; 2f-6f; 2f-8f; 3g-5e; 3g-7g; 4d-5e; 4d-6f; 4d-7g; 5e-6f; 5e-7g; 6f-7g; 6f-8f; 7g-8f; Hitung semua nilai h jika posisi satu 1 2 3 4 5 6 7 8 bidak catur dirubah a Misal 1: posisi 1e dirubah ke 1d maka b state 1d 2f 3g 4d 5e 6f 7g 8f; h=15 c Misal 2: posisi 2f dirubah ke 2e maka d state 1e 2e 3g 4d 5e 6f 7g 8f; h=14 e Nilai h terkecil adalah h=12, jadi f Kondisi state dapat diubah ke: g 1e 2a 3g 4d 5e 6f 7g 8f … … … … h 1e 2f 3g 4d 5e 6f 7h 8f (8 pilihan) Aturan Hill-Climbing, pilihan state selanjutnya nilai h <= 12 8 Misal state current = 1e 2a 3g 4d 5e 6f 7g 8f
Contoh 8-queens dengan Hill-Climbing state current = 1e 2a 3g 4d 5e 6f 7g 8f Nilai h(current)= 12 pasangan saling menyerang 1
2
3
4
5
6
7
8
a b c d e f
Hitung semua nilai h jika posisi satu bidak catur dirubah
Nilai h terkecil adalah h=??, jadi Kondisi state dapat diubah ke: … … … … (?? pilihan)
g Aturan Hill-Climbing, pilihan state h selanjutnya nilai h <= 12
Proses berhenti saat nilai h(semua neighbor)> h(current) dan return state current sebagai solusi 9
Kekurangan Hill-Climbing • Terjebak dalam kondisi local maxima – Seolah-olah tidak ada pilihan, nilai terkecil h(neighbor) > h(current) – Namun jika state terpilih saat current-1 adalah state lain, maka mungkin ditemukan nilai terkecil h(neighbor) <= h(current)
• Alternatif cara untuk hindari local maxima – Pilih state dari neighbor dengan hitung nilai h(current+1) • Hitung h(neighbor) dan h(current=neighbor) • Pilih current baru dari neighbor dengan h(current=neighbor) <= h(current) 10
Contoh Hill-Climbing untuk Cari Jalur • Pemasangan poster Gemastik dalam ITS akan dilakukan di Jurusan Matematika(M), T.Computer(C), Warung Gebang(W), T.Elektro(E), Statistika (S) • Jarak antar lokasi sbb dalam km • Cari jalur M C W E S pemasangan dengan M 0 .9 .6 .8 .7 jarak terpendek C 0 1.3 1.5 1.3 W 0 .2 .3 • Nilai h = total jarak E S
0
.2 0 11
Contoh Hill-Climbing untuk Cari Jalur • Initial state = (M -> E -> C -> S -> W) secara random • Nilai h = .8 + 1.5 + 1.3 + .3 = 3.9 • Contoh proses swap: (A->B->C) – Tukar A-B didapat (B->A->C) – Tukar A-C didapat (C->B->A) – Tukar B-C didapat (A->C->B)
• Neighbor terbentuk dengan merubah (swap) 2 lokasi (E -> M -> C -> S -> W) = 3.3 (S -> E -> C -> M -> W) = 3.2 (M -> C -> E -> S -> W) = 2.9 (M -> W -> C -> S -> E) = 3.4 (M -> E -> W -> S -> C) = 2.6
(C -> E -> M -> S -> W) = 3.3 (W -> E -> C -> S -> M) = 3.7 (M -> S -> C -> E -> W) = 3.7 (M -> E -> S -> C -> W) = 3.6 (M -> E -> C -> W -> S) = 3.9
• Hill-Climbing akan memilih h=2.6 •
untuk current state (M -> E -> W -> S -> C)
• Proses swap dilakukan 1x lagi, dan solusi optimal didapat •
(S->E->W->M->C) dengan h=1.9
12
Problem Romanian
Jalur terpendek dari Arad ke Bucharest adalah … ??? Pendekatan solusi: teknik pencarian
13
AIMA untuk Problem Romanian
14
AIMA untuk Problem Romanian
15
AIMA untuk Problem Romanian
16
AIMA untuk Problem Romanian
17
Perbandingan Algoritma Pencarian 1. Pencarian tanpa informasi (uninformed search) a. b. c.
Depth-First Search (DFS): path cost = 733, expanded = 10 nodes Breadth-First Search (BFS): path cost = 450, expanded = 5 nodes Uniform Cost Search (UCS): : path cost = 418, expanded = 12 nodes
2. Pencarian dengan informasi (informed search) a. b.
Greedy Best First (greedy): path cost = 450, expanded = 3 nodes A* (baca: A-star): path cost = 418, expanded = 5 nodes
3. Pencarian dengan optimasi (local search & optimization) Hill-Climbing Search (hillclimb): path cost = 450, expanded = 4 nodes
• Rekomendasi pencarian dengan informasi A* memberikan hasil yang bagus • Pencarian dengan optimasi memberikan hasil yang mendekati A* 18
Algoritma Genetik (Genetic Algorithm, GA) • Rekapitulasi Materi tentang pemilihan state berikut – Hill-Climbing Search: berdasarkan nilai objektifnya – Genetic Algorithm: berdasarkan aturan seleksi alam yang diterapkan pada state collection (sering disebut sebagai populasi)
• Pada GA – Inisialisasi state diambil dari populasi (kumpulan sejumlah n state) – Kandidat state berikut adalah populasi baru berisi state baru hasil kombinasi state pada populasi sekarang – Pemilihan state dari populasi baru berdasarkan nilai tertinggi hasil perhitungan fitness function 19
Tahapan dalam Algoritma Genetika • Pengkodean state atau disebut kromosom (encoding technique) • Proses inisialisasi pembentukan state atau kromosom awal (initialization procedure) • Fungsi evaluasi nilai kromosom (fitness function) • Penentuan kromosom pilihan sebagai parent (selection) • Operator genetika untuk kombinasi kromosom baru (mutation) 20
Algoritma Genetika function Genetic-Algorithm(population, Fitness-Fn) returns an individual inputs: population, a set of individuals Fitness-Fn, a function that measures the fitness of an individual repeat new_population <- empty set for i=1 to Size(population) do x <- Random-Selection(population, Fitness-Fn) y <- Random-Selection(population, Fitness-Fn) child <- Reproduce(x, y) if (small random probability) then child <- Mutate(child) add child to new_population population <- new_population until some individual is fit enough, or enough time has elapsed return the best individual in population, according to Fitness-Fn Sumber: [AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010
21
Algoritma Genetika function Reproduce(x, y) returns an individual inputs: x, y, parent individuals n <- Length(x); c <- random number from 1 to n return Append(Substring(x, 1, c), Substring(y, c+1, n))
Sumber: [AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010 22
Pengkodean Kromosom (encoding) • Representasi state menjadi kromosom • Contoh problem pencarian rute jalan (travelling salesman problem) untuk 4 kota – Satu state atau satu rute 12341 berarti kunjungan dari kota 1->2->3->4->diakhiri ke->1 • Kromosom tertulis 1234 (permutation encoding)
• Pencarian koefisien yang sesuai untuk persamaan y=ax5+bx4+cx3+dx2+ex+f (value encoding) – Contoh kromosom [0, 0, 0, 2, 3, 5] berarti persamaan menjadi ý = 0x5 + 0x4 + 0x3 + 2x2 +3x + 5 23
Pengkodean Kromosom (encoding) • Teknik sebelumnya – permutation encoding & value encoding • Binary encoding – Pengkodean kromosom terdiri dari angka 1 dan 0 – Problem Knapsack -> optimasi pemilihan benda untuk dimasukkan ke wadah dengan keterbatasan ruang • Berat dan nilai benda menjadi prioritas pemilihan • Misal 4 benda: A(3kg, 6rb), B(2kg, 5rb), C(5kg, 9rb), D(4 kg, 8rb)
• Contoh: kromosom 0101 berarti wadah berisi B & D
24
Contoh Problem Persamaan • Pencarian koefisien yang sesuai untuk persamaan y = ax5 + bx4 + cx3 + dx2 +ex + f – Contoh kromosom [0, 0, 0, 2, 3, 5] berarti persamaan menjadi ý = 0x5 + 0x4 + 0x3 + 2x2 +3x + 5 • Fungsi Evaluasi (fitness function) – Cek dengan contoh data (x, y), hitung ý = ax5 + bx4 + cx3 + dx2 +ex + f • Hitung jumlah (y – ý)2 yang disebut sebagai Sum Squared Error (SSE) untuk semua x • Jika nilai jumlah semakin besar menunjukkan kombinasi koefisien pada kromosom tidak tepat Diambil dari: Nysret Musliu, Materi Kuliah SS 2012 Problem Solving and Search in Artificial Intelligence, Technische Universität Wien, Austria 25 url: http://www.dbai.tuwien.ac.at/staff/musliu/ProblemSolvingAI/
Contoh Problem Persamaan • Untuk kromosom [0, 0, 0, 2, 3, 5] dan data (1, 12) (2, 22): – ý = 0x5 + 0x4 + 0x3 + 2x2 +3x + 5 = 2 + 3 + 5 = 10 jika x =1 – ý = 0x5 + 0x4 + 0x3 + 2x2 +3x + 5 = 8 + 6 + 5 = 19 jika x =2 – SSE = (12 – 10)2 + (22 – 19)2 = 22 + 32 = 13 • Untuk kromosom [0, 0, 0, 2, 3, 6] dan data (1, 12) (2, 22): – ý = 0x5 + 0x4 + 0x3 + 2x2 +3x + 6 = 2 + 3 + 6 = 11 jika x =1 – ý = 0x5 + 0x4 + 0x3 + 2x2 +3x + 6 = 8 + 6 + 6 = 20 jika x =2 – SSE = (12 – 11)2 + (22 – 20)2 = 12 + 22 = 5
• Jadi untuk contoh data (1, 12) dan (2, 22) maka kromosom dengan nilai error (hasil fitness function) yang lebih baik adalah [0, 0, 0, 2, 3, 6] – Kromosom tersebut dipilih untuk masuk dalam populasi berikutnya
26
Langkah-Langkah Algoritma Genetik untuk Problem Persamaan • Buat populasi berisi 100 kromosom secara random – @kromosom = array 6 angka, misal: [0, 0, 0, 2, 3, 5]
• Ulangi proses berikut sampai 500 kali (atau n kali): – Hitung SSE dari 100 kromosom dengan contoh data tersedia – Ambil 10 kromosom dengan nilai SSE terkecil – Dari setiap kromosom, buat kromosom baru dengan aturan sbb • Pilih satu angka secara random dari 6 angka dalam array • Ambil angka konstanta secara random antara 0.0-2.0 • Kalikan konstanta dengan angka pilihan
• Setelah n kali perulangan, ambil kromosom terbaik sebagai jawaban koefisien dari persamaan – Kromosom dengan nilai SSE terkecil 27
Metode Seleksi • Roulette-wheel • Selection • Stochastic universal • sampling • Local selection • • Truncation selection • • Tournament Selection • Group Selection
Rank-based Fitness Selection Steady-State Selection Boltzmann Selection Elitism
28
Operator Genetika • Crossover – Mengkombinasikan sebagian kromosom parent 1 dengan parent 2 • • • •
Parent 1 Parent 2 Offspring 1 Offspring 2
100|0111 111|1000 1001000 1110111
(a|b) (c|d) (hasil ad) (hasil cb)
• Mutasi – Kromosom hasil perubahan 1 gen / karakter • 1 0 0 0 1 1 1 menjadi 1 1 0 0 1 1 1 (perubahan di bit 2) 29
Variasi Crossover & Variasi Mutasi CROSSOVER
MUTASI
• • • • •
• • • • •
One-point Two-point Uniform Arithmetic Heuristic
Flip Bit Boundary Non-Uniform Uniform Gaussian
30
Parameter Penting Algoritma Genetik • Probabilitas Mutasi • Probabilitas Crossover • Ukuran populasi
31
