Algoritma Genetika

Genetic algorithm atau algoritma genetika (GA) masuk dalam kelompok Evolutionary Algoritm. Genetic algorithm didasarkan pada prinsip-prinsip genetika dan seleksi alam. Elemen-elemen dasar dari genetika alam adalah: reproduksi, crossover, dan mutasi. Elemen-elemen ini yang dipakai dalam prosedur GA. Algoritma ini banyak dipakai dalam penyelesaian masalah kombinatorial seperti TSP, VRP hingga permasalahan kontrol. GA termasuk pelopor dalam hal Metaheuristik, banyak algoritma yang belakangan ditemukan mengadopsi beberapa langkah dari GA. Dalam evolution-based approach biasanya akan dibangkitkan sejumlah populasi yang dalam masalah optimasi menjadi solusi awal. Dengan prosedur tertentu seperti mutasi, seleksi, reproduksi dan crossover akhirnya didapatkan solusi akhir dari problem optimasi yang dihadapi. Algoritma yang sangat populer dalam hal ini adalah algoritma genetika. Ini termasuk temuan besar dalam bidang optimasi. Dimana suatu algoritma diciptakan dengan meniru mekanisme evolusi dalam perkembangan makhluk hidup. Dalam GA prosedur pencarian hanya didasarkan pada nilai fungsi obyektif, tidak ada pemakaian gradient. Banyak masalah telah berhasil diselesaikan dengan algoritma ini. Sebagai contoh, antara lain crew scheduling untuk airline. Masalah crew scheduling termasuk masalah kombinatorial yang sulit diselesaikan. GA juga diterapkan untuk portfolio selection, Traveling Salesman Problem,optimized Telecommunications Routing, Trip, Traffic and Shipment Routing. Beberapa istilah dipakai dalam algoritma genetika antara lain [Venkataraman, 2002].

Kromosom

Satu kromosom mewakili satu vektor solusi. Kadang kita bisa langsung menggunakan vektor solusi ini dalam implementasi GA. Atau kadang bisa juga dilakukan encoding atau pengkodean untuk mewakili suatu nilai. Dalam GA kita akan membangkitkan populasi sebagai kumpulan vector solusi awal. Populasi disusun oleh beberapa kromosom. Setiap anggota kromosom yang disusun oleh gen-gen, dimana masing-masing gen mewakili elemen dari vektor solusi. Dengan dibangkitkannya populasi ini, maka kemungkinan terjebak dalam suatu local optima akan terhindar karena ada banyak alternatif solusi yang mungkin yang bisa mencakup solusi terbaik.

Fitness dan seleksi

Fungsi fitness digunakan untuk mengukur tingkat kebaikan (fitness) suatu solusi. Fungsi fitness bisa berhubungan langsung dengan fungsi obyektif. Sejumlah solusi yang dibangkitkan dalam populasi akan dievaluasi menggunakan fungsi fitness. Fungsi fitness yang biasa digunakan adalah  

dimana f(x) adalah fungsi tujuan dari problem yang kita selesaikan. Setelah setiap solusi dievaluasi, perlu dilakukan proses seleksi. Proses seleksi dilakukan untuk memilih diantara anggota populasi ini, mana yang bisa menjadi induk (parent) atau melakukan identifikasi diantara populasi ini yang akan menjadi anggota populasi berikutnya. Ada beberapa cara melakukan seleksi ini. Sebagian anggota populasi bisa dipilih untuk proses reproduksi dan promosi. Proses reproduksi ini juga disebut crossover. Proses ini akan menghasilkan turunan baru (solusi baru) yang merupakan perkawinan silang dari induk yang terpilih. Sedangkan anggota yang lain berasal dari proses pembangkitan populasi baru (imigrasi).

Crossover

Ada bermacam-macam teknik crossover. Di sini kita akan membahas dua macam crossover yaitu crossover sederhana dan crossover aritmatik. Jika ada dua induk P1 dan P2 dan menghasilkan dua keturunan C1 dan C2. Misalkan anggota induk adalah X =[x1,x2, .., xn]dan Y =[y1,y2, .., yn] dan r adalah bilangan random maka U dan V yaitu mewakili keturunan C1 dan C2 didefinisikan sebagai 

Sedangkan dalam crossover aritmatik keturunan dihasilkan dengan cara melakukan kombinasi linier dari vektor induk. Secara matematis

 

Mutasi

Mutasi mengacu pada penggantian satu elemen dari suatu vektor solusi dengan nilai lain yang dibangkitkan secara random. Elemen tersebut juga dipilih secara random. Misalkan untuk vektor solusi X, untuk elemen terpilih k

Ada beberapa cara mutasi yang lain termasuk mutasi nonuniform dan directional.

Secara garis besar Algoritma genetika dasar bisa dijelaskan sebagai berikut

1.  Bangkitkan populasi awal- set solusi awal atau kromosom. Evaluasi nilai solusi awal ini dengan menggunakan fungsi fitness

2.  Set iterasi t=1

3. menggunakan operator genetik untuk membangkitkan keturunan dengan crossover atau mutasi

4.       bangkitkan ppopulasi baru secara random

5.       evaluasi lagi populasi baru dengan fungsi fitness

6.       lakukan seleksi kompetitif dimana akan terpilih anggota untuk iterasi berikutnya

7.       jika belum mencapai konvergensi set iterasi t=t+1

8.       kembali ke langkah 2