Skip to content
Kembali ke hasil pencarian

Optimisasi Stokastik Multi-Objektif — Mengoptimalkan beberapa tujuan yang saling bertentangan di bawah ketidakpastian

Diperkenalkan oleh
Various (Fonseca, Fleming, Deb, Zitzler, and others)
Tahun
1990s–2000s
Jenis
Stochastic metaheuristic optimization
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Optimisasi Stokastik Multi-Objektif (SMOO) adalah kelas metode yang secara simultan mengoptimalkan dua atau lebih tujuan yang saling bertentangan ketika parameter, biaya, atau kendala bersifat tidak pasti atau acak.

Alih-alih satu solusi optimal tunggal, metode ini menghasilkan front Pareto dari solusi-solusi yang tidak didominasi, yang masing-masing mewakili keseimbangan yang berbeda di antara tujuan-tujuan di bawah ketidakpastian yang dimodelkan.

Intuisi di balik metode

Sebagian besar keputusan nyata melibatkan pertukaran (trade-off) di antara beberapa tujuan — meminimalkan biaya sambil memaksimalkan kualitas dan kecepatan — dan dunia bersifat tidak pasti. MOO Stokastik mengakui bahwa nilai fungsi tujuan bukanlah angka tetap melainkan variabel acak yang dibentuk oleh masukan yang tidak pasti seperti permintaan, harga, atau tingkat kegagalan. Dengan melakukan sampling atau propagasi ketidakpastian secara analitis melalui evaluasi multi-objektif, metode ini menemukan sekumpulan solusi pertukaran yang kuat (robust) yang tetap tidak didominasi di seluruh realisasi ketidakpastian yang realistis, memberikan pembuat keputusan pilihan yang jujur daripada jawaban tunggal yang secara keliru dianggap presisi.

Sejarah

Optimisasi multi-objektif di bawah ketidakpastian muncul pada tahun 1990-an bersamaan dengan maraknya optimisasi multi-objektif evolusioner. Kontribusi fundamental oleh Fonseca dan Fleming (1993) serta Deb et al. (2002) menetapkan kerangka kerja evolusioner berbasis Pareto. Integrasi elemen stokastik — melalui tujuan nilai harapan, kendala peluang, dan pendekatan berbasis skenario — menjadi area penelitian aktif sepanjang tahun 2000-an dan 2010-an, didukung oleh kekuatan komputasi yang meningkat yang memungkinkan pencarian intensif Monte Carlo.

Kapan digunakan

Gunakan SMOO ketika ada dua atau lebih tujuan yang benar-benar saling bertentangan DAN parameter kunci (permintaan, biaya, durasi, probabilitas kegagalan) tidak pasti atau bervariasi. Metode ini sesuai untuk desain teknik di bawah ketidakpastian, perencanaan rantai pasokan, optimisasi portofolio energi, dan evaluasi kebijakan dengan beberapa kriteria kesejahteraan. JANGAN gunakan jika semua parameter bersifat deterministik (gunakan MOO standar), jika hanya satu tujuan yang penting (gunakan optimisasi multi-objektif tunggal stokastik), jika ketidakpastian bersifat epistemik dan tidak dapat dikuantifikasi, atau jika anggaran komputasi terlalu terbatas untuk mendukung evaluasi fungsi stokastik berulang — setiap kandidat solusi mungkin memerlukan puluhan hingga ribuan sampel Monte Carlo.

Batasan dan pertimbangan

  • Mahal secara komputasi: setiap evaluasi fungsi memerlukan sampling Monte Carlo atau enumerasi skenario, dikalikan dengan banyaknya evaluasi yang diperlukan untuk pencarian multi-objektif.
  • Hasil sangat bergantung pada kualitas model ketidakpastian; asumsi distribusi yang buruk menghasilkan front Pareto yang menyesatkan.
  • Konvergensi ke front Pareto stokastik yang sebenarnya lebih sulit dijamin daripada dalam kasus deterministik; kepercayaan pada hasil memerlukan analisis statistik yang cermat.
  • Jumlah solusi Pareto yang besar dapat membebani pembuat keputusan tanpa alat visualisasi atau artikulasi preferensi yang efektif.
  • Memerlukan data yang cukup atau pengetahuan domain untuk menentukan distribusi ketidakpastian untuk setiap parameter yang tidak pasti.

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

