Algoritma GenetikaKOnsep Algoritma GenetikaAlgoritma genetika (AG) adalah suatu algoritma pencarian yang berbasis pada mekanisme dari seleksi alam dan genetika. Algoritma genetika merupakan salah satu algoritma yang sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode yang konvensional.Algoritma Genetika diperkenalkan pertama kali oleh John Holland (1975) dari Universitas Michigan. John Holland menyatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat diformulasikan dalam terminologi genetika, kemudian 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.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.Solusi yang dicari dalam algoritma genetik adalah titik (satu atau lebih) di antara solusi yang layak dalam ruang pencarian. Sifat dari pencarian inilah yang menyebabkan algoritma genetik baik diterapkan untuk menyelesaikan masalah NP-complete.Algoritma genetik bergerak dari suatu populasi kromosom (bit string yang direpresentasikan sebagai calon solusi suatu masalah ke populasi baru dengan menggunakan 3 operator yaitu seleksi, crossover dan mutasi.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 Umum Algoritma GenetikAlgoritma genetika memberikan suatu pilihan bagi penentuan nilai parameter dengan meniru cara reproduksi genetik, pembentukan kromosom baru serta seleksi alami seperti yang terjadi pada makhluk hidup.Struktur umum algoritma genetik dapat diilustrasikan dalam diagram alir berikut ini :

Gambar 2.1. Diagram Alir Algoritma genetikaInisialisasi populasi awal dilakukan untuk menghasilkan solusi awal dari suatu permasalahan algoritma genetika. Inisialisasi ini dilakukan secara acak sebanyak jumlah kromosom/populasi yang diinginkan. Selanjutnya dihitung nilai fitness dan seterusnya dilakukan seleksi dengan menggunakan metode roda roullete, tournament atau ranking. Kemudian dilakukan perkawinan silang (crossover) dan mutasi. Setelah melalui beberapa generasi maka algoritma ini akan berhenti sebanyak generasi yang diinginkan.Goldberg(1989) mengemukakan bahwa algoritma genetika mempunyai karakteristik-karakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain yaitu :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 pada algoritma genetika adalah :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 generasi3. Probabilitas terjadinya persilangan (crossover) pada suatu generasi4. Probabilitas terjadinya mutasi pada setiap individu.5. Jumlah generasi yang akan dibentuk yang menentukan lama dari penerapan AGSecara umum Thiang, dkk (2001) mengemukakan bahwa struktur dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut: Membangkitkan populasi awalPopulasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan. Membentuk generasi baruUntuk membentuk generasi baru digunakan operator reproduksi/seleksi, crossover dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru. Generasi baru ini dikenal dengan istilah anak (offspring). Evaluasi solusiPada tiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang dinamakan fitness. Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut. Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. Beberapa kriteria berhenti yang sering digunakan antara lain : berhenti pada generasi tertentu, berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah, berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi.Sebelum algoritma genetika dilakukan, ada dua hal penting yang harus dilakukan yaitu pendefinisian kromosom yang merupakan suatu solusi yang masih berbentuk simbol dan fungsi fitness atau fungsi obyektif. Dua hal ini berperan penting dalam algoritma genetika untuk menyelesaikan suatu masalah