Algoritma genetika memberikan suatu pilihan bagi penentuan nilai parameter dengan meniru cara reproduksi genetik, pembentukan kromosom baru serta seleksi alami seperti terjadi pada mahluk hidup.
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.
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.
- Seleksi
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.
Operator Genetik dalam Algoritma Genetika
- Crossover: penggabungan kromosom dari dua orangtua untuk menghasilkan keturunan baru.
- Mutasi: perubahan acak pada kromosom keturunan untuk menghasilkan variasi dalam populasi.
- Seleksi alam: menghilangkan individu yang buruk dari populasi dan mempertahankan individu yang baik.
- Seleksi berbasis fitness: menentukan individu terbaik yang akan dijadikan induk untuk generasi selanjutnya berdasarkan fitness function.
- Elitisme: menjaga individu terbaik dari generasi sebelumnya dalam populasi saat melakukan seleksi.
- Penggantian generasi: mengganti generasi lama dengan generasi baru setelah melakukan seleksi dan operator genetik.
Parameter dalam Algoritma Genetika
- Ukuran populasi: jumlah individu dalam populasi pada setiap generasi.
- Probabilitas crossover: probabilitas bahwa crossover akan terjadi saat melakukan operator genetik.
- Probabilitas mutasi: probabilitas bahwa mutasi akan terjadi saat melakukan operator genetik.
- Jumlah generasi: jumlah iterasi atau generasi yang dijalankan sebelum terminasi.
- Fitness function: fungsi yang digunakan untuk mengevaluasi kualitas individu dalam populasi.
- Panjang kromosom: jumlah gen dalam kromosom yang digunakan dalam populasi.
Aplikasi Algoritma Genetika
- Pencarian solusi optimal dalam bidang matematika dan optimasi.
- Desain sistem terdistribusi dan pengalokasian sumber daya.
- Peramalan dan analisis data, seperti dalam trading saham dan pemrosesan citra.
- Desain dan optimasi sistem manufaktur.
- Pemilihan fitur dalam pengenalan pola dan pembelajaran mesin.
- Optimasi parameter dalam pembelajaran mesin dan jaringan saraf tiruan.
- Pemecahan masalah di bidang biologi, seperti pemetaan genom dan perancangan obat.
Kelebihan dan Kekurangan Algoritma Genetika
- Kelebihan:
- Dapat menemukan solusi yang baik dalam waktu yang relatif singkat.
- Memiliki kemampuan untuk menemukan solusi yang optimal atau suboptimal secara otomatis.
- Dapat digunakan untuk menyelesaikan berbagai masalah optimasi dan pencarian.
- Mudah dimodifikasi dan dapat disesuaikan dengan masalah tertentu.
- Dapat bekerja dengan baik pada masalah yang memiliki banyak variabel dan kompleksitas tinggi.
- Kekurangan:
- Terkadang menghasilkan solusi suboptimal atau tidak memuaskan karena keterbatasan ukuran populasi atau metode seleksi yang digunakan.
- Membutuhkan banyak waktu dan sumber daya komputasi jika digunakan pada masalah yang sangat kompleks.
- Dalam beberapa kasus, sulit untuk menentukan fitness function yang tepat.
- Operator genetik yang digunakan dapat menghasilkan solusi yang tidak valid atau menimbulkan efek samping yang tidak diinginkan.
Perbandingan Algoritma Genetika dengan Metode Optimasi Lainnya
- Algoritma genetika vs. pencarian garis: Algoritma genetika mampu menemukan solusi yang optimal atau suboptimal secara otomatis, sedangkan pencarian garis hanya dapat menemukan solusi terbatas pada area yang telah ditentukan.
- Algoritma genetika vs. optimasi gradient: Algoritma genetika dapat menemukan solusi pada ruang pencarian yang kompleks dan tidak teratur, sedangkan optimasi gradient hanya dapat bekerja pada ruang pencarian yang halus dan teratur.
- Algoritma genetika vs. simulasi annealing: Algoritma genetika dapat menemukan solusi secara otomatis tanpa memerlukan parameter tuning yang rumit, sedangkan simulasi annealing memerlukan tuning parameter yang cermat.
- Algoritma genetika vs. swarm intelligence: Algoritma genetika mampu menemukan solusi dengan variasi yang lebih banyak dibandingkan swarm intelligence, namun swarm intelligence memiliki kecepatan konvergensi yang lebih cepat.
- Algoritma genetika vs. neural network: Algoritma genetika mampu menemukan solusi dengan variasi yang lebih banyak, sedangkan neural network memerlukan waktu yang lebih singkat dalam pelatihan. Namun keduanya dapat digunakan bersama-sama untuk meningkatkan kinerja sistem pembelajaran mesin.
Pengembangan Terkini dalam Algoritma Genetika
- Penggunaan algoritma genetika dalam pembelajaran mesin dan deep learning.
- Pengembangan algoritma genetika berbasis pemrograman genetik untuk menemukan solusi yang lebih efektif.
- Penggunaan teknik genetika dalam penyelesaian masalah dalam bidang biologi seperti pengobatan kanker dan terapi gen.
- Integrasi algoritma genetika dengan teknologi blockchain untuk menghasilkan sistem keamanan yang lebih baik.
- Pengembangan algoritma genetika berbasis quantum untuk menyelesaikan masalah optimasi yang sangat kompleks.
Aplikasi Algoritma Genetika dalam Berbagai Bidang
Algoritma genetika telah diterapkan dalam berbagai bidang, di antaranya:
- Bidang industri: Algoritma genetika digunakan dalam pengaturan jadwal produksi, perencanaan logistik, pengoptimasian rantai pasok, dan pengendalian kualitas.
- Bidang keuangan: Algoritma genetika digunakan dalam peramalan harga saham, portofolio investasi, dan pengoptimasian risiko investasi.
- Bidang sains: Algoritma genetika digunakan dalam identifikasi struktur protein, optimasi proses kimia, dan perancangan obat.
- Bidang rekayasa: Algoritma genetika digunakan dalam perancangan mesin dan kendaraan, optimasi proses manufaktur, dan pengaturan jadwal perawatan mesin.
- Bidang komputer: Algoritma genetika digunakan dalam optimasi pengaturan parameter pada mesin pencari (search engine), pelatihan model jaringan saraf (neural network), dan perancangan sirkuit terpadu (integrated circuit).
- Bidang permainan: Algoritma genetika digunakan dalam pembuatan kecerdasan buatan (artificial intelligence) pada permainan, seperti catur dan Go.