![Page 1: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/1.jpg)
Teny Handhayani
![Page 2: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/2.jpg)
Algoritma Genetika Algoritma yang meniru seleksi alam
Diperkenalkan oleh Prof. John Holland pada tahun1975
Algoritma Genetika terdiri atas siklus sederhana yaitu:
1. Membuat populasi string secara acak
2. Evaluasi setiap string
3. Seleksi string terbaik
4. Manipulasi genetika untuk memperoleh populasibaru yang lebih baik
![Page 3: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/3.jpg)
Siklus Algoritma Genetika
Population(chromosomes)
Fitness EvaluationGenetic Operators
Selection(Mating Pool)
Parents
Decoded strings
ReproductionManipulation
OffspringNew Generation
![Page 4: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/4.jpg)
Algoritma Genetika Elemen-elemen dalam populasi dikodekan sebagai
bit-strings
Bit-string disebut sebagai kromosom
Fitness digunakan sebagai istilah untuk performastring
![Page 5: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/5.jpg)
Crossover
11010 1010
11010 1001
10101 1001
10101 1010
Parents
Offspring
10101 1001 10011
10101 1110 10011
01101 1110 11101
01101 1001 11101
Single point crossover
Two point crossover
Parents
Offspring
![Page 6: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/6.jpg)
Mutation
1 0 1 0 1 1 0 1 0 1 0 1
1 0 1 0 1 1 1 1 0 1 0 1
![Page 7: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/7.jpg)
Contoh Algoritma Genetika untuk fungsi pada
interval 0 ≤ x ≤ 31
Dimuali dengan 4 string inisialisasi
� � = ��
String no
Initial population x F(x) Strength fitness(% of total)
1 01101 13 169 14.4
2 11000 24 576 49.2
3 01000 8 64 5.5
4 10011 19 361 30.9
Sum-Fitness 1170 100.00
![Page 8: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/8.jpg)
String no
Mating Pool MatesString
Swapping New Population
1 01101 2 0110[1] 01100
2 11000 1 1100[0] 11001
3 11000 4 01[000] 11011
4 10011 2 10[011] 10000
InitialPopulation
x F(x)(fitness)
Strength (% of total)
01100 12 144 8.2
11001 25 635 35.6
11011 27 729 41.5
10000 16 256 14.7
Sum-Fitness 1754 100.00
Nilai fitness pada generasi ke dua
![Page 9: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/9.jpg)
Latihan
Mencari solusi
Tahap 0 Inisialisasi populasi
Menggunakan 10 kromosom dengan 5 bit string
� � = �� − 64
![Page 10: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/10.jpg)
� � = �� − 64
Tahap 1: Evaluasi fitness function
Fungsi yang digunakanx adalah nilai desimal dari kromosom
Mencari nialai �� − 64 = 0 � = ±8
Misalnya dicari solusi x = 8, sehingga fungsi f akan memberikan nilai mendekati 0
![Page 11: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/11.jpg)
�� =�(��)
∑ �(��)�����
![Page 12: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/12.jpg)
��
= � ��
�
�=1
= �1
+ �2
+ ⋯ + ��−1
+ ��
= ��−1
+ ��
![Page 13: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/13.jpg)
Untuk menyeleksi kromosom, maka dibuat 10 nilai secara acak pada rentang [0 1]Misalnya nilai tersebut yaitu:
0.5436 0.7412 0.8924 0.2455 0.6874 0.2842 0.3864 0.9981 0.3684 0.7240
1 2 3 4 5 6 7 8 9 10
Mencari qj > 0.5436 dan qj-1 <0.5436Sehinggaq8 = 0.6221 > 0.5436q7 = 0.5063 < 0.5436 sehingga kromosom 8 dipilih pertama
![Page 14: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/14.jpg)
Diperoleh sebagai berikut:
![Page 15: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/15.jpg)
Tahap 2 Cross Over
Memilih probabilitas crossover sebesar pc = 0.25Membuat 10 bilangan random pada rentang [0 1], cross over dilakukan jika bilangan < 0.25
0.2890 0.1527 0.2690 0.1890 0.2630 0.1442 0.1628 0.2585 0.5830 0.6532
1 2 3 4 5 6 7 8 9 10
�6′′ = 10 000
�7′′ = 11 001
� �ℎ�����
�6′ = 10 001
�7′ = 11 000
� ������
![Page 16: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/16.jpg)
Hasil crossover
![Page 17: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/17.jpg)
Tahap 3: Mutation
Menentukan pm =0.01Membuat 10 bilangan random pada rentang [0 1]Bilangan yang pm < 0.01 maka dilakukan mutasi
Perulahan tahapan algoritma genetikadilakukan sampai pada threshold tertentu (batasan yg ditetapkan) ataurata-rata fitness telah melewatithreshold
![Page 18: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/18.jpg)
Algoritma Genetika MenggunakanMATLAB
![Page 19: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/19.jpg)
![Page 20: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/20.jpg)
Contoh 1 Sum Squares Function
![Page 21: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/21.jpg)
function y = sum2(x)% The default value of n = 15.n = 15;s = 0;for j = 1:n s=s+j*x(j)^2;
endy = s;
![Page 22: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/22.jpg)
![Page 23: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/23.jpg)
![Page 24: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/24.jpg)
Contoh 2 Ackley Function
![Page 25: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/25.jpg)
![Page 26: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/26.jpg)
![Page 27: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/27.jpg)
![Page 28: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/28.jpg)
![Page 29: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/29.jpg)
Contoh 3 Rastrigin’s Function
![Page 30: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/30.jpg)
function y = rast(x)n = 2;s = 0;for j = 1:n
s = s+(x(j)^2-10*cos(2*pi*x(j))); endy = 10*n+s;
![Page 31: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/31.jpg)
Contoh 4 Easom Function
![Page 32: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/32.jpg)
function y = easom(x)y = -cos(x(1))*cos(x(2))*exp(-(x(1)-pi)^2-(x(2)-pi)^2);
![Page 33: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/33.jpg)
![Page 34: Teny Handhayani · Fitness digunakan sebagai istilah untuk performa string. Crossover ... Memilih probabilitas crossover sebesar pc = 0.25 ... Bilangan yang pm < 0.01 maka dilakukan](https://reader037.vdokumen.com/reader037/viewer/2022100303/5c8c436c09d3f245088b594b/html5/thumbnails/34.jpg)
Tugas 1 Buatlah script untuk menyelesaikan persamaan
Carilah nilai best fitness dan mean fitness untukkedua nilai!
Ada berapa banyak generasi?
� � = �� − 64a
b