Przejdź do treści
Wróć do wyników wyszukiwania

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

Rozmiar czcionki

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

1

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]
2

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)
3

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}
4

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

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

    ISBN: 978-0-691-07951-6
    Skopiowano.