Saya memiliki fungsi 2-D non-cembung terbatas yang ingin saya temukan minimum. Fungsinya cukup lancar. Mengevaluasi itu mahal. Kesalahan yang dapat diterima adalah sekitar 3% dari domain fungsi di setiap sumbu.
Saya mencoba menjalankan implementasi algoritma DIRECT di perpustakaan NLOPT, tetapi tidak memberikan peningkatan yang cukup besar terhadap pencarian brute force dalam hal jumlah evaluasi fungsi yang dibutuhkan untuk akurasi yang diperlukan dan ada beberapa pencilan.
Pemecah pengoptimalan global mana yang harus saya pertimbangkan?
optimization
Victor May
sumber
sumber
Jawaban:
Saya ingin menyarankan pendekatan yang agak berbeda dibandingkan dengan jawaban lain, meskipun @barron secara tidak langsung membahas hal yang sama.
Alih-alih mengoptimalkan fungsi Anda secara langsung, yaitu dengan mengevaluasinya pada serangkaian poin poin yang (semoga) menyatu dengan (lokal) optimal, Anda bisa menggunakan konsep , yang sangat cocok untuk masalah tipe yang Anda gambarkan (biaya tinggi, halus, terbatas, berdimensi rendah yaitu kurang dari 20 yang tidak diketahui).sebagai pemodelan penggantix1, x2, ... , xk pemodelan pengganti
Secara khusus, pemodelan pengganti bekerja dengan mengatur fungsi model dari fungsi Anda yang sebenarnya . Kuncinya adalah bahwa walaupun tentu saja tidak sepenuhnya mewakili , jauh lebih murah untuk mengevaluasi. f ∈ R d → R c fc∈Rd→R f∈Rd→R c f
Jadi, proses pengoptimalan yang khas adalah sebagai berikut:
Secara umum, inilah yang dimaksud dengan EGO, Efficient Global Optimization, seperti yang disarankan @barron. Saya ingin menekankan bahwa untuk aplikasi Anda, ini tampaknya sangat cocok - Anda mendapatkan model yang sangat akurat berdasarkan evaluasi relatif sedikit , dan kemudian dapat menggunakan algoritma pengoptimalan yang Anda inginkan. Apa yang sering juga menarik adalah bahwa Anda sekarang dapat mengevaluasi pada mesh dan plot itu, sehingga mendapatkan wawasan tentang penampilan umum . Hal lain yang menarik adalah bahwa kebanyakan teknik pemodelan pengganti juga memberikan perkiraan kesalahan statistik, sehingga memungkinkan estimasi ketidakpastian.c ff c f
Bagaimana membangun tentu saja merupakan pertanyaan terbuka, tetapi sering kali Kriging atau yang disebut model pemetaan ruang digunakan.c
Tentu saja, ini semua sedikit pekerjaan pengkodean, tetapi banyak orang lain telah melakukan implementasi yang sangat baik. Di Matlab, saya hanya tahu DACE toolbox perangkat lunak gratis. TOMLAB mungkin juga menawarkan paket Matlab, tetapi membutuhkan biaya - namun, saya percaya itu juga bekerja di C ++ dan memiliki kemampuan yang jauh lebih banyak daripada yang pernah dimiliki DACE. (Catatan: Saya adalah salah satu pengembang DACE versi baru, yang akan segera dirilis, yang akan menawarkan dukungan tambahan untuk EGO.)
Semoga gambaran umum yang kasar ini membantu Anda, ajukan pertanyaan jika ada poin yang dapat dibuat lebih jelas atau hal-hal yang saya lewatkan, atau jika Anda ingin materi lebih lanjut tentang masalah ini.
sumber
Lihat
LM Rios dan NV Sahinidis, Optimalisasi bebas-derivatif: Tinjauan algoritma dan perbandingan implementasi perangkat lunak
untuk perbandingan solver terbaru yang sangat berguna.
DOI: 10.1007 / s10898-012-9951-y
sumber
Untuk fungsi yang lancar, metode Optimasi Global yang Efisien harus berkinerja cukup baik dan secara dramatis lebih efisien daripada DIRECT. Implementasi tersedia di TOMLAB (belum pernah menggunakannya sendiri) dan DAKOTA (yang saya telah sukses dengannya).
sumber
Karena fungsinya halus, metode Newton akan menjadi metode yang paling efisien untuk menemukan nilai minimum. Karena fungsi ini tidak cembung, Anda harus menerapkan trik yang biasa untuk membuat metode Newton menyatu (modifikasi Levenberg-Marquardt, pencarian garis atau wilayah kepercayaan untuk mengglobal). Jika Anda tidak dapat memperoleh turunan dari fungsi Anda, cobalah menghitungnya melalui perbedaan hingga atau menggunakan pembaruan BFGS. Jika Anda mencurigai bahwa masalahnya memiliki lebih dari satu minimum lokal, orang hanya akan memulai metode Newton dari sekelompok titik yang dipilih secara acak atau tidak begitu acak dan melihat di mana mereka bertemu.
sumber
Karena evaluasi Anda mahal, Anda perlu memanfaatkan menjalankan evaluasi fungsi sevaral secara paralel.
Saya akan merekomendasikan Anda untuk melihat kode ini . Matematika di belakang dijelaskan di sini .
sumber