İçeriğe atla
Arama sonuçlarına dön

Deterministik Dinamik Programlama — Bilinen Parametreler Altında Kesin Sıralı Optimizasyon

Ortaya koyan
Richard E. Bellman
Yıl
1957
Tür
Exact sequential optimization algorithm
Aile
Simulation / optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Deterministik Dinamik Programlama (DDP), çok aşamalı bir karar problemini, tüm sistem parametrelerinin — geçiş fonksiyonları, maliyetler ve ödüller — kesin olarak bilindiği durumlarda onları kesin olarak çözen daha basit alt problemlere ayırarak ele alan matematiksel bir optimizasyon tekniğidir.

Bellman'ın optimallik prensibi aracılığıyla küresel olarak optimal bir politika garanti eder.

Yöntemin mantığı

Tüm yol maliyetlerinin önceden bilindiği bir şehir ağı üzerinden en ucuz rotayı planladığınızı hayal edin. Dinamik programlama, olası tüm tam yolları değerlendirmek yerine geriye doğru çalışır: her şehirde, oradan hedefe ulaşmanın en ucuz maliyetini kaydeder. Her şehir etiketlendikten sonra, optimal yolu ileriye doğru izlemek önemsizdir. Bu geriye dönük akıl yürütme — Bellman'ın optimallik prensibi — deterministik DP'nin özüdür: optimal bir yolun herhangi bir alt yolu kendisi de optimal olmalıdır.

Tarih

Richard Bellman, 1957'deki Princeton monografisinde dinamik programlamayı biçimlendirmiş ve tüm DP yöntemlerinin temelini oluşturan optimallik prensibini türetmiştir. Geçişlerin ve ödüllerin bilindiği deterministik durum, orijinal formülasyondur. Bellman'ın savaş zamanı operasyonel araştırma çalışmalarından gelişmiş ve kontrol teorisi, ekonomi ve kombinatoryal optimizasyonda temel hale gelmiştir. Bertsekas daha sonra teoriyi birden fazla ciltte genişletmiş ve sistematize etmiştir.

Ne zaman kullanılır?

Sistemin iyi tanımlanmış sıralı aşamalara sahip olduğu, tüm geçiş maliyetlerinin ve sonuçlarının kesin olarak bilindiği ve optimallik prensibinin geçerli olduğu (optimal alt yapı) durumlarda Deterministik Dinamik Programlamayı kullanın. Stok yönetimi, zaman içinde kaynak tahsisi, en kısa yol yönlendirme ve sabit parametrelerle üretim planlamasında üstündür. Parametrelerin belirsiz veya rastgele olduğu durumlarda kullanmayın — bunun yerine Stokastik Dinamik Programlamaya geçin. Ayrıca, durum uzayı çok büyük veya analitik yapıya sahip olmadan sürekli ise, boyutluluk laneti nedeniyle hesaplama açısından uygulanamaz olduğundan DDP'den kaçının. Sıralı veya özyinelemeli bir yapıya sahip olmayan problemler için uygun değildir.

Sınırlar ve dikkat edilmesi gerekenler

  • Boyutluluk lanetinden ciddi şekilde muzdariptir: hesaplama ve bellek gereksinimleri durum değişkenlerinin sayısıyla üssel olarak artar.
  • Geçiş fonksiyonu ve ödül yapısının tam ve kesin bilgisini gerektirir; herhangi bir parametre belirsizliği deterministik modeli geçersiz kılar.
  • Sürekli durum veya eylem uzaylarının ayrıklaştırılması yaklaştırma hataları getirir ve gerçek optimumu kaçırabilir.
  • Optimal kararın her aşamada yalnızca mevcut duruma bağlı olduğu, o duruma nasıl ulaşıldığına dair geçmişe değil, bir Markov yapısı varsayar.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Optimizasyon prensibinin geçerli olduğu ve parametrelerin bilindiği durumlarda küresel olarak optimal bir çözüm garanti eder.
  • Tek bir büyük optimizasyon problemi olarak çözülemeyecek çok aşamalı sıralı kararları doğal olarak ele alır.
  • Değer fonksiyonu hesaplandıktan sonra, tüm durumlar için optimal kararlar eş zamanlı olarak kullanılabilir hale gelir, bu da başlangıç koşulları boyunca hassasiyet analizine olanak tanır.
  • Hem ayrık hem de sürekli durum-eylem uzaylarına uygulanabilir (uygun ayrıklaştırma veya analitik işlemle).
  • Kavramsal olarak şeffaftır: geriye doğru tümevarım prosedürünün adım adım denetlenmesi ve doğrulanması kolaydır.

