Metoda przeszukiwania tabu
Zaawansowane programowanie
[Fred Glover: Tabu Search  Part I, ORSA Journal on Computing 1
wykład 2: metoda przeszukiwania tabu
(1989) 190 206; Tabu Search  Part II, ORSA Journal on
Computing 2 (1990) 4 32]
Metoda przeszukiwania tabu (ang. tabu search) jest
metaheurystyką realizującą heurystyczną procedurę
przeszukiwania lokalnego, wychodzącą jednak poza
obszar lokalnego optimum
W tym podejściu reguły deterministyczne są preferowane
dr hab. inż. Marta Kasprzak, prof. nadzw. nad probabilistycznymi
Instytut Informatyki, Politechnika Poznańska Metoda przeszukiwania tabu operuje na pojedynczym
rozwiązaniu, które iteracyjnie jest poprawiane pod kątem
optymalizacji funkcji celu
2
Rozwiązanie początkowe Sąsiedztwo
Bieżące rozwiązanie, na którym dokonywane są operacje Każde rozwiązanie x��X przestrzeni rozwiązań (ang. solution
w metodzie, jest  niekoniecznie liniowym  zapisem space) ma przypisane sąsiedztwo (ang. neighborhood) N(x)��X,
rozwiązania problemu. Może to być np. ciąg indeksów którego każdy element x2 ��N(x) jest osiągany z x przez operację
elementów, dwuwymiarowa lista następników elementów, zwaną ruchem (ang. move)
kwadratowa macierz sąsiedztwa grafu, itp. Zazwyczaj im większa
Ruch ma na celu zwykle niedużą zmianę w obrębie rozwiązania.
struktura, tym większe zużycie pamięci i czasu w algorytmie
Może być np. wstawieniem, usunięciem, przesunięciem elementu
Rozwiązanie początkowe, od którego rozpoczynane są rozwiązania, zamianą miejscami pary elementów, itp.
obliczenia, może być losowe, choć zwykle lepszy efekt
X stanowi zazwyczaj zbiór rozwiązań dopuszczalnych (gdy ruchy
uzyskuje się generując je wstępną heurystyką (np. zachłanną)
są ograniczone do dopuszczalnych), ale można stosować wyjątki
W razie stosowania restartów procedury przeszukiwania, kolejne
x1
rozwiązanie  początkowe można wygenerować w oparciu
x2  elementy przestrzeni rozwiązań
x6 x x, xi
o dotychczasowe obserwacje. Przykładowo, można je złożyć
N(x) = {x1, x2, x3, x4, x5, x6}
z najrzadziej używanych dotąd elementów (aby wystartować
x5
x3  ruch
z innego obszaru przestrzeni rozwiązań) albo korzystać
z fragmentów najlepszych (zróżnicowanych) rozwiązań x4
3 4
Sąsiedztwo Sąsiedztwo
Zastosowanie wszystkich zdefiniowanych ruchów w stosunku Zazwyczaj wybierany jest taki ruch, który prowadzi
do bieżącego rozwiązania może zaowocować zbyt dużym do największej poprawy wartości funkcji celu (ew. jej
sąsiedztwem. Przegląd takiego sąsiedztwa wraz z wyliczeniem przybliżenia) lub do najmniejszego pogorszenia jej wartości,
wartości funkcji celu może zająć zbyt wiele czasu gdy poprawa w obrębie sąsiedztwa nie jest możliwa
Sąsiedztwo można ograniczyć do krótszej listy kandydatów Ta zasada dążenia do optimum lokalnego jest elementem
(ang. candidate list), biorąc pod uwagę jedynie najbardziej strategii intensyfikacji w metodzie
obiecujące ruchy
Przykładowo, można wybierać ruchy zapamiętane jako
maksimum globalne
najskuteczniejsze w przeszłości lub ruchy odnoszące się
maksimum lokalne
do najsłabszych fragmentów rozwiązania
Skrócenie obliczeń uzyskuje się także poprzez ewaluację
funkcji oceny prostszej niż funkcja celu dla całego rozwiązania,
np. pewnego jej przybliżenia albo przez oszacowanie względnej
wartości lokalnej zmiany wywołanej przez ruch
5 6
1
Lista tabu Lista tabu
Po osiągnięciu w wyniku serii ruchów lokalnego optimum Listę tabu realizuje się najczęściej jako listę/tablicę typu FIFO
kolejny ruch może spowodować jedynie pogorszenie (ang. first-in-first-out). Zawiera ona wszystkie bieżące atrybuty
bieżącego rozwiązania (chwilowe). Zgodnie z przyjętą zasadą o statusie tabu
wybierany jest ruch skutkujący najmniejszym pogorszeniem
Atrybut najczęściej opisuje ruch (np. wstawienie czy usunięcie
Bardzo łatwo w ten sposób cofnąć się do obszaru już elementu), także fragment rozwiązania
przeszukanego. W konsekwencji można zapętlić poszukiwania
Inną postacią listy tabu jest tablica o liczbie pól równej liczbie
w obrębie stale tego samego obszaru
atrybutów, każde jej pole zawiera wartość równą liczbie iteracji,
Strukturą uniemożliwiającą powrót do ostatnio odwiedzonych przez którą dany atrybut będzie posiadał status tabu. Tablica
punktów przestrzeni rozwiązań jest lista tabu (ang. tabu list). taka zajmuje więcej pamięci niż tradycyjna lista tabu, ale za to
Zamieszczone na niej ostatnio osiągnięte fragmenty umożliwia sprawdzenie statusu atrybutu w stałym czasie
rozwiązania czy ostatnio wykonane ruchy blokują ich
1 2 3 4 5 6 7 8 9 10 11 12
ponowne osiągnięcie/wykonanie przez zadaną liczbę iteracji
3 8 5 9 1 4 5 0 1 6 3 0 0 2 4 0 0 0
Dopuszczalne sąsiedztwo jest teraz zdefiniowane jako
N*(x) = N(x)\T, gdzie T to rozwiązania ze statusem tabu
lista FIFO tablica wszystkich atrybutów
7 8
Lista tabu Lista tabu  przykład
Zbyt krótka lista tabu może spowodować cykliczne powracanie Minimum k-tree problem: poszukiwanie w grafie
do już wygenerowanych rozwiązań. Zbyt długa może nieskierowanym drzewa złożonego z k krawędzi takiego,
zablokować zbyt wiele ruchów że suma wag tych krawędzi jest minimalna
W ogólności krótkie listy tabu skutkują przeszukiwaniem Ruch zdefiniowany jest jako równoczesne wstawienie do
okolicy lokalnego optimum, długie umożliwiają wyjście poza rozwiązania jednej krawędzi i usunięcie innej
tę okolicę. Długość listy można zmieniać w trakcie działania
v1
Można przykładowo nadać status tabu
algorytmu w zależności od przyjętej w danej chwili strategii
na tę samą liczbę iteracji obu operacjom:
v6 v2
intensyfikacji czy dywersyfikacji
dla krawędzi wstawianej będzie to zakaz
Długość listy tabu jest często stała w trakcie działania algorytmu. usuwania, dla usuwanej  wstawiania
v5
v3
Długość najwłaściwszą dla danego problemu i danego rozmiaru
Ponieważ jednak krawędzi w grafie mamy
v4
instancji można w pewnym stopniu oszacować teoretycznie,
zazwyczaj dużo więcej niż k, warto rozważyć
lecz zazwyczaj na jej dobór wpływa seria wstępnych testów
implementację dłuższej listy tabu dla k=4
Może być więcej niż jedna lista tabu w algorytmie, wtedy krawędzi usuwanych niż wstawianych wagi: 1, 2, 3
pamiętają one różnego rodzaju atrybuty
9 10
Kryterium aspiracji Kryterium aspiracji
Wybierany ruch (lub jego konsekwencje) nie powinien Przykłady kryterium aspiracji cd.:
zawierać atrybutów znajdujących się na liście tabu.
�%
gdy jesteśmy na etapie wychodzenia z obszaru lokalnego
Nie zawsze jednak można lub należy zachować
optimum, statusu tabu można pozbawić ruch o znaczącym
tę prawidłowość. Zasadę pozwalającą pominąć status tabu
wpływie na postać bieżącego rozwiązania, powodujący skok
nazywa się kryterium aspiracji (ang. aspiration criterion)
w odległy punkt przestrzeni rozwiązań
Przykłady kryterium aspiracji:
�%
można także usunąć status tabu z ruchu o małym wpływie
�%
ruch ze statusem tabu może być wybrany, gdy prowadzi
na postać rozwiązania, jeśli od czasu umieszczenia go
do poprawy najlepszego rozwiązania (najlepszej wartości
(lub jego atrybutów) na liście tabu wykonany został skok
funkcji celu) otrzymanego do tej pory
do innego obszaru przestrzeni rozwiązań
�%
gdy w pewnym momencie obliczeń sąsiedztwo danego
�%
gdy w trakcie stałego poprawiania jakości rozwiązania
rozwiązania okaże się zbyt małe, lub lista tabu zbyt długa,
pewien ruch otrzyma status tabu i póz
niejsze jego wykonanie
wszystkie możliwe ruchy będą miały przydzielony status
nie zakłóci tendencji wzrostu, to można go wykonać, gdyż
tabu; wykonuje się wtedy ruch z początku listy, tzn.
nie spowoduje powrotu do ostatnio otrzymanych rozwiązań
o najmniejszym okresie oczekiwania na opuszczenie listy
11 12
2
Dywersyfikacja rozwiązań Podział pamięci ze względu na czas
Strategia dywersyfikacji realizowana jest poprzez czynności Pamięć krótkotrwała (ang. short-term memory) służy
mające na celu skok do innego obszaru przestrzeni rozwiązań zapamiętywaniu ostatnio wykonanych ruchów czy atrybutów
rozwiązań w celu uniknięcia odwrócenia ruchu oraz
Elementem tej strategii może być długa lista tabu,
wpadnięcia w cykle ruchów
wyprowadzająca poszukiwanie poza dotychczasowy obszar
Pamięć długotrwała (ang. long-term memory) służy
Można dopuścić wykonanie co jakiś czas ruchów bardziej
zapamiętywaniu ruchów/rozwiązań w dłuższym okresie
wpływających na postać rozwiązania niż standardowe.
czasu, w celu wynagradzania ruchów najlepszych bądz

