Algoritma Genetika

Algoritma genetika merupakan algoritma optimasi. apa maksudnya optimasi??? optimasi adalah penyelesaian suatu masalah menggunakan suatu cara se simple mungkin dan se optimal mungkin. Dari namanya algoritma ini kita sudah tahu, algoritma ini terinspirasi dari fenomena alam, yaitu evolusi (teori darwin).

Algoritma genetika merupakan salah satu algoritma yang sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode yang konvensional.

Pertama kali algoritma ini di perkenalakan oleh John Holland (1975) dari Universitas Michigan. Mr.John Holland mengatakan bahwa setiap masalah yang berbentuk adaptasi (baik itu alami atau buatan), dan dapat diformulasikan dalam terminologi genetika. lalu Goldberg (1989)  mendefinisikan algoritma genetika ini sebagai suatu pencarian algoritma berdasarkan pada mekanisme seleksi alam dan genetika alam dan Bauer (1993) mendefinisikan algoritma genetika sebagai perangkat lunak, prosedur yang dimodelkan setelah genetika dan evolusi.

Algoritma Genetika ini banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan. Algoritma ini dapat dipakai untuk mendapatkan solusi yang tepat untuk masalah optimal dari satu variabel atau multi variabel. Sebelum algoritma ini dijalankan, masalah yang ingin dioptimalkan harus dinyatakan dalam fungsi tujuan, atau biasa dikenal dengan fungsi fitness. Jika nilai fitness semakin besar maka sistem yang si hasilkan semakin baik.

Sifat dari algoritma genetik adalah mencari kemungkinan-kemungkinan dari kandidat solusi untuk mendapatkan suatu solusi yang optimal bagi penyelesaian masalah. Ruang cakupan dari semua solusi yang layak (feasible) yaitu obyek-obyek di antara solusi yang sesuai dinamakan ruang pencarian (search space). Tiap titik dalam ruang pencarian merepresentasikan satu solusi yang layak. Tiap solusi yang layak dapat ditandai dengan nilai fitnessnya bagi masalah.Sifat dari pencarian inilah yang menyebabkan algoritma genetik baik diterapkan untuk menyelesaikan masalah NP-complete.

suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operator yaitu:  operator reproduksi, operator crossover (persilangan) dan operator mutasi. Algoritma genetik bergerak dari suatu populasi kromosom (bit string) yang direpresentasikan sebagai calon solusi suatu masalah ke populasi baru)

Algoritma genetika bekerja dari populasi yang merupakan himpunan solusi yang dihasilkan secara acak. Setiap anggota himpunan yang merepresentasikan satu solusi masalah dinamakan kromosom. Kromosom dalam suatu populasi berevolusi dalam iterasi yang dinamakan generasi, tiap kromosom dievaluasi berdasarkan pada fungsi evaluasi (fitness function). Pada algoritma genetika, fitness biasanya dapar berupa fungsi objektif dari masalah yang akan dioptimasi.

Kromosom-kromosom diseleksi menurut nilai fitness masing-masing. Kromosom yang kuat mempunyai kemungkinan tinggi untuk bertahan hidup pada generasi berikutnya tetapi tidak menutup kemungkinan juga kromosom lemah untuk tetap bertahan hidup dari proses seleksi tersebut kemudian ditentukan kromosom-kromosom baru (offspring) melalui proses crossover dan mutasi dari kromosom yang terpilih (parents). Dari dua proses tersebut di atas maka terbentuk suatu generasi baru yang akan diulangi secara terus menerus sampai tercapainya suatu konvergensi yaitu sebanyak generasi yang diinginkan.

Struktur Algoritma Genetik

Struktur umum dari algoritma genetika kurang lebih seperti ini flowchartnya

Inisialisasi awal dilakukan untuk mendapatkan solusi awal dari suatu permasalahan algoritma genetik. Inisisalisasi dilakukan secara acak sebanyak jumlah populasi/kromosom yang di inginkan. Lalu di hitung nilai fitnessnya dan seterusnya diseleksi dengan matode roda roullete, tournament atau ranking. Kemudian dilakukan perkawinan silang (CrossOver), lalu dilakukan perulangan sampai sebanyak generasi yang di inginkan.

Karakteristik-karakteristik Algoritma genetik menurut Goldberg

1. - AG bekerja dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dan bukan parameter itu sendiri. Sebagai contoh untuk mendapatkan minimum dari fungsi  f(x)=y=x3+x2+5, AG tidak secara langsung mencari nilai x atau y, tetapi terlebih dahulu merepresentasikan x dalam bentuk string biner.
2. - AG melakukan pencarian pada sebuah populasi dari sejumlah individu-individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu.
3. - AG merupakan informasi fungsi objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi.
4. - AG menggunakan aturan-aturan transisi peluang, bukan aturan-aturan deterministik.

Parameter yang digunakan

1. - Fungsi fitness(fungsi tujuan) yang dimiliki oleh masing-masing individu untuk menetukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai.
2. - Populasi jumlah individu yang dilibatkan pada setiap generasi
3. - Probabilitas terjadinya persilangan (crossover) pada suatu generasi
4. - Probabilitas terjadinya mutasi pada setiap individu.
5. - Jumlah generasi yang akan dibentuk yang menentukan lama dari penerapan AG

Inti dari proses Algoritma ini adalah membentuk populasi baru, setelah itu di bentuk generasi baru untuk memecahkan permasalahan, dan evaluasi generasi jika ada generasi yang sudah tidak layak, maka akan di gantikan dengan generasi baru yang lebih baik yang di hasilkan melalui proses crossover atau mutasi