Skip to content
Kembali ke hasil pencarian

Differential Evolution — Optimiser Stokastik Global

Diperkenalkan oleh
Rainer Storn & Kenneth Price
Tahun
1997
Jenis
Population-based stochastic metaheuristic

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

Ukuran huruf

Apa fungsinya?

Differential Evolution (DE), diperkenalkan oleh Rainer Storn dan Kenneth Price pada tahun 1997, adalah algoritma optimisasi stokastik berbasis populasi yang dirancang untuk ruang parameter kontinu.

Algoritma ini menghasilkan solusi kandidat dengan menggabungkan perbedaan vektor antar anggota populasi yang ada, menjadikannya alternatif yang kuat dan hemat parameter dibandingkan Algoritma Genetika dan Optimisasi Kawanan Partikel ketika lanskap pencarian bersifat non-konveks, multimodal, atau kurang cocok untuk metode berbasis gradien.

Intuisi di balik metode

Bayangkan sekelompok penjelajah tersebar di lanskap yang belum diketahui mencari lembah terendah. Di setiap langkah, setiap penjelajah mengamati tiga rekan yang dipilih secara acak, bergerak ke arah yang disarankan oleh perbedaan antara dua di antaranya yang diskalakan oleh faktor ukuran langkah, dan kemudian memutuskan apakah posisi baru atau posisi lama adalah medan yang lebih baik. Selama banyak putaran, seluruh kelompok secara bertahap mengelompok di sekitar lembah terdalam yang telah mereka temukan secara kolektif. Differential Evolution bekerja persis seperti ini: 'perbedaan' antara dua vektor populasi bertindak sebagai arah pencarian, dan faktor skala F mengontrol seberapa berani setiap langkahnya.

Sejarah

Differential Evolution diperkenalkan oleh Rainer Storn dan Kenneth Price dalam makalah penting mereka tahun 1997 di Journal of Global Optimization. Algoritma ini berkembang dari karya Price sebelumnya tentang penyejukan genetik dan eksperimen Storn dengan persilangan floating-point. Varian asli, yang sekarang disebut DE/best/1/bin, terbukti kompetitif dengan — dan sering kali lebih unggul dari — strategi evolusioner dan algoritma genetika kontemporer pada tolok ukur standar. Tinjauan komprehensif oleh Das, Mullick, dan Suganthan (2016) mengkatalogkan lebih dari dua dekade varian, skema adaptif, dan aplikasi, menetapkan DE sebagai salah satu metode fundamental dalam literatur metaheuristik.

Kapan digunakan

Differential Evolution sesuai ketika fungsi objektif bersifat kontinu, mungkin tidak dapat dibedakan atau multimodal, dan batas pencarian untuk semua parameter diketahui sebelumnya. Algoritma ini tidak memerlukan informasi gradien dan tidak ada asumsi normalitas, sehingga cocok untuk desain teknik, penyetelan hyperparameter, kalibrasi model simulasi, dan tugas optimisasi kotak hitam apa pun. Ukuran populasi sekitar 10 kali jumlah parameter adalah titik awal yang umum. DE tidak boleh diterapkan pada masalah diskrit atau kombinatorial murni; algoritma ini juga membutuhkan setidaknya 1.000 iterasi untuk konvergen secara andal — jika anggaran evaluasi fungsi sangat ketat, optimisasi Bayesian adalah alternatif yang lebih efisien sampel.

Batasan dan pertimbangan

  • Konvergensi bisa lambat jika jumlah iterasi tidak mencukupi; kurang dari 1.000 generasi sering kali menghasilkan hasil suboptimal.
  • Kinerja sensitif terhadap pilihan F dan CR — parameter yang disetel dengan buruk dapat menyebabkan konvergensi dini atau kemajuan yang terlalu lambat.
  • Tidak dirancang untuk ruang pencarian yang murni diskrit atau kombinatorial; ekstensi diskrit ada tetapi kurang standar.
  • Setiap iterasi memerlukan evaluasi fungsi objektif sebanyak NP kali, yang bisa mahal ketika setiap evaluasi secara komputasi mahal.

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

Kelebihan

  • Tidak memerlukan informasi gradien — bekerja dengan fungsi objektif kotak hitam apa pun, termasuk yang tidak dapat dibedakan dan yang berisik.
  • Sangat sedikit parameter kontrol (F, CR, NP) dibandingkan dengan kekuatan pencariannya, membuatnya relatif mudah dikonfigurasi.
  • Secara alami menangani lanskap multimodal di mana optimiser berbasis gradien konvergen ke optimum lokal.
  • Evaluasi populasi independen dan dapat diparalelkan secara langsung, mengurangi waktu dinding pada sistem multi-core.
  • Kompetitif dengan Algoritma Genetika dan Optimisasi Kawanan Partikel pada banyak tolok ukur sambil menggunakan aturan pembaruan yang lebih sederhana.

Penerapan

  • Kalibrasi model simulasi dan berbasis agen yang fungsi objektifnya non-analitik.
  • Optimisasi hyperparameter untuk pipeline pembelajaran mesin ketika ruang pencarian kontinu dan terbatas.
  • Masalah desain teknik seperti desain antena, optimisasi struktural, dan penyetelan pengontrol.
  • Melatih jaringan saraf dan menyesuaikan model non-linear dalam teknik dan ilmu alam.
  • Optimisasi bobot portofolio dan estimasi parameter dalam model deret waktu keuangan.

Cara kerjanya

Cara kerjanya

1

Sebuah populasi NP vektor solusi kandidat ditarik secara seragam secara acak dalam batas pencarian yang telah ditentukan untuk setiap parameter. Batas pencarian harus ditentukan oleh pengguna sebelum algoritma dimulai; DE tidak dapat menyimpulkannya dari masalah. Populasi awal yang baik mencakup seluruh ruang yang layak sehingga algoritma tidak melewatkan wilayah yang menjanjikan sejak awal.

