ERWIEN TJIPTA WIJAYA, ST.,M.KOM
DEFINISI ALGEN adalah algoritma yang memanfaatkan proses seleksi alamiah yang dikenal dengan evolusi Dalam evolusi, individu terus menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya Hanya individu yang kuat yang akan bertahan
STRUKTUR ALGEN Genotype (Gen) bagian dari kromosom yang mewakili 1 variabel (nilai biner, float, integer, character dan lain - lain) Allele, nilai dari gen Kromosom/individu gabungan gen – gen yang menyatakan salah satu solusi yang mungkin Populasi, sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi Generasi, satuan siklus proses evolusi Nilai Fitness, seberapa baik nilai dari suatu individu/solusi
PENERAPAN ALGEN Penyelesaian TSP (Traveling Solution Problem) / Sorthess path Mencari nilai maksimal dari suatu fungsi Mencari nilai optimasi Peramalan (Forecasting)
FLOWCHART ALGEN Bangkitkan populasi awal
Evaluasi fungsi tujuan
Apakah kriteria optimasi tercapai?
Ya
Individu – individu terbaik
Tidak Start
Hasil seleksi
rekombinasi
mutasi Bangkitkan populasi baru
DESKRIPSI Populasi awal, didapatkan dari inisialisasi kromosom dengan dilakukan secara acak Fungsi evaluasi, evaluasi kromosom ada 2 macam:
Evaluasi fungsi obyektif Konversi fungsi obyektif ke dalam fungsi fitness
Secara umum fungsi fitness diturunkan oleh fungsi obyektif dengan nilai yang positif (+), apabila fungsi obyektif bernilai negatif (-) maka perlu ditambahkan konstanta C agar nilai fitness yang terbentuk menjadi positif (+)
DESKRIPSI FLOWCHART Seleksi, seleksi ini bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang paling fit. Ada beberapa metode seleksi, antara lain:
Rank-based fitness assigment Roulette wheel selection Stochastic universal sampling Local selection Truncation selection Tournament selection
DESKRIPSI
Operator Genetika, ada 2 operator genetika : Operator Rekombinasi ○ Rekombinasi bernilai real
○
Rekombinasi diskret Rekombinasi intermediate Rekombinasi garis Rekombinasi garis yang diperluas
Rekombinasi bernilai biner (crossover) Crossover 1 titik (single-point-crossover) Crossover banyak titik (Multi-point-crossover) Crossover seragam (uniform crossover)
○ Crossover dengan permutasi
Mutasi ○ Mutasi bernilai real ○ Mutasi bernilai biner
DESKRIPSI
Penentuan Parameter, parameter kontrol ALGEN, yaitu ukuran populasi (popsize), peluang crossover (pc) dan peluang mutasi (pm). Nilai parameter ini ditentuka juga berdasarkan permasalahan yang akan dipecahkan. Ada beberapa rekomendasi yang bisa digunakan, antara lain : Menurut De Jong, untuk permasalahan yang memiliki kawasan
solusi cukup besar, maka nilai parameter kontrol (popsize;pc;pm)=(50; 0,6 ;0,001) Menurut Grefenstette, bila rata – rata fitness setiap generasi
digunakan sebagai indikator, maka nilai parameter kontrol (popsize;pc;pm)=(30; 0,95 ;0,01) Bila fitness dari individu terbaik dipantau pada setiap generasi,
maka nilai parameternya adalah (popsize;pc;pm)=(80; 0,45; 0,01) Ukuran
populasi sebaiknya tidak lebih kecil dari 30, untuk sembarang jenis permasalahan
ALGORITMA GENETIKA SEDERHANA
Misalkan P (generasi) adalah populasi dari 1 generasi, maka secara sederhana urutan-urutan langkahnya adalah sebagai berikut: Generasi=0 (Generasi awal) Inisialisasi populasi awal, P(generasi) dengan bilangan acak Evaluasi nilai fitness pada setiap individu dalam P(Generasi) Kerjakan langkah-langkah berikut hingga generasi mencapai maksimum generasi :
1. 2. 3. 4. a. b. c. d. e. f. g.
Generasi= generasi + 1 (tambah generasi) Seleksi populasi tersebut untuk mendapatkan kandidat induk, P(Generasi) Lakukan crossover pada P(Generasi) Lakukan mutasi pada P(Generasi) Lakukan evaluasi fitness setiap individu pada P(Generasi) Bentuk populasi baru: P(Generasi)=P(Generasi-1) yang kuat/survive Kriteria berhenti apabila pada setiap generasi – generasi memiliki nilai fitness yang tidak berubah
CONTOH: TSP (TRAVELING SALES PROBLEM)
A
8
B 4
7
5 3
D
6
C
MEMBENTUK POPULASI AWAL
Populasi awal, dapat dibangkitkan secara acak atau melalui prosedur tertentu Tentukan parameter misalkan : Popsize = 4 Pc (Probabilitas Crossover) = 0,5 Pm(Probabilitas Mutasi) = 0,2 Maksimum Generasi = 10
Misal dibangkitkan populasi awal dengan 4 individu : Kromosom[1] = [A B C D] Kromosom[2] = [B C D A] Kromosom[3] = [C D A B] Kromosom[4] = [D A B C]
EVALUASI FITNESS Kromosom [1] = 8 + 5 + 6 = 19 Kromosom [2] = 5 + 6 + 7 = 18 Kromosom [3] = 6 + 7 + 8 = 21 Kromosom [4] = 7 + 8 + 5 = 20
NO
KROMOSOM
FITNESS
[1]
AB C D
19
[2]
B C DA
18
[3]
C DAB
21
[4]
DAB C
20
SELEKSI Seleksi untuk mendapatkan calon induk yang baik Induk yang baik akan mendapatkan keturunan yang baik Semakin tinggi nilai fitness suatu individu semakin besar kemungkinan terpilih Metode seleksi yang digunakan adalah Roulette Wheel
SELEKSI KROMOSOM
Pada TSP nilai fitness yang terpilih adalah nilai terkecil maka digunakan inverse : Q[i] = 1 / Fitness[i] Q[1] = 1 / 19 = 0,052 Q[2] = 1 / 18 = 0,056 Q[3] = 1 / 21 = 0,048 Q[4] = 1 / 20 = 0,05 Total Q[i] = Q[1]+Q[2] +Q[3] +Q[4]
0,052 + 0,056 + 0,048 + 0,05 = 0,207
SELEKSI KROMOSOM
Menghitung individu
probabilitas
P[i] = Q[i] / Total Q[i] P[1] = 0,052 / 0,207 = 0,256 P[2] = 0,056 / 0,207 = 0,27 P[3] = 0,048 / 0,207 = 0,232 P[4] = 0,05 / 0,207 = 0,242
/
fitness
relatif
tiap
SELEKSI KROMOSOM
Menghitung fitness kumulatif / nilai kumulatif dari probabilitas : C[1] = 0,256 C[2] = 0,256 + 0,27 = 0,526 C[3] = 0,526 + 0,232 = 0,758 C[4] = 0,758 + 0,242 = 1
SELEKSI KROMOSOM Memilih induk yang akan menjadi kandidat untuk di-crossover Membangkitkan bilangan acak (R)
R[1] = 0,314 R[2] = 0,743 R[3] = 0,418 R[4] = 0,203
Kemudian membandingkan antara (Random) dengan C (Komulatif)
nilai
C > R (pilih nilai C yang mendekati dengan nilai R)
Contoh :
R[1] = 0,314 maka nilai R[2] = 0,743 maka nilai R[3] = 0,418 maka nilai R[4] = 0,203 maka nilai
yang mendekati adalah yang mendekati adalah yang mendekati adalah yang mendekati adalah
= 0,526 C[2] = 0,758 C[3] = 0,526 C[2] = 0,256 C[1]
R
KROMOSOM BARU HASIL SELEKSI
NO
KROMOSOM
FITNESS
ASAL
[1]’
B C DA
18
[2]
[2]’
C DAB
21
[3]
[3]’
B C DA
18
[2]
[4]’
AB C D
19
[1]
LANGKAH-LANGKAH CROSSOVER
Karena peluang crossover (pc) = 0,5; maka diharapkan 50% dari total kromosom akan mengalami crossover (2 dari 4 kromosom) Untuk memilih kromosom-kromosom yang akan dilakukan crossover yaitu dengan cara membangkitkan bilangan acak [0 1] sebanyak 4 buah. Misal bilangan acak yang tercipta adalah :
R[1] = 0,442 R[2] = 0,206 R[3] = 0,895 R[4] = 0,319
Pilih bilangan – bilangan yang kurang / lebih kecil dari nilai pc dalam hal ini nilai pc = 0,5 untuk dilakukan crossover, nilai yang terpilih adalah : R[1] = 0,442 R[2] = 0,206
PROSES CROSSOVER
Kromosom yang akan ditukarkan adalah : Kromosom[1]’’ = B C D A Kromosom[2]’’ = C D A B
Tukarkan kromosom[1] dengan kromosom[2] Contoh
Kromosom[1] = Kromosom[2] Kromosom[2] = Kromosom[1]
Populasi setelah proses crossover : NO
KROMOSOM
FITNESS
[1]’’
C DAB
21
[2]’’
B C DA
18
[3]’
B C DA
18
[4]’
AB C D
19
LANGKAH – LANGKAH MUTASI
Hitung panjang Gen pada populasi
Panjang total gen = popsize * jumlah Gen pada setiap kromosom = 4 * 4 = 16 (total Gen)
Memilih posisi gen yang di mutasi dilakukan dengan membangkitkan bilangan acak antara 1 sampai dengan panjang total gen (1 - 16) Misal ditentukan pm=0,2 atau 20% maka jumlah gen yang akan dimutasi adalah : 0,2 * 16 = 3,2 =3 bit (setelah dibulatkan) Ciptakan bilangan acak [0 1] sebanyak 16 Gen kemudian kelompokan menjadi 4 kromosom Kemudian mutasi / pindahkan Gen tersebut dengan mengambil nilai Gen didepannya kemudian lakukan pertukaran, maka Gen = Gen + 1 dan Gen + 1 = Gen Apabila Gen pada posisi terakhir maka ambilkan dari Gen yang paling depan, kemudian tukar Gen depan = Gen terakhir dan Gen terakhir = Gen depan
TABEL BILANGAN ACAK MUTASI KROMOSOM[1] R[1] = 0,412
R[2] = 0,737
R[3] = 0,379
R[4] = 0,192
R[2] = 0,718
R[3] = 0,565
R[4] = 0,082
R[2] = 0,755
R[3] = 0,371
R[4] = 0,386
R[2] = 0,980
R[3] = 0,108
R[4] = 0,860
KROMOSOM[2] R[1] = 0,234 KROMOSOM[3] R[1] = 0,949 KROMOSOM[4] R[1] = 0,840
PROSES MUTASI
Kromosom dan Gen yang terkena mutasi Kromosom[1] dan Gen[4] Kromosom[2] dan Gen[4] Kromosom[4] dan Gen[3]
Bentuk populasi awal :
Kromosom[1]’’ = [C D A B] B ditukar dengan A Kromosom[2]’’ = [B C D A] A ditukar dengan D Kromosom[3]’ = [B C D A] Kromosom[4]’ = [A B C D] C ditukar dengan B
Bentuk populasi setelah mutasi :
Kromosom[1] ‘’’= [C D B A] Kromosom[2] ‘’’= [B C A D] Kromosom[3] ‘= [B C D A] Kromosom[4] ‘’’= [A C B D]
EVALUASI
Proses 1 Generasi selesai : Fitness[1] = 6 + 4 + 8 = 18 Fitness[2] = 5 + 3 + 7 = 15 Fitness[3] = 5 + 6 + 7 = 18 Fitness[4] = 5 + 3 + 4 = 12
Karena TSP adalah rute yang paling pendek yang harus dipilih maka dalam kasus ini nilai Fitness yang terkecil yang harus dipilih Pada kasus ini kromosom[4]=12 dengan rute [A C B D]
POPULASI BARU Populasi terakhir digunakan sebagai data awal / populasi baru pada iterasi berikutnya Lanjutkan sendiri sampai mendapatkan nilai fitness terkecil
