Skip to content
Kembali ke hasil pencarian

Strategi Evolusi (CMA-ES) — Adaptasi Matriks Kovarians

Diperkenalkan oleh
Nikolaus Hansen & Andreas Ostermeier
Tahun
2001
Jenis
Derivative-free continuous black-box optimizer

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

Ukuran huruf

Apa fungsinya?

CMA-ES, singkatan dari Covariance Matrix Adaptation Evolution Strategy, adalah pengoptimal turunan-bebas modern untuk fungsi kotak-hitam kontinu yang diperkenalkan oleh Hansen dan Ostermeier pada tahun 2001.

Algoritma ini mempertahankan populasi solusi kandidat yang ditarik dari distribusi normal multivariat dan secara iteratif memperbarui rata-rata, ukuran langkah, dan matriks kovarians lengkap dari distribusi tersebut untuk mengarahkan pencarian menuju wilayah ruang parameter yang lebih baik. Algoritma ini telah menjadi standar de-facto untuk optimasi kotak-hitam kontinu dan banyak digunakan dalam pencarian arsitektur saraf dan optimasi kebijakan pembelajaran penguatan.

Intuisi di balik metode

Bayangkan Anda sedang mencari titik terendah di lanskap berbukit tetapi Anda tidak dapat melihat medannya — Anda hanya dapat menyelidiki lokasi individual dan mengetahui ketinggiannya. CMA-ES bekerja seperti kawanan yang dipandu: ia menjatuhkan awan penyelidik di sekitar perkiraan terbaik saat ini, mengukur seberapa baik setiap penyelidik, dan kemudian membentuk kembali awan untuk putaran berikutnya. Awan tersebut bukanlah bola sederhana — ia mempelajari bentuk lembah yang memanjang dan miring tempat ia turun dengan mengingat arah mana yang mengarah pada perbaikan. Selama beberapa generasi berturut-turut, awan menyempit dan miring untuk sejajar dengan kelengkungan permukaan kerugian, memungkinkan algoritma menavigasi lembah panjang yang sempit yang akan menjebak metode yang lebih sederhana.

Sejarah

Strategi evolusi diperkenalkan pada tahun 1960-an dan 1970-an sebagai keluarga pengoptimal berbasis populasi yang terinspirasi oleh evolusi biologis. Mekanisme adaptasi matriks kovarians dikembangkan oleh Hansen dan Ostermeier dan dijelaskan sepenuhnya dalam makalah Evolutionary Computation mereka tahun 2001, yang menunjukkan bahwa adaptasi diri yang sepenuhnya derandomisasi — mempelajari geometri urutan kedua dari lanskap pencarian dari riwayat langkah-langkah yang berhasil — secara dramatis mengungguli strategi evolusi sebelumnya pada masalah yang berkondisi buruk dan tidak terpisahkan. Tutorial Hansen tahun 2016 mengkonsolidasikan algoritma dan sifat-sifat teoretisnya, menjadikan CMA-ES sebagai metode referensi standar untuk pembandingan optimasi kotak-hitam kontinu.

Kapan digunakan

CMA-ES sesuai ketika fungsi objektifnya kontinu, mungkin tidak cembung, multimodal, atau bising, dan ketika informasi gradien tidak tersedia atau terlalu mahal untuk dihitung. Rentang dimensi yang ideal adalah sekitar 10 hingga 1000 parameter; di bawah 10 dimensi metode yang lebih sederhana seringkali sudah cukup, dan di atas 1000 biaya memori kuadratik dari matriks kovarians dapat menjadi penghalang. Tidak ada persyaratan ukuran sampel minimum dalam arti statistik — algoritma itu sendiri menghasilkan titik evaluasinya sendiri. CMA-ES sangat cocok untuk penyetelan hyperparameter, pencarian arsitektur saraf, optimasi kebijakan pembelajaran penguatan, dan masalah desain teknik di mana simulator hanya menyediakan keluaran kotak-hitam.

Batasan dan pertimbangan

  • Biaya memori kuadratik dan komputasi per generasi dalam jumlah dimensi membatasi penerapan di atas sekitar 1000 parameter tanpa varian pengurangan dimensi.
  • Konvergen ke optimum lokal tanpa pengulangan; untuk lanskap yang sangat multimodal, beberapa pengulangan (IPOP-CMA-ES atau BIPOP-CMA-ES) diperlukan.
  • Tidak cocok untuk ruang pencarian diskrit atau kombinatorial — metode ini secara inheren didefinisikan pada vektor bernilai riil kontinu.

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

Kelebihan

  • Tidak memerlukan informasi gradien — bekerja pada fungsi objektif yang dapat dipanggil apa pun, termasuk yang bising atau berbasis simulasi.
  • Mempelajari kelengkungan lokal lanskap pencarian melalui adaptasi kovarians, memungkinkannya menavigasi ruang pencarian yang memanjang dan berkondisi buruk yang mengalahkan metode bebas gradien dengan distribusi pencarian tetap.
  • Invarian terhadap transformasi yang mempertahankan urutan dari fungsi objektif dan terhadap rotasi ruang pencarian, membuatnya kuat di berbagai geometri masalah.
  • Sangat cocok untuk masalah kontinu berdimensi sedang hingga tinggi (10–1000 parameter) dengan satu hyperparameter yang dapat disetel — ukuran langkah awal.

