Simulated Annealing Robust — Menemukan solusi yang tetap baik di bawah ketidakpastian
- Diperkenalkan oleh
- Kirkpatrick, Gelatt & Vecchi (SA basis); robust formulation developed across the operations research community
- Tahun
- 1983 (SA); robust variant emerged 1990s–2000s
- Jenis
- Metaheuristic with robustness evaluation
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Simulated Annealing Robust (RSA) mengadaptasi metaheuristik simulated annealing klasik untuk mencari solusi yang berkinerja baik tidak hanya dalam kondisi nominal tetapi di seluruh rentang nilai parameter yang tidak pasti atau adversarial. Dengan menyematkan evaluasi ketahanan — kasus terburuk, kasus yang diharapkan, atau berbasis penyesalan — ke dalam langkah penerimaan SA, RSA menukar beberapa optimalitas nominal dengan ketahanan, membuatnya berharga ketika parameter masalah diketahui secara tidak tepat atau tunduk pada variasi lingkungan.
Intuisi di balik metode
Simulated annealing meniru pendinginan fisik logam untuk keluar dari optimum lokal dalam lanskap solusi yang kompleks. Robust SA memperluas intuisi ini dengan mengubah apa yang dianggap sebagai solusi 'baik': alih-alih solusi yang terlihat terbaik di bawah data nominal yang diasumsikan, algoritma mencari solusi yang paling sedikit menurun ketika kenyataan berbeda dari asumsi. Pada setiap iterasi SA, solusi kandidat dinilai tidak oleh evaluasi objektif tunggal tetapi oleh kriteria ketahanan — misalnya, objektif kasus terburuk di atas serangkaian skenario yang masuk akal atau realisasi parameter yang disampel — memberikan bias pencarian eksplisit terhadap stabilitas daripada kinerja mentah.
Sejarah
Simulated annealing diperkenalkan oleh Kirkpatrick, Gelatt, dan Vecchi (1983) berdasarkan algoritma Metropolis untuk mekanika statistik. Sepanjang tahun 1990-an dan 2000-an, seiring dengan meningkatnya prominensi optimasi tangguh — yang diformalkan terutama oleh Ben-Tal dan Nemirovski — para peneliti mulai menyematkan kriteria evaluasi tangguh ke dalam loop pencarian SA untuk mengatasi optimasi di bawah ketidakpastian, sehingga memunculkan robust SA sebagai kerangka kerja praktis yang diakui dalam riset operasi dan desain teknik.
Kapan digunakan
Gunakan Robust SA saat mengoptimalkan sistem dengan ketidakpastian parameter yang signifikan (variabilitas pasokan, fluktuasi permintaan, kebisingan pengukuran) di mana solusi yang optimal secara nominal tetapi rapuh tidak dapat diterima. Sangat cocok untuk masalah kombinatorial dan kontinu berukuran sedang hingga besar di mana optimasi tangguh yang tepat secara komputasi tidak mungkin dilakukan. Pilih RSA daripada SA biasa ketika pemangku kepentingan memerlukan jaminan atau batas kepercayaan pada kualitas solusi. Hindari RSA ketika ketidakpastian dapat diabaikan, ketika evaluasi ketahanan internal terlalu mahal dibandingkan dengan komputasi yang tersedia, atau ketika masalahnya cembung dan dapat diatasi dengan metode pemrograman tangguh yang tepat.
Batasan dan pertimbangan
- Evaluasi ketahanan internal (pengambilan sampel skenario atau enumerasi) melipatgandakan biaya komputasi: setiap iterasi SA memerlukan evaluasi objektif berkali-kali.
- Kinerja sangat bergantung pada parameter algoritma: jadwal pendinginan, suhu awal, struktur lingkungan, dan jumlah skenario ketahanan semuanya harus disetel.
- Tidak ada jaminan menemukan solusi tangguh optimal global; kualitas hasil bergantung pada panjang lari dan keacakan.
- Pilihan kriteria ketahanan (kasus terburuk vs. yang diharapkan vs. penyesalan) secara signifikan memengaruhi solusi mana yang ditemukan dan memerlukan penilaian domain eksplisit.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menangani ruang solusi non-cembung, non-diferensiabel, dan kombinatorial di mana optimasi tangguh yang tepat tidak dapat diatasi.
- Kriteria ketahanan yang fleksibel: kasus terburuk, nilai yang diharapkan, CVaR, atau penyesalan dapat dimasukkan tanpa menstruktur ulang algoritma.
- Penerimaan probabilistik dari solusi yang lebih buruk membantu keluar dari optimum lokal dalam lanskap objektif yang tangguh, meningkatkan kualitas solusi daripada pencarian tangguh yang serakah.
- Secara konseptual mudah diimplementasikan dengan memperluas basis kode SA yang ada dengan pembungkus evaluasi skenario.
- Dapat diterapkan pada berbagai domain: penjadwalan, perutean, lokasi fasilitas, desain teknik, dan optimasi portofolio keuangan.
Penerapan
- Penjadwalan produksi tangguh di bawah waktu pemrosesan dan ketersediaan mesin yang tidak pasti
- Perutean kendaraan yang tangguh di bawah waktu tempuh stokastik dan variabilitas permintaan
- Perencanaan lokasi fasilitas tangguh di bawah distribusi permintaan pelanggan yang tidak pasti
- Optimasi desain teknik dengan ketidakpastian toleransi dan manufaktur
- Optimasi portofolio keuangan di bawah ketidakpastian pasar berbasis skenario
- Desain jaringan dengan kapasitas tautan yang tidak pasti atau probabilitas kegagalan
Cara kerjanya
Cara kerjanya
Definisikan masalah optimasi dengan parameter yang tidak pasti: objektif f(x, xi) di mana x adalah vektor keputusan dan xi mewakili input yang tidak pasti. Tentukan himpunan ketidakpastian atau distribusi probabilitas atas xi. Pilih kriteria ketahanan: kasus terburuk (minimax), nilai yang diharapkan, value at risk bersyarat, atau penyesalan maksimum.
Untuk setiap solusi kandidat x, hitung ukuran ketahanan R(x) dengan mengevaluasi f(x, xi) di atas realisasi ketidakpastian yang disampel atau dienumerasi. Untuk ketahanan berbasis skenario, R(x) = max_s f(x, xi_s); untuk ketahanan stokastik, R(x) = E[f(x, xi)]. Evaluasi internal ini mungkin memerlukan pengambilan sampel Monte Carlo atau enumerasi skenario.
Inisialisasi dengan solusi awal yang layak x_0 dan suhu awal T_0. Pada setiap iterasi, hasilkan solusi tetangga x' melalui operator gerakan spesifik masalah (misalnya, pertukaran, gangguan). Evaluasi R(x') menggunakan ukuran ketahanan yang dipilih.
Terima tetangga x' tanpa syarat jika R(x') lebih baik dari R(x). Terima gerakan yang memburuk dengan probabilitas exp(-(R(x') - R(x)) / T), di mana T adalah suhu saat ini. Aturan penerimaan Metropolis ini memungkinkan keluar dari optimum lokal dalam lanskap objektif yang tangguh.
Kurangi suhu sesuai dengan jadwal pendinginan, umumnya pendinginan geometris T_{k+1} = alpha * T_k dengan alpha dalam (0.9, 0.99), atau jadwal adaptif yang menyesuaikan berdasarkan tingkat penerimaan. Lanjutkan hingga kriteria penghentian terpenuhi: iterasi maksimum, ambang batas suhu minimum, atau stagnasi.
Kembalikan solusi terbaik yang ditemukan sesuai dengan R(x) di semua iterasi, bukan hanya inkumben terakhir. Opsional lakukan pencarian lokal terakhir dari solusi tangguh terbaik untuk memperbaikinya. Laporkan kinerja nominal f(x*, xi_nominal) dan kinerja tangguh R(x*) untuk mengkomunikasikan trade-off ketahanan-optimalitas.
Kesalahan umum
- Menggunakan sampel skenario yang terlalu sedikit dalam evaluasi ketahanan memperkenalkan kebisingan ke dalam kriteria penerimaan, menyebabkan algoritma mengejar solusi yang secara keliru 'tangguh'.
- Pendinginan terlalu cepat (alpha tinggi) menyebabkan konvergensi prematur ke optimum tangguh lokal; pendinginan terlalu lambat meningkatkan waktu berjalan tanpa peningkatan kualitas yang proporsional.
- Mencampuradukkan optimalitas nominal dengan optimalitas tangguh: melaporkan solusi nominal terbaik yang ditemui daripada solusi tangguh terbaik mengalahkan tujuan metode ini.
- Mengabaikan trade-off ketahanan-optimalitas dalam pelaporan: selalu ungkapkan R(x*) dan f(x*, xi_nominal) sehingga pembaca dapat menilai apa yang dikorbankan untuk ketahanan.
Pertanyaan yang sering diajukan
Bagaimana Robust SA berbeda dari Stochastic SA?
Stochastic SA memperkenalkan keacakan dalam pembuatan gerakan atau evaluasi untuk keluar dari optimum lokal dari objektif tetap. Robust SA mengubah objektif itu sendiri: ia mengoptimalkan ukuran ketahanan (kasus terburuk, yang diharapkan, atau penyesalan) atas parameter yang tidak pasti, sengaja mencari solusi yang tangguh terhadap variasi parameter daripada sekadar kebisingan dalam proses pencarian.
Berapa banyak skenario yang dibutuhkan dalam evaluasi ketahanan?
Ini tergantung pada struktur ketidakpastian dan presisi yang dibutuhkan. Untuk himpunan skenario diskrit, enumerasi semua atau skenario yang paling adversarial. Untuk distribusi kontinu, 50–500 sampel Monte Carlo per evaluasi umum dalam praktik, dengan diagnostik konvergensi digunakan untuk membenarkan ukuran sampel. Lebih banyak sampel meningkatkan akurasi tetapi secara proporsional meningkatkan waktu berjalan.
Bisakah Robust SA menangani banyak objektif bersama dengan ketahanan?
Ya, tetapi masalahnya menjadi jauh lebih kompleks. Salah satu pendekatan adalah mengubah ketahanan menjadi objektif tambahan dan menjalankan SA multi-objektif (misalnya, Pareto-SA). Alternatifnya, ketahanan diperlakukan sebagai kendala atau istilah penalti yang ditambahkan ke objektif agregat berbobot.
Kapan saya harus memilih Robust SA daripada Robust Tabu Search atau Robust GA?
Robust SA sering dipilih ketika lanskap solusi sangat kasar dan pencarian mendapat manfaat dari penerimaan sesekali dari solusi yang lebih buruk untuk keluar dari jebakan. Tabu Search bisa lebih kuat ketika riwayat gerakan informatif. Algoritma genetik unggul pada masalah keragaman populasi. Pilihan tersebut seringkali bersifat empiris dan spesifik masalah.
Apakah implementasi paralel bermanfaat?
Ya. Evaluasi ketahanan internal (pengambilan sampel skenario) sangat paralel: semua skenario untuk solusi kandidat dapat dievaluasi secara bersamaan. Memparalelkan loop internal ini secara substansial mengurangi waktu dinding tanpa mengubah logika algoritma.
Metode terkait
Sumber
Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
Buka referensi DOIDisalin.Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.
ISBN: 9780691143682Disalin.