Optymalizacja. Algorytmy dokładne
dr inż. Maciej Komosiński
Instytut Informatyki
Politechnika Poznańska
www.cs.put.poznan.pl/mkomosinski
Maciej Komosiński, Maciej Hapke
Definicje
Algorytmy
Problem optymalizacji kombinatorycznej
Problem optymalizacji kombinatorycznej jest problemem
minimalizacji bądz
maksymalizacji i charakteryzuje się
zbiorem instancji
Instancja jest parą (S, f )
S oznacza skończony zbiór wszystkich możliwych rozwiązań
f jest odwzorowaniem definiowanym jako
f : S R
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Definicje
Algorytmy
Minimalizacja
W przypadku minimalizacji należy znalez
ć takie rozwiązanie
iopt " S które spełnia
f (iopt) d" f (i) dla wszystkich i " S
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Definicje
Algorytmy
Maksymalizacja
W przypadku maksymalizacji należy znalez
ć takie rozwiązanie
iopt " S które spełnia
f (iopt) e" f (i) dla wszystkich i " S
Takie rozwiązanie iopt jest globalnie optymalne (minimalne lub
maksymalne)
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Definicje
Algorytmy
Klasyfikacja Algorytmów
algorytmy optymalizacyjne dokładne
przeszukiwanie wyczerpujące (exhaustive)
programowanie matematyczne
podziału i ograniczeń (B&B)
programowanie dynamiczne
algorytmy heurystyczne
specjalizowane
losowego przeszukiwania (random search)
lokalnego przeszukiwania i odmiany
symulowane wyżarzanie
przeszukiwanie tabu
ewolucyjne
hybrydy
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Definicje
Algorytmy
Klasyfikacja Algorytmów (2)
Ponadto w obu klasach można wyróżnić
algorytmy ogólne (general algorithms)  niezależne od
rozwiązywanego problemu (np. B&B)
oraz algorytmy dopasowywane (tailored algorithms) 
wykorzystujące specyficzną wiedzę o problemie (np. heurystyki
priorytetowe w szeregowaniu)
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Definicje
Algorytmy
Co jest potrzebne do zaprojektowania algorytmu?
1
Reprezentacja rozwiązania
2
Cel
3
Funkcja oceny
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Definicje
Algorytmy
Reprezentacja rozwiązania
Ciąg binarny, np. SAT
Reprezentacja zmiennoprzecinkowa, np. programowanie
nieliniowe
Permutacja, np. TSP, QAP
Macierz
Drzewo
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Exhaustive search
Wymaga wygenerowania i sprawdzenia każdego rozwiązania
dopuszczalnego  wady oczywiste
Zaleta  proste
Jedyne wymaganie  systematyczny sposób przeszukiwania S
Jak to zrobić, zależy od reprezentacji
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Exhaustive search  SAT
0000  0
0001  1
0010  2
0011  3
...
Ale można inaczej dzieląc S. Jak?
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Exhaustive search  SAT(2)
Wielokrotny podział na dwie przestrzenie, x1 = T , x1 = F , ...
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Exhaustive search  TSP
Permutacja dopuszczalna, np. nie
1-2-3-1-4
Liczba permutacji  n!
Rekurencyjne generowanie permutacji
ustalenie pierwszej pozycji
generowanie (n - 1)! permutacji dla ustalonej pierwszej
pozycji...
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Przeszukiwanie losowe
procedure PRZESZUKIWANIE LOSOWE;
begin
xbest:=GENERUJ LOSOWO;
repeat
x:=GENERUJ LOSOWO; �!- implementacja?
if f(x)<=f(xbest) then
xbest:=x;
until WARUNEK STOPU;
end;
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Jeśli w drzewie umieścimy rozwiązania częściowe...
Czy można ograniczyć przeglądanie takiego drzewa?
Tak  można nie przeglądać gałęzi prowadzących tylko do
rozwiązań niedopuszczalnych
Tak  można nie przeglądać gałęzi, w których nie istnieje
rozwiązanie lepsze od już znalezionego
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Branch & Bound  TSP
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Problem plecakowy
Dany jest zbiór I elementów
Każdy element i = 1, ..., I ma wagę wi i wartość ci
W plecaku o pojemności W należy umieścić elementy o jak
największej łącznej wartości i łącznej wadze nie
przekraczającej W
Przykład  wybór projektów inwestycyjnych
Elementy  projekty inwestycyjne
Wagi  koszty projektów
Wartości  zyski z projektów
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Problem plecakowy  zapis matematyczny
Zmienne
xi " {0, 1} - 1 jeżeli element i jest umieszczany w plecaku
Maksymalizuj
xi ci
i
Przy ograniczeniu:
xi wi d" W
i
Problem plecakowy jest NP-trudny
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Metoda podziału i ograniczeń  Branch & Bound
Konstruowanie rozwiązania jest widziane jak przeglądanie drzewa.
Np. dla problemu plecakowego:
{0,0,0,0}
{1,0,0,0}
{0,1,0,0}
{1,1,0,0}
{1,0,0,1}
{1,0,1,0} {0,1,0,1}
{0,1,1,0}
{1,1,1,0}
{1,1,0,1}
{0,1,1,1}
{1,0,1,1}
{1,1,1,1}
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Górna (dolna) granica  upper (lower) bound
Górna granica  wartość, której na pewno nie przekroczy
funkcja celu dla żadnego z rozwiązań, w których ustalono
pewne elementy (np. pewne zmienne decyzyjne)
Np. jaka jest górna granica dla rozwiązań, w których x1 = 1 i
x5 = 1 ?
Górna granica nie musi być, i z reguły nie jest, osiągalna przez
żadne rozwiązanie
Znajdowanie górnej granicy jest zależne od problemu
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Znajdowanie górnej granicy dla problemu plecakowego
Załóżmy, że do plecaka możemy wkładać części elementów
Posortuj elementy według stosunku ci/wi
Wkładaj do plecaka elementy rozpoczynając od elementu o
największym stosunku ci/wi aż do zapełnienia plecaka.
Ostatni element może zostać włożony częściowo.
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Przykład. Pojemność plecaka = 10
Element i wi ci Stosunek ci/wi
1 3 5 1.666667
2 6 5 0.833333
3 5 4 0.8
4 2 1.5 0.75
3 1 0.333333
4 1 0.25
1
Górna granica = 5 + 5 + � 4 = 10.8
5
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Znajdowanie górnej granicy dla problemu plecakowego
Jeżeli pewne części rozwiązania są już ustalone (elementy są
wybrane  1, lub nie  0), to rozpatrujemy tylko pozostałe
elementy
Np. jeśli zadecydowaliśmy, że nie umieszczamy elementu 1, a
element 2 jest już w plecaku i mamy 4 jednostki wolne:
4
3
4
Górna granica = 5 + � 4 = 8.2
5
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Metoda podziału i ograniczeń
Jeżeli dla danej gałęzi drzewa górna granica jest niższa od znanego
już rozwiązania, to gałąz
tę można pominąć.
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
B&B  przykład
{0,0,0,0,0,0}
C=0, GG=10.8
{0,1,0,0,0,0}
{1,0,0,0,0,0}
C=5, GG=8.2
C=5, GG=10.8
{1,1,0,0,0,0}
{1,0,1,0,0,0}
C=10, GG=10.8
C=9, GG=10.5
{1,0,0,1,0,0} {1,0,0,0,1,0}
C=6.5, GG=8 C=6, GG=7
{1,0,1,1,0,0}
C=10.5, GG=10.5
Niedopuszczalność
Niedopuszczalność
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Branch & Bound  produkcja
Znajdz
przydział, który maksymalizuje łączną wydajność.
Wydajność cij:
Wyrób
1 2 3 4
Stanowisko
A 2 10 9 7
B 15 4 14 8
C 13 14 16 11
D 4 15 13 9
1
Sformułuj ogólne zadanie
2
Zaproponuj algorytm jego rozwiązania
3
Zastosuj go do powyższej instancji problemu.
B.O.D.I., zad. 2.21
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Programowanie dynamiczne
Stosowane do wieloetapowych procesów decyzyjnych z
właściwością Markowa
WPD: N stanów (si), N decyzji (xi), sk = T (sk-1, xk-1)
Właściwość Markowa: w dowolnym stanie procesu, wpływ
dalszych decyzji na funkcję celu zależy tylko od bieżącego
stanu i tych decyzji (historia nie wpływa)
Na przykład z = f1(s1, x1) + ... + fN(sN, xN)
Wiele zadań optymalizacji da się sprowadzić (potraktować jak)
WPD z właściwością Markowa.
B.O.D.I., str. 91 94
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Programowanie dynamiczne  przykład
Zadanie: jednowymiarowy proces alokacyjny. Rozdziel M = 8
jednostek zasobu na N = 3 działalności (zyski podane w tabeli)
tak, aby zmaksymalizować całkowity zysk.
x 0 1 2 3 4 5 6 7 8
f1(x) 0 5 15 40 80 90 95 98 100
f2(x) 0 5 15 40 60 70 73 74 75
f3(x) 0 4 26 40 45 50 51 52 53
1
Sformułuj ogólne zadanie
2
Zaproponuj sposób jego dekompozycji dla PD
3
Rozwiąż powyższą instancję problemu.
B.O.D.I., str. 91 94
Maciej Komosiński Optymalizacja. Algorytmy dokładne
Pełne przeszukiwanie
Definicje Przeszukiwanie losowe
Algorytmy Metoda podziału i ograniczeń
Programowanie dynamiczne
Programowanie dynamiczne [obliczenia]
x 0 1 2 3 4 5 6 7 8
f1(x) 0 5 15 40 80 90 95 98 100
f2(x) 0 5 15 40 60 70 73 74 75
f3(x) 0 4 26 40 45 50 51 52 53
x 0 1 2 3 4 5 6 7 8
q3(x)
d3(x)
q2(x)
d2(x)
q1(x)
d1(x)
Maciej Komosiński Optymalizacja. Algorytmy dokładne