Programowanie dynamiczne
- Autor metody
- Richard Bellman
- Rok
- 1957
- Typ
- Exact combinatorial optimization via recursive decomposition
- Rodzina
- Mathematical programming
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Programowanie dynamiczne (DP) jest dokładną techniką optymalizacji wprowadzoną przez Richarda Bellmana w 1957 roku do rozwiązywania wieloetapowych problemów decyzyjnych.
Polega ono na dekompozycji złożonego problemu na prostsze, nakładające się podproblemy, rozwiązaniu każdego podproblemu raz i przechowywaniu wyników w celu uniknięcia zbędnych obliczeń. Oparte na Zasadzie Optymalności, DP gwarantuje globalnie optymalne rozwiązania, gdy problem wykazuje nakładające się podproblemy i optymalną podstrukturę.
Intuicja stojąca za metodą
Wyobraźmy sobie planowanie najkrótszej trasy przez miasto poprzez wcześniejsze znalezienie najkrótszych ścieżek między każdą parą pobliskich skrzyżowań, a następnie łączenie tych małych rozwiązań w górę. Zamiast ponownego analizowania każdej możliwej pełnej trasy od zera, wykorzystujemy ponownie wstępnie obliczone lokalne odpowiedzi. Programowanie dynamiczne działa w ten sam sposób: buforuje rozwiązania małych podproblemów, tak aby budowanie pełnej odpowiedzi wymagało jedynie odczytów z tabeli, a nie powtarzających się intensywnych obliczeń.
Historia
Richard Bellman ukuł termin „programowanie dynamiczne” w 1957 roku, pracując w RAND Corporation, celowo wybierając słowo „programowanie” w odniesieniu do planowania, a nie kodowania komputerowego. Zasada Optymalności, którą sformułował, stała się podstawą teoretyczną dla teorii sterowania, badań operacyjnych, a później uczenia ze wzmocnieniem. Klasyczne algorytmy DP — algorytm Dijkstry dla najkrótszej ścieżki, algorytm Viterbiego i algorytm wyrównywania sekwencji Needleman-Wunsch — wszystkie wywodzą się bezpośrednio z ram Bellmana.
Kiedy stosować
Programowanie dynamiczne jest odpowiednie, gdy problem ma nakładające się podproblemy i optymalną podstrukturę — właściwości powszechne w podejmowaniu decyzji sekwencyjnych, alokacji zasobów, harmonogramowaniu i zadaniach wyrównywania sekwencji. Wymaga, aby przestrzeń stanów była w pełni wyliczalna i miała zarządzalny rozmiar; metoda cierpi na klątwę wymiarowości, gdy zmienne stanu jest wiele lub są ciągłe. Dla problemów z nietraktowalnymi przestrzeniami stanów preferowane są przybliżone DP lub uczenie ze wzmocnieniem jako alternatywy.
Ograniczenia i uwagi
- Cierpi na klątwę wymiarowości: wymagania dotyczące pamięci i czasu rosną wykładniczo wraz z liczbą zmiennych stanu.
- Wymaga pełnej wcześniejszej wiedzy o strukturze przejść i funkcji nagrody; nie stosuje się do nieznanych środowisk bez aproksymacji.
- Przestrzeń stanów musi być dyskretna lub dyskretyzowalna; ciągłe problemy o wysokiej wymiarowości wymagają schematów aproksymacji, które poświęcają dokładność.
- Sformułowanie poprawnej reprezentacji stanu i relacji rekurencyjnej wymaga znacznego wglądu specyficznego dla problemu.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Gwarantuje dokładne globalnie optymalne rozwiązania dla problemów spełniających Zasadę Optymalności.
- Eliminuje zbędne obliczenia poprzez memoizację, osiągając czas wielomianowy względem liczby stanów.
- Produkuje jawną optymalną politykę, a nie tylko optymalną wartość, umożliwiając proste wsparcie decyzyjne.
- Szeroko stosowalne w różnych dziedzinach, w tym w teorii sterowania, bioinformatyce, ekonomii i badaniach operacyjnych.
Zastosowania
- Problemy najkrótszej ścieżki i trasowania w sieciach (warianty algorytmów Bellmana-Forda, Dijkstry).
- Wyrównywanie sekwencji w biologii obliczeniowej (algorytmy Needleman-Wunsch, Smith-Waterman).
- Optymalna alokacja zasobów i kombinatoryczne problemy typu plecakowego w badaniach operacyjnych.
- Rozpoznawanie mowy i pisma ręcznego za pomocą algorytmu Viterbiego na ukrytych modelach Markowa.
- Optymalne sterowanie i wielookresowa optymalizacja portfela w ekonomii i inżynierii.
Jak to działa
Jak to działa
Ogólny problem optymalizacji jest wyrażany jako relacja rekurencyjna. Dla każdego stanu s i etapu decyzyjnego n, funkcja wartości V_n(s) jest równa najlepszej natychmiastowej nagrodzie plus zdyskontowana wartość wynikającego następnego stanu. To równanie Bellmana formalizuje Zasadę Optymalności: każda podścieżka optymalnej ścieżki musi być sama w sobie optymalna.
Wzór
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]Rekurencja jest rozwiązywana iteracyjnie lub rekurencyjnie. W iteracji wartości, V^*(s) jest wielokrotnie aktualizowane dla wszystkich stanów aż do zbieżności, przy użyciu bieżącej estymacji wartości sąsiednich stanów. Każda aktualizacja zastępuje starą wartość najlepszą osiągalną nagrodą plus przyszłą wartością, propagując informacje o optymalności przez przestrzeń stanów.
Wzór
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)Obliczone wartości są przechowywane w tabeli indeksowanej przez stan. Stany terminalne otrzymują wartość bazową zero (lub znaną nagrodę), a wszystkie inne wpisy są wypełniane w miarę rozwiązywania podproblemów. Memoizacja zapewnia, że każdy stan jest oceniany co najwyżej raz, redukując wykładnicze przeszukiwanie rekurencyjne do czasu wielomianowego względem liczby stanów i etapów.
Wzór
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}Gdy tabela wartości jest kompletna, optymalna polityka pi^*(s) jest odzyskiwana przez prostą przejściową zachłanną: dla każdego stanu wybierany jest akcja maksymalizująca natychmiastową nagrodę plus przechowywaną wartość stanu następczego. Ta jednoprzebiegowa ekstrakcja jest tania obliczeniowo i daje deterministyczną, globalnie optymalną regułę decyzyjną.
Wzór
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]Częste pułapki
- Zdefiniowanie niewystarczająco ekspresyjnej reprezentacji stanu prowadzi do niepoprawnych rekurencji i suboptymalnych rozwiązań.
- Mylenie memoizacji z góry na dół z tabulacją z dołu do góry może prowadzić do błędów przepełnienia stosu lub nieprawidłowej kolejności oceny podproblemów.
- Zastosowanie DP do problemów, którym brakuje optymalnej podstruktury (np. najdłuższa ścieżka w ogólnym grafie), daje nieprawidłowe wyniki bez ostrzeżenia.
- Ignorowanie precyzji numerycznej w obliczeniach skumulowanych nagród może powodować subtelne błędy optymalności we implementacjach zmiennoprzecinkowych.
Najczęściej zadawane pytania
Jaka jest różnica między programowaniem dynamicznym a metodą dziel i zwyciężaj?
Obie metody rozkładają problemy na podproblemy, ale metoda dziel i zwyciężaj zakłada niezależne podproblemy rozwiązywane naturalnie tylko raz. Programowanie dynamiczne celuje w nakładające się podproblemy — ten sam podproblem pojawia się w wielu gałęziach — i stosuje memoizację wyników, aby uniknąć powtarzalnej pracy. Bez nakładających się podproblemów DP nie oferuje żadnej przewagi obliczeniowej nad prostą rekurencją.
Kiedy powinienem używać memoizacji z góry na dół zamiast tabulacji z dołu do góry?
Memoizacja z góry na dół jest łatwiejsza do zaimplementowania bezpośrednio z rekurencji i oblicza tylko potrzebne podproblemy, co jest korzystne dla rzadkich przestrzeni stanów. Tabulacja z dołu do góry unika narzutu rekurencji i ograniczeń stosu, pasuje do gęstych przestrzeni stanów i jest często szybsza w praktyce. Wybierz metodę z góry na dół, gdy trudno przewidzieć zestaw potrzebnych podproblemów, a z dołu do góry, gdy wszystkie podproblemy będą potrzebne.
Jak programowanie dynamiczne ma się do uczenia ze wzmocnieniem?
Klasyczne DP wymaga w pełni znanego modelu procesu decyzyjnego Markowa (prawdopodobieństwa przejść i nagrody). Uczenie ze wzmocnieniem rozszerza idee DP na ustawienia, w których model jest nieznany, wykorzystując zamiast tego próbkowane doświadczenie. Algorytmy takie jak Q-learning i metody gradientu polityki są przybliżonymi procedurami DP, które uczą się funkcji wartości z interakcji, a nie z jawnego modelu.
Pokrewne metody
Źródła
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
ISBN: 978-0-691-07951-6Skopiowano.