Wykład 5

Problemy optymalizacji dyskretnej.
Algorytmy heurystyczne.

Streszczenie

Wykład obejmuje przegląd heurystycznych (przybliżonych) metod optymalizacji dyskretnej: algorytm zachłanny, przeszukiwanie wiązkowe, algorytm wspinaczki. Analizowane jest też pojęcie sąsiedztwa rozwiązań.


Zadania optymalizacyjne

Przypomnijmy definicję problemu optymalizacyjnego:

Niech X - dowolny zbiór skończony (przestrzeń stanów), niech f:X->R - pewna rzeczywista funkcja na X (funkcja celu). Wówczas zadanie optymalizacyjne polega na znalezieniu punktu x0 ze zbioru X, takiego że (w zależności od problemu):

Każde dyskretne i skończone zadanie optymalizacyjne można rozwiązać przez przejrzenie wszystkich możliwości (wszystkich elementów przestrzeni stanów). Dla większych zadań jest to zwykle niemożliwe, stąd potrzeba szukania metod przybliżonych, nie zawsze dajacych optymalny wynik, ale za to szybkich. Metody takie nazywać będziemy algorytmami heurystycznymi.

Zanim przejdziemy do omówienia algorytmów optymalizacyjnych, przyjrzyjmy się przykładowym problemom. Ich wspólną cechą jest stosunkowo proste sformułowanie, duże znaczenie praktyczne, a przy tym brak prostego i szybkiego sposobu rozwiązania.

Przykład: Problem komiwojażera.

Dany jest graf G, którego krawędzie mają ustalone długości. Znaleźć najkrótszą drogę przechodzącą dokładnie raz przez wszystkie wierzchołki (o ile istnieje).

Przestrzeń stanów: wszystkie możliwe drogi przechodzące przez każdy wierzchołek dokładnie raz. Wielkość przestrzeni stanów: co najwyżej n!, gdzie n - liczba wierzchołków.

Funkcja celu: łączna długość trasy. Zadanie polega na minimalizacji funkcji celu.

Z oczywistych względów rozwiązanie tego problemu może interesować firmy transportowe. Równie często problemy tego typu pojawiają się np. podczas optymalizacji produkcji (np. projektowanie ruchu ramienia robota nitującego blachy).

Przykład: Problem pokrycia macierzy.

Dana jest macierz A={aik} o wartościach 0 lub 1. Znaleźć taki najmniejszy zbiór kolumn B, że w każdym i-tym wierszu macierzy A można wskazać wartość aik=1 taką, że kolumna k należy do B.

Przestrzeń stanów: wszystkie możliwe pokrycia kolumnowe macierzy A. Wielkość przestrzeni stanów: mniej, niż 2n, gdzie n - liczba kolumn.

Funkcja celu: wielkość zbioru B.

Problem ten pojawia się w sytuacjach, gdy ze zbioru obiektów o różnych cechach chcemy wybrać minimalny podzbiór mający wszystkie wymagane cechy. Np. wśród wielkiej rzeszy dostawców podpisujemy kontrakty z jak najmniejszą ich liczbą, jdnak tak, by każdy potrzebny nam towar był oferowany przynajmniej przez jednego z nich.

Przykład: Problem plecakowy.

Mamy n przedmiotów, każdy o masie mi i wartości wi. Zmieścić w plecaku o ograniczonej pojemności M przedmioty o możliwie największej łącznej wartości.

Przestrzeń stanów: wszystkie możliwe podzbiory przedmiotów. Wielkość przestrzeni stanów: 2n.

Funkcja celu: wartość przedmiotów, które zmieściły się do plecaka (pod warunkiem, że nie przekroczyliśmy ładownści).

Algorytm zachłanny

Zasada ogólna działania: algorytm zachłanny buduje rozwiązanie "po kawałku", na każdym etapie konstruowania odpowiedzi podejmując taką decyzję, by lokalnie dawała ona największe zyski.

Przykład: Problem wyboru zajęć.

Danych jest n zajęć, każde z nich zaczyna się i kończy o ustalonej godzinie. Znaleźć taki podzbiór zajęć, by żadne dwa nie kolidowały ze sobą, a jednocześnie by wybrać ich jak najwięcej.

Algorytm zachłanny: jako pierwsze wybieramy to zajęcie, które kończy się najwcześniej (daje nam ono największe zyski w postaci czasu na nastepne zajęcia). Następnie w kolejnych krokach wybieramy te, które nie kolidują z poprzednio wybranymi i kończą się możliwie najwcześniej.

Algorytm zachłanny daje w tym przypadku zawsze rozwiązanie optymalne.

Przykład: Problem komiwojażera.

W każdym kroku idziemy do najbliższego nieodwiedzonego miasta.

