Skip to content
Kembali ke hasil pencarian

Simulated Annealing Multi-Objektif (MOSA)

Diperkenalkan oleh
Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
Tahun
1992–1998
Jenis
Metaheuristic / Pareto-based optimizer
Keluarga
Simulation / optimization

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Simulated Annealing Multi-Objektif (MOSA) memperluas metaheuristik simulated annealing klasik ke masalah dengan dua atau lebih fungsi tujuan yang saling bertentangan.

Alih-alih konvergen ke satu optimum tunggal, MOSA menjelajahi ruang solusi secara stokastik dan memelihara arsip solusi yang tidak didominasi (Pareto-optimal), menawarkan pembuat keputusan sebuah front trade-off yang beragam daripada satu jawaban yang ditentukan.

Intuisi di balik metode

Simulated annealing klasik meniru pendinginan terkontrol logam untuk keluar dari optimum lokal — sesekali menerima solusi yang lebih buruk pada suhu tinggi, kemudian menjadi lebih selektif saat suhu turun. MOSA menerapkan mekanisme pelarian probabilistik yang sama ini di berbagai tujuan secara bersamaan. Ketika solusi kandidat memperburuk beberapa tujuan tetapi memperbaiki tujuan lain, logika dominasi menentukan apakah solusi tersebut masuk ke dalam arsip Pareto. Jadwal pendinginan secara bertahap mengurangi keacakan, memfokuskan pencarian di dekat batas Pareto. Hasilnya adalah aproksimasi dari front Pareto sebenarnya yang dicapai tanpa memerlukan informasi gradien atau asumsi konveksitas.

Sejarah

Simulated annealing diperkenalkan oleh Kirkpatrick et al. pada tahun 1983. Serafini (1992) adalah salah satu yang pertama secara formal mengusulkan perluasannya ke multi-objektif. Czyzak dan Jaszkiewicz (1998) mengembangkan Pareto Simulated Annealing (PSA), yang menetapkan arsip Pareto sebagai struktur keluaran pusat dan menyediakan formulasi kriteria penerimaan yang diadopsi secara luas saat ini. MOSA sejak itu diterapkan dalam desain teknik, penjadwalan, dan logistik.

Kapan digunakan

Gunakan MOSA ketika Anda menghadapi masalah optimasi dengan dua atau lebih tujuan yang saling bertentangan dan variabel keputusan kontinu atau kombinatorial, terutama ketika lanskap tujuan bersifat non-konveks, multimodal, atau tanpa gradien. Sangat cocok untuk masalah penjadwalan, perutean, desain teknik, dan alokasi sumber daya di mana front trade-off eksplisit lebih berguna daripada agregat tertimbang tunggal. Pilih MOSA daripada Monte Carlo yang murni stokastik ketika Anda memerlukan optimasi daripada kuantifikasi ketidakpastian. JANGAN gunakan MOSA ketika masalah memiliki satu tujuan (SA klasik sudah cukup), ketika front Pareto harus ditemukan secara tepat (algoritma eksak lebih baik untuk masalah kecil), ketika jumlah tujuan melebihi sekitar lima (metode berbasis hypervolume memiliki skala yang lebih baik), atau ketika evaluasi tujuan sangat mahal per panggilan (metode berbasis surrogate lebih disukai).

Batasan dan pertimbangan

  • Kualitas solusi dan cakupan front Pareto sensitif terhadap pilihan suhu awal, laju pendinginan, dan operator lingkungan, memerlukan penyetelan spesifik masalah.
  • Konvergensi ke front Pareto berkualitas tinggi dapat memerlukan banyak evaluasi tujuan, membuatnya lambat untuk simulasi black-box yang mahal.
  • Pemeliharaan dan pembaruan arsip Pareto menimbulkan overhead dan arsip dapat menjadi besar, meningkatkan biaya memori dan perbandingan.
  • Berbeda dengan metode berbasis populasi (misalnya, NSGA-II), sifat lintasan tunggal MOSA dasar dapat menghasilkan cakupan front Pareto yang tidak merata.
  • Jaminan konvergensi teoretis memerlukan jadwal pendinginan yang lambat tak terhingga, yang tidak praktis; jadwal terbatas mengorbankan jaminan optimalitas.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Tidak memerlukan informasi gradien dan menangani lanskap tujuan non-konveks, diskontinu, dan multimodal.
  • Penerimaan probabilistik solusi inferior memungkinkan pelarian dari front Pareto lokal yang menjebak pendekatan yang murni serakah.
  • Menghasilkan aproksimasi yang beragam dari seluruh front Pareto dalam satu kali jalan, memberikan opsi trade-off eksplisit kepada pembuat keputusan.
  • Implementasinya lugas dan jadwal pendinginan menyediakan parameter intuitif untuk menyetel keseimbangan eksplorasi–eksploitasi.
  • Dapat diterapkan pada masalah optimasi kontinu dan kombinatorial dengan reformulasi minimal.

Penerapan

  • Penjadwalan job-shop dan flow-shop multi-objektif (meminimalkan makespan dan keterlambatan secara bersamaan)
  • Masalah desain dan perutean jaringan dengan tujuan biaya dan keandalan
  • Optimasi desain teknik (misalnya, meminimalkan berat dan tegangan pada komponen struktural)
  • Optimasi portofolio yang menyeimbangkan pengembalian dan risiko yang diharapkan
  • Perencanaan penggunaan lahan dan spasial dengan tujuan ekonomi dan lingkungan yang bersaing
  • Alokasi sumber daya layanan kesehatan yang menyeimbangkan biaya, cakupan, dan kualitas layanan

Cara kerjanya

Cara kerjanya

1

