Dinamik Programlama
- Ortaya koyan
- Richard Bellman
- Yıl
- 1957
- Tür
- Exact combinatorial optimization via recursive decomposition
- Aile
- Mathematical programming
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Dinamik Programlama (DP), 1957'de Richard Bellman tarafından tanıtılan, çok aşamalı karar problemlerini çözmek için kullanılan kesin bir optimizasyon tekniğidir.
Karmaşık bir problemi daha basit, örtüşen alt problemlere ayırır, her alt problemi bir kez çözer ve gereksiz hesaplamaları önlemek için sonuçları saklar. Optimalite İlkesi'ne dayanan DP, problem örtüşen alt problemler ve optimal alt yapı sergilediğinde küresel olarak optimal çözümleri garanti eder.
Yöntemin mantığı
Bir şehrin en kısa rotasını planlamayı, önce her birbiriyle yakın kesişim arasındaki en kısa yolları bularak, ardından bu küçük çözümleri yukarı doğru birleştirerek hayal edin. Her olası tam rotayı sıfırdan yeniden keşfetmek yerine, önceden hesaplanmış yerel cevapları yeniden kullanırsınız. Dinamik Programlama da aynı şekilde çalışır: küçük alt problemlerin çözümlerini önbelleğe alır, böylece tam cevaba ulaşmak tekrarlanan yoğun hesaplama yerine yalnızca tablo aramaları gerektirir.
Tarih
Richard Bellman, 1957'de RAND Corporation'da çalışırken 'dinamik programlama' terimini ortaya attı, 'programlama' kelimesini bilgisayar kodlaması yerine planlama anlamına gelecek şekilde kasıtlı olarak seçti. Belirttiği Optimalite İlkesi, kontrol teorisi, operasyon araştırması ve daha sonra pekiştirmeli öğrenme için teorik temel haline geldi. Dijkstra'nın en kısa yolu, Viterbi algoritması ve Needleman-Wunsch dizisi hizalayıcısı gibi klasik DP algoritmaları, Bellman'ın çerçevesinden doğrudan türetilmiştir.
Ne zaman kullanılır?
Dinamik Programlama, örtüşen alt problemler ve optimal alt yapıya sahip olduğunda uygundur - ardışık karar verme, kaynak tahsisi, zamanlama ve dize hizalama görevlerinde yaygın özellikler. Durum uzayının tam olarak sayılabilir ve yönetilebilir boyutta olmasını gerektirir; durum değişkenleri çok sayıda veya sürekli olduğunda yöntem, boyutluluk lanetinden muzdariptir. Aşırı karmaşık durum uzaylarına sahip problemler için, yaklaşık DP veya pekiştirmeli öğrenme tercih edilen alternatiflerdir.
Sınırlar ve dikkat edilmesi gerekenler
- Boyutluluk lanetinden muzdariptir: bellek ve zaman gereksinimleri durum değişkenlerinin sayısıyla üstel olarak artar.
- Geçiş yapısı ve ödül fonksiyonu hakkında tam ön bilgi gerektirir; yaklaşım olmadan bilinmeyen ortamlar için uygulanamaz.
- Durum uzayı ayrık veya ayrıklaştırılabilir olmalıdır; sürekli yüksek boyutlu problemler kesinlikten ödün veren yaklaşım şemaları gerektirir.
- Doğru durum temsili ve özyineleme ilişkisinin formüle edilmesi, önemli ölçüde probleme özgü içgörü gerektirir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Optimalite İlkesi'ni karşılayan problemler için kesin küresel optimal çözümleri garanti eder.
- Belleğe alma yoluyla gereksiz hesaplamaları ortadan kaldırır, durum sayısında polinom zaman elde eder.
- Yalnızca optimal bir değer değil, açık bir optimal politika üretir, bu da doğrudan karar desteği sağlar.
- Kontrol teorisi, biyoinformatik, ekonomi ve operasyon araştırması dahil olmak üzere alanlarda geniş çapta uygulanabilir.
Uygulama alanları
- Ağlarda en kısa yol ve yönlendirme problemleri (Bellman-Ford, Dijkstra varyantları).
- Hesaplamalı biyolojide dizi hizalama (Needleman-Wunsch, Smith-Waterman algoritmaları).
- Operasyon araştırmasında optimal kaynak tahsisi ve sırt çantası tipi kombinatoryal problemler.
- Gizli Markov Modelleri üzerinde Viterbi algoritması aracılığıyla konuşma ve el yazısı tanıma.
- Ekonomi ve mühendislikte optimal kontrol ve çok dönemli portföy optimizasyonu.
Nasıl çalışır?
Nasıl çalışır?
Genel optimizasyon problemi bir özyineleme ilişkisi olarak ifade edilir. Her s durumu ve n karar aşaması için, değer fonksiyonu V_n(s), en iyi anlık ödül artı sonuçta ortaya çıkan sonraki durumun indirimli değerine eşittir. Bu Bellman denklemi, Optimalite İlkesi'ni biçimlendirir: optimal bir yolun herhangi bir alt yolu kendisi de optimal olmalıdır.
Formül
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]Özyineleme iteratif veya özyinelemeli olarak çözülür. Değer yinelemesinde, V^*(s) komşu durum değerlerinin mevcut tahminini kullanarak tüm durumlar boyunca yakınsama olana kadar tekrar tekrar güncellenir. Her güncelleme, eski değeri elde edilebilecek en iyi ödül artı gelecek değeri ile değiştirir ve optimalite bilgisini durum uzayı boyunca yayar.
Formül
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)Hesaplanan değerler durum tarafından indekslenen bir tabloda saklanır. Son durumlar sıfır (veya bilinen bir ödül) temel değeri alır ve diğer tüm girişler alt problemler çözüldükçe doldurulur. Belleğe alma, her durumun en fazla bir kez değerlendirilmesini sağlar, üstel özyinelemeli aramayı durum ve aşama sayısında polinom zamana indirir.
Formül
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}Değer tablosu tamamlandıktan sonra, optimal politika pi^*(s) basit bir açgözlü geçişle elde edilir: her durum için, anlık ödülü artı ardıl durumun saklanan değerini en üst düzeye çıkaran eylemi seçin. Bu tek geçişli çıkarma hesaplama açısından ucuzdur ve deterministik, küresel olarak optimal bir karar kuralı sağlar.
Formül
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]Sık yapılan hatalar
- Yetersiz ifade gücüne sahip bir durum temsilinin tanımlanması, yanlış özyinelemelere ve suboptimal çözümlere yol açar.
- Yukarıdan aşağıya belleğe almayı aşağıdan yukarıya tablo oluşturma ile karıştırmak, yığın taşması hatalarına veya alt problem değerlendirmesinin yanlış sıralanmasına neden olabilir.
- DP'yi optimal alt yapıya sahip olmayan problemlere (örneğin, genel bir grafikte en uzun yol) uygulamak, uyarı olmadan yanlış sonuçlar verir.
- Kümülatif ödül hesaplamalarında sayısal hassasiyeti göz ardı etmek, kayan nokta uygulamalarında ince optimalite hatalarına neden olabilir.
Sık sorulan sorular
Dinamik programlama ile böl ve yönet arasındaki fark nedir?
Her ikisi de problemleri alt problemlere ayırır, ancak böl ve yönet, bağımsız alt problemlerin doğal olarak yalnızca bir kez çözüldüğünü varsayar. Dinamik programlama, örtüşen alt problemleri hedefler - aynı alt problem birden fazla dalda görünür - ve gereksiz işten kaçınmak için sonuçları belleğe alır. Örtüşen alt problemler olmadan, DP düz özyinelemeye göre hesaplama avantajı sunmaz.
Ne zaman yukarıdan aşağıya belleğe alma yerine aşağıdan yukarıya tablo oluşturmayı kullanmalıyım?
Yukarıdan aşağıya belleğe alma, özyinelemeden doğrudan uygulaması daha kolaydır ve yalnızca gerekli alt problemleri hesaplar, seyrek durum uzaylarından yararlanır. Aşağıdan yukarıya tablo oluşturma, özyineleme ek yükünü ve yığın sınırlarını önler, yoğun durum uzaylarına uyar ve pratikte genellikle daha hızlıdır. Gerekli alt problemler kümesinin tahmin edilmesi zor olduğunda yukarıdan aşağıya, tüm alt problemlerin gerekli olacağı zaman aşağıdan yukarıya seçin.
Dinamik programlama pekiştirmeli öğrenme ile nasıl ilişkilidir?
Klasik DP, tam olarak bilinen bir Markov Karar Süreci modeli (geçiş olasılıkları ve ödüller) gerektirir. Pekiştirmeli öğrenme, modeli bilinmeyen ortamlara DP fikirlerini genişletir, bunun yerine örneklenmiş deneyleri kullanır. Q-öğrenme ve politika gradyan yöntemleri gibi algoritmalar, açık bir modelden ziyade etkileşimden değer fonksiyonlarını öğrenen yaklaşık DP prosedürleridir.
İlgili yöntemler
Kaynaklar
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
ISBN: 978-0-691-07951-6Kopyalandı.