Algoritma Genetika
Algoritma Genetika
Bismillahirrahmanirrahiim. Assalamualaikum, wr. wb.
Puji dan syukur senantiasa kita panjatkan kehadirat
Allah SWT, shalawat serta salam semoga senantiasa dilimpahkan kepada Nabi
Muhammad SAW, juga untuk para keluarga, sahabat dan pengikutnya sampai akhir
zaman. Karena atas rahmat-Nya, penyusun dapat menyelesaikan penyusunan makalah
ini yang berjudul “Algoritma Genetika”.
Makalah ini disusun untuk memenuhi tugas mata kuliah
“Kecerdasan Buatan”. Penyusun mengucapkan terimakasih kepada Bapak Victor
Amrizal, MKom. selaku dosen pengampu, teman-teman dan semua pihak yang membantu
dalam penyelesaian karya tulis ini.
Penyusun berharap makalah ini dapat menambah pengetahuan
pembaca dan memberikan gambaran mengenai materi terkait yaitu Algoritma
Genetika. Sehingga pembaca dapat menggunakan makalah ini sebagai literatur
pendukung dalam pengembangan bidang ilmu selanjutnya yang terkait dengan
penggunaan algoritma genetika.
Penyusun menyadari bahwa makalah ini masih jauh dari
kesempurnaan, maka penyusun mengharapkan saran dan kritik yang membangun untuk
perbaikan makalah ini. Besar harapan penyusun agar penulisan makalah ini dapat
berguna bagi siapapun yang menjadikan makalah ini sebagai bahan literatur
mengenai materi terkait.
Wassalamualaikum,
wr. wb.
Penyusun
BAB I PENDAHULUAN
I.1
Latar Belakang
Kehidupan merupakan suatu kesatuan dari
kejadian-kejadian dinamis yang bisa jadi merupakan suatu masalah ataupun solusi
atas kemungkinan-kemungkinan masalah yang akan terjadi. Dinamisnya kehidupan
menuntut siapa saja yang berada di dalamnya untuk menjadi lebih kebal terhadap
keadaan buruk suatu kejadian. Pemilihan tindakan sudah sebagaimana mestinya
haruslah memenuhi kriteria sebuah solusi sehingga pemecahan masalah benar-benar
didapatkan pada akhirnya.
Seperti proses evolusi yang mutlak terjadi sebagai bentuk representasi kehidupan yang mengharuskan siapapun menjadi
lebih kebal secara genetika sehingga dapat melewatkan proses seleksi alam yang
terjadi. Dimana yang lebih kuatlah yang mampu bertahan, sehingga yang kuat
itulah yang merupakan suatu kualitas solusi optimal dari sebuah masalah.
Terinspirasi dari kehidupan dan seleksi alam yang terjadi di dalamnya,
algoritma genetika kemudian dikembangkan sebagai bentuk algoritma khusus yang
digunakan dalam mencari solusi optimal terhadap masalah yang diangkat dengan
teknis yang disesuaikan dengan proses evolusi.
[1]
I.2
Tujuan Penulisan
Makalah ini disusun bertujuan
untuk :
1.
Mengetahui dan memahami mengenai algoritma genetika
2.
Memahami teknis kerja
algoritma genetika sampai mendapatkan solusi optimal dari masalah yang diangkat.
I.3
Manfaat Penulisan
Penyusunan makalah ini diharapkan dapat memberikan
kontribusi dalam menambah wawasan, pengetahuan, dan pemahaman mengenai
algoritma genetika.
I.4
Metodologi Penulisan
Penyusunan makalah dilakukan dengan metode analisis
literatur mengenai materi algoritma genetika yang didapatkan dari internet dan
buku teks.
BAB II LANDASAN TEORI
II.1
Sejarah Algoritma Genetika
Algoritma genetika pertama kali ditemukan oleh Jhon
Holland dari Universitas Michigan pada awal 1970-an di New York, Amerika
Serikat. Jhon Holland bersama murid- muridnya serta rekan kerjanya lalu
menghasilkan buku yang berjudul “Adaption
in Natural and Artificial Systems” pada tahun 1975, yang cara kerjanya
berdasarkan pada seleksi dan genetika alam. Konsep yang dipergunakan dalam
algoritma genetika adalah mengikuti apa yang dilakukan oleh alam. [2]
Algoritma genetik khususnya diterapkan sebagai simulasi
komputer dimana sebuah populasi representasi abstrak (kromosom) dari
solusi-solusi calon (individual) pada sebuah masalah optimisasi akan berkembang
menjadi solusi-solusi yang lebih baik. Secara tradisional solusi-solusi
tersebut dilambangkan dalam biner sebagai string '0' dan '1', walaupun
dimungkinkan juga penggunaan penyandian (encoding)
yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap
dan terjadi dalam generasi- generasi. Dalam tiap generasi kemampuan keseluruhan
populasi dievaluasi, kemudian multiple
individuals dipilih dari populasi sekarang (current) secara stochastic (berdasarkan
kemampuan mereka) lalu dimodifikasi (dengan mutasi atau rekombinasi) menjadi
bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.
II.2
Aplikasi Algoritma Genetika
Algoritma genetika sudah banyak digunakan pada masalah
praktis yang berfokus pada pencarian parameter-parameter atau solusi yang optimal.
Hal ini membuat banyak orang mengira bahwa algoritma genetika hanya dapat
digunakan untuk menyelesaikan masalah optimasi saja. Namun, pada kenyataanya
algoritma genetika juga memiliki kemampuan untuk menyelesaikan masalah-masalah
selain optimasi. Algoritma genetika banyak diaplikasikan untuk berbagai macam
permasalahan, yaitu :
1. Optimasi
Beberapa
penggunaan algoritma genetika untuk optimasi antara lain untuk optimasi numerik
dan optimasi kombinatorial seperti Traveling
Salesmen Problem (TSP),
Perancangan
Integrated Circuit atau IC, Job Scheduling, dan Optimasi video dan
suara.
2. Pemrograman Otomatis
Algoritma genetika untuk pemrograman otomatis antara lain untuk melakukan
proses evolusi terhadap program komputer dalam merancang struktur
komputasional, seperti cellular automata dan
sorting networks.
3. Machine
Learning
Algoritma genetika juga telah berhasil diaplikasikan untuk memprediksi
struktur protein. Algoritma genetika juga berhasil diaplikasikan dalam
perancangan neural networks (jaringan
syaraf tiruan) untuk melakukan proses evolusi terhadap aturan- aturan pada learning classifier system atau symbolic production system dan dapat
digunakan untuk mengontrol robot.
4. Model Ekonomi
Dalam bidang ekonomi, algoritma genetika digunakan untuk memodelkan
proses- proses inovasi dan pembangunan bidding
strategies.
5. Model
Sistem Imunisasi
Contoh penggunaan algoritma genetika dalam bidang ini untuk memodelkan
berbagai aspek pada sistem imunisasi alamiah, termasuk somatic mutation selama kehidupan individu dan menemukan keluarga
dengan gen ganda (multi gen families)
sepanjang waktu evolusi.
6. Model Ekologis
Algoritma genetika juga dapat digunakan untuk memodelkan fenomena
ekologis seperti host-parasite co
evolutions, simbiosis dan aliran sumber di dalam ekologi.
II.3
Keuntungan Menggunakan
Algoritma Genetika
Keuntungan penggunaan algoritma genetika terlihat dari
kemudahan implementasi dan kemampuannya untuk menemukan solusi yang optimal dan
bisa diterima secara cepat untuk masalah-masalah berdimensi tinggi. Algoritma
Genetika sangat berguna dan efisien untuk masalah dengan karakteristik sebagai
berikut :
·
Ruang masalah sangat besar, kompleks, dan sulit dipahami,
·
Kurang atau bahkan tidak ada
pengetahuan yang memadai untuk merepresentasikan masalah ke dalam ruang
pencarian yang lebih sempit,
·
Tidak tersedianya analisis matematika yang memadai,
·
Ketika metode-metode
konvensional sudah tidak mampu menyelesaikan
masalah yang dihadapi,
·
Solusi yang diharapkan tidak
harus paling optimal, tetapi cukup “bagus” atau bisa diterima,
·
Terdapat batasan waktu, misalnya dalam real time system atau sistem waktu
nyata.
BAB III PEMBAHASAN
III.1
Pengertian Algoritma Genetika
Algoritma genetika adalah algoritma komputasi yang
diinspirasi teori evolusi yang kemudian diadopsi menjadi algoritma komputasi
yang biasa digunakan untuk memecahkan suatu pencarian nilai dalam sebuah
masalah optimasi. Algoritma ini didasarkan pada proses genetik yang ada dalam
makhluk hidup; yaitu perkembangan generasi dalam sebuah populasi yang alami,
secara lambat laun mengikuti prinsip seleksi alam atau “siapa yang kuat, dia
yang bertahan (survive)”. Dengan
meniru teori evolusi ini, algoritma genetika dapat digunakan untuk mencari
solusi permasalahan-pemasalahan dalam dunia nyata.
Ada 4 kondisi yang sangat
mempengaruhi proses evolusi, yaitu :
1.
Kemampuan organisme untuk melakukan reproduksi,
2.
Keberadaan populasi organisme yang bias
melakukan reproduksi,
3.
Keberagaman organisme dalam suatu populasi dan
4.
Perbedaan kemampuan untuk survive. [3]
 |
