Skip to content
Kembali ke hasil pencarian

Algoritma Genetik — Optimasi Evolusioner

Diperkenalkan oleh
John Henry Holland
Tahun
1975
Jenis
Population-based metaheuristic

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Algoritma genetik (AG) adalah metode optimasi metaheuristik berbasis populasi yang diperkenalkan oleh John Henry Holland (1975) yang meniru prinsip seleksi alam.

Algoritma ini memelihara populasi solusi kandidat dan secara iteratif memperbaikinya melalui operator seleksi, persilangan (crossover), dan mutasi, menjadikannya sangat ampuh pada ruang pencarian yang diskontinu, non-konveks, dan multimodal di mana metode berbasis gradien klasik gagal.

Intuisi di balik metode

Bayangkan Anda memiliki ribuan kemungkinan jawaban untuk masalah yang sulit dan tidak ada rumus untuk menemukan yang terbaik. Algoritma genetik memperlakukan setiap jawaban kandidat sebagai individu dalam populasi. Dalam setiap generasi, ia mempertahankan individu yang paling bugar, mengawinkannya untuk mencampur sifat-sifat baiknya, dan sesekali memutasikan keturunannya untuk menyuntikkan kebaruan. Selama banyak generasi, populasi bergeser menuju solusi yang semakin baik — bukan dengan mengikuti gradien, tetapi dengan meniru cara evolusi membentuk organisme dari waktu ke waktu.

Sejarah

Algoritma genetik diperkenalkan oleh John Henry Holland dalam bukunya tahun 1975 Adaptation in Natural and Artificial Systems, yang memformalkan gagasan skema (blok pembangun) dan memberikan analisis teoretis mendasar tentang mengapa persilangan dan seleksi mendorong pencarian menuju wilayah yang lebih bugar. Murid-murid Holland — terutama David Goldberg — mempopulerkan AG melalui aplikasi teknik pada tahun 1980-an. Kalyanmoy Deb kemudian memperluas kerangka kerja ke pengaturan multi-objektif, yang berpuncak pada algoritma NSGA-II yang diadopsi secara luas (2002). Saat ini AG tetap menjadi alat standar dalam komputasi evolusioner, dengan penelitian aktif dalam metode hibrida yang menggabungkan pencarian evolusioner dengan penyempurnaan lokal.

Kapan digunakan

Algoritma genetik sesuai ketika ruang pencarian besar, diskontinu, non-diferensiabel, atau sangat multimodal — kondisi di mana pemecah berbasis gradien tidak dapat beroperasi atau terjebak dalam optimum lokal. Algoritma ini berlaku untuk tipe variabel kontinu, kategorikal, biner, dan ordinal serta tidak memberlakukan asumsi normalitas atau distribusi. Satu-satunya persyaratan adalah fungsi kebugaran yang dapat dihitung. Untuk masalah di mana formulasi analitik atau konveks ada, metode klasik (pemrograman linier, penurunan gradien) lebih cepat dan harus diutamakan. Iterasi yang cukup (biasanya jauh di atas 1.000 generasi) diperlukan untuk konvergensi yang bermakna; menjalankan terlalu sedikit generasi adalah mode kegagalan yang paling umum.

Batasan dan pertimbangan

  • Tidak ada jaminan konvergensi ke optimum global; hasil dapat bervariasi antar pengujian.
  • Mahal secara komputasi: setiap generasi memerlukan evaluasi seluruh populasi, yang memberatkan ketika fungsi kebugaran lambat.
  • Kinerja sensitif terhadap pilihan hiperparameter — ukuran populasi, probabilitas persilangan, dan laju mutasi — yang seringkali memerlukan penyetelan spesifik masalah.
  • Untuk masalah yang mulus, konveks, atau terstruktur dengan baik, metode klasik berbasis gradien atau linier akan lebih cepat dan lebih andal.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Bekerja pada lanskap objektif yang diskontinu, non-diferensiabel, dan multimodal di mana metode berbasis gradien gagal.
  • Tidak memberlakukan asumsi distribusi — satu-satunya masukan yang diperlukan adalah fungsi kebugaran yang dapat dihitung.
  • Secara alami menangani berbagai jenis variabel: kontinu, biner, kategorikal, dan ordinal.
  • Keragaman populasi memungkinkan eksplorasi simultan dari berbagai wilayah ruang pencarian, mengurangi risiko jebakan optimum lokal prematur.
  • Sangat dapat diperluas: operator persilangan dan mutasi spesifik domain, penanganan kendala, dan varian multi-objektif (misalnya, NSGA-II) sudah mapan dalam literatur.

Penerapan

  • Optimasi desain teknik: menemukan konfigurasi parameter optimal untuk struktur, sirkuit, atau sistem mekanik.
  • Masalah penjadwalan dan perutean: penjadwalan job-shop, perutean kendaraan, dan pembuatan jadwal di mana ruang pencarian kombinatorial terlalu besar untuk pencarian menyeluruh.
  • Pembelajaran mesin: penyetelan hyperparameter, pencarian arsitektur saraf, dan pemilihan fitur.
  • Riset operasi: optimasi rantai pasokan, alokasi portofolio, dan penugasan sumber daya di bawah kendala yang kompleks.
  • Bioinformatika: penyelarasan sekuens, prediksi struktur protein, dan inferensi jaringan regulasi gen.

Cara kerjanya

Cara kerjanya

1

