WYKŁAD 06

Ostatnio - metaalgorytm wyżarzania.

TABU SEARCH

Metoda ta pojawiła się w roku '76. W '97 napisano artykuł podsumuwujący tę metodę.

Banalna jest ta metoda, ale trudność polega w dodawaniu pewnych dodatków do tej metody, aby
działała metoda lepiej. Oraz trudnosc metody implementacyjnej. Dużo czasu potrzeba na jej
obliczanie.

Rozwiązanie S inicjalizujemy rozwiązaniem (np losowe).
<wzór 1>

S - najlepsze rozwiązanie w sąsiedztwie. To jest algorytm poszukiwań.

W symulowanym wyż tę rolę powierzyliśmy losowości. Nasz algorytm potrafił opuścić minimum
lokalne. Tutaj algorytm zapamiętuje wszystko co robił po drodze. Lista tabu - pozwala na
zapamiętanie drogi, którą przeszedł algorytm.

Jeżeli jakiś rozwiazanie zostało wybrane jako najlepsze, to nie chcemy, aby w kolejnym kroku
przejsziemy do poprzedniego rozwiązania, czyli cofać się i tworzyć cykle.

do while (stop conditions){
s' <- Best (N(s));
T +-s;
s = s';
}

musimy weykorzystać to, że mamy zapisane już poprzednie rozwiazania. Aby zabronić powrotów
do odwiedzonych już rozwiązań robimy tak:

do while (stop conditions){
s' <- Best (N(s)\T); //!!!!!!
T +-s;
s = s';
}

Zbiór rozwiązań minus lista Tabu.

Jak ma wyglądać taka lista? Nieskończonej długości. Dzięki temu gwarancja, że w końcu znajdzie
się takie rozwiązanie, które będzie optymalne. Ale to niemożliwe.

Przy wyborze najlepszego z sąsiedztwa musimy odfiltrować sąsiedztwo i sprawdzić co z sąsiedztwa
nie znajduje się już w liście. Lista zatem będzie ograniczonej wielkości.

Załóżmy, że rozmiar listy tabu to l:

|T| = l;

