Arti metode pencarian dan metode optimasi

9

Saya bertanya-tanya apa perbedaan dan hubungan antara "metode pencarian" dan "metode optimasi"?

Apalagi saat menyelesaikan masalah optimasi? Saya menekankan konteks penyelesaian masalah pengoptimalan, karena saya kira metode pencarian tidak hanya untuk menyelesaikan masalah pengoptimalan, tetapi juga masalah non-pengoptimalan?

Kebingungan saya berasal dari fakta-fakta berikut:

  1. Ada beberapa metode optimasi, bernama "pencarian xxx", seperti pencarian lokal , pencarian stokastik , .... Apa arti sebenarnya dari "pencarian"? Saya ingin tahu apakah ada metode pengoptimalan yang bukan "pencarian"?
  2. Juga dalam buku ini Pengantar Pencarian Stokastik dan Optimasi oleh Spall , saya tidak begitu mengerti perbedaan antara "Pencarian" dan "Optimasi" dalam judulnya dan juga kontennya. Mengapa harus membedakan antara "Pencarian" dan "Optimasi", jika artinya sama? Atau apakah "Optimasi" berarti tugas / masalah optimasi stokastik alih-alih metode optimisasi, sebagai lawan dari "pencarian" berarti metode untuk menyelesaikan tugas / masalah optimasi?
  3. Juga Tidak ada makan siang gratis dalam pencarian dan optimisasi yang membedakan pencarian dan optimisasi lagi.

Terima kasih dan salam!

Tim
sumber

Jawaban:

11

search = upaya untuk menemukan titik layak yang memenuhi semua kendala (dan untuk pengoptimalan, titik yang lebih baik daripada yang ditemukan sejauh ini), umumnya menggunakan nilai fungsi saja.

pencarian lokal: meningkatkan titik layak (atau jarak ke ukuran kelayakan) dengan mencari di antara titik-titik tetangga.

Pencarian stokastik: pencarian menggunakan kriteria nondeterministic untuk memilih poin percobaan.

Ini terlepas dari apakah kriteria optimasi diberikan. Secara khusus, dalam '' Tidak ada makan siang gratis dalam pencarian dan optimisasi '' pencarian mengacu pada pencarian kelayakan, sedangkan optimasi mengacu pada pencarian optimalitas.

Secara umum, untuk masalah pengoptimalan, pencarian dan pengoptimalan adalah setara. Namun, mereka memiliki konotasi yang membuat perbedaan dalam penggunaan istilah.

metode optimisasi = metode untuk menyelesaikan masalah optimisasi, seringkali (tetapi tidak harus) menggunakan informasi gradien (atau subgradien atau bahkan Hessian).

Mampu menggunakan gradien secara drastis meningkatkan efisiensi metode optimisasi. Satu menggunakan dalam konteks ini (yaitu, dengan gradien diketahui) untuk pencarian istilah hanya dalam kombinasi '' pencarian baris '' yang berarti mencari titik yang lebih baik di sepanjang arah yang dipilih.

Arnold Neumaier
sumber
(3) Apakah metode pencarian dalam arti sempit semuanya metaheuristik?
Tim
@ Tim: Pencarian baris mungkin atau mungkin tidak menggunakan gradien dalam pencariannya (misalnya, pencarian baris Wolfe membutuhkannya). Anda tidak harus melampirkan kata-kata ini dengan makna yang terlalu tepat; mereka sugestif terhadap sesuatu, bukan konsep matematika dengan makna yang tepat. - Metode Newton menggunakan gradien dan Goni. - Sebuah metode bersifat stokastik setelah pencarian melibatkan generator angka acak. - Pencarian lokal dapat digunakan dalam arti umum dari metode yang tidak menjamin konvergensi ke optimal global, atau berarti pencarian langsung berdasarkan inspeksi lingkungan lokal dari titik terbaik saat ini saja.
Arnold Neumaier
Metaheuristik harus mengandung prinsip-prinsip yang lebih spesifik daripada sekadar '' pencarian lokal '' untuk mendapatkan naame; Saya tidak pernah mendengar ini berlaku secara umum. Tetapi terminologinya tidak terlalu tepat
Arnold Neumaier
4

xg(x)g(x)=0xf(x)min!fg(x)=f(x)

Wolfgang Bangerth
sumber
g(x)=0,f(x)fbestg(x)