Kapan algoritma genetika merupakan pilihan yang baik untuk optimasi?

20

Algoritma genetika adalah salah satu bentuk metode optimasi. Seringkali penurunan gradien stokastik dan turunannya adalah pilihan terbaik untuk optimasi fungsi, tetapi kadang-kadang algoritma genetika masih digunakan. Misalnya, antena pesawat ruang angkasa ST5 NASA dibuat dengan algoritma genetika:

Antena ST5

Kapan metode optimisasi genetik merupakan pilihan yang lebih baik daripada metode gradient descent yang lebih umum?

Gus
sumber
7
+1 sebagai contoh, saya menemukan makalah aslinya: alglobus.net/NASAwork/papers/Space2006Antenna.pdf
Tim

Jawaban:

19

Algoritma genetika (GA) adalah keluarga heuristik yang secara empiris baik dalam memberikan jawaban yang layak dalam banyak kasus, meskipun mereka jarang merupakan pilihan terbaik untuk domain tertentu.

Anda menyebutkan algoritma berbasis turunan, tetapi bahkan tanpa adanya turunan, ada banyak algoritme pengoptimalan bebas turunan yang berkinerja lebih baik daripada GAS. Lihat ini dan jawaban ini untuk beberapa ide.

Apa yang banyak dimiliki oleh algoritma optimasi standar (bahkan metode bebas turunan) adalah asumsi bahwa ruang yang mendasari adalah manifold yang halus (mungkin dengan beberapa dimensi diskrit), dan fungsi untuk mengoptimalkan agak berperilaku baik.

Namun, tidak semua fungsi didefinisikan pada manifold yang halus. Terkadang Anda ingin mengoptimalkan grafik atau struktur diskrit lainnya (optimasi kombinatorial) - di sini ada algoritma khusus, tetapi GAS juga berfungsi.

Semakin banyak Anda menuju fungsi yang didefinisikan lebih kompleks, struktur diskrit, semakin banyak GAS dapat berguna, terutama jika Anda dapat menemukan representasi di mana operator genetik bekerja dengan sebaik-baiknya (yang membutuhkan banyak penyetelan tangan dan pengetahuan domain).

Tentu saja, masa depan mungkin mengarah untuk melupakan GAS sama sekali dan mengembangkan metode untuk memetakan ruang diskrit ke ruang kontinu , dan menggunakan mesin optimisasi yang kita miliki pada representasi kontinu.

Lacerbi
sumber
2

Metode genetik sangat cocok untuk optimasi multikriteria ketika gradient descent didedikasikan untuk optimasi monocriteria. Keturunan gradien memungkinkan untuk menemukan fungsi minimum ketika turunan ada dan hanya ada satu solusi optimal (jika kita kecuali minimas lokal). Algoritma genetika dapat digunakan dalam masalah multikriteria dan mengarah pada rangkaian solusi, masing-masing dari individu populasi, setelah berevolusi dari populasi awal. Nilai-nilai untuk mengoptimalkan adalah fenotip individu dan mungkin ada beberapa fenotipe. Secara umum, tidak ada individu yang secara bersamaan memiliki nilai yang lebih baik dari masing-masing fenotipe, sehingga tidak hanya ada satu solusi. Individu dalam populasi akhir, yang semuanya merupakan solusi dari optimasi, adalah bagian dari "front Pareto" dan ditandai sebagai "Pareto peringkat satu" individu. Ini berarti bahwa dibandingkan dengan setiap individu lain yang memiliki kinerja yang sama untuk setiap fenotipe, mereka setidaknya lebih baik untuk satu fenotipe daripada yang lain.

manu190466
sumber
Ok untuk downvote, tetapi bisakah Anda menjelaskan di mana saya salah?
manu190466
5
Situs ini menghargai jawaban yang memberikan konteks dan latar belakang. Lihat halaman bantuan ini untuk bagaimana memberikan jawaban yang akan menambah repositori kami jawaban yang berguna untuk pertanyaan menarik. Menjelaskan jawaban Anda juga merupakan cara yang baik untuk menguji pemahaman Anda sendiri. Sebagai contoh, dalam hal ini Anda mungkin ingin memperluas tentang bagaimana algoritma genetika "sangat cocok untuk optimasi multikriteria," seperti halaman Wikipedia tampaknya menyiratkan fungsi kebugaran bernilai tunggal sebagai tujuan untuk algoritma genetika.
EdM
0

Terbaik dalam arti apa?

Dalam pengalaman saya, GAS adalah salah satu pengoptimal yang paling pragmatis. Sementara banyak algoritma yang lebih tepat membutuhkan waktu dan upaya untuk memformalkan masalah nyata di dunia matematika, GAS dapat menangani fungsi biaya apa pun dengan aturan dan kendala yang kompleks (GAS terkait dengan pendekatan eksekusi setelah semua dan bukan dengan perhitungan khusus). Proses ini mudah dan Anda dapat mencoba banyak pendekatan untuk pekerjaan eksplorasi.

Saya menghargai juga kemungkinan untuk memasukkan kembali solusi masa lalu ke algoritma untuk menjalankan masa depan yang baik untuk tugas yang berulang.

Secara konseptual, algoritma genetika dapat diwakili oleh hashmap fungsi dan cocok sehingga bahasa fungsional juga seperti Clojure yang juga merupakan bahasa di mana Anda dapat mencapai hasil besar dengan sangat cepat.

Algoritma Genetika juga dapat disarangkan: fungsi biaya satu GA dapat menjadi GA! Algoritme ini memanfaatkan perangkat keras dan infrastruktur modern yang memungkinkan mereka menghitung populasi yang sangat besar sehingga - bahkan dengan operasi mutasi / seleksi sederhana - Anda masih dapat mencapai hasil yang baik.

Bahkan untuk masalah sederhana seperti menemukan fungsi gelombang minimum, GAS tidak seburuk itu dan dapat mencapai presisi yang layak dalam waktu yang dapat diterima.

Jadi ya, solusi analitis mungkin memiliki waktu eksekusi dan ketepatan yang lebih cepat, tetapi waktu yang dibutuhkan untuk menghasilkannya kelebihan berat sering kali mendapatkan manfaat yang diharapkan! Jadi ketika ? Hampir setiap waktu bagi saya, setidaknya untuk meta-optimisasi.

Joseph Yourine
sumber
Dorongan utama dari argumen ini tampaknya adalah bahwa algoritma genetika adalah pengoptimal kotak hitam. Tetapi ada banyak pengoptimal kotak hitam di luar sana. Mengapa ini lebih baik daripada pilihan lain? Selain itu, saya tidak berpikir itu benar-benar terjadi bahwa GA dapat dengan mudah menangani kendala. Sebagai contoh, jika fungsinya tidak ditentukan kecuali untuk subruang 3D di dunia 4D, pasti GA vanilla akan gagal.
Cliff AB
@CliffAB Sebenarnya saya tidak mengatakan apa-apa tentang itu dan mungkin lebih tepatnya. Di GA, Anda memiliki banyak kendali atas perhitungan inti, GA itu sendiri adalah urutan langkah-langkah dan pemesanan ringan. Saat Anda menentukan fungsi biaya, Anda dapat menangani apa pun dalam fungsi tersebut, bahkan kendala eksternal yang dapat Anda tanyakan. Argumen utama saya adalah: menangani banyak masalah, Anda tidak perlu khawatir dengan kompatibilitas dengan kerangka kerja (Anda hanya perlu mengembalikan biaya), datang dengan solusi kehidupan nyata yang layak dalam kebanyakan kasus bisnis BAHKAN jika tidak selalu yang terbaik
Joseph Yourine