Algoritma genetika merupakan sebuah algoritma komputasi yang diinspirasi teori evolusi yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”. Salah satu aplikasi algoritma genetika adalah pada permasalahan optimasi kombinasi, yaitu mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang mempunyai banyak kemungkinan solusi. Dalam tulisan ini, akan dibahas teori dasar algoritma genetika beserta contoh aplikasinya dalam menyelesaikan suatu permasalahan optimasi kombinasi sederhana.
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 Natural and Artificial Systems” pada tahun 1975.
Struktur Umum Algoritma Genetika
Struktur umum algoritma genetik dapat diilustrasikan dalam diagram alir berikut ini:
Inisialisasi 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.
Algoritma Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string ‘0’ dan ‘1’, walaupun dimungkinkan 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 individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.
Karakteristik Algoritma Genetika
Goldberg (1989) mengemukakan bahwa algoritma genetika mempunyai karakteristik-karakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain yaitu:
- 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=x4+2x3+5, AG tidak secara langsung mencari nilai x atau y, tetapi terlebih dahulu merepresentasikan x dalam bentuk string biner.
- AG melakukan pencarian pada sebuah populasi dari sejumlah individu-individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu.
- AG merupakan informasi fungsi objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi.
- AG menggunakan aturan-aturan transisi peluang, bukan aturan-aturan deterministik.
Parameter yang digunakan pada algoritma genetika adalah:
- Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai.
- Populasi jumlah individu yang dilibatkan pada setiap generasi
- Probabilitas terjadinya persilangan (crossover) pada suatu generasi
- Probabilitas terjadinya mutasi pada setiap individu.
- Jumlah generasi yang akan dibentuk yang menentukan lama dari penerapan AG
Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operator yaitu : operator reproduksi, operator crossover (persilangan) dan operator mutasi.
Langkah-langkah Algoritma Genetika
Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut:
- Pengkodean Pengkodean disini meliputi pengkodean gen dan kromosom.
- Inisialisasi populasi awal Membangkitkan sejumlah kromosom (sesuai dengan ukuran populasi) untuk dijadikan anggota populasi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan.
- Evaluasi nilai fitnes Setiap kromosom pada populasi dihitung nilai fitnessnya berdasarkan fungsi 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.
- Pembentukan kromosom baru
- Seleksi Memilih sejumlah kromosom yang akan menjadi kromosom calon parent
- Crossover Mengkombinasikan dua kromosom parent (induk) berdasar nilai probabilitas crossovernya untuk menghasilkan offspring
- Mutasi Mengubah sejumlah gen berdasar nilai probabilitas mutasinya untuk menghasilkan kromosom baru.
- Update Generasi Membaharui kromosom yang terdapat dalam populasi.
- Pengecekan faktor pemberhenti
Jika memenuhi dari salah satu dari kondisi untuk berhenti, maka siklus algoritma genetika berhenti. Proses evolusi bisa dihentikan berdasarkan beberapa kondisi, misalnya ketika:
- evolusi telah mencapai jumlah generasi maksimum yang diizinkan,
- terdapat suatu individu yang telah memiliki fitness tertentu yang diharapkan,
- keberagaman populasi telah mencapai tingkat minimum yang diizinkan,
- dalam beberapa generasi tertentu, tidak ada peningkatan nilai fitness yang diharapkan.
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.
Sumber:
https://id.wikipedia.org/wiki/Algoritma_genetik
http://informatika.web.id/struktur-umum-algoritma-genetika.htm