Dopuszcza się w tej metodzie elementy losowości
wykonywanych rzadko, albo karania ruchów najgorszych
Innym sposobem mogą być restarty procedury poszukiwania,
bądz
występujących często (lub fragmentów rozwiązań
czyli rozpoczynanie całego procesu od nowego rozwiązania
zamiast ruchów). Pamięć może gromadzić informacje
początkowego, zlokalizowanego w innej części przestrzeni
przez cały czas obliczeń algorytmu albo pomiędzy restartami,
rozwiązań. Często pamięć i zmienne są wtedy zerowane
może być o stałej długości (FIFO) lub obejmować wszystkie
Do dywersyfikacji można wykorzystać także niektóre
zdarzenia w zadanym przedziale czasu
z rodzajów pamięci zdefiniowanych w metaheurystyce
13 14
Podział pamięci ze względu na zawartość Podział pamięci ze względu na funkcję
Lista tabu jest rodzajem pamięci określającej (ang. attributive Recency-based memory  pamięć gromadząca informacje
memory), tzn. zapamiętuje informacje o atrybutach/cechach o ostatnio wykorzystanych atrybutach, np. lista tabu
ruchów prowadzących do rozwiązania
Frequency-based memory  pamięć oparta na częstości
Drugim typem pamięci w metaheurystyce jest pamięć wykorzystania atrybutów, może korzystać z miar:
bezpośrednia (ang. explicit memory), pamiętająca kompletne
�%
transition measure  liczba iteracji, w których dany
rozwiązania, zazwyczaj najlepsze dotychczas odwiedzone
atrybut został użyty do wykonania ruchu, czyli wpłynął
Pamięć bezpośrednia może także zapamiętywać atrakcyjnych,
na postać rozwiązania
lecz nieodwiedzonych dotąd sąsiadów najlepszych rozwiązań
�%
residence measure  liczba iteracji, podczas których
(do intensyfikacji poszukiwań). Może służyć unikaniu
atrybut należał do rozwiązania; wysoka wartość residence
odwiedzania rozwiązań więcej niż raz, osiąga jednak wtedy
measure może świadczyć o atrakcyjności atrybutu,
duże rozmiary
gdy otrzymujemy rozwiązania wysokiej jakości, lub wręcz
przeciwnie, gdy rozwiązania są słabe
15 16
Podział pamięci ze względu na funkcję Pamięć a strategie  przykłady użycia
Quality-based memory  pamięć oparta na jakości, używana Frequency-based memory można użyć w strategii
do zidentyfikowania elementów wspólnych dla dobrych dywersyfikacji, np. przy restarcie procesu obliczeniowego,
rozwiązań lub ścieżek prowadzących do dobrych rozwiązań. do złożenia nowego rozwiązania z najrzadziej używanych
Na jej podstawie preferuje się czynności skutkujące dobrymi dotąd elementów. Można też, w trakcie procesu
rozwiązaniami albo obarcza karami czynności prowadzące obliczeniowego, w mniejszym stopniu wpłynąć na postać
do słabych rozwiązań rozwiązania poprzez wykorzystanie w części rzadko
używanych atrybutów
Influence-based memory  uogólnienie quality-based
memory; zapamiętuje wpływ dokonanych wyborów Quality-based memory można użyć w strategii intensyfikacji,
na rozwiązania, nie tylko pod względem wartości funkcji celu, np. składając nowe rozwiązania z fragmentów dobrych
lecz także struktury rozwiązania. Pamięć ta może wspomagać rozwiązań. Aby wpłynąć na postać rozwiązania w mniejszym
np. badanie dopuszczalności generowanych rozwiązań zakresie, można wybierać pojedyncze ruchy prowadzące
czy ich regionalności (gdy chcemy skoczyć w inny obszar w przeszłości do dobrych rozwiązań
przestrzeni rozwiązań)
17 18
3
Ogólny schemat metody tabu search Metoda przeszukiwania tabu  parametry
Parametrami tej metaheurystyki umożliwiającymi dostosowanie
wygenerowanie rozwiązania początkowego
jej do indywidualnych potrzeb są:
zainicjalizowanie struktur pamięci
�%
długość listy tabu
�%
rozmiar innych rodzajów pamięci używanych w algorytmie
przegląd sąsiedztwa bieżącego rozwiązania
wybór najlepszego sąsiada
�%
liczba iteracji; można przyjąć z góry zadaną liczbę iteracji
albo np. liczbę iteracji bez poprawy funkcji celu; często
tak
definiowane są dwie lub więcej wartości składające się
aktualizacja najlepszego rozwiązania
warunek
aktualizacja struktur pamięci na liczbę iteracji, np. liczba kroków intensyfikacji, następująca
stopu
po nich liczba kroków dywersyfikacji, liczba takich cykli
i liczba restartów
ew. dywersyfikacja rozwiązania, także restart nie
ew. inna modyfikacja procesu podstawowego
�%
inne
19 20
Metoda przeszukiwania tabu a losowość Literatura  cd.
Metaheurystyka tabu search dopuszcza losowość, przy czym Fred Glover, Manuel Laguna, Tabu Search, Kluwer Academic
autor metody sugeruje minimalne jej użycie. Prawie zawsze Publishers, Boston, 1997.
zastosowanie przemyślanej strategii deterministycznej
http://spot.colorado.edu/~glover/
prowadzi do lepszych wyników niż zastosowanie losowości
Nawet słaba deterministyczna strategia daje więcej informacji
niż losowa, gdyż jest skonstruowana z uwzględnieniem cech
danego problemu w celu poprawienia jakości rozwiązania
(czego nie można powiedzieć o wyborach losowych).
Słabą zasadę wyboru deterministycznego można poprawić
na podstawie uzyskiwanych wyników
Wybory deterministyczne są preferowane w tabu search także
ze względu na pojedyncze rozwiązanie, na którym operujemy.
Losowe wybory lepiej sprawdzają się, gdy mamy
do dyspozycji dużo więcej  materiału eksperymentalnego
21 22
4