Skip to content
Kembali ke hasil pencarian

Pemrograman Dinamis Multi-Objektif — Kebijakan Pareto-optimal atas keputusan sekuensial

Diperkenalkan oleh
Extension of Bellman (1957); formalized by multiple authors from 1970s onward
Tahun
1957-1975
Jenis
Exact optimization — recursive multi-objective decomposition
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Pemrograman Dinamis Multi-Objektif (MODP) memperluas pemrograman dinamis klasik Bellman ke pengaturan di mana pengambil keputusan harus mengoptimalkan beberapa tujuan yang bersaing secara bersamaan di seluruh urutan tahapan.

Alih-alih satu kebijakan optimal, ia menghasilkan sekumpulan kebijakan Pareto-optimal — masing-masing mewakili profil trade-off yang berbeda — dengan menyebarkan fungsi nilai bernilai vektor mundur melalui ruang keadaan.

Intuisi di balik metode

Dalam pemrograman dinamis satu-objektif, setiap keadaan membawa satu nilai terbaik dan satu tindakan terbaik. Pemrograman dinamis multi-objektif menggeneralisasi ini dengan menyimpan, di setiap keadaan, seluruh muka Pareto dari vektor imbalan kumulatif yang tidak didominasi. Saat algoritma menyapu mundur melalui tahapan keputusan, ia menggabungkan dan memangkas kumpulan Pareto ini sehingga hanya kebijakan yang benar-benar tidak didominasi yang bertahan hingga tahap akhir. Hasilnya bukan satu jawaban tetapi permukaan trade-off lengkap dari mana pengambil keputusan dapat memilih kebijakan yang paling sesuai dengan preferensinya, tanpa harus menentukan bobot terlebih dahulu.

Sejarah

Pemrograman Dinamis Multi-Objektif dibangun di atas kerangka kerja pemrograman dinamis dasar Richard Bellman yang diterbitkan pada tahun 1957. Perluasan ke tujuan vektor muncul dalam literatur riset operasi melalui tahun 1970-an dan 1980-an, didorong oleh aplikasi dalam pengelolaan sumber daya air, perencanaan militer, dan kebijakan ekonomi. Bidang ini matang bersamaan dengan teori optimasi multi-objektif, dengan kontribusi kunci yang memformalkan rekursi fungsi nilai Pareto dan algoritma pemangkasan. Ini tetap menjadi area penelitian aktif, terutama dalam konteks proses keputusan Markov dengan beberapa sinyal imbalan.

Kapan digunakan

Gunakan MODP ketika keputusan terungkap selama beberapa tahapan sekuensial, ketika setidaknya dua tujuan berkonflik, dan ketika ruang keadaan dan tindakan cukup kecil untuk diuraikan atau didiskretisasi. Ini ideal untuk alokasi sumber daya dari waktu ke waktu, penjadwalan proyek multi-tahap, dan evaluasi kebijakan kesehatan atau lingkungan sekuensial di mana solusi Pareto-lengkap diperlukan. Jangan gunakan ketika ruang keadaan sangat besar (kutukan dimensionalitas membuat komputasi muka Pareto yang tepat tidak mungkin), ketika tujuan mudah digabungkan menjadi satu skalar sebelum analisis, atau ketika struktur masalah non-Markovian (imbalan masa depan bergantung pada riwayat di luar keadaan saat ini).

Batasan dan pertimbangan

  • Sangat menderita akibat kutukan dimensionalitas: biaya komputasi dan memori tumbuh secara eksponensial dengan jumlah variabel keadaan dan tujuan.
  • Memerlukan ruang keadaan diskrit atau didiskretisasi, yang dapat menimbulkan kesalahan perkiraan untuk masalah kontinu.
  • Jumlah kebijakan yang tidak didominasi yang disimpan di setiap keadaan dapat tumbuh sangat besar, membuat metode yang tepat tidak praktis untuk masalah dengan lebih dari tiga atau empat tujuan.
  • Mengasumsikan properti Markov — tindakan masa depan yang optimal hanya bergantung pada keadaan saat ini, bukan pada riwayat keputusan masa lalu.
  • Implementasi secara signifikan lebih kompleks daripada pemrograman dinamis satu-objektif, membutuhkan pemeriksaan dominasi Pareto yang efisien dan manajemen himpunan di setiap keadaan.

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

