Algoritma Evolusi
Evolution Strategies (ES) Imam Cholissodin |
[email protected]
Pokok Bahasan 1. 2. 3. 4. 5. 6.
Struktur Dasar Evolution Strategies (ES) Siklus ES (µ, λ) Siklus ES (µ/r + λ) Studi Kasus ES (µ + λ) ES untuk Representasi Permutasi Tugas
Pengantar Teknik optimasi evolution strategies (ES) dicetuskan sejak awal tahun 1960-an dan kemudian dikembangkan lebih lanjut pada tahun 1970-an oleh Ingo Rechenberg, Hans-Paul Schwefel, dan rekan-rekannya di Technical University of Berlin (TUB) (Beyer & Schwefel 2002). Seperti halnya GAs, ES telah diaplikasikan dalam berbagai bidang, misalnya penjadwalan pemrosesan sinyal digital pada system multiprocessor (Greenwood, G W, Gupta & McSweeney 1994), pemrosesan citra dan computer vision (Louchet 2000), optimasi pelepasan airbag secara otomatis pada mobil (Ostertag, Nock & Kiencke 1995), dan penjadwalan tugas pada real-time distributed computing systems (Greenwood, G. W., Lang & Hurley 1995). ES juga cukup efektif dikombinasikan/dihibridisasi dengan algoritma lain seperti particle swarm optimization untuk penjadwalan staff (Nissen & Günther 2009).
Pengantar Ciri utama evolution strategies (ES) adalah penggunaan vektor bilangan pecahan (real-vector) sebagai representasi solusi. Berbeda dengan GAs yang menggunakan crossover sebagai operator reproduksi utama dan mutasi sebagai operator penunjang, ES lebih bertumpu pada operator mutasi. Mekanisme self-adaptation digunakan untuk mengontrol perubahan nilai parameter pencarian. GAs dan ES bisa digunakan untuk menyelesaikan permasalahan yang sama. Tetapi mana yang terbaik di antara kedua metode tersebut sangat tergantung pada permasalahan yang dihadapi.
Struktur Dasar ES
Beberapa notasi digunakan oleh ES : o µ (miu) menyatakan ukuran populasi (sama seperti popSize pada
o
GAs). l (lambda) menyatakan banyaknya offspring yang dihasilkan pada proses reproduksi (sama seperti crossover rate dan mutation rate pada GAs). Beberapa penelitian menyarankan besarnya nilai l sebesar 7 µ.
Apabila P(t) dan C(t) merupakan populasi (parents) dan offspring pada generasi ke-t, maka siklus ES dideskripsikan sebagai berikut: procedure EvolutionStrategies begin t = 0 inisialisasi P(t): generate µ individu while (bukan kondisi berhenti) do rekombinasi : produksi C(t) sebanyak l dari P(t) mutasi C(t) seleksi P(t+1) dari P(t) dan C(t) t = t + 1 end while end
Struktur Dasar ES
Perhatikan bahwa siklus ES serupa dengan siklus algoritma genetika (GAs). Perbedaan nyata ES dan GAs adalah pada operator yang digunakan. Perbedaan lain, mutasi pada GAs digunakan untuk menghasilkan individu baru (offspring) sebagai tambahan dari offspring yang diproduksi oleh operator crossover. Pada ES, mutasi diterapkan pada offspring yang dihasilkan proses rekombinasi. Rekombinasi pada ES mirip dengan operator crossover pada GAs tapi bisa menggunakan lebih dari satu induk. Karena ES lebih mengandalkan mutasi, maka proses rekombinasi tidak selalu digunakan. Secara umum terdapat empat tipe proses dari ES, yaitu: o (µ, l) o (µ/r, l) o (µ + l) o (µ/r + l)
Struktur Dasar ES
Karena ES lebih mengandalkan mutasi, maka proses rekombinasi tidak selalu digunakan. Secara umum terdapat empat tipe proses dari ES, yaitu: ES
rekombinasi
proses seleksi
seleksi melibatkan
(µ, l)
-
Elitism
Offspring
(µ/r, l)
√
Elitism
Offspring
(µ + l)
-
Elitism
Induk dan Offspring
(µ/r + l)
√
Elitism
Induk dan Offspring
ES(µ, l) tidak menggunakan rekombinasi dalam proses reproduksi. Seleksi menggunakan elitism selection hanya melibatkan individu dalam offspring, individu induk dalam populasi tidak dilibatkan. ES(µ/r, l) serupa dengan ES(µ, l) dengan tambahan melibatkan proses rekombinasi. ES(µ+l) tidak menggunakan rekombinasi dan proses seleksi menggunakan elitism selection melibatkan individu offspring dan induk.
Siklus ES (µ, λ) (Studi Kasus: Maksimasi Fungsi dengan Presisi Tertentu) akan digunakan untuk menjelaskan siklus ES secara detil
1. Representasi Chromosome o Seperti halnya untuk real-coded GA pada Pert. Ke-4, variabel keputusan (x1 dan x2) langsung menjadi gen string chromosome. chromosome x1 P1 P2
x2
f(x1,x2)
1,4898 8,4917
2,0944 2,5754
19,8206 34,7058
-4,5575
0,1679
28,4324
..
P10
o Parameter tambahan yang melekat pada setiap chromosome adalah s (sigma) yang menyatakan level mutasi. Nilai ini akan ikut berubah secara adaptif sepanjang generasi. Jika P adalah satu chromosome maka P=(x1,x2,s1,s2) dengan panjang string sebesar 4.
Siklus ES (µ, λ) 2. Inisialisasi o Populasi inisial dibangkitkan secara random. Nilai x1 dan x2 dibangkitkan dalam rentang variabel ini (lihat Pert. Ke-3, Slide 24 ). Nilai s1 dan s2 dibangkitkan dalam rentang [0,1]. Misalkan ditentukan µ=4 maka akan dihasilkan populasi seperti contoh berikut: P(t)
x1
x2
s1
s2
f(x1,x2)
P1
1,48980
2,09440
0,14197
0,91090
19,8212830
P2
8,49170
2,57540
0,53801
0,86904
34,7060873
P3
-1,84610
1,70970
0,99835
0,49351
11,5863900
P4
5,81140
5,07790
0,40521
0,98911
14,5620828
Siklus ES (µ, λ) 3. Reproduksi o Karena rekombinasi tidak digunakan maka hanya mutasi yang berperan menghasilkan offspring. Misalkan P=(x1,x2,s1,s2) adalah individu yang terpilih untuk melakukan mutasi, maka dihasilkan offspring P’=(x1’,x2’,s1’,s2’) sebagai berikut: x’ = x + s N(0,1) o Rumusan diatas bisa didetailkan sebagai berikut: x’1 = x1 + s1 N(0,1) x’2 = x2 + s2 N(0,1) o N(0,1) merupakan bilangan acak yang mengikuti sebaran normal dengan rata-rata sebesar 0 dan standard deviasi sebesar 1. Pada program komputer, nilai N(0,1) bisa didapatkan dengan membangkitkan dua bilangan random r1 dan r2 pada interval [0,1]. Rumus yang digunakan adalah (Schwefel, 1995): N 0,1 2 ln r1 sin 2r2
o Misalkan r1 = 0,4749 dan r2 = 0,3296 maka didapatkan N(0,1)= 1,0704
Siklus ES (µ, λ) 3. Reproduksi o Nilai s dinaikkan jika ada paling sedikit 20% hasil mutasi yang menghasilkan individu yang lebih baik dari induknya. Jika tidak maka nilai s diturunkan. Misalkan l=3×µ=12, maka setiap individu dalam populasi akan menghasilkan 3 offspring. Pada kasus ini, nilai s akan dinaikkan jika ada setidaknya 1 offspring yang lebih baik. o Contoh hasil mutasi diberikan sebagai berikut: C(t) C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
Induk P1
N1(0,1) 0,0098
N2(0,1) -0,8394
x’1 1,491191
x’2 s ‘1 1,3298 0,15617
1,00199
f(x1,x2) 10,04952
P2
1,0334 -1,9967 -0,0398
-0,6351 -1,8970 0,6565
1,63651 1,206331 8,470287
1,5159 0,15617 0,3664 0,15617 3,1459 0,48421
1,00199 1,00199 0,78214
9,03814 27,06928 24,40017
-0,7821 1,3563 -1,1466 1,1021 0,7094 1,8635
-0,2305 0,1430 1,3203 -1,9381 -0,2813 -0,2293
8,070926 9,221397 -2,9908 -0,74582 -1,13787 6,566503
2,3751 2,6997 2,3613 0,7532 1,5709 4,8511
0,48421 0,48421 1,09818 1,09818 1,09818 0,44573
0,78214 0,78214 0,54286 0,54286 0,54286 1,08802
27,82881 19,00143 26,01116 26,00610 10,30137 27,74543
0,5542 1,4608
-1,2182 -0,5120
6,035966 6,403326
3,873 0,44573 4,5715 0,44573
1,08802 1,08802
17,29977 30,40250
P3
P4
s ‘2
Perhatikan dari hasil mutasi ini; Nilai s ’ dari offspring yang dihasilkan P1, P3, dan P4 dinaikkan dengan rumusan s ’ = s x 1,1. Nilai s ’ dari offspring yang dihasilkan P2 diturunkan dengan rumusan s ’ = s x 0,9
Siklus ES (µ, λ) 4. Seleksi o Seleksi menggunakan elitism selection hanya melibatkan individu dalam offspring, individu induk dalam populasi tidak dilibatkan. Dari proses ini didapatkan populasi baru sebagai berikut: x2
s1
s2
f(x1,x2)
6,40333
4,57148
0,44573
1,08802
30,4025035
C5
8,07093
2,37509
0,48421
0,78214
27,8288128
P3
C10
6,56650
4,85110
0,44573
1,08802
27,7454295
P4
C3
1,20633
0,36642
0,15617
1,00199
27,0692849
P(t+1)
asal
P1
C12
P2
x1
Siklus ES (µ/r + λ) Siklus ES dibahas lagi dengan melibatkan proses rekombinasi, dengan populasi inisial seperti pada Slide 9 (digunakan lagi).
1. Reproduksi: Rekombinasi dan Mutasi o Rekombinasi dilakukan untuk menghasilkan offspring sebanyak l dari sejumlah µ individu dalam populasi. o Setiap satu individu offspring dihasilkan dari beberapa induk. o Induk dipilih secara acak dari populasi. Metode rekombinasi paling sederhana adalah dengan menghitung rata-rata nilai elemen induk. Contoh proses rekombinasi diberikan sebagai berikut: • Misalkan offspring didapatkan dari 2 induk. Jika P1 dan P3 terpilih maka akan didapatkan offspring C=(-0,17815, 1,90205, 0,57016, 0,70221). • Misalkan offspring didapatkan dari 3 induk. Jika P1, P2 dan P3 terpilih maka akan didapatkan offspring C=(2,71180, 2,12650, 0.55944, 0,75782).
Siklus ES (µ/r + λ) 1. Reproduksi: Rekombinasi dan Mutasi o Pada studi kasus ini, misalkan l=6 dan offspring didapatkan dari 2 induk. Contoh hasil rekombinasi diberikan sebagai berikut P(t)
x1
s2
s1
x2
f(x1,x2)
P1
1,48980
2,09440
0,14197
0,91090
19,8212830
P2
8,49170
2,57540
0,53801
0,86904
34,7060873
P3
-1,84610
1,70970
0,99835
0,49351
11,5863900
P4
5,81140
5,07790
0,40521
0,98911
14,5620828
Dari Slide 9
Hasil offspring (Ci), yaitu dengan menghitung rata-rata nilai elemen induk
C(t)
induk
s1
s2
C1 C2
P1 dan P3 P2 dan P3
x1 -0,17815 3,32280
x2 1,90205 2,14255
0,57016 0,76818
0,70221 0,68128
f(x1,x2) 16,6418295
C3
P1 dan P4
3,65060
3,58615
0,27359
0,95001
9,5700496
C4
P2 dan P4
7,15155
3,82665
0,47161
0,92907
12,5240357
C5 C6
P1 dan P3 P3 dan P4
-0,17815 1,98265
1,90205 3,39380
0,57016 0,70178
0,70221 0,74131
16,6418295
19,5813015
12,6500683
Hasil Rekombi nasi
Siklus ES (µ/r + λ) 1. Reproduksi: Rekombinasi dan Mutasi o Pada studi kasus ini, misalkan l=6 dan offspring didapatkan dari 2 induk. Contoh hasil rekombinasi diberikan sebagai berikut x1
P(t)
x2
s2
s1
f(x1,x2)
P1
1,48980
2,09440
0,14197
0,91090
19,8212830
P2
8,49170
2,57540
0,53801
0,86904
34,7060873
P3
-1,84610
1,70970
0,99835
0,49351
11,5863900
P4
5,81140
5,07790
0,40521
0,98911
14,5620828
Dari Slide 9
o Mutasi dilakukan dengan cara yang sama seperti slide sebelumnya. nilai s dinaikkan jika hasil mutasi lebih baik. Sebaliknya jika hasil mutasi lebih buruk maka nilai s diturunkan. Berikut ini contoh hasil mutasi: C’(t) C7
N1(0,1) 0,1885
N2(0,1) 0,2747
x’1 -0,07068
x’2 s ‘1 2,094946 0,62717
s ‘2 0,77243
f(x1,x2) 21,3386958
C8 C9 C10
-1,7947 -0,5603 0,6189
-0,1359 -1,8657 -0,4613
1,944154 3,497309 7,443427
2,049965 0,84499 1,813724 0,30095 3,398068 0,42445
0,74940 1,04501 0,83617
19,9034447 10,9809788 5,4075091
C11 C12
-0,1371 1,1125
-0,4201 -0,2153
-0,25632 2,763377
1,607053 0,51314 3,234196 0,77195
0,63199 0,81544
11,2620580 16,3293685
Hasil Mutasi
Siklus ES (µ/r + λ) 2. Seleksi o Seleksi menggunakan elitism selection melibatkan individu dalam offspring dan individu induk dalam populasi. Dari proses ini didapatkan populasi baru sebagai berikut x2
s1
s2
8,49170
2,57540
0,53801
0,86904
34,7060873
C7
-0,07068
2,09495
0,62717
0,77243
21,3386958
P3
C8
1,94415
2,04996
0,84499
0,74940
19,9034447
P4
P1
1,48980
2,09440
0,14197
0,91090
19,8212830
P(t+1)
asal
x1
P1
P2
P2
f(x1,x2)
Siklus ES (µ + λ) : Optimasi Fungsi Berkendala Perhatikan permasalahan pada sebuah perusahaan yang akan memproduksi dua jenis lemari, sebut saja lemari A dan lemari B. Untuk memproduksi kedua lemari tersebut dibutuhkan tiga macam bahan baku, yaitu: kayu, aluminium, dan kaca. Kebutuhan detil tiga bahan baku tersebut (dalam unit tertentu) untuk tiap buah lemari ditampilkan pada tabel berikut: lemari kayu A 10 B
20
aluminium 9 8
kaca 12 18
Persedian bahan baku kayu, aluminium, dan kaca di gudang berturut-turut adalah 350, 200, dan 300. Jika keuntungan penjualan sebuah lemari A sebesar 400 dan B sebesar 500, berapakah banyaknya lemari A dan B harus diproduksi agar didapatkan keuntungan maksimum?
Siklus ES (µ + λ) : Optimasi Fungsi Berkendala Kebutuhan detil tiga bahan baku: lemari kayu
aluminium
kaca
A
10
9
12
B
20
8
18
Untuk
Persedian bahan baku kayu, aluminium, dan kaca di gudang berturut-turut adalah 350, 200, dan 300. Jika keuntungan penjualan sebuah lemari A sebesar 400 dan B sebesar 500, berapakah banyaknya lemari A dan B harus diproduksi agar didapatkan keuntungan maksimum?
menyelesaikan permasalahan ini dibutuhkan model matematis yang disusun atas fungsi tujuan (objective functions) dan kendala (constraints). Fungsi tujuan merepresentasikan tujuan yang ingin dioptimalkan (maksimumkan atau minimumkan). Jika banyaknya lemari yang harus diproduksi dilambangkan dengan x1 dan x2, maka fungsi tujuan bisa dinyatakan sebagai: o Maksimumkan f(x1,x2)=400x1 + 500x2 o Kendala ketersediaan bahan baku bisa dinyatakan sebagai berikut: kendala 1 : 10x1 + 20x2 ≤ 350 kendala 2 : 9x1 + 8x2 ≤ 200 kendala 3 : 12x1 + 18x2 ≤ 300
Siklus ES (µ + λ) : Optimasi Fungsi Berkendala Berdasarkan dua aturan sebelumnya, maka bisa disusun fungsi fitness sebagai berikut: fitness(x1,x2) = f(x1,x2) – M(c1 + c2 + c3), dimana M: bil. positif yang cukup besar, misalnya 1000 Nilai x1 dan x2 merupakan bilangan pecahan (real). Karena permasalahan ini memerlukan solusi dalam bentuk bilangan bulat maka dalam perhitungan fitness nilai x1 dan x2 dibulatkan terlebih dahulu.
0, jika 10x 1 20x 2 350 c1 10x 1 20x 2 350, selainnya 0, jika 9x 1 8x 2 200 c2 9x 1 8x 2 200, selainnya 0, jika 12x 1 18x 2 300 c3 12x 1 18x 2 300, selainnya
Contoh perhitungan fitness: x1
x2
Round(x1) Round(x2) f(x1,x2)
c1
c2
c3
fitness
21,9 0,2
0,3 15,9
22 0
0 16
8800 8000
0 0
0 0
0 0
8800 8000
10,3
11,4
10
11
9500
0
0
18
-8500
8,1
13,6
8
14
10200
0
48
-47800
10
Siklus ES (µ + λ) : Optimasi Fungsi Berkendala 1. Inisialisasi o Populasi inisial dibangkitkan secara random. Nilai x1 dan x2 dibangkitkan sebagai bilangan pecahan (real) dalam rentang [0,50]. Misalkan ditentukan µ=4 maka akan dihasilkan populasi dengan contoh sebagai berikut: x1 x2 s2 s1 P(t) fitness
P1 P2 P3 P4
21,9 0,2 10,3 8,1
0,3 15,9 11,4 13,6
0,23241 0,82123 0,79231 0,31982
0,02713 0,10383 0,93718 0,75632
8800 8000 -8500 -47800
Siklus ES (µ + λ) : Optimasi Fungsi Berkendala 2. Reproduksi o Karena rekombinasi tidak digunakan maka hanya mutasi yang berperan
menghasilkan offspring. Pada studi kasus ini, misalkan l=2xµ=8 dan µ=4 maka dihasilkan offspring seperti contoh berikut: C(t) Induk N1(0,1) N2(0,1) C1 P1 1,8023 -1,3414 C2 -0,7837 1,2838 C3 P2 0,6234 -0,9298 C4 -1,2394 -0,3293 C5 P3 1,0383 -2,0459 C6 1,9932 1,2427 C7 P4 -0,4513 -1,6313 C8 -1,2093 2,0348
x '1
x '2
22,3189 21,7179 0,7120 -0,8178 11,1227 11,8792 7,9557 7,7132
0,2636 0,3348 15,8035 15,8658 9,4826 12,5646 12,3662 15,1390
s’
1
s'
2
0,20917 0,02442 0,20917 0,02442 0,68574 -1,02278 -1,36334 -0,36223 0,87154 1,03090 0,87154 1,03090 0,35180 0,83195 0,35180 0,83195
fitness 8800 8800 8400 7600 8900 -108700 -2800 -85300
Perhatikan dari hasil mutasi ini, nilai s’ dari offspring yang dihasilkan P2, P3, dan P5 dinaikkan dengan rumusan s’ = s x 1,1 karena paling tidak menghasilkan 1 anak yang lebih baik. Nilai s’ dari offspring yang dihasilkan P1 diturunkan dengan rumusan s’ = s’ x 0,9.
Siklus ES (µ + λ) : Optimasi Fungsi Berkendala 3. Seleksi o Seleksi menggunakan elitism selection melibatkan individu dalam offspring dan individu induk dalam populasi. Dari proses ini didapatkan populasi baru sebagai berikut: x1 x2 s2 s1 P(t+1) asal fitness P1 C5 11,1227 9,4826 0,87154 1,03090 8900 P2 P1 21,9 0,3 0,23241 0,02713 8800 P3 C1 22,3189 0,2636 0,20917 0,02442 8800 P4 C2 21,7179 0,3348 0,20917 0,02442 8800
ES untuk Representasi Permutasi Seperti telah diuraikan pada awal slide, ciri utama ES adalah
penggunaan vektor bilangan pecahan (real-vector) sebagai representasi. Pada perkembangannya, ES juga diadopsi untuk permasalahan kombinatorial yang menggunakan representasi permutasi. Cara paling mudah adalah dengan menggunakan struktur ES yang hanya menggunakan mutasi tanpa rekombinasi. Mekanisme self-adaptation juga tidak digunakan. Pendekatan ini pada hakekatnya menghasilkan siklus yang sama seperti GAs tanpa crossover. Adopsi mekanisme self-adaptation pada representasi permutasi bisa dilakukan dengan cara sederhana jika yang digunakan adalah reciprocal exchange mutation atau insertion mutation.
ES untuk Representasi Permutasi Pada kasus ini, nilai s menyatakan berapa kali proses exchange atau insertion dilakukan untuk menghasilkan satu anak. Misalkan diberikan contoh dua induk dalam tabel berikut: P(t) P1 P2
permutasi [25143] [41532]
s 1,3452 2,0728
Misalkan reciprocal exchange mutation digunakan dan l=3µ. induk
P1 = [ 2 5 1 4 3 ]
P2 = [ 4 1 5 3 2 ]
proses tukar posisi 1 dan 3 tukar posisi 2 dan 5 tukar posisi 4 dan 5 tukar posisi 2 dan 4 tukar posisi 1 dan 5
offspring C1 = [ 1 5 2 4 3 ] C2 = [ 2 3 1 4 5 ] C3 = [ 2 5 1 3 4 ] C4 = [ 2 3 5 1 4 ]
tukar posisi 1 dan 4 tukar posisi 3 dan 4
C5 = [ 3 1 4 5 2 ]
tukar posisi 3 dan 4 tukar posisi 2 dan 4
C6 = [ 4 5 3 1 2 ]
Berdasarkan nilai s yang dibulatkan, offspring dari P1 dihasilkan melalui proses sekali pertukaran dan offspring dari P2 dihasilkan melalui dua kali pertukaran. Contoh offspring yang dihasilkan ditampilkan dalam tabel disamping.
Tugas Kelompok 1. Jelaskan ciri utama evolution strategies! 2. Jelaskan perbedaan utama ES dengan GAs? 3. Misalkan terdapat himpunan individu dalam populasi dengan µ=4 dan l=6 sebagai berikut: individu P1 P2 P3 P4
fitness 10 9 7 5
Terdapat juga himpunan offspring sebagai berikut: individu C1 C2 C3 C4 C5 C6
fitness 11 9 8 7 6 4
Tentukan himpunan individu yang lolos ke generasi selanjutnya pada ES(µ, l)!
Tugas Kelompok 4. Kerjakan ulang Soal no. 3 untuk ES(µ+l)! 5. Perhatikan fungsi berikut:
f x1 , x2 x1 sin 2 x1 x2 sin 4 x2 , 0 x1 10, 0 x2 10
Cari nilai minimum dari fungsi ini dengan menggunakan ES (µ/r+l). Gunakan nilai µ=4 dan l=8. Lakukan interasi sampai 3 putaran. 6. Untuk permasalahan pada Slide ke-17 Studi Kasus ES (µ + l): Optimasi Fungsi Berkendala, selesaikan dengan menggunakan ES (µ/r, l). Gunakan nilai µ=4 dan l=8. Lakukan interasi sampai 3 putaran. 7. Selesaikan persoalan transportasi pada Pert. Ke-6 Slide ke-21 dengan menggunakan ES (µ,l). Gunakan nilai µ=4 dan l=8. Lakukan interasi sampai 3 putaran.
Terimakasih Imam Cholissodin |
[email protected]