Nie będą [powstawały cykle o długości mniejszej niż l.

<rysunek 2>

Nasz algorytm będzie się w taki sposób kręcił. Jakie musi zatem być to l? Jeśli lista będzie mała, to
jest to intensyfikacja poszukiwać - przestrzeń przeszukiwana w wąskim gronie. Jaki lista będzie
długa, to z jakiegoś obszaru zostanie przejrzana lista.
Można zatem dynamicznie zmieniać długość l podczas działąnia algorytmu.
l np od 10 do 100. Jak algorytm wpadnie w cykl, to trochę się pokręci, a jak zwiększymy o 1 cykl,
to kiedyś zrobi się z tego cykl.
Inna metoda: napisać detektor cykli - coś co śledzi wartości wcześniejszej i na podst analizy
statystycznej dowiadujemy sie, że moze występować cykl. (Książka, Eugeniusz Nowicki jakiś).
Wady: musimy poradzić sobie z kosztem przeglądu sąsiedztwa i filtrowanie. Druga to warunki
stopu. Czas działania algorytmu. Może być, że przez 1000 iteracji nie znależliśmy poprawy
rozwiazania. Mamy więc przesłankę do skończenia poszukiwań. Bo może wystartowaliśmy ze
złego miejsca poszukiwań. Byćmoże warto rozpocząć działanie programu od nowa.
Kiedy może sie zatrzymać algorytm? Sytuacja: wszystkie ruchy z otoczenia są zabronione. Co
zrobić? Wyczyścić listę tabu. To radykalne, ale możena robić to tak:

Mamy listę jakąś z zabronionymi rozwiazaniami. Jeśli wszystkie rozwiązania są zabronione, to
usuwamy najstarszy wpis. Jeżeli jakikolwiek się odblokuje, to działamy dalej. To może nas
doprowadzić do tego, że wyczyścimy całą listę tabu, ale cóż...

Zajmijmy się sąsiedztwem. Czy te rozwiązania nie mają statusu zabronionych opcji. To co sie
wprowadza, to nie zapamiętujemy rozwiazań odwiedzonych, lecz cechy charakteryzujące
rozwiązania. Najprościej: wartość funkcji celu dla odwiedzonych już rozwiazań. Jeżeli się
zastanowimy: efektywność jest doskonała, o(1), ale tracimy informację. Być może zabraniamy
może nawet całego dużego obszaru rozwiązań przejrzeć. Pytanie: czy to dobre podejście? To zależy.
Czasami nic lepszego nie da się znaleźć, czasami tak, że gorzej się nie da.
Pokażemy jak to zrobić gdy wartość f. celu jest liczbą całkowitą.
Załóżmy, ze na liście tabu przechuwemy pełne rozwiązania. Pojawił sie pomysł, żeby jako listę tabu
nie rozbić listy, tabeli itd, tylko asocjacyjną sieć neuronową. Nieważne, odpuścimy sobie to.
Zastosujemy:

FILTRY BLOOM'A

Załóżmy, ze mamy rzwiazanie jakieś. Funkcja haszująca:

H s -> D (dziedzina D)

Możemy wyobrazić, żze D jest indeksem do tablicy haszującej, do której doczepiamy s.

H s - > [0;D]
H(s) = k

Jak funkcja zwróciła indeks, to dolinkowujemy s.
Potraktujemy to jako indeks i pod indeksem k piszemy 1.

<rys 3>

Jeżeli 1, tzn, że funkcja jest zabroniona.

Minus: jeżeli zapiszemy 1, to istaniejue wiele rozwiązań, które po wyliczeniu funkcji haszującej też

trafią do jedynki. Wiec wymyślono filtr blooma,.

Mamy zestaw n funkcji haszujących

Hm(s) = km

Wszystkie pola z funkcji haszującej otrzymują 1.

Na necie można wzorki różne poznajdywać.

Można się też pokusić o zrobienie nieskończonej listy tabu.
Jeżeli dopisujemy jakieś rozwiązanie, wyznaczamy funkcji i indeksy, zamiast 1 wpisujemy +1 i
rozwiązanie s dopisujemy do listy:

s1 - s2 - s3 - s4

Znajdujemy nowe rozwiązanie minimalne, stare mamy dopisać do listy tabu. Nasza lista jest
zajęta,więc usuwamy najstarsze i dopisujemy s' i usunięcie powoduje usunięcie z niektórych miejsc
listy haszującej. wpisujemy wówczas zamiast +1 - -1

[s1 ]- s2 - s3 - s4 - s5

Wszystko da sie zrobić w o(1)

Zabranianie rozwiązań o wartości funkcji celu która już była: tak jak to robimliśmy w
programowaniu dynamicznym. Wektor od zera do D max. Jak zabraniamy dla indeksu 10, to przy
tym indeksie wpisujemy jedynkę

<rysunek 4>

Każda z czynności to o(1)

Mamy algorytm, który jest zaawansowany. Można wprowadzić tam pamięć długoterminową. Nasz
algorytm nie jest w stanie nic lepszego wymyślić, więc może warto od nowa uruchomić algorytm
Ale tracimy poprzednie rozwiązania. Więc warto wprowadzić rozwiązania elitarne. Np lista o dł. 3 -
4 . Tam w sposób FIFO przechowujemy rozw. elitarne. Jak kiedyś stwierdzimy, że nasz algorytm
nic nie wymyśli lepszego, to wracamy do jednego z rozwiązań elitarnych. Ale sam powrót moze
być za mało. Jest szansa, jeżeli tam ta ścieżka ma cykle, to znowu później pójdziemy tam, gdzie
byliśmy. Więc może zapamiętać dodatkowo ruch, jaki został wykonany z rozwiązania elitarnego.
Podczas restartu z tego miejsca zabraniamy dodatkowo wykonywania tego zapisanego i
sorawdzonego już wcześniej ruchu.

Parametry można użyć, które nie opisują rozwiazania, ale ruch, który spowodował dojście do
rozwiązania. Możemy zapisywać, np:

<rys 5>

Można zapisać, aby zabronić aby wykonywać ruchy,w których k będzie na pozycji lub przed
pozycją p.

Zabraniamy dokładnie tych trzech:

<rys 6>

Jeżeli jakkolwiek potrafimy stworzyć parametry opisujące ruch, to sami możemy stworzyć jakąś
regułę zabraniającą ruchów, które mamy zapisane na liście tabu.

Czas zająć się sąsiedztwem.

Best (N(s)\T)

Ale to nie musi być najlepsza wartość! Nie zawsze liczy sie wartość, bo istanieje wiele rozewiązać
o takiej wartości, bo może być ich wiele. Należy patrzyć na cechy rozwiazania, bo może to pomóc
w dalszym działaniu algorytmu tabu search.
------------------------
Aby algorytm znalazł dobre rozwiązanie, potrzeba wiele iterracji.

Zacznijmy od kontynuowania sąsiedztw dla problemu komiwojażera.

Najprostszy ruch: mamy permutację i przestawiamy miasto na inną pozycję.
<rysunek 1> Będzie 6 permutacji - zawsze o(1).

Popatrzmy na jakieś rozwiazanie z cyklem. Dobry ruch:

Losujemy 2 pozycje. Usuwamy dwie następujące po sobie i łączymy:

<rys 2>

To działa w komiwożerze.

PRzechodzimy do rozwiązania problemu przepływaowego.

Fm||Cmax

Flow system przepływowy, brak parametrów.

Mamy maszynę produkcyjną:

<rys 3>

Zadanie wchodzi na linię, przechodzi przez wszystkie maszyny, opuszcza linię i jest zrealizowane.

Potok procesora działa tak samo. Wykres:

<rys 4>

Wiemy, że rozwiązanie w naszym problemie to permutacja. Więc wstawiamy po prostu z jednego
na drugie miejsce element permutacji.
Jak wyznaczyć Cmax mając permutacje?

Tworzymy graf

<rys 5>

Każda kolumna to zadanie, a wiersze to etapy wykonywania zadania ze względu na realizację
zadania. Nanosimy zależności w kolejnoścy wykonywania zadań.
Zadanie 2 na maszynie 1 może się zacząć wykonywać tylo gdy poprzednie się skończy.
Załóżmy, ze każdy wierzchołek będzie przechowywał informację c i j.

Moment wykonywania zadania i na maszynie j.Czy wartość potrafimy szybko wyliczyć? tak. Bo 1
zadanie na początku może się zacząć wykonywać w czasie zero.

Zasada rekurencyjna: Wartość Ci,j max wartości plus czas wykonywania zadania i,j. Mamy
maszynę dynamiczną. Czas wyznaczenia Cmax to O(n*m).jeżeli dla nas wykonaniae ruchu to w
permutacji usunięcie jakiegoś zadania i przestawienie go, to znalezienie nowej wartości funkcji
celu to stworzenie takiego grafu i wyznaczenia wartości funkcji. Kazðe zadanie mozna wstawić na
n innych pozycji, więc O(n^3 * m). Więc taka złożoność iteracji w Tabu Search, a to wymaga
czasu.
Jak to zrobić szybciej?

Dygresja - pełny rozmiar otoczenia to n^2, bo każde z zadań można na inną pozycję przestawić.
Koszt wynaczenie celu to n*m. Przyspieszenie to zmniejszenie rozmiaru sąsiedztwa. Pozdbiór
większego sąsiedztwa. Wybrać jedno z tych zadań i powedzieć, że sąsiedztwo to wszytskie możliwe
przestawienia tego zadania. Jak dobrze to zrobimy, to sporo czsu oszczędzamy. Książka prof
Smutnickiego. Nie jest gruba, ale szybkość czytania to strona na godzinę.
Jak algortym znajdzie rozwiązanie to należy pamiętać skąd była brana wartość. Np że do danego
węzła przeszliśmy z jakiegoś poprzedniego węzła. Mamy do dyspozycji wyznaczoną ścieżkę
krytyczną. Długość ścieżki to suma WAG należy pamiętać.

To co bedziemy mówić, to technika stosowana dla wyznaczania f celu dla sąsiedztwa. Jak będziemy
generować rozw ze zbioru i wyznaczać funkcję celu to liczniść sąsiedztwa*n*m.
Możemy jednak wykorzystać strukturę generowania otoczenia, aby wykonywać niektóre rzeczy
inkrementacyjnie. Załóżmy, ze wybnraliśmy jedno zadanie, które przerzucamy na inne pozycje. Z
grafu wywalamy jedną kolumnę i wyznaczamy ścieżkę krytyczną grafu bez jednego zadania.
Problem sprowadza się, że to jedno zadanie musimy na dole wstawić na poszczególne pozycje.
Przestawienbie kolumny to dodanie ze strony lewej do prawej. Te operacje mozna zrobić w czsie
o(1).

Stosuje się prawie zawsze taką technikę
Jak będzie wyglądała ścieżka krytyczna jak przestawimy zwroty krawędzi w drugą stronę. Jak ta
ścieżka będzie wygolądać? Tak samo, bo jeżeli by to nie była ta ścieżka to... ble ble ble.

Załóżmy, że przecinamy graf:

<rys 6>

NAjdłuższa droga z wierzchołka 1 do 2 zawierająca krawędź da sie obiczyć w czasie o(1).

Ścieżka krytyczna musi zawierać jedną z krawędzi z przecięcia.
Wyznaczenie dł ścieżki krytycznej to O(m). bo na przecięciu jest m krawędzi, tyle co maszyn. JAk
dodać nową teraz kolumnę?

Mamy graf, wybieramy miejsce gdzie wstawiamy brakującą kolumnę:

<rys 7>

X - w tym miejscu dla różnych rozstawień połączenia liczymy wartość funkcji i liczymy dla
każdego przypadku.

Pojedyncze wstawienie kolumny to O(m*n). Więc lepiej niż na początku.

JEżeli ktoś zaczyna pisać to , to pisze się normalnie to. Potem optymalizacja gdy wiemy, że jest
dobrze. I przy takich na przykład dodatkatkach algorytm potrafi przyśpieszyc nawet kilka tysięcy
razy!