Skip to content
Kembali ke hasil pencarian

Pemrograman Dinamis Deterministik — Optimasi sekuensial eksak di bawah parameter yang diketahui

Diperkenalkan oleh
Richard E. Bellman
Tahun
1957
Jenis
Exact sequential optimization algorithm
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Pemrograman Dinamis Deterministik (DDP) adalah teknik optimasi matematis yang menguraikan masalah keputusan multi-tahap menjadi urutan submasalah yang lebih sederhana, menyelesaikannya secara eksak ketika semua parameter sistem — fungsi transisi, biaya, dan imbalan — diketahui dengan pasti.

Ini menjamin kebijakan optimal secara global melalui prinsip optimalitas Bellman.

Intuisi di balik metode

Bayangkan merencanakan rute termurah melalui jaringan kota di mana semua biaya jalan diketahui sebelumnya. Daripada mengevaluasi setiap jalur lengkap yang mungkin, pemrograman dinamis bekerja mundur: di setiap kota ia mencatat biaya termurah untuk mencapai tujuan dari sana. Setelah setiap kota diberi label, menelusuri jalur optimal ke depan menjadi mudah. Penalaran mundur ini — prinsip optimalitas Bellman — adalah inti dari DP deterministik: setiap sub-jalur dari jalur optimal haruslah optimal.

Sejarah

Richard Bellman memformalkan pemrograman dinamis dalam monografnya tahun 1957 di Princeton, menurunkan prinsip optimalitas yang mendasari semua metode DP. Kasus deterministik — di mana transisi dan imbalan diketahui — adalah formulasi asli. Ini tumbuh dari pekerjaan riset operasi Bellman selama perang dan menjadi dasar dalam teori kontrol, ekonomi, dan optimasi kombinatorial. Bertsekas kemudian memperluas dan mensistematisasikan teori tersebut di berbagai volume.

Kapan digunakan

Gunakan Pemrograman Dinamis Deterministik ketika sistem memiliki tahapan sekuensial yang terdefinisi dengan baik, semua biaya transisi dan hasil diketahui dengan pasti, dan prinsip optimalitas berlaku (sub-struktur optimal). Ini unggul dalam manajemen inventaris, alokasi sumber daya dari waktu ke waktu, perutean jalur terpendek, dan penjadwalan produksi dengan parameter tetap. JANGAN gunakan ketika parameter tidak pasti atau acak — beralihlah ke Pemrograman Dinamis Stokastik sebagai gantinya. Juga hindari DDP ketika ruang keadaan sangat besar atau kontinu tanpa struktur analitis, karena kutukan dimensi membuatnya tidak layak secara komputasi. Ini tidak sesuai untuk masalah tanpa struktur sekuensial atau rekursif.

Batasan dan pertimbangan

  • Sangat menderita akibat kutukan dimensi: kebutuhan komputasi dan memori tumbuh secara eksponensial dengan jumlah variabel keadaan.
  • Membutuhkan pengetahuan lengkap dan eksak tentang fungsi transisi dan struktur imbalan; ketidakpastian parameter apa pun membatalkan model deterministik.
  • Diskretisasi ruang keadaan atau tindakan kontinu memperkenalkan kesalahan perkiraan dan dapat melewatkan optimum yang sebenarnya.
  • Mengasumsikan struktur Markovian — keputusan optimal di setiap tahap hanya bergantung pada keadaan saat ini, bukan pada riwayat bagaimana keadaan itu dicapai.

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

Kelebihan

  • Menjamin solusi optimal secara global ketika masalah memenuhi prinsip optimalitas dan parameter diketahui.
  • Secara alami menangani keputusan sekuensial multi-tahap yang akan sulit dipecahkan sebagai satu masalah optimasi besar.
  • Setelah fungsi nilai dihitung, keputusan optimal untuk semua keadaan tersedia secara bersamaan, memungkinkan analisis sensitivitas di berbagai kondisi awal.
  • Dapat diterapkan pada ruang keadaan-aksi diskrit dan kontinu (dengan diskretisasi yang sesuai atau perlakuan analitis).
  • Secara konseptual transparan: prosedur induksi mundur mudah diaudit dan diverifikasi langkah demi langkah.

Penerapan

  • Kebijakan pengisian ulang inventaris optimal dengan jadwal permintaan yang diketahui selama cakrawala perencanaan terbatas.
  • Masalah jalur terpendek dan perutean jaringan (misalnya, algoritma Dijkstra sebagai kasus khusus DP).
  • Penjadwalan produksi dan penentuan lot dalam manufaktur dengan permintaan dan kendala kapasitas yang deterministik.
  • Ekstraksi sumber daya dan perencanaan investasi modal dalam ekonomi di bawah kepastian.
  • Penyelarasan urutan dan bioinformatika (misalnya, algoritma Needleman-Wunsch).
  • Perencanaan penggantian dan pemeliharaan peralatan dengan fungsi biaya dan degradasi yang diketahui.

Cara kerjanya

Cara kerjanya

1

Definisikan tujuan optimasi, cakrawala perencanaan (terbatas atau tak terbatas), dan urutan keputusan. Identifikasi apa yang merupakan tahap, keadaan, tindakan, imbalan atau biaya langsung r(s, a), dan fungsi transisi deterministik s' = f(s, a) yang memetakan pasangan keadaan-tindakan ke keadaan berikutnya dengan kepastian.