Gambar 1 - Flowchart
Algoritma Genetika [4]
III.2
Struktur Umum Algoritma Genetika
Algoritma genetika memiliki struktur umum, antara lain :
·
Populasi, istilah pada
teknik pencarian yang dilakukan sekaligus atas sejumlah kemungkinan solusi.
·
Kromosom, individu yang
terdapat dalam satu populasi dan merupakan suatu solusi yang masih berbentuk simbol.
·
Generasi, populasi awal
dibangun secara acak sedangkan populasi selanjutnya merupakan hasil evolusi
kromosom-kromosom melalui iterasi.
·
Fungsi Fitness, alat ukur yang digunakan untuk proses evaluasi kromosom. Nilai fitness dari
suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut.
·
Generasi berikutnya dikenal
dengan anak (offspring) yang terbentuk dari gabungan dua kromosom
generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilang (crossover).
·
Mutasi, operator untuk memodifikasi kromosom.
III.3
Komponen Utama Algoritma Genetika
Dalam algoritma genetika
terdapat enam komponen utama, yaitu :
1.
Teknik Penyandian
Teknik penyandian meliputi penyandian gen dari kromosom. Gen merupakan
bagian dari kromosom, satu gen biasanya mewakili satu variable. Gen dapat
direpresentasikan dalam bentuk : string bit, pohon, array bilangan real, daftar
aturan, elemen permutasi, elemen program dan
lain-lain.
2.
Prosedur Inisialisasi
Ukuran populasi tergantung pada permasalahan yang akan dipecahkan
dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran
populasi telah ditentukan, kemudian harus dilakukan inisialisasi terhadap
kromosom yang terdapat pada populasi tersebut. Inisialisasi kromosom dapat
dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi
dan kendala permasalahan yang ada.
3.
Fungsi Evaluasi
Ada dua hal yang harus dilakukan dalam melakukan evaluasi kromosom yaitu
: evaluasi fungsi objektif dan konversi fungsi objektif kedalam fungsi fitness
4.
Seleksi
Memiliki tujuan untuk memberikan kesempatan reproduksi yang lebih besar
bagi anggota populasi yang paling fit. Seleksi
akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan
rekombinasi dan bagaimana offspring terbentuk
dari individu-individu terpilih tersebut. Langkah pertama yaitu pencarian nilai
fitness. Langkah kedua adalah nilai fitness yang diperolah digunakan pada
tahap- tahap seleksi selanjutnya.
Ada beberapa definisi yang bisa digunakan untuk melakukan perbandingan
terhadap beberapa metode yang akan digunakan, antara lain :
·
Selective Pressure : probabilitas dari individu terbaik yang akan
diseleksi dibandingkan dengan rata-rata probabilitas dari semua individu yang diseleksi.
·
Bias : perbedaan absolut antara fitness ternormalisasi dari suatu
individu dan probabilitas reproduksi yang diharapkan.
·
Spread : range nilai
kemungkinan untuk sejumlah offspring dari
suatu individu.
·
Loss of diversity: proposi 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).
Ada beberapa metode seleksi dari
induk, yaitu :
·
Rank-based
fitness assignment
Populasi diurutkan menurut nilai objektifnya. Nilai fitness dari
tiap-tiap individu hanya tergantung pada posisi individu tersebut dalam urutan,
dan tidak dipengaruhi oleh nilai objektifnya.
·
Roulette wheel selection
Istilah lainnya adalah stochastic sampling with replacement.
Individu-individu dipetakan dalam suatu segmen garis secara berurutan
sedemikian hingga tiap- tiap segmen individu memiliki ukuran yang sama dengan
ukuran fitnessnya. Sebuah bilangan random dibangkitkan dan individu yang
memiliki segmen dalam kawasan segmen dalam kawasan bilangan random tersebut
akan terseleksi. Proses ini berulang hingga didapatkan sejumlah individu yang
diharapkan.
·
Stochastic
universal sampling
Memiliki nilai bias nol dan penyebaran yang minimum. Individu-individu
dipetakan dalam suatu segmen garis secara berurut 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 pada garis tersebut. Andaikan N adalah jumlah
individu yang akan diseleksi, maka jarak antar pointer adalah 1/N, dan posisi
pointer pertama diberikan secara acak pada range [1, 1/N].
·
Local selection
Setiap individu yang berada di dalam konstrain tertentu disebut dengan
nama lingkungan lokal. Interaksi antar individu hanya dilakukan di dalam
wilayah tersebut. Lingkungan tersebut ditetapkan sebagai struktur dimana
populasi tersebut terdistribusi. Lingkungan tersebut juda dapat dipandang
sebagai kelompok pasangan-pasangan yang potensial. Langkah pertama yang
dilakukan adalah menyeleksi separuh pertama dari populasi yang berpasangan
secara random. Kemudian lingkungan
baru tersebut diberikan pada setiap individu yang terseleksi.
Struktur lingkungan pada seleksi lokal dapat berbentuk : linear (full ring dan half ring), dimensi-2 (full
cross dan half cross, full star dan half star), dan dimensi-3 dan struktur yang lebih kompleks yang
merupakan kombinasi dari kedua struktur diatas. Jarak antara individu dengan
struktur tersebut akan sangat menentukan ukuran lingkungan. Individu yang
terdapat dalam lingkungan dengan ukuran yang lebih kecil, akan lebih terisolasi
dibandingkan dengan individu yang terletak pada lingkungan dengan ukuran yang
lebih besar.
·
Truncation selection
Merupakan seleksi buatan yang digunakan oleh populasi yang jumlahnya
sangat besar. Individu-individu diurutkan berdasarkan nilai fitnessnya. Hanya
individu yang terbaik saja yang akan diseleksi sebagai induk. Parameter yang
digunakan adalah suatu nilai ambang trunc
yang mengindikasikan ukuran populasi yang akan diseleksi sebagai induk yang
berkisar antara 50% -10%. Individu-individu yang ada dibawah nilai ambang tidak
akan menghasilkan keturunan.
·
Tournament selection
Ditetapkan suatu nilai tour untuk
individu-individu yang dipilih secara random dari suatu populasi.
Individu-individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk.
Parameter yang digunakan adalah ukuran tour
yang bernilai antara 2 sampai N
(jumlah individu dalam populasi).
5.
Operator Genetika
Ada dua operator genetika dalam
algoritma genetika, yaitu :
a.
Operator untuk melakukan rekombinasi, yang
terdiri dari :
i.
Rekombinasi bernilai real, yaitu :
1.
Rekombinasi diskrit :
menukar nilai variabel antar kromosom induk.
2.
Rekombinasi intermediate :
metode rekombinasi yang hanya dapat
digunakan untuk variabel real. Nilai
variabel anak dipilih di sekitar dan antara nilai-nilai variable induk.
3.
Rekombinasi garis : hamper sama dengan rekombinasi
menengah, hanya saja nilai alpha untuk semua
variable sama.
4. Rekombinasi
garis yang diperluas
ii.
Rekombinasi bernilai biner (Crossover), yaitu :
1. Crossover satu titik
2. Crossover banyak titik
3. Crossover seragam
4. Crossover dengan permutasi
b.
Mutasi, yang
terdiri dari :
i.
Mutasi bernilai real
ii.
Mutasi bernilai biner
6.
Penetuan Parameter
Parameter adalah parameter control algoritma genetika, yaitu ukuran
populasi (popsize), peluang crossover (pc)
dan peluang mutasi (pm). Rekomendasi untuk menentukan nilai parameter :
i.
Untuk permasalahan yang
memiliki kawasan solusi cukup besar, De Jong merekomendasikan nilai parameter :
(popsize; pc; pm) = (50;0,6;0,001)
ii.
Bila rata-rata
fitness setiap generasi digunakan sebagai indikator, maka Grefenstette
merekomendasikan : (popsize; pc; pm) = (30;0,95;0,01)
iii.
Bila fitness
dari individu terbaik dipantau pada setiap generasi, maka usulannya adalah :
(popsize; pc; pm) = (80;0,45;0,01)
iv.
Ukuran populasi sebaiknya
tidak lebih kecil dari 30, untuk sembarang jenis permasalahan. [5]
III.4
Hal-Hal Yang Harus
Dilakukan Dalam Algoritma Genetika
Beberapa hal yang harus dilakukan dalam algoritma genetika
adalah :
·
Mendefinisikan individu, dimana individu menyatakan salah satu solusi
(penyelesaian) yang mungkin dari
permasalahan yang diangkat.
·
Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah
individu atau baik-tidaknya solusi yang didapatkan.
·
Menentukan proses pembangkitan populasi awal. Hal ini
biasanya dilakukan dengan menggunakan pembangkitan acak seperti random-walk.
·
Menentukan proses seleksi yang akan digunakan.
·
Menentukan proses perkawinan silang (cross-over) dan mutasi
gen yang akan digunakan. [6]
III.4.1 Pengertian individu
Individu menyatakan salah satu solusi yang mungkin.
Individu bisa dikatakan sama dengan kromosom, yang merupakan kumpulan gen. Gen
ini bisa bersifat biner, float, dan kombinatorial. Beberapa definisi penting
yang perlu diperhatikan dalam mendefinisikan individu untuk membangun
penyelesaian permasalahan dengan algoritma genetika adalah sebagai berikut :
·
Genotype (gen), sebuah nilai
yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu
kesatuan gen yang dinamakan kromosom. Dalam
algoritma
genetika, gen ini bisa brupa nilai biner, float, integer maupun karakter, atau
kombinatorial.
·
Allele, nilai dari gen.
·
Kromosom, gabungan gen-gen yang membentuk
nilai tertentu.
·
Individu, menyatakan satu
nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari
permasalahan yang diangkat.
·
Generasi, menyatakan satu
siklus proses evolusi atau satu iterasi di dalam algoritma genetika. [7]
 |
