Mengenal Algoritma Genetik

Algoritma Genetik atau sering disingkat GA - Genetic Algorithm, adalah teknik pencarian yang digunakan untuk mencari solusi yang tepat atau perkiraan solusi yang mungkin bisa dioptimalisasi dan untuk mencari masalah itu sendiri.

GA dikatogorikan sebagai pencarian global yang menggunakan heuristics yang adalah sekumpulan aturan yang digunakan untuk meningkatkan kemungkinan menyelesaikan beberapa masalah. Dalam bentuk spesifik, fungsi heuristics atau yang biasa disebut heuristic saja adalah fungsi untuk menentukan ranking dari beberapa alternatif solusi dan solusi dengan rangking tertinggi akan terpilih untuk dilakukan pencarian selanjutnya sampai ditemukan solusi optimal namun heuristic tidak menjamin solusi yang benar.

GA termasuk algoritma evolusioner yang menggunakan teknik optimasi masalah. Teknik ini terinspirasi dari evolusi biologi yang merupakan sub bidang biologi yang berkonsentrasi proses perubahan spesies, perkembangbiakan dan keanekaragaman yang terjadi sepanjang masa seperti pewarisan sifat, mutasi (proses perubahan sembarang bit dari urutan genetik pada kondisi asli), proses seleksi (memilih dari populasi yang ada berdasarkan karateristik yang diharapkan) dan crossover (proses rekombinasi kromosom antar spesies dari waktu ke waktu).

Di dalam GA koromosom adalah sekumpulan parameter yang mendefinisikan solusi dari problem dan biasa direpresentasi dalam bentuk string walaupun terdapat juga struktur lain yang digunakan seperti yang akan dijelaskan dibawah.

Gambaran Dasar Algoritma Genetik

Algoritma ini dimulai dengan sekumpulan kemungkinan solusi (direpresentasi dengan kromosom) yang disebut populasi. Solusi dari sebuah populasi digunakan untuk menghasilkan populasi yang baru. Populasi yang baru diharapkan merupakan perbaikan dari populasi sebelumnya. Solusi dipilih berdasarkan kemampuan yang dimilikinya. Semakin cocok karateristik yang dimiliki sebuah kromosom dengan hasil yang diharapkan (didefinisikan lewat fungsi heuristic) semakin besar kromosom itu terpilih dalam proses crossover. Ulangi proses ini (membuat populasi yang baru dari yang lama) sampai kondisi yang diharapkan tercapai.

Secara rinci dijelaskan sebagai berikut:

1. Membangkitkan populasi acak dari kromosom yang sesuai dengan solusi
2. Membuat fungsi f(x) untuk mengevaluasi "kualitas" kromosom x di dalam populasi
3. Membuat populasi baru dengan melakukan langkah-langkah berikut ini: seleksi, mutasi dan crossover, accepting (menempatkan kromosom yang baru terbentuk ke dalam populasi yang baru) sampai populasi yang baru selesai terbentuk.
   
4. Gunakan populasi yang baru untuk melanjutkan algoritma
5. Cek apakah kondisi akhir dari algoritma ini sudah terpenuni, jika sudah lakukan proses stop, dan kembalikan/return solusi terbaik dari populasi terbaru.
6. Kembali ke langkah 2
   

Desain Kromosom Kromosom disesuaikan dengan problem yang hendak diselesaikan. Maksudnya adalah kromosom yang dibentuk spesifik pada masalah tertentu. Kromosom pada masalah yang berbeda akan memiliki bentuk yang berbeda pula.

Berikut ini adalah beberapa bentuk encoding dari kromosom:

Binary Encoding


Kromosom dibentuk sebagai rangkaian dari angka 0 dan 1. Setiap bit dapat mewakili karateristik dari solusi dan dapat juga digunakan untuk mendeteksi adanya kesesuaian karateristik kromosom input dengan hasil yang diharapkan. Jumlah bit bisa saja lebih sedikit, contoh 4 bit.

Permutation Encoding


Jenis encoding ini bisa digunakan dalam masalah pengurutan, sebagai contoh TSP. Setiap kromosom adalah string dari angka yang menunjukkan urutan dari angka. Di dalam TSP setiap angka bisa dianggap sebagai kota yang dikunjungi.

Value Encoding


Value encoding digunakan dalam masalah yang menggunakan nilai kompleks sehingga tidak bisa direpresentasi oleh biner encoding. Biasanya sering dibutuhkan pendefinisian proses crossover dan mutasi untuk kromosom. Pada Kromosom 1, A bisa merepresentasi tugas tertentu dan B adalah tugas yang lain sedangkan pada kromosom 2, N bisa merepresentasi North, S South sehingga mungkin saja kromosom ini merepresentasi jalur yang harus ditempuh.

Tree Encoding

Encoding jenis ini digunakan jika kita harus membuat program. Misalnya dengan LISP. Sebagai contoh digunakan masalah pencarian fungsi yang didasarkan pada nilai input dan output. Katakan saja mencari output terbaik berdasarkan semua input yang ada. .

Reference:

[1] http://en.wikipedia.org/wiki/Genetic_algorithm
[2] wordnet.princeton.edu/perl/webwn
[3] en.wikipedia.org/wiki/Heuristic_(function)
[4] http://en.wikipedia.org/wiki/Evolutionary_biology
[5] http://www.tjhsst.edu/~ai/AI2001/GA.HTM