Çok Amaçlı Dinamik Programlama — Ardışık Kararlar Üzerinde Pareto-Optimal Politikalar
- Ortaya koyan
- Extension of Bellman (1957); formalized by multiple authors from 1970s onward
- Yıl
- 1957-1975
- Tür
- Exact optimization — recursive multi-objective decomposition
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Çok Amaçlı Dinamik Programlama (ÇADP), Bellman'ın klasik dinamik programlamasını, bir karar vericinin bir dizi aşama boyunca birden fazla rakip hedefi aynı anda optimize etmesi gereken ortamlara genişletir.
Tek bir optimal politika yerine, her biri farklı bir ödünleşme profili temsil eden bir Pareto-optimal politika kümesi üretir; bu, vektör değerli değer fonksiyonlarını durum uzayı boyunca geriye doğru yayarak gerçekleştirilir.
Yöntemin mantığı
Tek amaçlı dinamik programlamada, her durum tek bir en iyi değere ve tek bir en iyi eyleme sahiptir. Çok amaçlı dinamik programlama, her durumda baskın olmayan kümülatif ödül vektörlerinden oluşan bir Pareto cephesi depolayarak bunu genelleştirir. Algoritma karar aşamaları boyunca geriye doğru ilerledikçe, yalnızca gerçekten baskın olmayan politikaların son aşamaya ulaşmasını sağlamak için bu Pareto kümelerini birleştirir ve budar. Sonuç tek bir cevap değil, karar vericinin önceden ağırlık belirtmek zorunda kalmadan tercihine en uygun politikayı seçebileceği eksiksiz bir ödünleşme yüzeyidir.
Tarih
Çok Amaçlı Dinamik Programlama, Richard Bellman'ın 1957'de yayınlanan temel dinamik programlama çerçevesini temel alır. Vektör hedeflerine yönelik uzantılar, 1970'ler ve 1980'lerde su kaynakları yönetimi, askeri planlama ve ekonomik politika alanlarındaki uygulamalarla araştırma operasyonları literatüründe ortaya çıktı. Alan, Pareto-değer fonksiyonu özyinelemesi ve budama algoritmalarını biçimlendiren temel katkılarla çok amaçlı optimizasyon teorisiyle birlikte olgunlaştı. Özellikle çoklu ödül sinyallerine sahip Markov karar süreçleri bağlamında aktif bir araştırma alanı olmaya devam etmektedir.
Ne zaman kullanılır?
Kararlar birden çok ardışık aşama boyunca ilerlediğinde, en az iki hedef çakıştığında ve durum ve eylem uzayları numaralandırılacak veya ayrıştırılacak kadar küçük olduğunda ÇADP'yi kullanın. Zaman içinde kaynak tahsisi, çok aşamalı proje çizelgeleme ve Pareto-tam çözümlerin gerektiği ardışık sağlık veya çevre politikası değerlendirmeleri için idealdir. Durum uzayının çok büyük olduğu durumlarda (boyutluluk laneti, kesin Pareto cephesi hesaplamasını olanaksız hale getirir), hedeflerin analizden önce tek bir skalerde kolayca birleştirilebildiği durumlarda veya problem yapısının Markovian olmadığı durumlarda (gelecekteki ödüller mevcut durumun ötesindeki geçmişe bağlıdır) kullanmayın.
Sınırlar ve dikkat edilmesi gerekenler
- Boyutluluk lanetinden ciddi şekilde muzdariptir: hesaplama maliyeti ve bellek, durum değişkenleri ve hedeflerin sayısıyla üssel olarak artar.
- Sürekli problemler için yaklaşım hatası getirebilen ayrık veya ayrıştırılmış bir durum uzayı gerektirir.
- Her durumdaki baskın olmayan politikaların sayısı çok büyüyebilir, bu da üç veya dörtten fazla hedefi olan problemler için kesin yöntemleri pratik olmaktan çıkarır.
- Optimal gelecek eylemin yalnızca mevcut duruma, geçmiş kararların geçmişine değil, yalnızca bağlı olduğu Markov özelliğini varsayar.
- Uygulama, her durumda verimli Pareto baskınlık kontrolleri ve küme yönetimi gerektiren tek amaçlı dinamik programlamadan önemli ölçüde daha karmaşıktır.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Karar vericilere erken ağırlık belirtme zorunluluğu olmaksızın hedef ödünleşmelerinin tam görünürlüğünü sağlayan optimal politikaların eksiksiz bir Pareto cephesini sağlar.
- Çözülebilir boyuttaki problemler için sezgisel yaklaşımlar olmaksızın model dahilinde kesin Pareto-optimalliği garanti eder.
- Çoğu diğer çok amaçlı yöntemin yapay problem yeniden formülasyonu gerektirdiği ardışık ve aşamalı karar yapılarını doğal olarak ele alır.
- Optimizasyon aşamasını tercih belirleme aşamasından ayırır, bu da paydaş tercihlerinin cephe hesaplandıktan sonra uygulanmasına olanak tanır.
- Her durumda beklenen vektör değerlerinin Pareto kümelerini depolayarak stokastik ortamlara doğal olarak genişler.
Uygulama alanları
- Su taşkın kontrolü, sulama tedariki ve hidroelektrik üretimi arasında eş zamanlı denge kuran çok aşamalı su rezervuar yönetimi.
- Tedavi döngüleri boyunca tümör kontrolünü, toksisiteyi ve yaşam kalitesini optimize eden ardışık kanser tedavi planlaması.
- Yatırım ufukları boyunca getiri, risk ve likidite kısıtlamalarını dengeleyen çok dönemli portföy optimizasyonu.
- Zaman içinde ekonomik maliyet, karbon azaltımı ve biyoçeşitlilik etkisini dengelemek zorunda olan politikalar için çevre politikası değerlendirmesi.
- Rekabet eden maliyet, zaman ve güvenilirlik hedeflerine sahip lojistik ağlarda çok amaçlı yönlendirme ve çizelgeleme.
- Bütçe verimliliğini, inovasyon potansiyelini ve pazara sunma süresini dengeleyen Ar-Ge proje portföylerinde ardışık kaynak tahsisi.
Nasıl çalışır?
Nasıl çalışır?
Çok aşamalı karar problemini tanımlayın: bir dizi aşama t = 1, ..., T, bir durum uzayı S, bir eylem uzayı A, bir geçiş fonksiyonu ve k hedefi olan bir vektör ödül fonksiyonu r(s, a) = (r1, r2, ..., rk). Bu aşamada skaler ağırlık gerekmez.
Durum uzayını numaralandırın veya ayrıştırın. T aşamasındaki her terminal durum için, Pareto kümesini terminal ödül vektörünü içeren tekil bir küme olarak başlatın. Bu sınır değerleri geriye doğru özyinelemeyi sabitler.
Her s durumu ve t aşamasında, V(s, t) vektör değer fonksiyonunu, (s, t)'den terminal aşamaya kadar ulaşılabilir tüm baskın olmayan kümülatif ödül vektörleri kümesi olarak tanımlayın. Skaler Bellman optimalliğini Pareto baskın olmama ile değiştirin: bir v vektörü, v'nin her hedefte en azından v kadar iyi ve en az birinde kesin olarak daha iyi olması durumunda v'yi baskın kılar.
T aşamasından 1 aşamasına kadar geriye doğru ilerleyin. Her (s, t)'de, ardıl durum s' için V(s', t+1)'deki her elemanı anlık ödül r(s, a) ile birleştirerek her olası eylem a için aday vektör değerlerini hesaplayın. Tüm eylemler üzerinden birleşimi alın ve V(s, t) için yalnızca Pareto cephesini tutmak üzere baskın vektörleri budayın.
Başlangıç durumunda, V(s0, 1) Pareto-optimal kümülatif ödül vektörlerinin tam kümesini içerir. Her vektör farklı bir politikaya karşılık gelir. Bu Pareto cephesini, karar vericinin önceliklerine göre tercih edilen politikayı seçebileceği veya sonradan bir skalerleştirme (örneğin, ağırlıklı toplam) uygulayabileceği şekilde sunun.
Sık yapılan hatalar
- Çok amaçlı DP'yi, farklı ağırlıklarla tek amaçlı DP'yi birden çok kez çalıştırmakla karıştırmak — bu yaklaşım Pareto cephesinin dışbükey olmayan bölgelerini kaçırır.
- Yöntemi uygulamadan önce durum uzayının gerçekten Markovian olduğunu doğrulamayı ihmal etmek — gizli durum değişkenleri özyinelemeyi geçersiz kılacaktır.
- Her durumdaki Pareto kümesinin boyutunu hafife almak, çok sayıda hedefi veya uzun ufukları olan problemler için bellek tükenmesine yol açar.
- ÇADP'yi, yakınsama garantili bir yaklaşım şeması olmaksızın sürekli veya yüksek boyutlu durum uzaylarına uygulamak, güvenilmez sonuçlar üretir.
- ÇADP'yi, cephe hesaplandıktan sonra tercihlerin uygulandığı destek araçları olmaksızın karar vericilere tam Pareto cephesini sunmak, onları çok fazla politika seçeneğiyle bunaltır.
Sık sorulan sorular
Çok amaçlı dinamik programlama, her hedef için ayrı ayrı dinamik programlama çalıştırmaktan nasıl farklıdır?
Her hedef için ayrı ayrı DP çalıştırmak, genellikle aynı anda gerçekleştirilemeyen ve ödünleşme yapısını tamamen kaçıran bireysel tek amaçlı optimumlar verir. ÇADP, durum uzayı boyunca vektör değerli Pareto kümelerini yayarak, ağırlıklı toplam yaklaşımlarının bulamayacağı Pareto cephesinin dışbükey olmayan bölgelerindeki çözümler de dahil olmak üzere, tek bir politika tarafından elde edilebilen hedef değerlerinin tüm baskın olmayan kombinasyonlarını yakalar.
Boyutluluk laneti ÇADP'yi ne zaman pratik olmaktan çıkarır?
ÇADP, durum uzayının birkaç ayrık değişkenden fazlasına sahip olduğunda, planlama ufku çok uzun olduğunda veya üç veya dörtten fazla hedef olduğunda (her durumdaki Pareto cephesinin üssel olarak büyümesine neden olur) çözülemez hale gelir. Bu gibi durumlarda genellikle çok amaçlı pekiştirmeli öğrenme veya sezgisel Pareto arama gibi yaklaşık yöntemler tercih edilir.
ÇADP belirsizlikleri geçişlerde veya ödüllerde ele alabilir mi?
Evet. Stokastik bir ortamda, vektör değer fonksiyonu, ardıl durumlar üzerinden olasılık ağırlıklı toplam kullanılarak hesaplanan beklenen Pareto-optimal ödül vektörlerini depolar. Bu, çok amaçlı Markov karar süreçlerine (ÇMDS'ler) doğal olarak genişler, ancak stokastiklik hesaplama taleplerini daha da artırır.
ÇADP'yi çalıştırmadan önce hedef ağırlıklarını belirtmem gerekiyor mu?
Hayır — bu ÇADP'nin temel avantajlarından biridir. Ağırlıklar veya tercih bilgileri optimizasyon aşamasında gerekli değildir. Algoritma tam Pareto cephesini hesaplar ve karar verici, belirli bir politikayı seçmek için sonradan tercihlerini uygular.
ÇADP ne tür bir çıktı üretir ve nasıl yorumlanmalıdır?
ÇADP, her biri kümülatif hedef değerleri vektörüyle ilişkilendirilmiş bir dizi Pareto-optimal politika üretir. Hiçbir tek politika diğerlerini her hedefte baskın kılmaz. Karar verici, genellikle hedef vektörlerin saçılım grafikleri veya paralel koordinat grafikleri gibi görselleştirme araçlarının yardımıyla öncelik sıralamasına uyan politikaları belirlemek için bu cepheyi inceler.
İlgili yöntemler
Kaynaklar
Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.
ISBN: 9780691079516Kopyalandı.Daellenbach, H. G., & Flood, R. L. (1992). Multi-objective dynamic programming. European Journal of Operational Research, 56(2), 215-225.
Yayın kaynağını açKopyalandı.