Kelebihan

  • Secara eksplisit memperhitungkan ketidakpastian dalam nilai tujuan, menghasilkan solusi yang kuat terhadap variabilitas parameter daripada optimal hanya di bawah nilai tetap yang diasumsikan.
  • Menghasilkan front Pareto penuh dari solusi pertukaran, menjaga otonomi pembuat keputusan untuk memilih di antara alternatif berdasarkan preferensi.
  • Kompatibel dengan berbagai macam representasi ketidakpastian (distribusi, skenario, himpunan ambiguitas) dan mesin optimisasi (algoritma evolusioner, dekomposisi, metode berbantuan pengganti/surrogate).
  • Menangkap relasi dominasi stokastik di antara solusi yang tidak akan terdeteksi oleh MOO deterministik.
  • Dapat diterapkan di berbagai domain termasuk teknik, logistik, keuangan, dan kebijakan publik.

Penerapan

  • Desain teknik: mengoptimalkan bobot struktur, biaya, dan keandalan secara simultan ketika properti material tidak pasti.
  • Manajemen rantai pasokan: menyeimbangkan biaya, tingkat layanan, dan emisi karbon di bawah ketidakpastian permintaan dan waktu tunggu.
  • Sistem energi: merencanakan portofolio pembangkitan yang meminimalkan biaya dan emisi sambil memenuhi target keandalan di bawah output terbarukan yang bervariasi.
  • Optimisasi portofolio keuangan: memaksimalkan pengembalian yang diharapkan sambil meminimalkan risiko (CVaR) di bawah ketidakpastian pengembalian aset.
  • Desain jaringan transportasi: meminimalkan waktu tempuh dan biaya infrastruktur di bawah ketidakpastian permintaan lalu lintas di masa depan.
  • Alokasi sumber daya kesehatan: menyeimbangkan hasil pengobatan dan anggaran di bawah ketidakpastian tingkat kedatangan pasien dan efikasi pengobatan.

Cara kerjanya

Cara kerjanya

1

Definisikan vektor fungsi tujuan f(x) = [f1(x,xi), f2(x,xi), ..., fk(x,xi)] di mana x adalah vektor variabel keputusan dan xi mewakili parameter yang tidak pasti. Tentukan batas variabel keputusan, kendala deterministik dan stokastik, serta struktur ketidakpastian (distribusi, skenario, atau himpunan ambiguitas).

2

Representasikan parameter yang tidak pasti melalui distribusi probabilitas (misalnya, Normal, Uniform, empiris), himpunan skenario diskrit dengan probabilitas terkait, atau himpunan ambiguitas yang kuat (robust). Pilih representasi yang sesuai dengan data yang tersedia: pendekatan berbasis skenario memerlukan asumsi distribusi yang lebih sedikit; model distribusi penuh memungkinkan sampling Monte Carlo.

3

Terapkan algoritma pencarian multi-objektif — umumnya algoritma evolusioner seperti NSGA-II, MOEA/D, atau SPEA2, atau dekomposisi pemrograman matematis — untuk menjelajahi ruang keputusan dan memelihara populasi atau arsip kandidat solusi yang tidak didominasi di seluruh iterasi.

4

Untuk setiap kandidat solusi x yang ditemui selama pencarian, evaluasi tujuan stokastik dengan menghitung nilai harapan E[fi(x,xi)], varians, value-at-risk bersyarat (CVaR), atau nilai rata-rata skenario melalui sampling Monte Carlo atau integrasi analitis. Ini menggantikan evaluasi fungsi deterministik dengan estimasi kebugaran (fitness) yang kuat secara statistik.

5

Perbarui dan pangkas arsip yang tidak didominasi menggunakan relasi dominasi Pareto yang diterapkan pada nilai tujuan stokastik yang diestimasi. Sebuah solusi x mendominasi x' jika vektor tujuan yang diestimasi tidak lebih buruk dalam semua dimensi dan secara ketat lebih baik dalam setidaknya satu dimensi, dengan memperhitungkan ketidakpastian estimasi jika diperlukan.

6

