Algoritma Genetika Lengkap Step by Step

 
Assalamualaikum wr wb..

Halo semuaa… kesempatan kali ini saya akan sedikit membahas mengenai sebuah algoritma pada bidang computer science yaitu Algoritma Genetika. Algoritma ini termasuk ke dalam kategori learning. Algoritma genetika termasuk ke dalam bidang kecerdasan buatan (Artificial Intelligence). Algoritma genetika merupakan bagian dari Evolutionary Computation (EC). Algoritma ini terinspirasi dari proses evolusi dan seleksi makhluk hidup secara natural.

Algoritma genetika umumnya digunakan untuk mengatasi masalah optimasi dan pencarian. Algoritma ini merupakan algoritma standar dan umum sehingga dapat dengan mudah diimplementasikan di berbagai persoalan. Algoritma ini akan memberikan hasil yang lebih baik untuk setiap iterasi pencarian solusi. Algoritma genetika dapat mencari solusi terbaik dari kandidat set yang luas dan memiliki banyak titik optimum dan juga hasil cenderung menuju ke pada global optima berbeda dengan jaringan syaraf tiruan yang kemungkinan memperoleh lokal optima lebih besar.

Jika di ilustrasikan pada gambar. Pada kedua gambar dibawah terlihat sekilas perbedaan dari algoritma genetika dan jaringan syaraf tiruan. Pada gambar ilustrasi di atas terlihat titik pencarian lebih variatif dibandingkan gambar di bawah. Namun tidak selamanya akan lebih baik algoritma genetika tergantung dari permasalahan yang dihadapi, jaringan syaraf tiruan juga merupakan algoritma yang powerful. So, sebelum menentukan algoritma yang digunakan selidiki dahulu masalahnya.

 

 

Istilah-istilah dalam Algoritma Genetika

Sebelum dilanjutkan lebih dalam berikut merupakan istilah-istilah yang akan sering digunakan dalam algoritma genetika.

• Populasi = Kumpulan dari kemungkinan solusi.
• Kromosom = Satu kemungkinan solusi
• Genotype = Elemen yang terdapat pada kromosom
• Fenotype = Nilai dari genotype
• Fungsi Fitness = fungsi yang menentukan bobot dari setiap kromosom
• Nilai Fitness = Nilai yang diperoleh dari hasil fungsi fitness
• Decoding dan Encoding = Pada beberapa kasus, bentuk fenotype dapat diganti menjadi bentuk lain, misalnya biner, real, permutasi dan integer. Decoding dan encoding adalah proses untuk merubahnya dari satu bentuk ke dalam bentuk lainnya.

 

Kelebihan Algoritma Genetika

Algorima genetika dapat digunakan untuk menyelesaikan beberapa kasus karena beberapa kelebihan sebagai berikut.

• Terdiri dari banyak calon solusi yang dibangkitkan sekaligus
• Setiap iterasi memberikan calon solusi yang lebih baik
• Ruang solusi yang besar tidak menjadi masalah
• Algoritma cepat dan efisien

 

Tahapan dalam Algoritma Genetika

Setiap algoritma merupakan kumpulan dari tahapan-tahapan matematis yang logis dan dapat dibuktikan kebenarannya. Algoritma genetika memiliki beberapa tahapan yang utama.Secara garis besar algoritma genetika terdiri dari.

Inisialisasi awal -> Penghitungan nilai fitness -> Pemilihan orang tua -> Crossover -> Mutasi -> Seleksi -> Hasil

 

Tahapan menerapkan algoritma genetika

1. Inisialisasi Populasi

Pada awal menerapkan algoritma genetika dibutuhkan inisialisasi populasi awal. Pada tahap ini harus ditentukan berapa jumlah kromosom dalam satu populasi. Tentukan representasi dari gen yang diinginkan, biner, real, integer dan permutasi. Tentukan threshold fitness dan jumlah iterasi maksimal gunanya untuk membatasi iterasi. Tentukan probabilitas crossover dan mutasi. Setelah semua ditentukan, kemudian bangkitkan populasi awal secara random.

Contoh representasi Biner:

 

 

 

Contoh representasi Integer:

 

 

 

Contoh representasi real:

 

 

 

Contoh representasi permutasi:

 

 

 

2. Hitung Nilai Fitness

