Saya sedang bekerja untuk meningkatkan proses optimasi beberapa perangkat lunak pemodelan demografis sehingga dapat lebih cocok dengan model demografis untuk data. Kami ingin mengurangi waktu pengoptimalan.
Waktu yang diperlukan untuk mengevaluasi fungsi tujuan kami sangat bervariasi, tergantung pada nilai input. Hubungan antara waktu untuk mengevaluasi fungsi tujuan dan input diketahui. Saya bertanya-tanya apakah ada metode optimasi yang mempertimbangkan biaya waktu relatif dari fungsi tujuan ketika memilih poin mana yang akan dievaluasi.
Terima kasih!
Memperbarui:
Seperti yang diminta Paulus, berikut adalah beberapa fitur yang menonjol dari fungsi tujuan khusus ini:
- Jumlah parameternya sedang (~ 12ish)
- Masalah kita adalah non-cembung, atau setidaknya ada "punggungan" yang sempit dan rata di permukaan fungsi tujuan. Saat ini kami sedang menghadapi hal ini menggunakan beberapa optimisasi dari berbagai titik, tetapi kami ingin melakukan yang lebih baik.
- Fungsi objektifnya cukup lancar, meskipun kita hanya bisa menghitung perkiraan beda hingga derivatif.
- Biaya evaluasi juga merupakan fungsi halus dari nilai parameter, dan itu cukup dapat diprediksi. secara kasar, untuk setiap parameter biaya untuk mengevaluasi tinggi di satu ujung kisaran dan rendah di ujung lainnya. Jadi kami memiliki daerah besar set parameter mahal untuk mengevaluasi, tapi kami tahu di mana mereka.
optimization
nova
sumber
sumber
Jawaban:
Salah satu pendekatan umum untuk menangani fungsi objektif yang mahal adalah dengan membangun (dengan contoh pemodelan regresi) "model permukaan respons" yang mendekati fungsi tujuan asli, dan kemudian mengoptimalkan permukaan respons tersebut daripada bekerja dengan fungsi asli. Dalam praktiknya permukaan respons biasanya hanya model kuadratik yang disesuaikan dengan regresi, sehingga menemukan permukaan respons minimum menjadi masalah optimisasi yang sangat mudah.
Anda belum mengatakan apa pun tentang kelancaran atau kecemburuan fungsi objektif Anda. Jika fungsinya nonmooth atau nonconvex, maka ini jelas menjadi jauh, jauh lebih sulit.
Anda juga belum mengatakan apa pun tentang di mana titik mahal berada di ruang parameter Anda. Jika mereka didistribusikan secara acak di seluruh ruang parameter, maka Anda dapat menggunakan desain teknik eksperimen untuk membangun model permukaan respons Anda sambil menghindari poin mahal. Jika ada daerah yang lebih besar dari ruang parameter di mana evaluasi itu mahal, maka Anda bisa mencoba meminimalkan jumlah titik di area-area yang Anda gunakan dalam membangun model permukaan respons. Tentu saja, jika optimum Anda terletak di tengah-tengah wilayah seperti itu, Anda akan ditakdirkan untuk mengevaluasi fungsi di wilayah mahal.
sumber
Saya tidak tahu metode yang secara khusus menimbang biaya relatif untuk mengevaluasi tujuan pada titik uji coba yang berbeda tetapi jika Anda dapat memprediksi secara relatif andal apakah seorang kandidat akan mahal untuk dievaluasi atau tidak, maka saya dapat menyarankan untuk mencoba. metode langsung . Metode langsung cocok dengan keluarga metode bebas derivatif. Itu tidak selalu merupakan hal yang buruk untuk menggunakannya bahkan jika Anda mencurigai bahwa masalah Anda cukup lancar karena mereka dapat memberikan beberapa tingkat fleksibilitas yang tidak bisa dilakukan metode untuk optimasi yang mulus.
Idenya adalah bahwa metode langsung mendefinisikan mesh (tergantung iterasi) tentang iterate saat ini dan "step" mesh yang bergantung pada iterasi. Berdasarkan langkah mesh ini, metode menentukan titik percobaan pada mesh yang merupakan tetangga dari iterate saat ini (mereka terletak pada mesh dan pada jarak yang ditentukan oleh langkah mesh). Kemudian akan dilanjutkan untuk mengevaluasi tujuan di tetangga. Segera setelah kandidat yang lebih baik ditemukan, itu menjadi iterate baru saat ini. Sesuai pilihan Anda, Anda juga dapat mengevaluasi semua tetangga dan memilih yang terbaik.
Dalam kasus Anda, mungkin ide yang baik untuk memesan tetangga berdasarkan perkiraan biaya evaluasi tujuan di sana. Evaluasi mereka dalam urutan ini dan pilih kesuksesan pertama sebagai iterate berikutnya. Secara intuitif, Anda menyukai kandidat yang murah. Dalam metode langsung, pemesanan seperti itu cocok dengan kategori model pengganti , sebuah konsep yang menggeneralisasi bahwa model permukaan respons yang disebutkan oleh Brian.
Berikut ini adalah implementasi metode langsung yang sangat baik (dalam C ++): http://www.gerad.ca/nomad/Project/Home.html
Jika itu tampaknya memberikan hasil yang menjanjikan, silakan kembali ke saya dan saya mungkin dapat menyarankan perbaikan lainnya.
Saya percaya NOMAD juga memiliki fitur untuk pengoptimalan global (seperti multi-start yang saat ini Anda terapkan) berdasarkan konsep pencarian variabel lingkungan .
sumber