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

[AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010

Variasi Teknik Pencarian

1. Pencarian tanpa informasi (uninformed search)

2. Pencarian dengan informasi (informed search)

3. Pencarian dengan optimasi (local search & optimization)

4. Pencarian dengan informasi status lawan (adversarial search)

5. 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

• 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

Pencarian dengan Optimasi (local search & optimization)

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

5

Sumber: [AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010

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

7

1 2 3 4 5 6 7 8

a

b

c

d

e

f

g

h

h = 1 pasangan bidak ratu yang dapat saling menyerang Yaitu 1a-8h

Contoh 8-queens dengan Hill-Climbing

8

1 2 3 4 5 6 7 8

a

b

c

d

e

f

g

h

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

bidak catur dirubah

Misal 1: posisi 1e dirubah ke 1d maka

state 1d 2f 3g 4d 5e 6f 7g 8f; h=15

Misal 2: posisi 2f dirubah ke 2e maka

state 1e 2e 3g 4d 5e 6f 7g 8f; h=14

Nilai h terkecil adalah h=12, jadi

Kondisi state dapat diubah ke:

1e 2a 3g 4d 5e 6f 7g 8f … … … …

1e 2f 3g 4d 5e 6f 7h 8f (8 pilihan)

Aturan Hill-Climbing, pilihan state selanjutnya nilai h <= 12

Misal state current = 1e 2a 3g 4d 5e 6f 7g 8f

Contoh 8-queens dengan Hill-Climbing

9

1 2 3 4 5 6 7 8

a

b

c

d

e

f

g

h

state current = 1e 2a 3g 4d 5e 6f 7g 8f

Nilai h(current)= 12 pasangan saling menyerang

Hitung semua nilai h jika posisi satu

bidak catur dirubah

Nilai h terkecil adalah h=??, jadi

Kondisi state dapat diubah ke:

… … … … (?? pilihan)

Aturan Hill-Climbing, pilihan state

selanjutnya nilai h <= 12

Proses berhenti saat nilai h(semua neighbor)> h(current) dan

return state current sebagai solusi

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 pemasangan dengan jarak terpendek

• Nilai h = total jarak

11

M C W E S

M 0 .9 .6 .8 .7

C 0 1.3 1.5 1.3

W 0 .2 .3

E 0 .2

S 0

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 (C -> E -> M -> S -> W) = 3.3 (S -> E -> C -> M -> W) = 3.2 (W -> E -> C -> S -> M) = 3.7 (M -> C -> E -> S -> W) = 2.9 (M -> S -> C -> E -> W) = 3.7 (M -> W -> C -> S -> E) = 3.4 (M -> E -> S -> C -> W) = 3.6 (M -> E -> W -> S -> C) = 2.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

13

Jalur terpendek dari Arad ke Bucharest adalah … ??? Pendekatan solusi: teknik pencarian

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. Depth-First Search (DFS): path cost = 733, expanded = 10 nodes

b. Breadth-First Search (BFS): path cost = 450, expanded = 5 nodes

c. Uniform Cost Search (UCS): : path cost = 418, expanded = 12 nodes

2. Pencarian dengan informasi (informed search)

a. Greedy Best First (greedy): path cost = 450, expanded = 3 nodes

b. 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

21 Sumber: [AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010

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))

22

Sumber: [AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010

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

25

Diambil dari: Nysret Musliu, Materi Kuliah SS 2012 Problem Solving and Search in Artificial Intelligence, Technische Universität Wien, Austria 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 1 0 0 | 0 1 1 1 (a|b)

• Parent 2 1 1 1 | 1 0 0 0 (c|d)

• Offspring 1 1 0 0 1 0 0 0 (hasil ad)

• Offspring 2 1 1 1 0 1 1 1 (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

• One-point

• Two-point

• Uniform

• Arithmetic

• Heuristic

MUTASI

• Flip Bit

• Boundary

• Non-Uniform

• Uniform

• Gaussian

30

Parameter Penting Algoritma Genetik

• Probabilitas Mutasi

• Probabilitas Crossover

• Ukuran populasi

31