Gambar 2 - Ilustrasi representasi penyelesaian
permasalahan dalam algoritma genetika
III.4.2 Nilai Fitness
Nilai fitness adalah nilai yang menyatakan baik tidaknya
suatu solusi (individu). Nilai fitness ini yang dijadikan acuan dalam mencapai
nilai optimal dalam algoritma genetika. Algoritma genetika bertujuan mencari
individu dengan nilai fitness yang paling tinggi.
III.4.3 Elitisme
Proses seleksi yang dilakukan secara random sehingga tidak ada jaminan bahwa
suatu indvidu yang bernilai fitness tertinggi akan selalu terpilih. Walaupun
individu bernilai fitness tertinggi terpilih, mungkin saja individu tersebut
akan rusak (nilai fitnessnya menurun) karena proses pindah silang (crossover). Oleh karena itu, untuk
menjaga agar individu bernilaifitness tertinggi tersebut tidak hilang selama
evolusi, maka perlu dibuat satu atau beberapa copy-nya. Prosedure ini dikenal sebagai elitisme. [8]
III.5
Hal-Hal Yang Harus Diperhatikan
Dalam Pemakaian Algoritma Genetika
Beberapa hal yang perlu
diperhatikan dalam pemakaian algoritma genetika adalah :
·
Algoritma genetika adalah
algoritma yang dikembangkan dari proses pencarian solusi menggunakan pencarian
acak, ini terlihat pada proses pembangkitan populasi awal yang menyatakan
sekumpulan solusi yang dipilih secara acak.
·
Berikutnya pencarian
dilakukan berdasarkan proses-proses teori genetika yang memperhatikan pemikiran
bagaimana memperoleh individu yang
lebih baik, sehingga dalam proses evolusi dapat diharapkan diproleh individu yang terbaik.
III.6
Contoh Pemakaian Algoritma Genetika
Kita
akan membahas sebuah contoh aplikasi algoritma genetika yang digunakan untuk
menyelesaikan masalah kombinasi. Misalkan ada persamaan :
“a + 2b + 3c + 4d = 30”
Kita mencari nilai a,
b, c, dan d yang memenuhi
persamaan diatas. Kita mencoba menggunakan algoritma genetika untuk
menyelesaikan permasalahan diatas. Flowchart dari algoritma genetika untuk
menyelesaikan permasalahan diatas dapat dilihat dibawah ini. [9]
Gambar 3 - Flowchart contoh penggunaan algoritma
genetika
Penjelasan
mengenai langkah-langkah penyelesaian permasalahan dari flowchart diatas
menggunakan algoritma genetika adalah sebagai berikut :
III.6.1 Pembentukan Kromosom
Karena yang dicari adalah nilai a, b, c, d maka variabel
a, b, c, d dijadikan sebagai gen-gen pembentuk kromosom. Batasan nilai variabel
a adalah bilangan integer 0 sampai 30. Sedangkan batasan nilai variabel b, c,
dan d adalah bilangan integer 0 sampai 10.
III.6.2 Inisialisasi
Proses inisialisasi dilakukan dengan cara memberikan
nilai awal gen-gen dengan nilai acak sesuai batasan yang telah ditentukan.
Misalkan kita tentukan jumlah populasi adalah 6, maka :
·
Kromosom[1] = [a;b;c;d] = [12;05;03;08]
·
Kromosom[2] = [a;b;c;d] = [02;01;08;03]
·
Kromosom[3] = [a;b;c;d] = [10;04;03;04]
·
Kromosom[4] = [a;b;c;d] = [20;01;10;06]
·
Kromosom[5] = [a;b;c;d] = [01;04;03;09]
·
Kromosom[6] = [a;b;c;d] = [20;05;07;01]
III.6.3 Evaluasi Kromosom
Permasalahan yang ingin
diselesaikan adalah nilai variabel a, b,
c, dan d yang memenuhi persamaan a + 2b + 3c + 4d = 30,
maka fungsi_objektif yang dapat digunakan untuk mendapatkan solusi adalah
“fungsi_objektif(kromosom) = | (a +
2b + 3c + 4d) – 30 |”
Kita hitung fungsi_objektif dari
kromosom yang telah dibangkitkan :
i. fungsi_objektif(Kromosom[1]) = Abs(( 12 + 2*5 + 3*3 + 4*8 ) - 30)
= Abs((12 + 10 + 9 + 32 ) - 30)
= Abs(63 - 30)
= 33
ii.
fungsi_objektif(Kromosom[2]) = Abs(( 2 + 2*1 + 3*8 + 4*3 ) - 30)
= Abs(( 2 + 2 + 24 + 12 ) - 30)
= Abs(40 - 30)
= 10
iii.
fungsi_objektif(Kromosom[3]) = Abs(( 10 + 2*4 + 3*3 + 4*4 ) - 30)
= Abs(( 10 + 8 + 9 + 16 ) - 30)
= Abs(43 - 30)
= 13
iv.
fungsi_objektif(Kromosom[4]) = Abs(( 20 + 2*1 + 3*10 + 4*6 ) - 30)
= Abs(( 20 + 2 + 30 + 24 ) - 30)
= Abs(76 - 30)
= 46
v.
fungsi_objektif(Kromosom[5]) = Abs(( 1 + 2*4 + 3*3 + 4*9 ) - 30)
= Abs(( 1 + 8 + 9 + 36 ) - 30)
= Abs(54 - 30)
= 24
vi.
fungsi_objektif(Kromosom[6]) = Abs(( 20 + 2*5 + 3*7 + 4*1 ) - 30)
= Abs(( 20 + 10 + 21 + 4) - 30)
= Abs(55 - 30)
= 25
Rata-rata dari fungsi objektif
tersebut adalah = (33+10+13+46+24+25)/6
= 151 / 6
= 25.167
III.6.4 Seleksi Kromosom
Proses seleksi dilakukan dengan cara membuat kromosom
yang mempunyai fungsi_objektif kecil mempunyai kemungkinan terpilih yang besar
atau mempunyai nilai probabilitas yang tinggi. Untuk itu dapat digunakan
“fungsi fitness = (1 / (1 +
fungsi_objektif))”
Fungsi_objektif perlu ditambah 1 untuk menghindari
kesalahan program yang diakibatkan pembagian oleh 0.
i. fitness[1] = 1 /
(fungsi_objektif[1]+1) = 1 / 34 = 0.0294
ii. fitness[2]
= 1 / (fungsi_objektif[2]+1) = 1 / 11 = 0.0909
iii. fitness[3]
= 1 / (fungsi_objektif[3]+1) = 1 / 14 = 0.0714
iv. fitness[4]
= 1 / (fungsi_objektif[4]+1) = 1 / 47 = 0.0212
v. fitness[5]
= 1 / (fungsi_objektif[5]+1) = 1 / 25 = 0.0400
vi. fitness[6]
= 1 / (fungsi_objektif[6]+1) = 1 / 26 = 0.0385
total_fitness = 0.0294 + 0.0909 + 0.0714 + 0.0212 + 0.04 + 0.0385
= 0.2914
Rumus untuk mencari probabilitas : “P[i] = fitness[i] / total_fitness”
i. P[1]
= 0.0294 / 0.2914 =
0.1009
ii. P[2]
= 0. 0909 / 0.2914 = 0.3119
iii. P[3]
= 0. 0714 / 0.2914 = 0.2450
iv. P[4]
= 0. 0212 / 0.2914 = 0.0728
v. P[5]
= 0.04 / 0.2914 = 0.1373
vi. P[6]
= 0.0385 / 0.2914 =
0.1321
Dari probabilitas diatas dapat kita lihat kalau kromosom ke-2 yang mempunyai fitness paling besar maka
kromosom tersebut mempunyai probabilitas untuk terpilih pada generasi
selanjutnya lebih besar dari kromosom lainnya. Untuk proses seleksi kita
gunakan roulette wheel, untuk itu
kita harus mencari dahulu nilai kumulatif probabilitasnya :
i. C[1] = 0.1009
ii. C[2]
= 0.1009 + 0.3119 = 0.4128
iii. C[3]
= 0.1009 + 0.3119 + 0.2450 = 0.6578
iv. C[4]
= 0.1009 + 0.3119 + 0.2450 + 0.0728 = 0.7306
v. C[5]
= 0.1009 + 0.3119 + 0.2450 + 0.0728 + 0.1373 =
0.8679
vi. C[6]
= 0.1009 + 0.3119 + 0.2450 + 0.0728 + 0.1373 + 0.1321 = 1
Setelah dihitung kumulatif probabilitasnya maka proses
seleksi menggunakan roulette-wheel dapat
dilakukan. Prosesnya adalah dengan membangkitkan bilangan acak R dalam range
0-1. Jika R[k] < C[1] maka pilih kromosom 1 sebagai induk, selain itu pilih
kromosom ke-k sebagai induk dengan syarat C[k-1] < R < C[k]. Kita putar
roulete wheel sebanyak jumlah populasi yaitu 6 kali (bangkitkan bilangan acak
R)
dan pada tiap putaran, kita pilih satu kromosom untuk populasi baru. Misal :
i. R[1] = 0.201
ii. R[2] = 0.284
iii. R[3] = 0.009
iv. R[4] = 0.822
v. R[5] = 0.398
vi. R[6] = 0.501
Angka acak pertama R[1] adalah lebih besar dari C[1] dan
lebih kecil daripada C[2] maka pilih Kromosom[2] sebagai kromosom pada populasi
baru, dari bilangan acak yang telah dibangkitkan diatas maka populasi kromosom
baru hasil proses seleksi adalah :
i.
Kromosom[1] = Kromosom[2]
ii.
Kromosom[2] = Kromosom[2]
iii.
Kromosom[3] = Kromosom[1]
iv.
Kromosom[4] = Kromosom[5]
v.
Kromosom[5] = Kromosom[2]
vi.
Kromosom[6] = Kromosom[3]
Kromosom baru hasil proses seleksi :
i. Kromosom[1] = [02;01;08;03]
ii.
Kromosom[2] = [02;01;08;03] iii.
Kromosom[3] = [12;05;03;08] iv.
Kromosom[4] = [01;04;03;09] v. Kromosom[5] = [02;01;08;03]
vi. Kromosom[6] = [10;04;03;04]
III.6.5 Crossover
Setelah proses seleksi maka proses selanjutnya adalah
proses crossover. Metode yang
digunakan salah satunya adalah one-cut
point, yaitu memilih secara acak satu posisi dalam kromosom induk kemudian
saling menukar gen. Kromosom yang dijadikan induk dipilih secara acak dan
jumlah kromosom yang mengalami crossover dipengaruhi
oleh parameter crossover_rate (ρc). Pseudo-code untuk proses crossover adalah sebagai berikut :
![Text Box: begin
k← 0;
while (k<populasi) do
R[k] ← random(0-1);](file:///C:/Users/NURADI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image008.gif) |
![Text Box: if (R[k] < ρc ) then
select Chromosome[k] as parent;
end; k = k + 1; end;
end;](file:///C:/Users/NURADI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image009.gif)
Misal kita
tentukan crossover probability adalah
sebesar 25%, maka
diharapkan
dalam satu generasi ada 50% kromosom (3 kromosom) dari satu generasi mengalami
proses crossover. Prosesnya adalah sebagai
berikut :
i.
Pertama kita bangkitkan bilangan acak R
sebanyak jumlah populasi
·
R[1] = 0.191
·
R[2] = 0.259
·
R[3] = 0.760
·
R[4] = 0.006
·
R[5] = 0.159
·
R[6] = 0.340
Maka kromosom ke-k akan dipilih sebagai induk jika R[k] < ρc, dari bilangan acak R diatas maka
yang dijadikan induk adalah Kromosom[1], Kromosom[4] dan Kromosom[5].
ii.
Setelah melakukan pemilihan
induk proses selanjutnya adalah menentukan posisi crossover. Ini dilakukan
dengan cara membangkitkan bilangan acak dengan batasan 1 sampai (panjang
kromosom - 1), dalam kasus ini bilangan acak yang
dibangkitkan adalah 1 – 3. Misalkan didapatkan posisi crossover adalah 1 maka kromosom induk
akan dipotong mulai gen ke-1 kemudian potongan gen tersebut saling ditukarkan antar induk.
·
Kromosom[1] >< Kromosom[4]
·
Kromosom[4] >< Kromosom[5]
·
Kromosom[5] >< Kromosom[1]
iii.
Posisi cut-point crossover dipilih menggunakan bilangan acak 1-3 sebanyak
jumlah crossover yang terjadi, misal :
·
C[1] = 1
·
C[2] = 1
·
C[3] = 2
Ø
offspring[1] =
Kromosom[1] >< Kromosom[4]
= [02;01;08;03] ><
[01;04;03;09]
= [02;04;03;09]
Ø
offspring[4] =
Kromosom[4] >< Kromosom[5]
= [01;04;03;09] ><
[02;01;08;03]
= [01;01;08;03]
Ø
offspring[5] =
Kromosom[5] >< Kromosom[1]
= [02;01;08;03] ><
[02;01;08;03]
= [02;01;08;03]
Dengan demikian populasi
kromosom setelah mengalami proses crossover
menjadi :
·
Kromosom[1] = [02;04;03;09]
·
Kromosom[2] = [02;01;08;03]
·
Kromosom[3] = [12;05;03;08]
·
Kromosom[4] = [01;01;08;03]
·
Kromosom[5] = [02;01;08;03]
·
Kromosom[6] = [10;04;03;04]
III.6.6 Mutasi
Jumlah kromosom yang mengalami mutasi dalam satu
populasi ditentukan oleh parameter mutation_rate.
Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih secara
acak dengan suatu nilai baru yang didapat secara acak. Prosesnya adalah sebagai
berikut :
i.
Pertama kita hitung dahulu
panjang total gen yang ada dalam satu populasi.
Dalam kasus ini panjang total gen adalah :
total_gen = (jumlah gen dalam kromosom) * jumlah populasi
= 4 * 6
= 24
ii.
Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan cara membangkitkan
bilangan integer acak antara 1 sampai total_gen, yaitu 1 sampai 24. Jika bilangan acak yang kita bangkitkan lebih
kecil daripada variabel mutation_rate (ρm) maka
pilih posisi tersebut sebagai sub-kromosom
yang mengalami
mutasi. Misal ρm kita tentukan 10% maka diharapkan ada 10% dari total_gen yang
mengalami populasi :
jumlah mutasi = 0.1 * 24
= 2.4
= 2
iii.
Misalkan setelah kita
bangkitkan bilangan acak terpilih posisi gen 12 dan 18 yang mengalami mutasi.
Dengan demikian yang akan mengalami mutasi adalah kromosom ke-3 gen nomor 4 dan
kromosom ke-5 gen nomor 2. Maka nilai gen pada posisi tersebut kita ganti dengan
bilangan acak 0-30. Misalkan bilangan acak yang terbangkitkan adalah 2 dan 5.
Maka populasi kromosom setelah mengalami proses mutasi adalah :
·
Kromosom[1] = [02;04;03;09]
·
Kromosom[2] = [02;01;08;03]
·
Kromosom[3] = [12;05;03;02]
·
Kromosom[4] = [01;01;08;03]
·
Kromosom[5] = [02;05;08;03]
·
Kromosom[6] = [10;04;03;04]
Setelah proses mutasi maka kita telah menyelesaikan satu
iterasi dalam algoritma genetika atau disebut dengan satu generasi. Maka
fungsi_objective setelah satu generasi adalah :
i. Kromosom[1] = [02;04;03;09]
fungsi_objektif[1] = Abs(( 2 + 2*4 + 3*3 + 4*9 ) - 30)
= Abs(( 2 + 8 + 9 + 36 ) - 30)
=
Abs( 55 - 30)
= 25
ii. Kromosom[2] = [02;01;08;03]
fungsi_objektif[2] = Abs(( 2 + 2*1 + 3*8 + 4*3 ) - 30)
= Abs(( 2 + 2 + 24 + 12 ) - 30)
=
Abs(40 - 30)
= 10
iii. Kromosom[3] = [12;05;03;02]
fungsi_objektif[3] = Abs(( 12 + 2*5 + 3*3 + 4*2 ) - 30)
= Abs(( 12 + 10 + 9 + 8 ) - 30)
=
Abs(39 - 30)
= 9
iv. Kromosom[4] = [01;01;08;03]
fungsi_objektif[4] =
Abs(( 1 + 2*1 + 3*8 + 4*3 ) - 30)
= Abs(( 1 + 2 + 24 + 12 ) - 30)
=
Abs(39 - 30)
= 9
v. Kromosom[5] = [02;05;08;03]
fungsi_objektif[5] =
Abs(( 2 + 2*5 + 3*8 + 4*3 ) - 30)
= Abs(( 2 + 10 + 24 + 12 ) - 30)
=
Abs(48 - 30)
= 18
vi. Kromosom[6] = [10;04;03;04]
fungsi_objektif[6] =
Abs(( 10 + 2*4 + 3*3 + 4*4 ) - 30)
= Abs(( 10 + 8 + 9 + 16 ) - 30)
=
Abs(43 - 30)
= 13
Rata-rata
fungsi objektif setelah satu generasi adalah : rata-rata = ( 25 + 10 + 9 + 9 +
18 + 13) / 6 = 84 / 6 = 14.0
Dapat dilihat dari hasil perhitungan fungsi objektif
diatas bahwa setelah satu generasi, nilai hasil rata-rata fungsi_objektif lebih
menurun dibandingkan hasil fungsi_objektif pada saat sebelum mengalami seleksi,
crossover dan mutasi. Hal ini
menunjukkan bahwa kromosom atau solusi yang dihasilkan setelah satu generasi
lebih baik dibandingkan generasi sebelumnya. Maka pada generasi selanjutnya
kromosom- kromosom yang baru adalah:
·
Kromosom[1] = [02;04;03;09]
·
Kromosom[2] = [02;01;08;03]
·
Kromosom[3] = [12;05;03;02]
·
Kromosom[4] = [01;01;08;03]
·
Kromosom[5] = [02;05;08;03]
·
Kromosom[6] = [10;04;03;04]
 |
Kromosom-kromosom ini akan mengalami proses yang sama seperti generasi sebelumnya yaitu proses evaluasi, seleksi, crossover dan mutasi yang kemudian akan menghasilkan kromosom-kromosom baru untuk generasi yang selanjutnya. Proses ini akan berulang sampai sejumlah generasi yang telah ditetapkan sebelumnya. Siklus ini menurut beberapa ilmuwan Zbigniew Michalewiz digambarkan sebagai berikut :
Gambar 4- Siklus Algoritma Genetika menurut
Michalewiz
Setelah
50 generasi didapatkan kromosom yang terbaik adalah : 1. Kromosom = [07;05;03;01]
Jika didekode maka :
2. A = 7 ; b = 5 ; c = 3 ; d = 1
Jika dihitung terhadap persamaan : 3. F = a + 2b + 3c + 4d
= 7 + (2*5) + (3*3) + (4*1)
= 30.
BAB IV KESIMPULAN & SARAN
IV.1
Kesimpulan
Dari pembahasan yang telah diuraikan sebelumnya, dapat
diambil suatu kesimpulan sebagai berikut, yaitu :
1.
Algoritma genetika
menggunakan cara kerja berdasarkan pada seleksi dan genetika alam, mengikuti
prinsip seleksi alam yaitu “siapa yang kuat,
dia
yang bertahan (survive)”.
2.
Algoritma genetika memiliki
komponen utama yaitu teknik pengkodean, prosedur inisialisasi, fungsi evaluasi,
seleksi, operator genetika dan penetuan parameter.
3.
Algoritma genetika dapat
memberikan solusi untuk pencarian nilai dalam sebuah masalah optimasi. [10]
4.
Pencarian solusi mendekati
optimal dilakukan dengan melakukan beberapa kali proses iterasi, yaitu evaluasi, seleksi, crossover dan mutasi secara berulang
sampai didapatkan solusi yang optimal.
IV.2
Saran
Penyusun menyarankan untuk pengembangan makalah
selanjutnya agar disertai contoh aplikasi algoritma genetika dalam bahasa
pemrograman tertentu untuk mempermudah simulasi serta juga menganalisis dan
membandingkan semua algoritma optimasi, bukan hanya algoritma genetika.
DAFTAR PUSTAKA
[1] Basuki,
Achmad. 2003. Algoritma Genetika :
Suatu Alternatif Penyelesaian
Permasalahan Searching, Optimasi dan Machine Learning. Surabaya :
Politeknik Elektronika Negeri Surabaya PENS –
ITS.
pukul 09.34 WIB.
[3] http://hendrik.staff.gunadarma.ac.id/Downloads/files/23066/algoritma-genetika.pdf, diakses pada 19
September 2012 pukul 08.12 WIB.
algoritma-genetika.ppt, diakses pada 19 September
2012 pukul 08.13 WIB.
[5] Kusumadewi, Sri. 2003. Artificial Intellegence – Teknik dan
Aplikasinya. Yogyakarta : Graha Ilmu.
its.edu/~entin/Kecerdasan%20Buatan/Buku/Bab%207%20Algoritma%20Genetika.pdf,
diakses pada 21 September 2012 pukul 09.41 WIB.
September 2012 pukul 08.22 WIB.
[8] Sanjoyo. Juni 2006. Aplikasi Algoritma Genetika. http://sanjoyo55.files.wordpress.com/2008/11/non-linier-gen-algol.pdf, diakses pada 19 September
2012 pukul 08.22 WIB.
_denny_hermawanto.pdf, diakses pada 21 September
2012 pukul 08.00 WIB.
[10] http://ejournal.undip.ac.id/index.php/matematika/article/download/1347/1108, diakses pada 19 September 2012 pukul 08.13
WIB.
Komentar
Posting Komentar