Uygulama alanları

  • Sonlu bir planlama ufku boyunca bilinen talep çizelgeleriyle optimal stok yenileme politikaları.
  • En kısa yol ve ağ yönlendirme problemleri (örneğin, Dijkstra algoritması DP'nin özel bir durumu olarak).
  • Belirlenmiş talep ve kapasite kısıtlamalarıyla imalatta üretim planlama ve parti büyüklüğü belirleme.
  • Kesinlik altında ekonomide kaynak çıkarma ve sermaye yatırımı planlaması.
  • Dizi hizalama ve biyoinformatik (örneğin, Needleman-Wunsch algoritması).
  • Bilinen maliyet ve bozulma fonksiyonlarıyla ekipman değiştirme ve bakım planlaması.

Nasıl çalışır?

Nasıl çalışır?

1

Optimizasyon hedefini, planlama ufkunu (sonlu veya sonsuz) ve karar dizisini tanımlayın. Bir aşamayı, bir durumu, bir eylemi, anlık ödülü veya maliyeti r(s, a) ve durum-eylem çiftlerini kesinlikle bir sonraki durumlara eşleyen deterministik geçiş fonksiyonu s' = f(s, a) oluşturan şeyi belirleyin.

2

Tüm olası durumları S ve her durum için tüm kabul edilebilir eylemleri A(s) numaralandırın veya parametrelendirin. Ayrık problemler için bu, sonlu bir durum-eylem tablosu verir; sürekli problemler için ayrıklaştırma veya analitik çözüm biçimleri kullanılır. Bellek gereksinimleri bu uzayın büyüklüğüyle ölçeklenir — temel hesaplama darboğazı.

3

Bellman optimallik denklemini yazın: V_t(s) = max_{a ∈ A(s)} [r(s,a) + V_{t+1}(f(s,a))]. Sonlu ufuklu bir problem için, V_T(s)'yi terminal değerlerle başlatın ve T-1'den 0'a kadar geriye doğru aşama aşama tekrarlayın. Sonsuz ufuklar için, yakınsama (değer yinelemesi) olana kadar değer güncellemelerini yineleyin.

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

Özyinelemeyi son dönemden ilk döneme doğru aşama aşama çözün (geriye doğru tümevarım). Her aşamada, her duruma optimal değeri atanır ve bunu sağlayan eylem kaydedilir. Bu, alt problem çözümlerinin deterministik geçiş modeli altında tutarlı ve küresel olarak optimal olmasını garanti eder.

5

Optimal politikayı ileriye doğru bir geçişle oluşturun: başlangıç durumu s_0'dan başlayarak, her aşamada pi*(s) = argmax_a [r(s,a) + V*(f(s,a))] uygulayarak, kaydedilen optimal eylemleri izleyin. Elde edilen karar dizisi, bilinen, sabit parametreler altında küresel olarak optimal plandır.

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

Sık yapılan hatalar

  • Deterministik DP'yi stokastik DP ile karıştırmak: herhangi bir sistem parametresi belirsizse, deterministik bir modelden elde edilen sonuçlar aşırı iyimser ve potansiyel olarak yanıltıcı olacaktır.
  • Optimizasyonu kaybetmek (çok kaba) veya durum uzayını patlatmak (çok ince) için çok kaba bir durum temsili seçmek; dikkatli durum uzayı tasarımı kritiktir.
  • Sınır koşullarını göz ardı etmek: yanlış terminal aşama değerleri V_T(s), tüm geriye doğru özyineleme boyunca hataları yayar.
  • Yerel optimalliğin küresel optimalliği garanti etmediği, optimal alt yapıya sahip olmayan problemlere DP uygulamak.
  • Problem gerçekten sonsuzken sonlu bir ufuk varsaymak veya tam tersi, uygun olmayan bir özyineleme formülasyonuna yol açmak.

Sık sorulan sorular

Deterministik DP, Stokastik Dinamik Programlamadan nasıl farklıdır?

Deterministik DP'de bir sonraki durum s' = f(s, a) bilinen bir fonksiyondur — rastgelelik yoktur. Stokastik DP, f'yi bir olasılık dağılımı P(s'|s, a) ile değiştirir ve beklenen değeri maksimize eder. Deterministik DP daha basittir ve kesindir; Stokastik DP, sonuçların belirsiz olduğu durumlarda uygundur.

Boyutluluk laneti nedir ve neden önemlidir?

Bellman, durum uzayının durum değişkenlerinin sayısıyla üssel olarak nasıl büyüdüğünü tanımlamak için bu terimi kullanmıştır. Örneğin, her biri 100 ayrık seviyeye sahip 10 durum değişkeni, herhangi bir bilgisayarın belleğinin çok ötesinde 10^20 durum üretir. Bu, tam DP'yi yüksek boyutlu problemler için uygulanamaz hale getirir ve Yaklaşık DP veya pekiştirmeli öğrenme gibi yaklaştırma yöntemlerini teşvik eder.

Ne zaman doğrusal programlamayı DP yerine kullanmalıyım?

Problem tek dönemli bir optimizasyon olarak doğrusal kısıtlamalar ve hedeflerle ifade edilebildiğinde doğrusal programlamayı kullanın. Kararın birden çok aşamada geliştiği ve her aşamadaki optimal eylemin o andaki sistemin durumuna bağlı olduğu durumlarda DP tercih edilir.

Deterministik DP, oyun teorisindeki geriye doğru tümevarımla aynı mıdır?

Aynı özyinelemeli mantığı paylaşırlar — sondan geriye doğru çözme — ancak oyun teorik geriye doğru tümevarım, birden fazla oyuncu ve stratejik etkileşim içerir. Deterministik DP, stratejik rakip olmayan tek ajanlı bir optimizasyon problemidir.

Deterministik DP, sürekli durum ve eylem uzaylarını işleyebilir mi?

Evet, analitik çözümlerin mevcut olduğu (örneğin, doğrusal-kuadratik problemler) veya değer fonksiyonunun bilinen fonksiyonel biçimlere sahip olduğu durumlarda. Aksi takdirde, sürekli uzaylar ayrıklaştırılmalıdır, bu da yaklaştırma hatası getirir ve hesaplama yükünü büyük ölçüde artırır.

İlgili yöntemler

Kaynaklar

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

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

    Yayın kaynağını aç
    Kopyalandı.