ALGORITMA GENETIKA DASAR

Pendahuluan

Algoritma Genetika sebagai cabang dari Algoritma Evolusi merupakan metode adaptive 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-permasalahan dalam dunia nyata. Peletak prinsip dasar sekaligus pencipta Algoritma Genetika adalah John Holland. Algoritma Genetika menggunakan analogi secara langsung dari kebiasaan yang alami yaitu seleksi alam. Algoritma ini bekerja dengan sebuah populasi yang terdiri dari individu-individu, yang masing-masing individu mempresentasikan sebuah solusi yang mungkin bagi persoalan yang ada. Dalam kaitan ini, individu dilambangkan dengan sebuah nilai fitness yang akan digunakan untuk mencari solusi terbaik dari persoalan yang ada.

Pertahanan yang tinggi dari individu memberikan kesempatan untuk melakukan reproduksi melalui perkawinan silang dengan individu yang lain dalam populasi tersebut. Individu baru yang dihasilkan dalam hal ini dinamakan keturunan, yang membawa beberapa sifat dari induknya. Sedangkan individu dalam populasi yang tidak terseleksi dalam reproduksi akan mati dengan sendirinya. Dengan jalan ini, beberapa generasi dengan karakteristik yang bagus akan bermunculan dalam populasi tersebut, untuk kemudian dicampur dan ditukar dengan karakter yang lain. Dengan mengawinkan semakin banyak individu, maka akan semakin banyak kemungkinan terbaik yang dapat diperoleh.

Sebelum Algoritma Genetika dapat dijalankan, maka sebuah kode yang sesuai (representatif) untuk persoalan harus dirancang. Untuk ini maka titik solusi dalam ruang permasalahan dikodekan dalam bentuk kromosom/string yang terdiri atas komponen genetik terkecil yaitu gen. Dengan teori evolusi dan teori genetika, di dalam penerapan Algoritma Genetika akan melibatkan beberapa operator, yaitu:

1. Operasi Evolusi yang melibatkan  proses seleksi (selection) di dalamnya.
2. Operasi Genetika yang melibatkan operator pindah silang (crossover) dan mutasi (mutation).

Untuk memeriksa hasil optimasi, kita membutuhkan fungsi fitness, yang menandakan gambaran hasil (solusi) yang sudah dikodekan. Selama berjalan, induk harus digunakan untuk reproduksi, pindah silang dan mutasi untuk menciptakan keturunan. Jika Algoritma Genetika didesain secara baik, populasi akan mengalami konvergensi dan akan didapatkan sebuah solusi yang optimum.

Karakteristik Algoritma Genetik

Algoritma genetik (GA) adalah suatu metode pencarian solusi optimal secara stokastik yang berdasar pada mekanisme evolusi dan seleksi alam [indra]. GA, berbeda dengan teknik optimasi konvensional, dimulai dengan suatu set solusi yang random yang disebut dengan populasi. Setiap individu dalam populasi yang disebut kromosom merepresentasikan sebuah solusi dari suatu persoalan.

Proses pencarian solusi berarti merupakan proses pencarian individu terbaik yang memenuhi solusi setelah dikenakan operator genetik. Solusi yang dikehendaki tersebut, akan selalu memperbaiki dirinya sampai pada kondisi akhir yang diinginkan. 

Bebarapa karakteristik dari Algoritma genetik sebagai berikut[GoldBerg]

1.    Prinsip Pengkodean Solusi. Solusi adalah sifat fisik yang tampak yang dikodekan ke dalam kromosom. GA memanipulasi isi kromosom, tidak memanipulasi sifat fisik secara langsung.  Hal ini berbeda dengan metode berbasis kalkulus yang bergantung pada persoalan yaitu informasi turunan, syarat kontinuias, dan sebagainya.

2.    GA bekerja pada kumpulan solusi (populasi) yang merupakan kandidat solusi dalam teknik pencarian, dengan kata lain kumpulan individu akan mengalami seleksi alam. Berbeda dengan metode lainnya yang hanya menggunakan satu solusi untuk mengevaluasi solusi berikutnya. Sehingga dengan menggunakan kumpulan alternatif solusi, didapatkan ruang pencarian (search space) yang lebih luas.

3.    GA hanya menggunakan informasi fungsi fitness yang didapatkan dari fungsi objektif persoalan. Sedangkan pada metode lainnya memerlukan informasi yang dihitung secar analitik dan numeric seperti turunan.

4.    GA menggunakan aturan transisi probabilistik sebagai alat bantu untuk mengarahkan pencarian.

SUMBER : ELIB UNIKOM GDL MUHAMMADAR