Sebuah populasi solusi kandidat (individu) dibuat, biasanya secara acak dalam ruang pencarian. Setiap individu mengkodekan solusi potensial — misalnya sebagai string biner, vektor bernilai riil, atau permutasi — dan ukuran populasi adalah parameter kunci yang menentukan seberapa luas ruang pencarian diambil sampelnya sejak awal.

2

Setiap individu dalam populasi dinilai oleh fungsi kebugaran (fitness function) yang mengukur seberapa baik solusi tersebut relatif terhadap tujuan masalah. Fungsi kebugaran adalah satu-satunya komponen spesifik domain yang harus disediakan pengguna; dapat berupa ukuran apa pun yang dapat dihitung — keluaran simulasi, rumus biaya, atau metrik kesalahan model.

3

Individu dengan kebugaran lebih tinggi dipilih secara istimewa untuk menjadi induk bagi generasi berikutnya. Mekanisme seleksi umum meliputi seleksi turnamen, seleksi roda roulette (proporsional kebugaran), dan seleksi berbasis peringkat. Tekanan seleksi mengontrol keseimbangan antara mengeksploitasi solusi berkualitas tinggi dan mempertahankan keragaman populasi.

4

Induk terpilih menghasilkan keturunan melalui persilangan (rekombinasi), di mana segmen dari pengkodean dua induk digabungkan untuk membentuk individu baru, dan melalui mutasi, di mana perubahan acak kecil diterapkan pada gen individu. Probabilitas persilangan dan laju mutasi adalah parameter penyetelan kritis: terlalu sedikit mutasi menyebabkan konvergensi prematur, terlalu banyak mengubah pencarian menjadi jalan acak.

5

Siklus evaluasi → seleksi → reproduksi berlanjut untuk sejumlah generasi yang ditetapkan atau hingga kriteria konvergensi terpenuhi (misalnya, tidak ada peningkatan selama jendela generasi). Individu terbaik yang ditemukan di semua generasi dikembalikan sebagai solusi. Karena konvergensi ke optimum global tidak dijamin, beberapa kali pengujian independen direkomendasikan untuk masalah berisiko tinggi.

Kesalahan umum

  • Menjalankan terlalu sedikit generasi adalah kesalahan paling umum: dengan generasi yang tidak mencukupi, algoritma tidak konvergen, sehingga metode analitik atau berbasis gradien harus diutamakan ketika hanya anggaran iterasi yang kecil yang tersedia.
  • Konvergensi prematur — populasi kehilangan keragaman terlalu dini — menghasilkan hasil optimum lokal tetapi suboptimal global; pertahankan ukuran populasi dan laju mutasi yang memadai untuk menangkal ini.
  • Menggunakan fungsi kebugaran yang salah didefinisikan atau salah spesifikasi menghasilkan hasil yang menyesatkan terlepas dari kebenaran algoritmik; validasi fungsi kebugaran secara independen sebelum menjalankan AG.
  • Menerapkan AG pada masalah mulus, konveks di mana penurunan gradien atau pemrograman linier sudah cukup akan membuang sumber daya komputasi dan memperkenalkan stokastisitas yang tidak perlu.
  • Melaporkan satu kali pengujian sebagai solusi tanpa memeriksa reproduktibilitas; untuk aplikasi berisiko tinggi, jalankan algoritma berkali-kali dan laporkan distribusi hasil.

Pertanyaan yang sering diajukan

Bagaimana algoritma genetik berbeda dari penurunan gradien?

Penurunan gradien memerlukan tujuan yang dapat dibedakan dan mengikuti gradien lokal ke bawah. Algoritma genetik hanya memerlukan kebugaran dapat dihitung untuk solusi kandidat apa pun; ia mencari dengan mengembangkan populasi daripada mengikuti gradien, sehingga dapat menangani lanskap yang diskontinu, non-diferensiabel, dan multimodal di mana penurunan gradien gagal atau terjebak.

Berapa generasi dan seberapa besar populasi yang saya butuhkan?

Tidak ada aturan universal; keduanya bergantung pada kompleksitas ruang pencarian. Populasi yang terlalu kecil atau pengujian yang terlalu singkat berisiko konvergensi prematur. Sebagai titik awal praktis, ukuran populasi 50–200 dan jumlah generasi 100–1.000 umum dalam literatur, tetapi masalah yang menantang secara rutin memerlukan lebih banyak. Selalu periksa kurva konvergensi daripada menetapkan kriteria penghentian yang sewenang-wenang.

Apakah algoritma genetik dijamin menemukan optimum global?

Tidak. AG adalah heuristik dan tidak memberikan jaminan konvergensi ke optimum global dalam waktu terbatas. Untuk jaminan deterministik, Anda memerlukan metode eksak seperti pemecah pemrograman integer. Untuk keputusan berisiko tinggi, jalankan AG berkali-kali, laporkan distribusi hasil, dan bandingkan solusi terbaik dengan batas yang diketahui.

Kapan saya harus memilih AG daripada simulated annealing atau particle swarm optimisation?

AG cenderung lebih disukai ketika solusi secara alami dikodekan sebagai struktur kombinatorial (permutasi, string biner) atau ketika ekstensi multi-objektif diperlukan. Particle swarm optimisation seringkali lebih cepat pada masalah unimodal kontinu. Simulated annealing lebih sederhana untuk diimplementasikan untuk masalah kombinatorial dengan lingkungan yang terdefinisi dengan baik. Dalam praktiknya, melakukan benchmark pada dua atau tiga metode pada contoh masalah kecil sebelum berkomitmen pada satu metode disarankan.

Metode terkait

Sumber

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Buka referensi publikasi
    Disalin.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Disalin.