Setelah populasi dibangkitkan, lakukan perhitungan nilai fitness dengan fungsi fitness yang sesuai. Fungsi fitness bisa bermacam-macam tergantung masalah yang dihadapi. Semakin besar nilai fitness semakin baik pula calon solusi yang digunakan.

3. Pemilihan Orang tua

Setelah diperoleh semua nilai fitness, kemudian dilakukan pemilihan orang tua. Tentukan jumlah pasangan orang tua yang diinginkan untuk dipilih kemudian lakukan pemilihan dengan cara berikut. Secara umum terdapat 4 cara memilih kromosong orang tua.

1. Random Selection

Random Selection adalah cara pemilihan pasangan kromosom orang tua secara acak tanpa ada pengaruh dari nilai fitness. Lebih simple nya hanya butuh men-generate nilai random untuk memilih index sebagai kromosom orang tua.

2. Tournament Selection

Metode seleksi ini melakukan pemilihan berdasarkan nilai fitness. Pemilihan dimulai dengan memunculkan beberapa nilai random sebagai index untuk memilih beberapa calon orang tua, kemudian di seleksi dengan nilai fitness terbaik.

Misalkan nilai random yg di generate ada 3 (1,3,4), sesuai gambar yang terpilih index 4 yaitu kromosom D.

3. Rank Selection

Metode seleksi ini melakukan pemilihan menggunakan sistem roulette wheel tetapi semua kandidat memiliki proporsi yang sama. Nilai fitness dari tiap kromosom mempengaruhi proses penguruan di awal. Nilai fitness yang tertinggi akan berada di rank pertama dan diikuti dengan rank keduaa dengan nilai fitness lebih rendah. Sesuai pada gambar ilustrasi tabel diurutkan berdasarkan nilai fitness dari rank pertama dan seterusnya, kemudian dipilih dengan angka random memakai skema Roulette Wheel dengan kromosom rank pertama berada di awal dan proporsi setiap kromosom sama.

 

 

4. Fitness Proportionate Selection

Metode ini merupakan yang paling populer dalam pemilihan kromosom orang tua. kromosom yang memiliki nilai fitness lebih besar akan memiliki kemungkinan terpilih dibandingkan nilai fitness yang lebih kecil. Sistemnya hampir sama seperti Rank Selection hanya saja yang membedakan pada proporsi setiap kromosom tidak sama tergantung dari nilai fitness. Kategori ini terdapat 2 macam yaitu Roulette Wheel Selection dan Stochastic Universal Sampling (SUS).

a. Roulette Wheel Selection

Penggunaan metode pemilihan ini berdasarkan probabilitas dari setiap kromosom. Dari gambar terlihat kromosom pada tabel tidak diurutkan seperti pada rank selection. Ukuran dari proporsi kromosom di dalam roulette wheel akan berbeda-beda tergantung nilai fitness. Pemilihan dilakukan dengan membangkitkan nilai random dari range jumlah semua fitness (dari contoh gambar 1-14).

 

b. Stochastic Universal Sampling (SUS)

Metode SUS ini sama seperti metode roulette wheel, yang membedakan hanya pada titik “fixed point”. Titik pemilihan kromosom dalam sekali putar roulette wheel ditempatkan lebih dari 1 titik. Pada gambar di bawah terlihat ada 2 buah “fixed point” sehingga dalam sekali putar akan diperoleh satu pasang orang tua. Pemilihan dilakukan dengan membangkitkan nilai random, nilai tersebut digunakan untuk orang tua pertama dan kemudian nilai random dikurangkan dengan suatu nilai (misal dalam contoh gambar ini dikurangkan setengah dari total fitness untuk memperoleh titik berseberangan) untuk orang tua kedua.

4. Crossover

Operator crossover ini yang paling penting di dalam algoritma genetika karena di sini proses pembuatan anak atau kromosom baru dilakukan. Jumlah kromosom baru yang dibuat tergantung dari keiinginan kita. Terdapat 2 jenis populasi model untuk membentuk kromosom baru:

a. Steady State

Pada metode ini, kromosom baru dibuat tidak sejumlah dengan banyaknya kromosom dalam satu populasi. kromosom baru hanya dibuat beberapa saja satu atau dua kromosom yang nantinya akan menggantikan kromosom lama sesuai dengan jumlah kromosom baru (tidak semua kromosom di dalam populasi digantikan).

b. Generational