Przykład: Problem pokrycia macierzy.

W każdym kroku wybieramy tę kolumnę, która pokrywa jak najwięcej dotychczas niepokrytych wierszy.

Przykład: Problem plecakowy.

Dodajemy kolejno te przedmioty, które mają największą wartość w przeliczeniu na masę, aż do wyczerpania się pojemności plecaka.

Jak widać na powyższych przykładach, algorytm zachłanny jest strategią bardzo prostą i intuicyjnie zrozumiałą (jedną z pierwszych, jakie przychodzą do głowy w sytuacjach praktycznych). Jest to jednak strategia często nieoptymalna, zachłanny wybór jakiejś ścieżki rozwiązania w danym momencie może nam w przyszłości przynieść więcej strat (w postaci gorszej jakości całego rozwiązania). Strategię zachłanną można porównać do szachisty wykonujacego w każdej sytuacji takie posunięcie, które daje natychmiastową przewagę materialną (i dającego się wciągać w rozmaite pułapki).

Algorytm wspinaczki

Algorytm wspinaczki, w przeciwieństwie do zachłannego, nie buduje rozwiązania po kawałku. Każdy punkt analizowany przez algorytm wspinaczki jest kompletnym (lepszym lub gorszym) rozwiązaniem problemu, które następnie jest lokalnie poprawiane.

Zasada ogólna działania: startujemy z losowego punktu, przeglądamy jego sąsiadów, wybieramy tego sąsiada, który ma największą wartość ("idziemy w górę"), czynności powtarzamy do osiągnięcia maksimum lokalnego.

Algorytm wspinaczki można zapisać następująco:

x0 = Random(X)
do
max=x0
for(x in N(x0))
if(f(x)>f(max)) max=x
end for
if(max=x0) break
x0=max
while(1)

Zbiór N(x) w powyższym algorytmie to zbiór sąsiadów rozwiązania x. Należy podkreślić, że chodzi o sąsiedztwo rozwiązań w przestrzeni stanów - a więc o (zdefiniowane przez nas) podobieństwo kompletnych rozwiązań. Np. w problemie komiwojażera nie należy sąsiedztwa rozwiązań wiązać w jakikolwiek sposób ze wzajemnym sąsiedztwem miast: przestrzeń stanów w tym przypadku składa się z kompletnych ścieżek; ścieżki podobne możemy zdefiniować jako np. różniące się zamianą kolejności dwóch dowolnych miast. Więcej o pojęciu sąsiedztwa w jednym z następnych rozdziałów.

Zalety metody wspinaczki to prosta implementacja i szybkie działanie. Do wad należy nieodporność na maksima lokalne (czyli takie rozwiązania, których nie da się już poprawić przez prostą modyfikację, a jednak nie są globalnie optymalne) i duża zależność wyniku od punktu startu.

Metoda tabu

Przykład działania metody tabuSchemat działania metody tabu: przeglądamy przestrzeń stanów (rozwiązań), przechodząc zawsze do tego sąsiada, dla którego wartość funkcji oceny jest największa (jak w algorytmie wspinaczki), o ile nie znajduje się on na liście punktów zabronionych (tabu). Na liście tej przechowujemy k ostatnio odwiedzonych punktów (np. k=1000).

Różnica między metodą tabu a zwykłym algorytmem wspinaczki polega na tym, że zezwalamy na odwiedzanie sąsiadów o jakości gorszej od aktualnie rozpatrywanej, a więc możemy wyjść z maksimum lokalnego i dalej szukać rozwiązań. Nie mogliśmy tej modyfikacji wprowadzić w zwykłym algorytmie wspinaczki, gdyż wówczas wpadlibyśmy szybko w pętlę (schodząc z optimum lokalnego i od razu do niego wracając). Lista tabu nas przed tym zabezpiecza.

Przeszukiwanie wiązkowe

Zasada ogólna działania: budujemy rozwiązanie krok po kroku (jak w alg. zachłannym), zawsze zapamiętując k najlepszych rozwiązań i od nich startując w krokach następnych. Przeszukiwanie odbywa się więc równolegle, przy czym na każdym etapie bierzemy pod uwagę k rozwiązań (wybranych jako najlepsze spośród wszystkich dotychczasowych ścieżek).

Przykład: problem komiwojażera dla 7 miast (k=3).

  1. Startujemy z losowego miasta.
  2. Znajdujemy k miast najbliższych.
  3. Startując z każdego z nich, liczymy odległości do miast dotąd nieodwiedzonych. Wybieramy k takich, by dotychczasowa długość drogi była minimalna.
  4. Powtarzamy punkt 3., zapamiętując zawsze k najlepszych dróg.
  5. Gdy dojdziemy do ostatniego miasta, wybieramy najkrótszą z k zapamiętanych dróg.
