Algoritma Genetika Stokastik — Pencarian Evolusioner Acak untuk Optimasi
- Diperkenalkan oleh
- Holland, J. H.
- Tahun
- 1975
- Jenis
- Stochastic evolutionary metaheuristic
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Algoritma Genetika Stokastik (SGA) adalah metaheuristik berbasis populasi yang meniru evolusi biologis — seleksi, persilangan (crossover), dan mutasi — untuk mencari solusi mendekati optimal dalam ruang yang kompleks, nonlinier, atau kombinatorial. Operator acaknya membuatnya kuat terhadap optimum lokal dan dapat diterapkan secara luas di bidang teknik, penjadwalan, pembelajaran mesin, dan riset operasi.
Intuisi di balik metode
Bayangkan sebuah populasi solusi kandidat bersaing untuk bertahan hidup. Solusi yang lebih baik lebih mungkin dipilih sebagai induk; keturunannya mewarisi dan menggabungkan sifat-sifat baik, sementara mutasi acak sesekali memperkenalkan kebaruan. Selama banyak generasi, proses ini konvergen menuju wilayah ruang pencarian berkualitas tinggi tanpa memerlukan informasi gradien. Label stokastik menggarisbawahi bahwa seleksi, persilangan, dan mutasi semuanya melibatkan penarikan probabilitas, yang membedakan GA kanonik dari varian deterministik yang jarang dan memberikannya kemampuan pencarian global.
Sejarah
Penjadwalan job-shop dan flow-shop dalam manufaktur dan logistik
Kapan digunakan
Gunakan Algoritma Genetika Stokastik ketika: (1) ruang pencarian besar, multimodal, atau diskontinu dan metode berbasis gradien gagal atau tidak berlaku; (2) fungsi tujuan adalah kotak hitam (black-box), berisik, atau mahal untuk dievaluasi tetapi dapat dikelola untuk pengambilan sampel tingkat populasi; (3) masalah kombinatorial atau bilangan bulat campuran (mixed-integer) tidak memiliki pemecah eksak yang efisien; (4) solusi mendekati optimal yang ditemukan dalam jumlah evaluasi yang wajar dapat diterima. JANGAN gunakan SGA ketika: masalahnya cembung (convex) atau gradien tersedia dan murah — optimasi klasik konvergen lebih cepat; ketika evaluasi fungsi sangat mahal (puluhan atau ratusan), metode berbasis populasi dapat menghabiskan anggaran; atau ketika solusi yang terjamin optimal diperlukan, karena GA tidak memberikan jaminan optimalitas.
Batasan dan pertimbangan
- Tidak ada jaminan menemukan optimum global; kualitas solusi bergantung pada ukuran populasi, pilihan operator, dan jumlah generasi.
- Mahal secara komputasi dibandingkan dengan metode berbasis gradien pada masalah mulus berdimensi rendah — diperlukan banyak evaluasi fungsi.
- Penyetelan hyperparameter (ukuran populasi, tingkat persilangan, tingkat mutasi) bergantung pada masalah dan seringkali memerlukan eksperimen.
- Konvergensi prematur dapat terjadi jika tekanan seleksi terlalu tinggi atau tingkat mutasi terlalu rendah, menjebak pencarian di wilayah suboptimal.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Tidak memerlukan informasi gradien — berlaku untuk tujuan kotak hitam, diskontinu, atau non-diferensiabel.
- Secara alami menangani ruang pencarian kombinatorial, bilangan bulat campuran, dan permutasi dengan pengkodean yang sesuai.
- Dapat diparalelkan berdasarkan desain: populasi dapat dievaluasi secara paralel, mengurangi waktu aktual (wall-clock time).
- Kuat terhadap optimum lokal karena keragaman populasi dan eksplorasi stokastik.
- Sangat dapat diperluas: operator, pengkodean, dan skema seleksi dapat disesuaikan untuk batasan spesifik domain.
Penerapan
- Seleksi fitur dan penyetelan hyperparameter dalam pipeline pembelajaran mesin
- Optimasi struktural dan topologi dalam teknik mesin dan sipil
- Masalah pedagang keliling (traveling salesman) dan rute kendaraan dalam riset operasi
- Prediksi struktur protein dan penemuan obat dalam bioinformatika
- Pencarian arsitektur jaringan saraf dan optimasi bobot
- Bagaimana Algoritma Genetika Stokastik berbeda dari Algoritma Genetika standar?
Cara kerjanya
Cara kerjanya
Hasilkan populasi awal N solusi kandidat (kromosom) secara acak atau dengan penaburan heuristik. Setiap kromosom mengkodekan titik yang layak dalam ruang keputusan — string biner, vektor riil, permutasi, atau pohon tergantung pada representasi masalah yang dipilih.
Hitung kebugaran (fitness) f(x_i) untuk setiap individu dalam populasi menggunakan fungsi tujuan (atau penggantinya). Kebugaran mengukur kualitas solusi; kebugaran yang lebih tinggi berarti solusi yang lebih baik. Untuk masalah minimisasi, kebugaran sering didefinisikan sebagai kebalikan atau transformasi dari fungsi biaya.
Rumus
f(x_i), \quad i = 1, \ldots, N
Terapkan operator seleksi stokastik untuk memilih induk. Seleksi roda rolet (proporsional terhadap kebugaran) memberikan setiap individu probabilitas yang proporsional dengan kebugarannya. Seleksi turnamen, seleksi peringkat, dan elitisme adalah varian umum yang mengontrol tekanan seleksi.
Rumus
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}Dengan probabilitas p_c (biasanya 0,6–0,9), gabungkan pasangan induk yang dipilih untuk menghasilkan keturunan. Persilangan satu titik, dua titik, atau seragam menukar materi genetik antara kromosom induk, menciptakan anak yang mewarisi sifat dari keduanya. Operator ini mendorong eksploitasi blok bangunan yang baik.
Dengan probabilitas rendah p_m (biasanya 0,001–0,05 per gen), ubah gen individu secara acak di setiap kromosom keturunan. Mutasi mempertahankan keragaman genetik, mencegah konvergensi prematur, dan memastikan algoritma dapat keluar dari optimum lokal. Tingkat mutasi adalah parameter kritis yang disesuaikan dengan masalah.
Ganti populasi saat ini dengan keturunan (penggantian generasi) atau gunakan pembaruan keadaan stabil (steady-state). Evaluasi kembali kebugaran dan ulangi dari langkah seleksi hingga kriteria penghentian terpenuhi — jumlah maksimum generasi, ambang batas kebugaran, atau tidak ada peningkatan selama sejumlah generasi yang ditetapkan.
Kesalahan umum
- Mengabaikan elitisme dalam strategi penggantian dapat menyebabkan solusi terbaik yang ditemukan hilang antar generasi.
- Menerapkan operator persilangan bernilai riil pada masalah yang dikodekan biner (atau sebaliknya) merusak pengkodean dan menghasilkan keturunan yang tidak layak.
- Berhenti terlalu dini — generasi tidak mencukupi — adalah alasan paling umum untuk kualitas solusi yang buruk dalam praktik.
- Mengabaikan penanganan kendala: persilangan dan mutasi yang tidak terkendala sering kali melanggar kendala masalah; fungsi penalti atau operator perbaikan harus dibangun secara eksplisit.
- John Holland memperkenalkan dasar-dasar teoritis algoritma genetika di University of Michigan pada tahun 1975, mengacu pada karya sebelumnya oleh Fraser (1957) tentang sistem genetik simulasi. Buku teks David Goldberg tahun 1989 mempopulerkan GA untuk optimasi teknik. Sifat stokastik seleksi diformalkan melalui teorema skema, dan metode ini menjadi landasan komputasi evolusioner dan kecerdasan komputasional.
Pertanyaan yang sering diajukan
Label 'stokastik' menekankan bahwa semua operator inti — seleksi, persilangan, dan mutasi — melibatkan penarikan probabilitas. GA kanonik yang diperkenalkan oleh Holland secara inheren stokastik. Label ini digunakan dalam literatur simulasi/optimasi untuk membedakan dari varian deterministik yang jarang (misalnya, crowdedness deterministik) dan untuk mengklarifikasi bahwa perilaku algoritma bervariasi antar eksekusi karena keacakan.
Seberapa besar populasi seharusnya?
Titik awal yang umum adalah 50–200 individu untuk masalah berdimensi sedang. Populasi yang lebih besar meningkatkan keragaman dan mengurangi konvergensi prematur tetapi meningkatkan biaya komputasi per generasi. Ada aturan praktis berdasarkan panjang kromosom (misalnya, 10× jumlah gen), tetapi penyetelan empiris atau meta-optimasi seringkali diperlukan.
Kapan saya harus memilih Optimasi Kawanan Partikel (Particle Swarm Optimization) atau Annealing Simulasi (Simulated Annealing) daripada Algoritma Genetika?
Optimasi Kawanan Partikel (PSO) seringkali lebih cepat pada masalah bernilai riil kontinu karena memanfaatkan informasi kecepatan. Annealing Simulasi (SA) lebih sederhana untuk diimplementasikan dan dapat efektif untuk pencarian lintasan solusi tunggal. GA lebih disukai ketika ruang pencarian bersifat kombinatorial, ketika persilangan secara bermakna menggabungkan struktur solusi, atau ketika keragaman populasi berharga untuk lanskap multimodal.
Apakah Algoritma Genetika Stokastik dapat diskalakan ke masalah berdimensi tinggi?
Kinerja menurun pada dimensi yang sangat tinggi (ratusan hingga ribuan variabel) karena populasi harus cukup besar untuk mengambil sampel ruang secara memadai. Varian khusus — seperti GA yang mempelajari keterkaitan (linkage-learning), algoritma estimasi distribusi, atau model pulau dengan migrasi — mengatasi skalabilitas tetapi menambah kompleksitas.
Bagaimana cara menangani kendala dalam Algoritma Genetika?
Tiga strategi utama digunakan: (1) fungsi penalti yang mengurangi kebugaran untuk pelanggaran kendala; (2) operator perbaikan yang memproyeksikan keturunan yang tidak layak kembali ke wilayah yang layak; (3) pengkodean dan operator khusus yang hanya menghasilkan solusi yang layak berdasarkan konstruksi. Metode berbasis penalti adalah yang termudah untuk diimplementasikan tetapi memerlukan kalibrasi koefisien penalti yang cermat.
Dalam praktik, atur ukuran populasi ke 50–100, tingkat persilangan ke 0,8, dan tingkat mutasi ke 1/L di mana L adalah panjang kromosom. Selalu sertakan elitisme (pertahankan 1–5 individu teratas). Jalankan setidaknya 200–500 generasi untuk masalah yang tidak sepele. Bandingkan beberapa eksekusi independen untuk menilai konsistensi solusi dan laporkan nilai tujuan terbaik, rata-rata, dan standar deviasi di seluruh eksekusi.
Metode terkait
Sumber
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
ISBN: 978-0262581110Disalin.Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.
ISBN: 978-0201157673Disalin.