Algoritma Genetika (Evalutionary Computing)

         1.  Definisi

Algoritma Genetik adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetik adalah kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)
Algoritma Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Naturan and Artifical System" pada tahun 1975.
Algoritma Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solus0solusi calon (disebut individual) ada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dakan biner sebagai string '0' dan '1', walaupun kemungkinan 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 indibiduals dipilih dari populasi sekarang (current) tersebut secara stochastic(berdasarkan kemampuan mereka), lalu dimodifinkasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang(current) pada iterasi berikutnya dari algoritma.

         2. Komponen Algoritma Genetik

Algoritma genetik terdiri dari delapan komponen, yang bertugas untuk menunjang dari optimasi tersebut, adapun komponen tersebut ialah, skema pengkodean, nilai fitness, seleksi orang tua, pindah silang, mutasi, elitisme, penggantian populasi dan kriteria penghentian.

        3. Skema Pengkodean

Untuk dapat diproses menggunakan algortima genetik, suatu permasalahan harus dikonversi dahulu kedalam bentuk individu yang diwakili oleh satu atau lebih kromosom dengan kode tertentu. Hal ini berbeda dengan teori genetika di dunia nyata.  Algoritma genetik merepresentasikan gen secara umum, sebagai bilangan real, desimal atau biner yaitu:
1. Real number enconding. Pada skema ini, niai gen berada dalam interval [0,R] dimana R ialah bilangan real positif dan biasanya R = 1.
2. Discrete decimal enconding. Pada skema ini setiap gen bisa berupa deretan bilangan bulat dalam interval [0.9].
3. Binary enconding. Setiap gen bisa berupa deretan nilai 0 atau 1.

        4. Nilai Fittnes

Nilai fitness dalam sebuah algoritma genetik menggambarkan tingkat kovergensi keoptimalan algoritma dimana yang diharapkan adalah nilai fitness yang optimal dalam hal ini angka tertinggi ialah nilai terbaik. Dalam evolusi dunia nyata, individu bernilai fitness tinggi akan bertahan hidup, sedangkan yang memiliki nilai fitness rendah akan gugur atau mati. Pada algoritma genetik, fitness biasanya dapat berupa fungsi objektif dari masalah yang akan dioptimalisasi. Kromosom-kromosom diseleksi menurut nilai fitnessmasing-masing Kromosom yang kuat mempunyai kemungkinan tinggi untuk bertahan hidup pada generasi berikutnya.  

        5. Seleksi Orang Tua

Seleksi merupakan proses pemilihan kromosom dari generasi lama untuk dijadikan orangtua yang akan saling kawin silang untuk membentuk kromosom baru digenerasi baru, dalam hal ini kita menggunakan seleksi roda roulette (roulette wheel selection). Dalam hal ini pemilihan dua buah kromosom sebagai orang tua (parent) dilakukan secara proposional sesuai dengan nilai fitnessnya. Dimana kromosom yang memiliki nilai fitness tertinggi akan menempati potongan yang lebih besar pada lingkaran daripada kromosom dengan nilai fitness yang lebih rendah. Contoh metode roulette-wheel dapat diilustrasikan sebagai berikut:

Pada contoh diatas, nilai dari S1 memiliki nilai fitnes yang paling besar, dengan demikian peluang dari S1 untuk terpilih menjadi orang tua sebesar 0.277 sedangkan untuk nilai S2 dan S3 memiliki peluang yang sama sebesar 0.138

6. Pindah Silang

Menurut George F.Luger dan William A. Stubblefield dalam buku Artificial Intelegence Structures and Strategies For Complex Promblem Solving. Kekuatan dari algoritma genetik ialah pada kemampuan pencarian mereka dalam pindah silang, dimana algoritma genetik menerapkan mempertahankan beberapa solusi terbaik, dan menghilangkan solusi yang tidak bagus. Komponen pindah silang digunakan untuk membentuk keturunan baru berdasarkan orangtua yang terpilih. Komponen ini sangat dominan dalam algoritma genetik dibandingkan dengan komponen mutasi. Dan jumlah kromosom yang digunakan sebanyak dua buah kromosom.

Pindah silang dilakukan dengan harapan kromosom-kromosom baru akan mempunyai bagian baik dari kromosom-kromosom lama dan tidak menutup kemungkinan menjadi kromosom-kromosom yang lebih baik

Skema dari pindah silang ini ialah, dengan mendapatkan dua buah individu orang tua, selanjutnya ditentukan titik pindah silang secara acak. Jika diasumsikan L adalah panjang kromosom, maka titik pindah silang berada diantara 1 hingga L-1, kemudian beberapa bagian dari dua kromosom ditukar pada titik pindah silang yang terpilih. Titik pindah silang ialah titik terjadinya pertukaran gen antar dua individu orang tua.

7.    Mutasi

Mutasi diperlukan untuk mengembalikan informasi bit yang hilang akibat pindah silang. Mutasi diterapkan dengan probabilitas yang sangat kecil. Jika mutasi dilakukan terlalu sering, maka akan menghasilkan individu yang lemah karena konfigurasi gen pada individu yang unggul akan dirusak. Berdasarkan bagian yang termutasi, proses mutasi dapat dibedakan atas tiga bagian:

8.    Eliteisme

Karena seleksi dilakukan secara acak, maka tidak ada jaminan bahwa suatu individu bernilai fitnestertinggi akan selalu terpilih. Kalaupun individu bernilai fitnes tertinggi terpilih, mungkin saja akan menjadi rusak karena proses pindah silang. Untuk menjaga agar individu bernilai fitnes tertinggi tersebut tidak hilang selama evolusi, perlu dibuat satu atau dua kopinya. Prosedur ini dikenal sebagai elitisme. Prosedur ini hanya digunakan pada algoritma genetic berjenis generational replacement.

9. Penggantian Populasi

Pada algoritma genetik berjenis generational replacement, N individu pada suatu generasi digantikan sekaligus oleh N individu baru hasil pindah silang dan mutasi. Untuk mempertahankan individu terbaik, diperlukan skema elitisme.

Adapun prosedur penggantian populasi pada algoritma genetik ialah:

1. Mengganti individu yang memiliki nilai fitnes terkecil.

2. Mengganti individu yang paling tua.

3. Membandingkan anak dengan kedua orang tua, apabila anak memiliki nilai menggantikan orang tua yang memiliki nilai fitnes terendah.

   10. Kriteria Penghentian

Terdapat beberapa syarat penghentian yang digunakan pada proses perulangan.

1.    Memberikan batasan jumlah iterasi, apabila batas iterasi tersebut tercapai dan nilai fitnes tertingi sebagai solusi.

2.   Memberikan batasan waktu proses algoritma genetic. Menghitung kegagalan penggantian anggota populasi yang terjadi secara berurutan sampai jumlah tertentu.

Sumber:

https://id.wikipedia.org/wiki/Algoritma_genetik

http://informatika.web.id/algoritma-genetik.htm