Download - ALGORITMA GENETIKA.doc
ALGORITMA GENETIKA
I. PENDAHULUAN
Algoritma genetika adalah agoritma pencarian heuristik yang didasarkan atas
mekanisme evaluasi biologis. Keberagamaan pada evaluasi biologis adalah variasi dari
kromosom antar indivdu organisme. Variasi kromosom ini akan mempengaruhi laju
reproduksi dan tingkat kemampuan organisme untuk tetap hidup. Pada dasarnya ada 4
kondisi yang sangat mempengaruhi proses evalusi, yaitu :
a. kemampuan organisme untuk melakuan reproduksi
b. keberafaan populasi organisme yang bisa melakukan reproduksi
c. keberagamaan organisme dalam suatu populasi
d. perbedaan kemampuan untuk survive
Individu yang lebih kuat (fit) akan memiliki tingkat survival adan tingkat
reproduksi yang lebih tinggi jika dibandingkan dengan individu yang kurang fit. Pada
kurun waktu tertentu (sering dikenal dengan istilah generasi), populasi secara
keseluruhan akan lebih banyak memuat organisme yang fit.
Algoritma genetik pertama kali dikembangkan oleh John Holland dari Universitas
Michigan (1975). John Holan mengatakan banyak setiap masalah yang berbentuk
adaptasi (apami maupun buatan) dapat diformulasikan dalam terminologi genetika.
Algoritma genetika adalah simulasi dari proses evaluasi Darwin dan operasi genetika atas
kromosom.
II. STRUKTUR UMUM ALGORITMA GENETIKA
Pada algoritma ini, teknik pencarian dilakuan sekaligus atas sejumlah solusi yang
mungkin yang dikenal dengan istilah populasi. Indivu yang terdapat dalam satu populasi
disebut dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih
berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya
merupakan hasil evaluasi kromosom-kromosom melalui interasi yang disebut dengan
istilah generasi. Pada setiap genrasi, kromosom akan melalui proses evaluasi dengan
menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dari suatu
kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut. Generasi
berikutnya dikenal dengan isitilah anak (offspring) terbentuk dari gabungan 2 kromosom
generasi sekarang yang bertindakn sebagain induk (parent) dengan menggunakan
operator penyilangan (crossover). Selain operator penyilangan, suatu kromosom dapat
juga diomodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru
dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk (parent) dan nilai
fitness dari kromosom anak (offspring), serta menolak kromosom-kromosom yang
lainnya sehingga ukuran populasi (jumlah kromosom dalam suatu populasi) konstan.
Setelah melalui beberapa generasi, maka algoritma ini akan konvegen ke kromosom
terbaik.
III. KOMPONEN –KOMPONEN UTAMA ALGORITMA GENETIKA
Ada 6 komponen dalam algoritma genetika, yaitu :
Teknik penyandian
Teknik penyandian disini meliputi penyandian gen dari kromosom. Gen merupakan
bagian dari kromosom. Satu gen biasanya akan mewakili satu variabel. Gen dapat
direpresentasikan dalam bentuk, string bit, pohon , array bilangan real, daftar aturan,
elemen permutasi, elemen program, atau representasi lainnya yang dapat
dimplementasikan untuk operator genetika. Gambar algorotma genetika
GAMBAR
Demikian juga, kromosom dapat direpresentasikan dengan menggunakan :
- String bit : 10011,01101,11101,dst
- Bilangan real : 65.65, -67.98, 562.88, dst
- Elemen permutasi : E2, E10, E5, dst
- Daftar aturan : R1, R2, R3, dst
- Elemen program : pemrograman genetika
- Struktur lainnya
Prosedur Inisialisasi
Ukuran populasi tergantung pada masalah yang akan dipecahkan dan jenis operator
genetika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian
harus dilakukan terhadap kromosom yang terdapat pada populasi tersebut. Inisialisasi
kromoson dilakukan secara acak, namun demikian harus tetap memperhatikan domain
solusi dan kendala permasalahan yang ada.
Fungsi Evaluasi
Ada 2 hal yang harus dilakukan dalam melakukan evaluasi kromosom, yaitu: evaluasi
fungsi objektif (fungsi tujuan) dan konversi fungsi objektif ke dalam fungsi fitness.
Secara umum, fungsi fitness diturunkan dari fungsi objective dengan nilai yang tidak
negatif. Apabila ternya fungsi objectif nilai negatif, maka perlu ditambahkan suatu
konstanta C agar nilai fitness yang terbentuk menjadi tidak negatif
Seleksi
Seleksi ini bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi
anggota populasi yang paling fit.
Ada beberapa metode seleksi dari induk, antara lain:
a. Rank-Based fitness assigment
b. Roulette wheel selection
c. Stochastic universal sampling
d. Local selection
e. Truncantion selection
f. Tournament selection
Operator Genetika
Ada 2 operator genetika, yaitu:
a. operator untuk melakukan rekombinasi, yang terdiri dari:
o Rekombinasi bernilai real
Rekombinasi diskret
Rekombinasi intermediate (menengah)
Rekombinasi garis
Rekombinasi garis yang diperluas
o Rekombinasi bernilai biner (crossover)
Crossover satu titik
Crossover banyak titik
Crossover seragam
o Crossover dengan permutasi
b. Mutasi
o Mutasi bernilai real
o Mutasi bernilai biner
Penentuan Parameter
Yang disebut dengan parameter disini adalah parameter kontrol algoritma genetika, yaitu:
ukuran populasi (popsize), peluang crossover(Pc), dan peluang mutasi (Pc). Nilai
parameter ini ditentukan juga berdasarnya permasalahan yang akan dipercahkan. Ada
beberapa rekomendasi yang bisa digunakan, antara lain:
Untuk Permasalahan yang memiliki kawasan solusi cukup bersar, De Jong
merekomendasikan untuk nilai parameter kontrol:
(popsize;Pc;Pm) = (50;0.6;0,001)
Bila rata rata fitness setiap generasi digunakan sebagai indikator , maka Grefenstette
merekomendasikan:
(popsize;Pc;Pm) = (30;0,95;0,01).
Bila fitness dari individu terbaik dipantau pada setiap generasi, maka usulannya
adalah:
(popsize;Pc;Pm) = (80;0,45;0,01
Ukuran populasi sebaiknya tidak lebih kecil dari 30, untuk sembarang jenis
permasalahan
SELEKSI
Seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan
rekombinasi dan bagaimana offspring terbentuk dari individu-individu terpilih tersebut.
Langkah pertama yang dilakukan dalam seleksi ini adalah pencarian nilai fitness.
Masing-masing individu dalam suatu wadah seleksi akan menerima probilitas reproduksi
yang tergantung pada nilai objektif dirinya sendiri terhadap nilai objektif dari semua
individu dalam wadah seleksi tersebut. Nilai fitness inilah yang nantinya akan digunakan
pada tahap-tahap seleksi berikutnya
Ada beberapa definsi yang bisa digunakan untuk melakukan perbandingan terhadap
beberapa metode yang akan digunakan, antara lain:
Selective pressure: probilitas dari individu terbaik yang akan diselelksi dibandingkan
dengan rata-rata probabilitas dari semua individu yang diseleksi
Bias: perbedaan absolut antara fitness ternormalisasi dari suatu individu dan
probabilitas reproduksi yang diharapakan
Spread: range nilai kemungkinan untuk sejumlah offspring dari suatu individu
Loss of diversity: proporsi dari individu-individu dalam suatu populasi yang tidak
terseleksi selama fase seleksi
Selection intensity: nilai fitness rata-rata yang diharapkan dalam suatu populasi
setelah dilakukan seleksi(menggunakan distribusi gauss ternormalisasi).
selection variance: variansi yang diharapkan dari distribusi fitness dalam populasi
setelah dilakukan seleksi (menggunakan distribusi gauss ternormalisasi).
Rank-based Fitness
Pada rank-based fitness, populasi diurutkan menurut nilai objektifnya. Nilai fitness dari
tiap-tiap individu hanya tergantung pada posisi individu tersebut tersebut dalam urutan,
dan tidak dipengaruhi oleh nilai objektifnya.
Misalkan N adalah jumlah individu dalam suatu populasi. Pos adalah posisi individu
dalam populasi tersebut(posisi terendah suatu individu adalah Pos=1, dan posisi
tertingginya adalah pos=N). sedang SP adalah selective pressure. Nilai fitness dari suatu
individu dapat dihitung sebagai
Linear ranking
Fitness(pos)= 2 – SP + 2 (SP-1)(pos-1)(N-1) Nilai SpE[1,2]
Non-linear ranking
Fitness(pos)=Nind * X^(Pos-1)sum(X^(i-1));i=1..N..
Sedangkan X dihitung Sebagai akar polinomial:
(SP-1)*X^(N-1)+SP*X^(N-2)+…+SP*X+SP=0
Nilai SpE
Seleksi Roda Roulette(Roulette Wheel Selection)
Metode seleksi roda roulette ini merupakan motode yang paling sederhana, dan sering
juga dikenal dengan nama stochastic sampling with replacement. Pada metode ini,
individu-individu dipetakkan dalam suatu segmen garis secara berurutan sedemikian
hingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran fitness-nya.
Sebuah bilangan random dibangkitkan dan individu yang memiliki segmen dalam
kawasan bilangan random tersebut akan terseleksi. Proses ini diulang hingga diperoleh
sejumlah individu yang diharapkan.
Pada Tabel 9.1 Menunjukkan probabilitas seleksi dari 11 individu. Individu pertama
memiliki fitness terbesar, dengan demikian dia juga memiliki interval terbesar.
Sedangkan individu ke-10 memiliki fitness terkecil kedua. Individu ke-11 memiliki
fitness terkecil (=0), interval terkecil sehingga tidak memiliki kesempatan untuk
melakukan reproduksi.
Setelah dilakukan seleksi, maka individu-individu yang terpilih adalah:
1 2 3 5 6 9
Stocastic Universal Sampling
Stocastic universal sampling memiliki nilai bias nol dan penyebaran yang minimum.
Pada metode ini, individu-individu dipetakan dalam suatu segmen garis secara berurutan
sedemikian hingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran
fitnessnya seperti halnya pada seleksi roda roulette. Kemudian diberikan sejumlah pointer
sebanyak individu yang ingin diseleksi di pada garis tersebut. Andaikan N adalah jumlah
individu yang akan diseleksi, maka jarak antara pointer adalah 1/N, dan posisi pointer
pertama diberikan secara acak pada range (1,1/N)
Apabila ada 6 individu yang akan diseleksi, maka jarak antara ponter adalah 1/6 = 0.167
(Gambar 9.3) sehingga, misalkan bilangan random yang dibangkitkan pada (0,0.167)
adalah 0,1, maka hasil yang diperoleh setelah seleksi adalah :
Seleksi Lokasl (Local Selection)
Pada seleksi lokal, setiap individu yang berada di dalam konstrain tertentu disebut dengan
nama lingkungan lokal. Interaksi antar individu hanyak dilakukan di dalam wilayah
tersebut. Lingkungan tersebut ditetapkan sebagai struktur dimana populasi tersebut
terdistribusi. Lingkungan tersebut juga dapat dipandang sebagai kelompok pasangan-
pasangan yang potensial.
Gambar 9.4 menunjukkan seleksi lokal, dalam lingkungan linear (full & half ring)
Algoritma Genetika
GAMBAR
Langkah pertama adalah menyeleksi saparo pertama dari populasi yang berpasangan
secara random (atau menggunakan salah satu metode yang sudah dijelaskan sebelumnya,
seperti : stochastic universal sampling). Kemudian lingkungan baru tersebut diberikan
pada setiap individu yang terseleksi. Pada lingkungan yang baru tersebut. Kita bisa
menyeleksi pasangan-pasangan yang cocok (pasangan yang terbaik, pasangan yang
memiliki fitness proporsional, atau pasangan yang seragam). Struktur lingkungan pada
seleksi lokal ini dapat berbentuk :
Liner : full ring dan half ring (gambar 9.4)
Dimensi -2:
- Full cross dan half cross (gambar 9.5)
- Full star dan half star (gambar 9.6)
Dimensi -3 dan struktur yang lebih kompleks yang merupakan kombinasi dari kedua
struktur di atas
Jarakan antara individu dengan struktur tersebut akan sangat menentukan ukuran
lingkungan (jumlah tentagga dari suatu individu). Hal ini dapat dilihat pada tabel 9.2.
jarak antara satu individu dengan individu yang lain tentu saja akan terbatas oleh ukuran
lingkungan suatu individu. Individu yang terdapat dalam lingkungan dengan ukuran yang
lebih kecil. Tentu saja akan lebih terisolasi jika di bandingkan dengan individu yang
terletak pada lingkungan yang ukuran yang lebih besar.
Tabel 9.2 jumlah tetangga (ukuran lingkungan) untuk seleksi lokal.
StrukturJarak
1 2
Full ring 2 4
Half ring 1 2
Full cross 4 8(12)
Half cross 2 4 (5)
Full star 8 24
Half star 3 8
9.4.5 Seleksi dengan Pemotongan (Truncation Selection)
Pada metode-metode seleksi yang telah dijelaskan terdahulu, seleksi dilakukan secara
alami. Pada seleksi dengan pemotongan ini lebih berkesan sebagai seleksi buatan. Seleksi
ini biasanya digunakan oleh populasi yang jumlahnya sangat besar. Pada metode ini,
individu diurutkan berdasarkan nilai fitnessnya. Hanya individu-individu yang terbaik
saja yang akan diseleksi sebagai induk. Parameter yang digunakan dalam metode ini
adalah suatu nilai ambang trunc yang mengindikasikan ukuran yang populasi yang akan
diseleksi sebagai induk yang berkisar antara 50%-10%. Individu-individu yang ada di
bawah nilai ambang ini tidak akan menghasilkan keturunan.
9.4.6 Seleksi dengan Turnamen (ournament Selection)
Pada metode seleksi dengan turnamen ini, akan ditetapkan suatu nilai tour untuk
individu-individu ang dipilih secara random dari suatu populasi. Individu-individu yang
terbaik dalam kelompok ini akan diseleksi sebagai induk. Para meter yang digunakan
pada metode ini adalah ukuran toru yang bernilai antara 2 sampai N (jumlah individu
dalam suatu populasi)
9.5 REKOMBINASI
9.5.1 Rekombinasi Diskret
Rekomenbinasi diskret akan menukar nilai variabel antar kromosom induk.
Misalkan ada 2 individu dengan 3 variabel, yaitu :
induk 1 ; 12 25 5
induk 2 ; 123 4 34
Untuk tiap-tiapvariabel induk yang menyumbangkan variabelna ke anak dipilih
secara random dengan probalitas yang sama
Sampel 1 : 2 2 1
Sampel 2 : 1 2 1
Setelah rekombinasi, krmosom-kromosom baru yang terbentuk :
Anak 1 : 123 4 5
Anak 2 : 12 4 5
Gambar 9.7 menunjukkan posisi yang mungkin dari anak setelah rekomendasi
diskret.
Anak yang mungkin
induk
Variabel-1
Gambar 9.7 Rekombinasi diskret
Rekombinasi ini dapat digunakan untuk sembarang variabel (biner, real, atau simbol)
9.5.2 Rekombinasi Menengah
Rekombinasi menengah merupakan metode rekombinasi yang hanya dapat
digunakan untuk variabel real ( dan variabel yang bukan biner). Nilai variabel anak
dipilih di sekitar dan antara nilai-nilai bariabel induk.
Anak dihasilkan menurut aturan sebagai berikut :
Anak – induk 1 + alpha (induk 2 – induk 1)
Dengan alpha adalah faktor skala yang dipilih secara random pada interval (-d, 1
+ d), biasanya d = 0.25 . tiap-tiap variabel pada anak merupakan hasil kombinasi
variabel-variabe menurut aturan diatas dengan nilai alpha dipilih ulang untuk tiap
variabel
induk 1 induk 2
area induk
area anak yang mungkin
0.25 0 1 1.25
Gambar 9.8 Are induk & anak pada rekombinasi menengah
Gambar 9.8 menunjukkan area induk dan anak yang mungkin misalkan ada 2
individu dengan 3 variabel, yaitu:
Induk 1 : 12 25 5
Induk 2 : 123 4 34
Misalkan Nilai alpha yang terpilih adalah:
Sampel 1 : 0,5 1,1 -0,1
Sampel 2 : 0,1 0,8 0,5
Setelah rekombinasi, kromosom-kromosom baru yang terbentuk
Anak 1 : 67,5 1,9 2,1
Anak 2 : 23,1 8,2 19,5
Gambar 9.9 menunjukkan posisi yang mungkin dari anak setelah remondasi
menengah
Rekombinasi ini dapat digunakan untuk sembarang variabel (biner, real, atau
simbol).
9.5.3 Rekombinasi Garis
Pada dasarnya rekombinasi garis ini sama dengan rekombinasi menengah, hanya
saja nilai alpha untuk semua variabel sama. Misalkan ada 2 kromosom dengan 3
variabel, yaitu :
induk 1 : 12 25 5
induk 2 : 123 4 34
untuk tiap-tiap variabel induk yang menyumbangkan variabel induk yang
menyumbangkan variabelnya ke anak dipilih secara random dengan probabilitas
yang sama.
Sampel 1 : 0,5
Sampel 2 : 0,1
Setelah rembinasi, kromosom-kromosom baru yang terbentuk
Anak 1 : 67,5 14,5 19,5
Anak 2 : 23,1 22,9 7,9
Gambar 9.10 menunjukkan posisi yang mungkin dari anak setelah rekomendasi
garis.
9.5.4 Penyilangan satu titik (single-point crossover)
Pada Penyilangan 1 titik, posisi penyilangan K (k=1,2….,N-1) dengan N=Panjang
kromosom diseleksi secara random. Variabel-variabel ditukan antar kromosom
pada titik tersebut untuk mengasilkan anak (gambar 9.11)
Misalkan ada 2 Kromosom dengan panjang 12
Induk 1 : 0 1 1 1 0 | 0 1 0 1 1 1 0
Induk 2 : 1 1 0 1 0 | 0 0 0 1 1 0 1
Posisi penyilangan yang terpilih: misalkan 5
Setelah penyilangan, diperoleh kromosom-kromosom baru :
Anak 1 : 0 1 1 1 0 | 0 0 0 1 1 0 1
Anak 2 : 1 1 0 1 0 | 0 1 0 1 1 1 0
9.5.5 Penyilangan Banyak titik (Multi-point crossover)
Pada penyilangan banyak titik, m posisi penyilangan Ki (k=1,2,...,N-1,1=1,2,...,m)
dengan n=panjang kromosom deseleksi secara random dan tidak diperbolehkan
ada posisi yang sama, serta diurutkan naik. Variabel-variabel ditukarkan antar
kromosom pada titik tersebut untuk menghasilkan anak (gambar 9.12)
Misalkan ada 2 kromosom dengan panjang 12:
Induk 1 : 0 1 1 1 0 0 1 0 1 1 1 0
Induk 2 : 1 1 0 1 0 0 0 0 1 1 0 1
Posisi penyilangan yang terpilih:
Misalkan (m=3): 2 6 10
Setelah penyilangan, diperoleh kromosom-kromosom baru:
Anak 1 : 0 1 | 0 1 0 0 | 1 0 1 1 | 0 1
Anak 2 : 1 1 | 1 1 0 0 | 0 0 1 1 | 1 0
9.5.6 Penyilangan seragam (Uniform Crossover)
Pada penyilangan seragam, setiap lokasi memiliki potensi sebagai tempat
penyilangan. Sebuah mask penyilangan dibuat sepanjang panjang krosom secara
random yang menunjukkan bit-bit dalam mask yang mana induk akan mensupply
anak dengan bit-bit yang ada.
Induk mana yang akan menyumbangkan bit ke anak dipilih secara random dengan
probabilitas yang sama. Tiap-tiap variabel induk yang akan. Disini, anak_1 akan
dihasilkan dari induk_1 jika bit mask bernilai 1, atau sebaliknya, anak_1 akan
dihasilkan dari induk_2 jika bit mask bernilai 0. sedangkan anak_2 dihasilkan dari
kebalikan mask.
Misalkan ada 2 krosom dengan panjang 12:
Induk 1 : 0 1 1 1 0 0 1 0 1 1 1 0
Induk 2 : 1 1 0 1 0 0 0 0 1 1 0 1
Mask bit:
Sampel 1 : 1 0 0 1 1 1 0 0 1 1 0 1
Sampel 2 : 0 1 1 0 0 0 1 1 0 0 1 0
Setelah penyilngan, diperoleh kromosom-kromosom baru:
Anak 1 : 0 1 0 1 0 0 0 0 1 1 0 0
Anak 2 : 1 1 1 1 0 0 1 0 1 1 1 1
9.5.7 Penyilangan dengan bermutasi (permutation Crossover)
Pada penyilangan dengan permutasi ini, kromosom-kromosom anak diperoleh
dengan cara memilih sub-barisan suatu tour dari satu induk tetap menjaga urutan
dan posisi sejumlah kota yang mungkin terhadap induk yang lainnya.
Misal:
induk 1 : (1 2 3 | 4 5 6 7 | 8 9)
induk 2: (4 5 3 | 1 8 7 6 | 9 2)
anak 1 : (x x x | 1 8 7 6 | x x)
anak 2 : (x x x | 4 5 6 7 | x x)
dari sini kita memperoleh pemetaan:
1 – 4 , 8 – 5 , 6 – 6 , 6 - 7
Kemudian kita copy sisa gen di induk-1 ke anak-1 dengan mengguna-kan
pemetaan yang sudah ada.
Anak 1: (1-4 2 3 | 1 8 7 6 |8-5 9)
Anak 2: (4 2 3 | 1 8 7 6 |5 9)
Lakukan hal yang sama untuk anak ke 2
Anak 2 : (4-1 5-8 3 | 4 5 6 7 | 9 2)
Anak 2 : (1 8 3 | 4 5 6 7 | 9 2)
9.6 MUTASI
Setelah mengalami proses rekombinasi, pada offspring dapat dilakukan mutasi. Variabel
osspring dimutasi. Peluang mutasi mengendalikan banyaknya gen baru yang akan
dimunculkan untuk evaluasi. Jika peluang mutas terlalu kecil, banyak gen yang mungkin
berguna tidak pernah dievaluasi. Tetapi bila peluang mutasi ini terlalu besar, maka akan
terlalu banyak gangguan acak, sehingga anak akan kehilangan kemiripan dari induknya,
dan juga algoritma akan kehilangan kemampuan untuk belajar dari histori pencarian. Ada
beberapa pendapat mengenai laju mutasi ini. Ada yang berpendapat bahwa, laju mutasi
sebesar 1/n akan memberikan hasil yang cukup baik. Ada juga yang beranggapan bahwa
laju mutasi tidak tergantung pada ukuran populasinya. Kromosom hasil mutasi harus
diperiksa, apakah berada pada domain solusi, dan bila perlu bisa dilakukan perbaikan.
Mutasi ini berperan untuk menggantikan gen yang hilang dari populasi akibat proses
seleksi yang memungkirkan munculnya kembali gen yang tidak muncul pada inisialisasi
populasi
9.6.1 Mutasi Bilangan Real
Pada mtasi bilangan real. Ukuran langkah mutasi biasanya sangat sulit ditentukan.
Ukuran yang kecil biasanya sering mengalami kesuksesan, namun adakalanya ukuran
yang lebih besar akan berjalan lebih cepat.
Operator mutasi untuk bilangan real ini dapat ditetapkan sebagai :
Variabel yang dimutasi = variabel + range *delta; (+ atau – memiliki probalitas yang
sama)
Range = 0.5 * domain variabel : (interval pencarian)
Delta= (ai*2-i); ai = 1 dengan probanilitas 1/m, selain itu ai = 0, dengan m=20
9.6.2 Mutasi Biner
Cara sederhana untuk mendapatkan mutasi biner adalah dengan mengganti satu atau
beberapa nilai gen dari kromosom. Langkah-langkah mutasi ini adalah :
Hitung jumlah gen pada populasi (panjang kromosom dikalikan dengan ukuran
populasi)
Pilih secara acak gen yang akan dimutai
Tentukan kromosom dari gen yang terpilih untuk dimutasi
Ganti nilai gen (0 ke 1, atau 1 ke 0) dari kromosom yang akan dimutasi tersebut.
9.7 ALGORITMA GENETIKA SEDERHANA
Misalnya P ( generasi) adalah populasi dari satu generasi, maka secara sederhana
algoritma genetika terdiri dari langkah-langkah.
1. Generasi = 0 (generasi awal)
2. Inisialisasi populasi awal, p (generasi), secara acak
3. evaluasi nilai fitness pada setiap individu dalam P (generasi)
4. Kerjakan langkah-langkah berikut hingga generasi mencapai maksimum generasi :
a. generasi = generasi + 1 (tambah generasi)
b. Seleksi populasi tersebut untuk mendapatkan kandidat induk , P (generasi)
c. Lakukan crossover pada P’(generasi)
d. Lakukan mutasi pada p’(generasi)
e. Lakukan evaluasi fitness setiap individu pada P’(generasi)
f. Bentuk populasi baru P (generasi) = {P(generasi-1) yang survive, P’ (generasi)}
9.7.1 Metode Seleksi dengan Roda Roulette
Seperti telah djelaskan di depan bahwa seleksi induk dengan menggunakan roda roulette
metode seleksi yang paling sering digunakan. Seleksi ini bertujuan untuk memberikan
kesempatan reproduksi yang lebih besar bagi anggota populasi yang memiliki fitness
tinggi untuk melakukan reproduksi.
Algoritma seleksi roda roulette :
1. Hitung total fitness (F) :
Totfintness = Fk ; k = 1, 2, ....., popsize
2. Hitung fitness realitif tiap individu ;
Pk = Fk / total fitness
3. Hitung fitness komulatif ;
q1 = p1
qk = qk – 1 + pk ; k = 2, 3, ….., popsize
4. Pilih induk yang akan menjadi kandidat untuk di-crossover dengan cara ;
Bangkitkan bilangan random r.
Jika qk < r dan qk + 1 > r, maka pilih kromosom ke ( k + 1) sebagai kandidat induk
9.7.2 Crossover
Crossover (penyilangan) dilakukan atas 2 kromosom untuk menghasilkan kromosom
anak (offspring). Kromosom anak yang terbentuk akan mewarisi sebagian sifat
kromosom induknya. Metode crossover yang paling sering digunakan pada algoritma
genetika sederhana dengan kromosom berbentuk string biner adalah crossover satu titik
(one-point crossover). Seperti telah dijelaskan sebelumnya, pada metode ini, kita pilih
sembarang bilangan secara acak untuk menentukan posisi persilangan. Kemudian kita
tukarkan bagian kanan titik potong dari kedua induk kromosom tersebut untuk
menghasilkan kromosom anak
Misalnya
V1 ‘ = 1 0 1 0 0 1 1 0
V2 ‘ = 0 1 0 1 0 1 0 0
Apabila posisi titik potong yang terpilih secara acak adalah 3, maka kromosom anak yang
terbentuk adalah :
V1 ‘ = 1 0 1 1 0 1 0 0
V2 ‘ = 0 1 0 0 0 1 1 0
Pada crossover ada satu parameter yang sangat penting, yaitu peluang crossover ( p c).
Peluang crossover menunjukkan rasio dari anak yang dihasilkan dalam setiap generasi
dengan ukuran populasi. Misalkan ukuran populasi (popsize=100), sedangkan peluang
crossover (Pc=0,25), berarti bahwa diharapkan ada 25 kromosom dari 100 kromosom
yang ada pada populasi tersebut akan mengalami crossover
9.7.3 Mutasi
Mutasi yang digunakan pada algoritma genetika sederhana dengan kromosom biner
seperti telah dijelaskan sebelumnya, pada dasarnya akan mengubah secara acak nilai
suatu bit pada posisi tertentu. Kemudian kita mengganti bit 1 dengan 0, atau mengganti
bit 0 dengan 1. pada mutasi ini sangat dimungkinkan munculkan kromosom baru yang
semula muncul dalam populasi awal
Misalkan:
V1 ‘ = 1 0 1 0 0 1 1 0
Terkena mutasi pada gen ke-5, diperoleh:
V2 ‘ = 1 0 1 0 1 1 1 0
Pada Mutasi ada satu parameter yang sangat penting yaitu peluang crossover (Pm).
Peluang mutasi menunjukkan prosentasi jumlah total gen pada populasi yang akan
mengalami mutasi. Untuk melakukan mutasi, terlebih dahulu kita harus menghitung
jumlah total gen pada populasi tersebut. Kemudian bangkitkan bilangan random yang
akan menentukan posisi mana yang akan dimutasi (gen keberapa pada kromosom
keberapa). Misalkan ukuran populasi (popsize=100), setiap kromosom memiliki panjang
20 gen, maka total gen adalah 100x20=2000 gen. jika peluang mutasi (pm=0,01), berarti
bahwa diharapkan ada (1/100)x2000 = 20 gen akan mengalami mutasi.
Secara umum, diagram alir algoritma genetika sederhana seperti terlihat pada gambar
9.13