2

Uraikan atau parametrisasikan semua keadaan yang layak S dan semua tindakan yang diizinkan A(s) untuk setiap keadaan. Untuk masalah diskrit, ini menghasilkan tabel keadaan-tindakan yang terbatas; untuk masalah kontinu, digunakan diskretisasi atau bentuk solusi analitis. Kebutuhan memori berskala dengan ukuran ruang ini — hambatan komputasi utama.

3

Tulis persamaan optimalitas Bellman: V_t(s) = maks atas a di A(s) dari [r(s,a) + V_{t+1}(f(s,a))]. Untuk masalah cakrawala terbatas, inisialisasikan V_T(s) dengan nilai terminal dan rekursikan mundur dari tahap T-1 ke tahap 0. Untuk cakrawala tak terbatas, ulangi pembaruan nilai hingga konvergensi (iterasi nilai).

Rumus
V_t(s) = \max_{a \in A(s)} \bigl[ r(s, a) + V_{t+1}(f(s, a)) \bigr]
4

Selesaikan rekursi tahap demi tahap dari periode terakhir ke periode awal (induksi mundur). Di setiap tahap, setiap keadaan diberi nilai optimalnya dan tindakan yang mencapainya dicatat. Ini menjamin bahwa solusi submasalah konsisten dan optimal secara global di bawah model transisi deterministik.

5

Konstruksi kebijakan optimal melalui lintasan maju: dimulai dari keadaan awal s_0, terapkan pi*(s) = argmax_a [r(s,a) + V*(f(s,a))] di setiap tahap, mengikuti tindakan optimal yang dicatat. Urutan keputusan yang dihasilkan adalah rencana optimal secara global di bawah parameter yang diketahui dan tetap.

Rumus
\pi^*(s) = \arg\max_{a \in A(s)} \bigl[ r(s, a) + V^*(f(s, a)) \bigr]

Kesalahan umum

  • Mencampuradukkan DP deterministik dengan DP stokastik: jika ada parameter sistem yang tidak pasti, hasil dari model deterministik akan terlalu optimis dan berpotensi menyesatkan.
  • Memilih representasi keadaan yang terlalu kasar (kehilangan optimalitas) atau terlalu halus (meledakkan ruang keadaan); desain ruang keadaan yang cermat sangat penting.
  • Mengabaikan kondisi batas: nilai tahap terminal V_T(s) yang salah menyebarkan kesalahan melalui seluruh rekursi mundur.
  • Menerapkan DP pada masalah yang tidak memiliki sub-struktur optimal, di mana optimalitas lokal tidak menjamin optimalitas global.
  • Mengasumsikan cakrawala terbatas ketika masalahnya benar-benar tak terbatas, atau sebaliknya, yang mengarah pada formulasi rekursi yang tidak tepat.

Pertanyaan yang sering diajukan

Bagaimana DP Deterministik berbeda dari Pemrograman Dinamis Stokastik?

Dalam DP Deterministik keadaan berikutnya s' = f(s, a) adalah fungsi yang diketahui — tidak ada keacakan. DP Stokastik menggantikan f dengan distribusi probabilitas P(s'|s, a) dan memaksimalkan nilai yang diharapkan. DP Deterministik lebih sederhana dan eksak; DP Stokastik sesuai ketika hasil tidak pasti.

Apa itu kutukan dimensi dan mengapa itu penting?

Bellman menciptakan istilah ini untuk menggambarkan bagaimana ruang keadaan tumbuh secara eksponensial dengan jumlah variabel keadaan. Misalnya, 10 variabel keadaan masing-masing dengan 100 tingkat diskrit menghasilkan 10^20 keadaan — jauh di luar memori komputer mana pun. Hal ini membuat DP eksak tidak layak untuk masalah berdimensi tinggi, memotivasi metode perkiraan seperti DP Perkiraan atau pembelajaran penguatan.

Kapan saya harus menggunakan pemrograman linier alih-alih DP?

Gunakan pemrograman linier ketika masalah dapat diekspresikan sebagai optimasi satu periode dengan kendala dan tujuan linier. DP lebih disukai ketika keputusan terungkap selama beberapa tahap dan tindakan optimal di setiap tahap bergantung pada keadaan sistem pada waktu itu.

Apakah DP Deterministik sama dengan induksi mundur dalam teori permainan?

Mereka berbagi logika rekursif yang sama — memecahkan dari akhir ke belakang — tetapi induksi mundur teori permainan melibatkan banyak pemain dan interaksi strategis. DP Deterministik adalah masalah optimasi agen tunggal tanpa lawan strategis.

Bisakah DP Deterministik menangani ruang keadaan dan tindakan kontinu?

Ya, ketika solusi analitis ada (misalnya, masalah linier-kuadratik) atau ketika fungsi nilai memiliki bentuk fungsional yang diketahui. Jika tidak, ruang kontinu harus didiskretisasi, yang menimbulkan kesalahan perkiraan dan sangat meningkatkan beban komputasi.

Metode terkait

Sumber

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

    ISBN: 9780691079516
    Disalin.
  2. Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control (4th ed., Vol. 1). Athena Scientific, Belmont, MA.

    Buka referensi publikasi
    Disalin.