2

Untuk setiap vektor target dalam populasi, tiga vektor yang berbeda dipilih secara acak. Vektor mutan dibentuk dengan menambahkan perbedaan yang diskalakan dari dua vektor ke vektor ketiga: v = x_r1 + F*(x_r2 - x_r3), di mana F adalah faktor skala (biasanya 0,4–1,0). Langkah berbasis perbedaan ini adalah yang membedakan DE dari algoritma evolusioner lainnya dan memberikannya informasi arah yang adaptif secara mandiri tanpa memerlukan komputasi gradien.

3

Vektor percobaan dibangun dengan mencampur vektor mutan dan vektor target asli elemen demi elemen. Setiap elemen diambil dari mutan dengan probabilitas CR (tingkat persilangan, biasanya 0,5–1,0) dan dari target sebaliknya; setidaknya satu elemen selalu diambil dari mutan. Langkah ini mengontrol keseimbangan antara eksplorasi dan eksploitasi: CR tinggi mendukung mutan, CR rendah mempertahankan lebih banyak dari solusi saat ini.

4

Vektor percobaan dievaluasi pada fungsi objektif dan dibandingkan dengan vektor target. Jika percobaan mencapai nilai objektif yang sama atau lebih baik, ia menggantikan target pada generasi berikutnya; jika tidak, target dipertahankan tidak berubah. Seleksi serakah satu-satu ini mencegah populasi memburuk dan memastikan peningkatan monoton dari solusi terbaik yang ditemukan.

5

Mutasi, persilangan, dan seleksi diulang untuk sejumlah generasi yang cukup (umumnya 1.000 atau lebih) hingga kriteria konvergensi terpenuhi — misalnya, perubahan nilai objektif terbaik turun di bawah ambang batas toleransi, atau jumlah iterasi maksimum tercapai. Vektor terbaik dalam populasi akhir adalah solusi algoritma.

Kesalahan umum

  • Menjalankan DE dengan iterasi yang terlalu sedikit (di bawah ~1.000) adalah kesalahan paling umum — algoritma belum memiliki generasi yang cukup untuk konvergen, dan hasilnya harus dianggap sebagai pendahuluan; beralih ke optimisasi Bayesian jika anggaran evaluasi ketat.
  • Menyetel faktor skala F terlalu rendah menyebabkan keragaman runtuh terlalu dini; menyetelnya terlalu tinggi mencegah konvergensi. Mulai dengan F dalam [0,4, 1,0] dan lakukan penyetelan secara empiris.
  • Menghilangkan atau salah menentukan batas pencarian adalah kesalahan kritis — DE menggunakan batas untuk menginisialisasi populasi dan akan menghasilkan hasil yang tidak berarti jika batasnya terlalu sempit atau tidak ada.
  • Memperlakukan DE sebagai satu kali jalan berisiko pada lanskap multimodal — jalankan beberapa uji coba independen dari benih acak yang berbeda dan laporkan solusi terbaik yang ditemukan di seluruh pengujian.

Pertanyaan yang sering diajukan

Bagaimana cara memilih faktor skala F dan tingkat persilangan CR?

Nilai default yang paling banyak dikutip adalah F = 0,8 dan CR = 0,9 untuk strategi DE/best/1/bin. Dalam praktiknya, F mengontrol ukuran langkah — nilai sekitar 0,4–1,0 adalah tipikal — dan CR mengontrol seberapa banyak mutan menggantikan target. Jika populasi konvergen terlalu cepat, naikkan F atau turunkan CR. Varian DE adaptif (jDE, JADE) menyesuaikan parameter ini secara otomatis selama berjalan, yang merupakan pilihan yang masuk akal ketika penyetelan manual tidak praktis.

Berapa banyak generasi yang dibutuhkan?

Sebagai aturan praktis, setidaknya 1.000 generasi direkomendasikan. Untuk masalah berdimensi tinggi (banyak parameter) atau lanskap yang kompleks, mungkin diperlukan lebih banyak iterasi. Amati nilai objektif dari solusi terbaik di seluruh generasi: jika tidak berubah selama ratusan iterasi, DE kemungkinan telah konvergen — atau stagnan, dalam hal ini menjalankan kembali dengan benih acak yang baru disarankan.

Bagaimana DE dibandingkan dengan Algoritma Genetika dan Optimisasi Kawanan Partikel?

Ketiganya adalah metaheuristik berbasis populasi untuk optimisasi kontinu. DE biasanya menggunakan lebih sedikit parameter kontrol daripada GA dan memiliki aturan pembaruan yang lebih sederhana dan deterministik dibandingkan dengan PSO. Pada banyak tolok ukur standar, DE kompetitif dengan atau mengungguli keduanya, tetapi kinerja bergantung pada masalah. Pilihan sering kali bergantung pada keakraban dan implementasi yang tersedia daripada peringkat universal.

Bisakah DE menangani parameter integer atau kategorikal?

DE dirancang untuk ruang kontinu. Parameter integer dapat diakomodasi dengan membulatkan solusi kontinu ke bilangan bulat terdekat setelah setiap pembaruan, tetapi ini adalah perkiraan. Masalah yang murni kategorikal atau kombinatorial — seperti penjadwalan atau perutean — lebih baik dilayani oleh metode yang dirancang untuk ruang diskrit, seperti Optimisasi Koloni Semut atau Pencarian Tabu.

Metode terkait

Sumber

  1. Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.

    Buka referensi DOI
    Disalin.
  2. Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.

    Buka referensi DOI
    Disalin.