Kelebihan

  • Menyediakan muka Pareto lengkap dari kebijakan optimal, memberikan pengambil keputusan visibilitas penuh dari trade-off tujuan tanpa memaksa spesifikasi bobot prematur.
  • Menjamin Pareto-optimalitas yang tepat dalam model — tidak ada perkiraan heuristik untuk masalah dengan ukuran yang dapat dikelola.
  • Secara alami menangani struktur keputusan sekuensial dan bertahap di mana sebagian besar metode multi-objektif lainnya memerlukan reformulasi masalah buatan.
  • Memisahkan fase optimasi dari fase elisitasi preferensi, memungkinkan preferensi pemangku kepentingan diterapkan setelah muka dihitung.
  • Meluas secara alami ke pengaturan stokastik dengan menyimpan kumpulan Pareto dari nilai vektor yang diharapkan di setiap keadaan.

Penerapan

  • Manajemen reservoir air multi-tahap yang menyeimbangkan pengendalian banjir, pasokan irigasi, dan pembangkit listrik tenaga air secara bersamaan.
  • Perencanaan pengobatan kanker sekuensial yang mengoptimalkan kontrol tumor, toksisitas, dan kualitas hidup selama siklus pengobatan.
  • Optimasi portofolio multi-periode yang menyeimbangkan pengembalian, risiko, dan kendala likuiditas di seluruh cakrawala investasi.
  • Evaluasi kebijakan lingkungan untuk kebijakan yang harus menyeimbangkan biaya ekonomi, pengurangan karbon, dan dampak keanekaragaman hayati dari waktu ke waktu.
  • Perutean dan penjadwalan multi-objektif dalam jaringan logistik dengan tujuan biaya, waktu, dan keandalan yang bersaing.
  • Alokasi sumber daya sekuensial dalam portofolio proyek R&D yang menyeimbangkan efisiensi anggaran, potensi inovasi, dan waktu ke pasar.

Cara kerjanya

Cara kerjanya

1

Definisikan masalah keputusan multi-tahap: sekumpulan tahapan t = 1, ..., T, ruang keadaan S, ruang tindakan A, fungsi transisi, dan fungsi imbalan vektor r(s, a) = (r1, r2, ..., rk) dengan k tujuan. Tidak ada bobot skalar yang diperlukan pada tahap ini.

2

Uraikan atau diskretisasi ruang keadaan. Untuk setiap keadaan terminal pada tahap T, inisialisasi kumpulan Pareto sebagai singleton yang berisi vektor imbalan terminal. Nilai batas ini menambatkan rekursi mundur.

3

Pada setiap keadaan s dan tahap t, definisikan fungsi nilai vektor V(s, t) sebagai kumpulan semua vektor imbalan kumulatif yang tidak didominasi yang dapat dicapai dari (s, t) ke tahap terminal. Ganti optimalitas Bellman skalar dengan non-dominasi Pareto: vektor v mendominasi v' jika v setidaknya sama baiknya pada setiap tujuan dan secara ketat lebih baik pada setidaknya satu.

4