Pada metode ini, kromosom baru dibuat sama jumlahnya dengan kromosom dalam satu populasi. Kemudian populasi lama dapat digantikan semua di akhir iterasi.

Crossover tidak selalu dilakukan karena memiliki probabilitas. Di awal ditentukan nilai probabilitas untu crossover, biasanya probabilitas crossover lebih besar daripada mutasi. Misalkan probabilitas crossover 0,8 nah kemudian bangkitkan nilai random dari rentang 0 sampai 1, jika nilai random lebih kecil atau sama dengan probabiitas maka crossover dilakukan. Jenis crossover dapat dipilih sesuai keperluan. Jenis-jenis operator crossover:

1. One point crossover

crossover ini melakukan penukaran gen-gen dari satu kromosom dengan kromosom lain untuk menghasilkan kromosom baru melalui satu titik potong.

2. Multi point crossover

crossover ini melakukan penukaran gen-gen dari satu kromosom dengan kromosom lain untuk menghasilkan kromosom baru melalui beberapa titik potong.

3. Uniform crossover

Crossover ini melakukan penukaran gen-gen dari satu kromosom dengan kromosom lain melalui tiap index berdasarkan probabilitas. Setiap gen memiliki probabilitas seperti coin misalkan jika yang muncul head maka di tukar dan jika muncul tail maka posisi gen tetap.

4. Whole Arithmetic Recombination

Crossover ini melakukan perhitungan melalui nilai dari gen masing-masing kromosom. Nilai alpha dapat ditentukan dari rentang 0-1. Jika nilai alpha 0,5 maka akan menghasilkan 2 anak yang sama. x adalah kromosom parent1 dan y kromosom parent2

5. Mutasi

Mutasi tidak selalu dilakukan karena memiliki probabilitas. Di awal ditentukan nilai probabilitas untuk mutasi, biasanya probabilitas mutasi lebih kecil daripada crossover. Misalkan probabilitas crossover 0,8 nah kemudian mutasi adalah 0,2, selanjutnya bangkitkan nilai random dari rentang 0 sampai 1, jika nilai random lebih kecil atau sama dengan probabilitas mutasi maka mutasi dilakukan.

Mutasi adalah proses mengubah fenotype dari gen (mengubah nilai gen). mutasi bisa dilakukan dengan satu titik atau juga bisa dengan banyak titik.

 

6. Seleksi Survivor

Selanjutnya adalah mendapatkan populasi lagi untuk iterasi berikutnya. Beberapa kromosom yang tidak penting akan dibuang dan digantikan dengan kromosom baru yang sudah melalui proses crossover dan mutasi. Beberapa cara yaitu Age Based Selection dan Fitness Based Selection.

Pada metode Age Based Selection, kromosom yang sudah tua atau melalui iterasi yang lama akan digantikan dengan kromosom yang baru terbentuk / kromosom anak. Kromosom lama akan digantikan sesuai dengan jumlah dari kromosom baru yang terbentuk.

Pada metode Fitness Based Selection, kromosom digantikan berdasarkan nilai fitness. Kromosom lama akan dibandingkan nilai fitnessnya dengan kromosom baru, jika kromosom baru lebih baik maka akan digantikan.

 

Dalam penerapan algoritma genetika sebaiknya menggunakan prinsip Elitisme, yang mana selalu menyimpan satu kromosom terbaik selama proses sehingga akan selalu ada kromosom dengan fitness tertinggi. Jika muncul kombinasi kromosom terbaru yang lebih baik maka satu kromosom yang disimpan sebelumnya di tukar dengan kromosom baru tersebut.

Jika Kondisi terminasi belum terpenuhi maka akan kembali ke tahap 2 hingga kondisi terminasi terpenuhi.

7. Hasil

Terakhir adalah terminasi iterasi jika kondisi iterasi telah terpenuhi maka iterasi dihentikan. Di awal inisialisasi tadi ada penentuan kondisi iterasi berhenti yaitu threshold fitness dan maksimal iterasi. Jika salah satu kondisi ini sudah terpenuhi maka proses iterasi pun dihentikan. Kemudian urutkan semua kromosom dan ambil kromosom dengan nilai fitness terbaik untuk menjadi hasil.

Yah segini dulu pembahasan tentang algoritma genetika. Jika ada yang salah dan ada pertanyaan mohon diberitahukan di comment.

Terima kasih…