Sajikan front Pareto stokastik yang diestimasi kepada pembuat keputusan, disertai dengan interval kepercayaan atau distribusi probabilitas atas tujuan untuk setiap solusi Pareto. Aktifkan pemilihan solusi yang disukai menggunakan skalarisasi fungsi nilai, metode titik referensi, atau analisis pertukaran interaktif.

Kesalahan umum

  • Menggunakan sampel Monte Carlo yang terlalu sedikit per evaluasi menyebabkan estimasi kebugaran yang berisik yang merusak perbandingan dominasi Pareto dan menyesatkan pencarian.
  • Memperlakukan tujuan yang tidak pasti sebagai deterministik dengan memasukkan nilai parameter rata-rata mengabaikan varians dan dapat menghasilkan solusi yang berkinerja buruk di bawah realisasi aktual.
  • Mencampuradukkan optimisasi kuat (kasus terburuk) dengan optimisasi stokastik (nilai harapan): kedua formulasi menghasilkan front Pareto yang berbeda dan sesuai dengan sikap risiko yang berbeda.
  • Mengabaikan ketidakpastian kendala: kegagalan memodelkan kendala stokastik sebagai kendala peluang (chance constraints) atau kendala nilai harapan mengarah pada solusi yang tidak layak dalam praktik.
  • Melaporkan front Pareto tanpa interval kepercayaan menyesatkan pemangku kepentingan untuk percaya bahwa estimasi tujuan bersifat presisi.

Pertanyaan yang sering diajukan

Bagaimana SMOO berbeda dari Optimisasi Multi-Objektif (MOO) standar (deterministik)?

Dalam MOO deterministik, nilai fungsi tujuan tetap untuk vektor keputusan tertentu. Dalam SMOO, tujuan adalah variabel acak karena beberapa parameter tidak pasti. Setiap kandidat solusi harus dievaluasi dengan mengestimasi kinerja harapan (atau ukuran risiko) di seluruh realisasi ketidakpastian, biasanya melalui sampling Monte Carlo, membuat optimisasi secara signifikan lebih menuntut secara komputasi.

Berapa banyak sampel Monte Carlo yang dibutuhkan per evaluasi solusi?

Tidak ada aturan universal; ini tergantung pada varians tujuan dan akurasi estimasi yang dibutuhkan. Titik awal yang umum adalah 100–1000 sampel per evaluasi, tetapi praktisi harus melakukan studi percontohan untuk menilai berapa banyak sampel yang dibutuhkan untuk menghasilkan estimasi kebugaran yang stabil dan peringkat Pareto yang stabil.

Bisakah saya menggunakan algoritma multi-objektif apa pun sebagai mesin pencari?

Ya. NSGA-II, MOEA/D, SPEA2, dan algoritma lain yang berbasis Pareto atau berbasis dekomposisi dapat diadaptasi dengan mengganti evaluasi fungsi deterministik dengan yang stokastik. Varian berbantuan pengganti (surrogate-assisted) semakin populer untuk mengurangi jumlah evaluasi stokastik yang mahal.

Ukuran risiko apa yang harus saya gunakan untuk tujuan stokastik?

Tergantung pada konteks keputusan. Nilai harapan sesuai untuk pemangku kepentingan yang netral risiko; varians atau standar deviasi memberi penalti pada variabilitas; CVaR (Conditional Value-at-Risk) menangkap risiko ekor (tail risk) untuk pengaturan yang menghindari risiko (risk-averse). Untuk keandalan teknik, probabilitas pemenuhan kendala (kendala peluang) seringkali lebih bermakna daripada nilai harapan.

Apakah optimisasi kuat (robust optimization) sama dengan optimisasi multi-objektif stokastik?

Tidak. Optimisasi kuat biasanya menggunakan model ketidakpastian kasus terburuk (formulasi min-max) tanpa memerlukan distribusi probabilitas. SMOO menggunakan model probabilistik dan mengoptimalkan nilai tujuan yang diharapkan atau disesuaikan dengan risiko. Keduanya mengatasi ketidakpastian, tetapi mereka mengkodekan sikap risiko yang berbeda dan memerlukan jenis informasi ketidakpastian yang berbeda.

Metode terkait

Sumber

  1. Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester.

    ISBN: 9780471873396
    Disalin.
  2. Caramia, M., Dell'Olmo, P. (2008). Multi-Objective Management in Freight Logistics. Springer, London.

    Buka referensi DOI
    Disalin.