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