Penerapan

  • Penyetelan hyperparameter untuk model pembelajaran mesin, termasuk arsitektur jaringan saraf dan agen pembelajaran penguatan.
  • Pencarian arsitektur saraf — mengoptimalkan parameter arsitektur yang dikodekan secara diskrit melalui relaksasi kontinu.
  • Optimasi kebijakan pembelajaran penguatan ketika kebijakan diparameterisasi oleh vektor kontinu.
  • Optimasi desain teknik, seperti optimasi bentuk aerodinamis dan penyesuaian parameter struktural, di mana hanya keluaran simulator yang tersedia.
  • Kalibrasi model ilmiah — menyesuaikan model simulasi dengan data eksperimental ketika kemungkinan tidak dapat dibedakan atau mahal secara komputasi.

Cara kerjanya

Cara kerjanya

1

Algoritma ini diawali dengan vektor solusi awal dan ukuran langkah awal (sigma). Matriks kovarians dimulai sebagai matriks identitas — awan pencarian yang sangat bulat. Ukuran populasi ditetapkan, biasanya sekitar 4 + floor(3 * ln(dimensi)).

2

Pada setiap generasi, populasi solusi kandidat diambil sampelnya dari distribusi normal multivariat saat ini yang didefinisikan oleh vektor rata-rata, ukuran langkah, dan matriks kovarians. Karena distribusinya normal multivariat, sampel mencerminkan perkiraan terbaik saat ini dan bentuk ruang pencarian yang dipelajari.

3

Setiap solusi kandidat dilewatkan ke fungsi objektif dan menerima skor kebugaran. Tidak ada informasi gradien yang diperlukan — hanya nilai objektif skalar di setiap titik yang diambil sampelnya. Hal ini membuat CMA-ES cocok untuk tujuan yang bising, tidak dapat dibedakan, dan berbasis simulasi.

4

Rata-rata digeser menuju solusi berperingkat lebih baik. Matriks kovarians dan ukuran langkah diperbarui menggunakan dua jalur adaptasi komplementer — pembaruan peringkat-satu dan peringkat-mu — sehingga arah yang menghasilkan perbaikan yang baik menjadi lebih mungkin pada generasi berikutnya. Ini adalah mekanisme inti di mana CMA-ES mempelajari geometri lokal dari lanskap.

5

Algoritma mengulang siklus pengambilan sampel–evaluasi–pembaruan hingga kriteria penghentian terpenuhi: jumlah maksimum evaluasi fungsi, toleransi pada perubahan rata-rata atau ukuran langkah, atau deteksi degenerasi matriks kovarians. Solusi terbaik yang ditemukan di semua generasi dikembalikan.

Kesalahan umum

  • Menetapkan ukuran langkah awal yang terlalu kecil menjebak pencarian di lingkungan yang sempit dan mencegah eksplorasi; terlalu besar dan generasi awal membuang evaluasi jauh dari optimum. Aturan praktis yang umum adalah menetapkan sigma sehingga optimum berada dalam jarak tiga sigma dari titik awal.
  • Menerapkan CMA-ES pada masalah berdimensi sangat rendah (kurang dari lima parameter) biasanya boros — pencarian grid atau Nelder-Mead yang lebih sederhana sudah cukup, dan kelebihan populasi CMA-ES tidak memberikan manfaat.
  • Menjalankan hanya satu instance CMA-ES pada lanskap multimodal berisiko melewatkan optimum global; gunakan strategi pengulangan multi-mulai atau berbasis populasi (IPOP/BIPOP) ketika lanskap diketahui sangat multimodal.
  • Memperlakukan solusi terbaik yang dikembalikan sebagai optimum global sejati tanpa verifikasi pengulangan adalah kesalahan umum — selalu konfirmasikan dengan beberapa kali percobaan independen ketika objektifnya sangat tidak cembung.

Pertanyaan yang sering diajukan

Bagaimana CMA-ES berbeda dari algoritma genetik sederhana?

Algoritma genetik klasik mempertahankan populasi dan menerapkan persilangan dan mutasi dengan operator tetap. Sebaliknya, CMA-ES memodelkan populasi sebagai sampel dari distribusi normal multivariat dan terus-menerus mengadaptasi distribusi tersebut — rata-rata, ukuran langkah, dan matriks kovarians lengkapnya — berdasarkan solusi mana yang berhasil. Hal ini memungkinkan CMA-ES untuk mempelajari bentuk lanskap kerugian dan menavigasi ruang yang berkorelasi dan berkondisi buruk jauh lebih efisien daripada algoritma genetik dengan operator tetap.

Apakah CMA-ES menjamin penemuan optimum global?

Tidak. CMA-ES adalah metode pencarian lokal dalam arti bahwa satu kali percobaan dapat konvergen ke optimum lokal. Untuk lanskap multimodal, beberapa pengulangan independen — mungkin dengan ukuran populasi yang meningkat (IPOP-CMA-ES) — direkomendasikan untuk meningkatkan cakupan ruang pencarian.

Apa hyperparameter yang paling penting untuk diatur?

Ukuran langkah awal sigma adalah hyperparameter yang paling berpengaruh. Heuristik yang baik adalah menetapkannya sehingga optimum yang diharapkan berada dalam jarak sekitar tiga sigma dari titik awal. Ukuran populasi dan jumlah maksimum evaluasi adalah kontrol sekunder; rumus ukuran populasi default (4 + floor(3 * ln(dimensi))) bekerja dengan baik dalam praktik.

Bisakah CMA-ES menangani fungsi objektif yang bising?

Ya. Karena CMA-ES hanya menggunakan informasi urutan peringkat dari populasi — bukan nilai fungsi absolut — ia relatif kuat terhadap kebisingan. Untuk evaluasi yang sangat bising, meningkatkan ukuran populasi atau merata-ratakan beberapa evaluasi per kandidat dapat lebih meningkatkan ketahanan.

Metode terkait

Sumber

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    Buka referensi DOI
    Disalin.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    Buka referensi publikasi
    Disalin.