Hasilkan solusi awal (acak atau heuristik), atur suhu awal T_0 yang cukup tinggi untuk memungkinkan eksplorasi luas, inisialisasi arsip Pareto dengan solusi non-dominasi yang ditemukan, dan definisikan kriteria penghentian (iterasi maksimum atau ambang batas suhu minimum).

2

Ganggu solusi saat ini menggunakan operator lingkungan yang sesuai dengan struktur masalah (misalnya, pertukaran, penyisipan, atau perturbasi Gaussian untuk variabel kontinu) untuk menghasilkan satu atau lebih solusi tetangga kandidat.

3

Evaluasi semua fungsi tujuan untuk kandidat tetangga. Tentukan apakah kandidat tersebut mendominasi, didominasi oleh, atau tidak didominasi relatif terhadap solusi saat ini dan solusi dalam arsip Pareto. Kandidat non-dominasi ditambahkan ke arsip; anggota arsip yang didominasi dihapus.

4

Terapkan kriteria penerimaan multi-objektif. Jika tetangga tidak didominasi sehubungan dengan solusi saat ini, maka diterima. Jika didominasi, ia mungkin masih diterima dengan probabilitas P = exp(−ΔF / T) di mana ΔF mengagregasi penurunan tujuan, memungkinkan pelarian dari front Pareto lokal.

Rumus
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

Kurangi suhu sesuai dengan jadwal pendinginan, umumnya geometris: T_{k+1} = α · T_k dengan α ∈ (0.8, 0.99). Suhu yang lebih rendah mempersempit penerimaan pergerakan yang inferior, secara progresif mengintensifkan pencarian di dekat wilayah yang menjanjikan dari front Pareto.

Rumus
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

Kembalikan arsip Pareto akhir sebagai hasil. Lakukan pasca-pemrosesan untuk memangkas solusi yang didominasi yang mungkin telah terakumulasi, dan sajikan arsip sebagai aproksimasi diskrit dari front Pareto-optimal untuk pemilihan pembuat keputusan.

Kesalahan umum

  • Menetapkan suhu awal terlalu rendah menyebabkan konvergensi prematur ke wilayah lokal front Pareto; selalu kalibrasi T_0 sehingga tingkat penerimaan awal sekitar 70–90%.
  • Menggunakan laju pendinginan α yang terlalu dekat dengan 1.0 membuat proses berjalan sangat lama; terlalu dekat dengan 0 menyebabkan konvergensi cepat sebelum front Pareto dieksplorasi secara memadai.
  • Mendefinisikan ΔF untuk probabilitas penerimaan dengan penjumlahan perbedaan tujuan yang naif mencampur skala yang tidak sebanding — normalisasi setiap tujuan sebelum agregasi.
  • Mengabaikan penghapusan solusi yang didominasi dari arsip secara berkala mengembangkannya dan menurunkan kualitas keluaran akhir.
  • Mengevaluasi keberhasilan pada satu kali jalan menyesatkan mengingat variasi stokastik; selalu agregasikan hasil dari beberapa kali jalan independen.

Pertanyaan yang sering diajukan

Bagaimana MOSA berbeda dari NSGA-II?

NSGA-II adalah algoritma evolusioner berbasis populasi yang mengembangkan sekumpulan solusi secara bersamaan menggunakan crossover, mutasi, dan pengurutan non-dominasi. MOSA adalah metode berbasis lintasan yang menjelajahi satu solusi pada satu waktu menggunakan pergerakan probabilistik. MOSA cenderung lebih sederhana untuk diimplementasikan dan bekerja dengan baik untuk masalah kombinatorial, sementara NSGA-II umumnya memberikan cakupan front Pareto yang lebih baik untuk masalah kontinu dan berskala lebih dapat diprediksi.

Bagaimana cara saya mengatur suhu awal T_0?

Heuristik umum adalah menjalankan fase pendahuluan singkat dan memilih T_0 sehingga sekitar 80% pergerakan tetangga acak diterima. Ini memastikan eksplorasi luas di awal. Kalibrasi spesifik masalah disarankan karena skala suhu yang sesuai bergantung pada besarnya perbedaan fungsi tujuan.

Bisakah MOSA menangani lebih dari dua tujuan?

Ya, tetapi kinerjanya menurun seiring bertambahnya jumlah tujuan. Biaya pengelolaan arsip Pareto meningkat, dan fraksi solusi non-dominasi tumbuh pesat, membuat kriteria penerimaan kurang diskriminatif. Untuk masalah dengan lebih dari empat atau lima tujuan, metode berbasis indikator hypervolume atau berbasis dekomposisi (misalnya, MOEA/D) umumnya lebih disukai.

Bagaimana saya tahu kapan harus menghentikan algoritma?

Kriteria penghentian umum meliputi pencapaian suhu minimum, kehabisan anggaran iterasi maksimum, atau tidak adanya peningkatan dalam indikator hypervolume arsip Pareto selama jumlah iterasi tertentu. Dalam praktiknya, membandingkan kualitas arsip di berbagai kali jalan independen pada anggaran iterasi yang berbeda adalah cara yang andal untuk mendiagnosis konvergensi.

Apakah MOSA cocok untuk model simulasi yang mahal?

Umumnya tidak tanpa modifikasi. Setiap iterasi memerlukan setidaknya satu evaluasi fungsi tujuan, dan MOSA biasanya membutuhkan ribuan iterasi untuk aproksimasi front Pareto yang baik. Ketika setiap evaluasi melibatkan simulasi yang mahal, versi MOSA yang dibantu surrogate (menggunakan metamodel untuk memperkirakan tujuan) lebih disukai.

Metode terkait

Sumber

  1. Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.

    Buka referensi DOI
    Disalin.
  2. Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.

    Buka referensi publikasi
    Disalin.