Sapu mundur dari tahap T ke tahap 1. Pada setiap (s, t), hitung nilai vektor kandidat untuk setiap tindakan yang layak a dengan menggabungkan imbalan langsung r(s, a) dengan setiap elemen di V(s', t+1) untuk keadaan penerus s'. Ambil gabungan atas semua tindakan dan pangkas vektor yang didominasi untuk mempertahankan hanya muka Pareto untuk V(s, t).

5

Pada keadaan awal, V(s0, 1) berisi kumpulan lengkap vektor imbalan kumulatif Pareto-optimal. Setiap vektor sesuai dengan kebijakan yang berbeda. Sajikan muka Pareto ini kepada pengambil keputusan, yang dapat memilih kebijakan yang disukai berdasarkan prioritas mereka, atau menerapkan skalarisasi (misalnya, jumlah tertimbang) secara post-hoc.

Kesalahan umum

  • Membingungkan DP multi-objektif dengan hanya menjalankan pemrograman dinamis secara terpisah untuk setiap tujuan — pendekatan itu kehilangan wilayah non-konveks dari muka Pareto.
  • Mengabaikan verifikasi bahwa ruang keadaan benar-benar Markovian sebelum menerapkan metode — variabel keadaan tersembunyi akan membatalkan rekursi.
  • Meremehkan ukuran kumpulan Pareto di setiap keadaan, yang menyebabkan kehabisan memori untuk masalah dengan banyak tujuan atau cakrawala yang panjang.
  • Menerapkan MODP ke ruang keadaan kontinu atau berdimensi tinggi tanpa skema perkiraan yang dijamin konvergensinya, menghasilkan hasil yang tidak dapat diandalkan.
  • Menyajikan muka Pareto lengkap kepada pengambil keputusan tanpa alat pendukung untuk elisitasi preferensi, membanjiri mereka dengan terlalu banyak pilihan kebijakan.

Pertanyaan yang sering diajukan

Bagaimana pemrograman dinamis multi-objektif berbeda dari sekadar menjalankan pemrograman dinamis secara terpisah untuk setiap tujuan?

Menjalankan DP secara terpisah untuk setiap tujuan menghasilkan optimum tunggal-objektif individu, yang umumnya tidak dapat dicapai secara bersamaan dan sepenuhnya kehilangan struktur trade-off. MODP menyebarkan kumpulan Pareto bernilai vektor melalui ruang keadaan, menangkap semua kombinasi nilai tujuan yang tidak didominasi yang dapat dicapai oleh kebijakan tunggal mana pun — termasuk solusi di wilayah non-konveks dari muka Pareto yang tidak dapat ditemukan oleh pendekatan jumlah tertimbang.

Kapan kutukan dimensionalitas membuat MODP tidak praktis?

MODP menjadi sulit dikelola ketika ruang keadaan memiliki lebih dari beberapa variabel diskrit, ketika cakrawala perencanaan sangat panjang, atau ketika ada lebih dari tiga atau empat tujuan (menyebabkan muka Pareto di setiap keadaan tumbuh secara eksponensial). Metode perkiraan seperti pembelajaran penguatan multi-objektif atau pencarian Pareto heuristik umumnya lebih disukai dalam kasus-kasus tersebut.

Bisakah MODP menangani ketidakpastian dalam transisi atau imbalan?

Ya. Dalam pengaturan stokastik, fungsi nilai vektor menyimpan vektor imbalan Pareto-optimal yang diharapkan, dihitung menggunakan jumlah tertimbang probabilitas atas keadaan penerus. Ini meluas secara alami ke proses keputusan Markov multi-objektif (MOMDP), meskipun stokastisitas semakin meningkatkan tuntutan komputasi.

Apakah saya perlu menentukan bobot tujuan sebelum menjalankan MODP?

Tidak — ini adalah salah satu keuntungan utama MODP. Bobot atau informasi preferensi tidak diperlukan selama fase optimasi. Algoritma menghitung muka Pareto lengkap, dan pengambil keputusan menerapkan preferensi mereka sesudahnya untuk memilih kebijakan tertentu.

Keluaran apa yang dihasilkan MODP, dan bagaimana seharusnya ditafsirkan?

MODP menghasilkan sekumpulan kebijakan Pareto-optimal, masing-masing dikaitkan dengan vektor nilai tujuan kumulatif. Tidak ada satu kebijakan pun yang mendominasi semua kebijakan lain di setiap tujuan. Pengambil keputusan memeriksa muka ini untuk mengidentifikasi kebijakan yang sesuai dengan urutan prioritas mereka, sering dibantu oleh alat visualisasi seperti plot sebar atau plot koordinat paralel dari vektor tujuan.

Metode terkait

Sumber

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.

    ISBN: 9780691079516
    Disalin.
  2. Daellenbach, H. G., & Flood, R. L. (1992). Multi-objective dynamic programming. European Journal of Operational Research, 56(2), 215-225.

    Buka referensi publikasi
    Disalin.