Przeszukiwanie wiązkowe

Przeszukiwanie wiązkowe jest ulepszoną wersją algorytmu zachłannego. Tym razem nie poprzestajemy na rozwiązaniu, które lokalnie wydaje się najlepsze, ale sprawdzamy też kilka mniej obiecujących alternatyw. Ograniczenie w każdym kroku szerokości "wiązki" do k ścieżek zabezpiecza nas przed wykładniczym wzrostem liczby rozwiązań.

Pojęcie sąsiedztwa

Aby korzystać z algorytmu wspinaczki (a także innych, o których będzie jeszcze mowa), powinniśmy na przestrzeni stanów X zdefiniować pojęcie sąsiedztwa: jeśli x jest przykładowym rozwiązaniem (punktem z przestrzeni stanów), to przez N(x) oznaczamy zbiór (skończony) jego "sąsiadów". Taka definicja daje nam całkowitą dowolność w definiowaniu "sąsiadów". W praktyce pojęcie to powinno być związane z konkretnym zadaniem: ponieważ zasadą algorytmu wspinaczki jest stopniowe poprawianie rozwiązań przez niewielkie zmiany, to nasza definicja sąsiedztwa powinna właśnie odpowiadać takim niewielkim zmianom rozwiązania.

Ponadto sąsiedztwo danego rozwiązania nie powinno być zbyt liczne - inaczej pętla sprawdzająca jakość sąsiadów wykonywałaby się zbyt długo. Z drugiej strony, sąsiedztwo powinno tworzyć relację spójną, tzn. między dowolnymi dwoma rozwiązaniami powinno dać się przejść przeskakując z sąsiada na sąsiada. W przeciwnym razie algorytm wspinaczki nie mógłby zbadać całej przestrzeni stanów i mógłby pominąć dobre rozwiązania.

Przykład: X - płaszczyzna. Za "sąsiadów" możemy np. uznać punkty odległe w poziomie lub pionie o 0.01 (jeśli rozwiązywany problem dopuszcza taką dokładność).

Przykład: problem pokrycia wierzchołkowego.
W danym grafie G znaleźć taki najmniejszy zbiór wierzchołków B, że każda krawędź grafu kończy się na jednym z wierzchołków z B.

Przykład sąsiedztwa

Przestrzeń stanów X to zbiór wszystkich potencjalnych pokryć (podzbiorów zbioru wierzchołków). Za dwa pokrycia sąsiednie można uznać takie, które różnią się jednym wierzchołkiem.


Podsumowanie i literatura

Wykład obejmował techniki optymalizacyjne, których działanie oparte jest o jedną z dwóch głównych zasad:

Zasada zachłanna: tworzymy rozwiązanie stopniowo, na każdym kroku wybierając drogę maksymalizującą (lokalnie) funkcję jakości rozwiązania częściowego.

Przeszukiwanie sąsiedztwa: definiujemy strukturę sąsiedztwa (określamy, które kompletne rozwiązania uznamy za sąsiednie, tzn. podobne) i badamy przestrzeń stanów przeskakując od sąsiada do sąsiada.

Zalecana literatura:


Słownik pojęć

Szczegółowe definicje znajdują się w treści wykładu (słowa kluczowe zaznaczone są na czerwono).

algorytm wspinaczki - algorytm poszukujący optymalnego rozwiązania poprzez poszukiwanie lepszych rozwiązań w sąsiedztwie aktualnie rozpatrywanego
algorytm zachłanny - algorytm konstruujacy rozwiązanie z lokalnie najlepszych fragmentów
funkcja celu - optymalizowana funkcja rzeczywista
metoda tabu - rozszerzenie metody wspinaczki o możliwość wychodzenia z maksimów lokalnych
przestrzeń stanów - zbiór wszystkich możliwych rozwiązań zadania, wśród których szukamy najlepszego
przeszukiwanie wiązkowe - rozszerzenie metody zachłannej o możliwość sprawdzania wielu ścieżek rozwiązania
sąsiad - dwa rozwiązania problemu optymalizacyjnego uznajemy za sąsiednie, jeśli (według ustalonych kryteriów) niewiele się różnią
zadanie optymalizacji - zadanie polegające na szukaniu minimum lub maksimum pewnej funkcji


Zadania

5.1. Podać przykład problemu komiwojażera (konkretny graf), dla którego algorytm zachłanny nie znajdzie optymalnej drogi.

5.2. Rozwiązać problem plecakowy za pomocą metody wspinaczki (ustalić pojęcie sąsiedztwa i funkcji celu).


Strona uaktualizowana przez Sinh Hoa Nguyen, 2009