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

Przeszukiwanie tabu — metaheurystyka przeszukiwania lokalnego

Autor metody
Fred Glover
Rok
1989
Typ
Local-search metaheuristic

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Przeszukiwanie tabu (Tabu Search) to metaheurystyka przeszukiwania lokalnego wprowadzona przez Freda Glovera w 1989 roku, która wykorzystuje listę tabu — krótkoterminową pamięć niedawno odwiedzonych rozwiązań — do zapobiegania cyklom i ucieczki z lokalnych minimów.

Poprzez jawne zakazywanie ruchów odwracających ostatnie decyzje, algorytm szerzej eksploruje przestrzeń poszukiwań i, dzięki strukturom pamięci długoterminowej, takim jak kryteria aspiracji, dąży do zbliżenia się do globalnego optimum nawet w dużych, złożonych problemach kombinatorycznych.

Intuicja stojąca za metodą

Wyobraź sobie nawigowanie po górzystym terenie w ciemności, próbując znaleźć najwyższy szczyt. Prosty algorytm wspinaczki lokalnej zawsze idzie pod górę i utyka na najbliższym wzniesieniu, do którego dotrze. Przeszukiwanie tabu nosi ze sobą notatnik niedawno odwiedzonych miejsc i odmawia powrotu do nich, nawet jeśli cofanie się wydaje kuszące. Ta wymuszona amnezja dotycząca ostatnich ruchów zmusza poszukiwania do wyjścia z pułapek i wkroczenia na niezbadany teren, pozwalając ostatecznie odkryć znacznie wyższe rejony niż zwykłe przeszukiwanie lokalne.

Historia

Przeszukiwanie tabu zostało wprowadzone przez Freda Glovera w przełomowym artykule z 1989 roku w ORSA Journal on Computing, gdzie zostało przedstawione jako strategia kierowania przeszukiwaniem lokalnym poprzez wykorzystanie pamięci o przeszłych ruchach. Podstawowe idee zostały skonsolidowane i rozwinięte w monografii Glovera i Laguny z 1997 roku wydanej przez Springer, która ustanowiła kanoniczną krótkoterminową listę tabu, kryteria aspiracji oraz długoterminowe strategie dywersyfikacji i intensyfikacji, które pozostają kluczowe dla tej metody do dziś. Od momentu wprowadzenia przeszukiwanie tabu było szeroko stosowane w badaniach operacyjnych, harmonogramowaniu, logistyce i projektowaniu kombinatorycznym, i nadal pozostaje standardową metaheurystyką porównawczą obok wyżarzania symulowanego i algorytmów genetycznych.

Kiedy stosować

Przeszukiwanie tabu jest dobrze dopasowane do problemów optymalizacji kombinatorycznej i dyskretnej, gdzie przestrzeń rozwiązań jest zbyt duża dla metod dokładnych, a struktura problemu pozwala na zdefiniowanie znaczącego sąsiedztwa. Typowe zastosowania obejmują problemy harmonogramowania, trasowania, przypisywania i sekwencjonowania. Jest szczególnie skuteczne, gdy krajobraz poszukiwań ma wiele lokalnych minimów, które pułapkują prostsze metody. Nie wymaga, aby funkcja celu była różniczkowalna lub ciągła. Definicja sąsiedztwa i czas trwania tabu muszą być starannie dostosowane do konkretnego problemu; źle dobrane sąsiedztwo lub zbyt krótki lub zbyt długi czas trwania mogą znacząco obniżyć wydajność. Potrzeba co najmniej kilkuset — a najlepiej ponad tysiąca — iteracji, aby poszukiwania odpowiednio zbadały przestrzeń.

Ograniczenia i uwagi

  • Wydajność jest wrażliwa na definicję sąsiedztwa i czas trwania tabu; złe wybory mogą uwięzić poszukiwania lub spowodować cykliczność pomimo mechanizmu tabu.
  • Wymaga minimalnego budżetu iteracji — zazwyczaj ponad 1000 iteracji — aby wystarczająco zbadać sąsiedztwo; przy zbyt małej liczbie iteracji wyniki nie są lepsze niż proste przeszukiwanie lokalne.
  • Lista tabu przechowuje atrybuty ruchów, a nie pełne rozwiązania, dlatego kryterium aspiracji jest potrzebne, aby zapobiec przypadkowemu blokowaniu naprawdę dobrych ruchów.
  • W przeciwieństwie do dokładnych solverów, przeszukiwanie tabu nie oferuje gwarancji optymalności, a jakość wyniku może się różnić w zależności od uruchomienia, jeśli rozwiązanie początkowe lub sąsiedztwo są stochastyczne.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Ucieka z lokalnych minimów za pomocą mechanizmu tabu bez potrzeby informacji o gradiencie.
  • Ma zastosowanie do problemów kombinatorycznych, mieszanych, a nawet ciągłych — nie zakłada normalności ani żadnych właściwości rozkładu.
  • Zawiera pamięć na wielu skalach czasowych (krótkoterminowa lista tabu, długoterminowa dywersyfikacja/intensyfikacja), umożliwiając zasadniczą eksplorację przestrzeni poszukiwań.
  • Często znajduje wysokiej jakości rozwiązania przy stosunkowo umiarkowanych budżetach obliczeniowych w porównaniu z metodami dokładnymi na dużych instancjach.

Zastosowania

  • Harmonogramowanie produkcji typu job-shop i flow-shop — optymalizacja sekwencji operacji w celu minimalizacji czasu wykonania lub opóźnienia.
  • Trasowanie pojazdów — znajdowanie efektywnych tras dostaw z uwzględnieniem ograniczeń pojemności i okien czasowych.
  • Przypisywanie i lokalizacja obiektów — przypisywanie zadań do zasobów lub lokalizowanie obiektów w celu minimalizacji kosztów.
  • Kolorowanie grafów, projektowanie sieci i telekomunikacja — rozwiązywanie dyskretnych problemów optymalizacji strukturalnej.
  • Selekcja cech i wyszukiwanie hiperparametrów — eksploracja dyskretnych przestrzeni konfiguracji w potokach uczenia maszynowego.

Jak to działa

Jak to działa

1

Poszukiwania rozpoczynają się od początkowego kandydata na rozwiązanie, który może być skonstruowany losowo lub za pomocą heurystyki zachłannej. Lista tabu jest inicjalizowana jako pusta kolejka o stałej długości, a najlepsze dotychczas znalezione rozwiązanie jest zapisywane. Struktura sąsiedztwa — reguła definiująca, które rozwiązania są o krok od bieżącego rozwiązania — musi być zdefiniowana w sposób znaczący dla konkretnego problemu.

2

Z bieżącego rozwiązania generowane i oceniane są wszystkie ruchy w zdefiniowanym sąsiedztwie względem funkcji celu. Każdy ruch odpowiada niewielkiej perturbacji, takiej jak zamiana dwóch elementów w sekwencji lub odwrócenie zmiennej binarnej. Sąsiedztwo musi być wystarczająco bogate, aby umożliwić znaczącą eksplorację, ale jednocześnie na tyle małe, aby było możliwe do przetworzenia w każdej iteracji.

3

Każdy ruch kandydujący jest testowany względem listy tabu. Jeśli ruch — lub jego charakteryzujący atrybut — znajduje się na liście, jest klasyfikowany jako tabu i jest zabroniony, chyba że spełnia kryterium aspiracji: zazwyczaj, jeśli wynikowe rozwiązanie byłoby lepsze niż najlepsze dotychczas znalezione rozwiązanie, status tabu jest uchylany, a ruch jest dozwolony. Ten mechanizm aspiracji daje algorytmowi elastyczność bez porzucania dyscypliny antycyklicznej.

4

Spośród wszystkich ruchów niebędących tabu (oraz wszelkich ruchów tabu spełniających kryterium aspiracji), wybierany i wykonywany jest ruch o najlepszej wydajności, nawet jeśli pogarsza wartość celu. Ta gotowość do akceptacji pogorszenia umożliwia algorytmowi ucieczkę z lokalnych minimów, co jest cechą wyróżniającą przeszukiwanie tabu w porównaniu z prostym wspinaniem się po wzgórzu.

5

Po wykonaniu ruchu lista tabu jest aktualizowana poprzez dodanie odwrotności wykonanego ruchu (lub jego charakteryzującego atrybutu), a najstarszy wpis jest usuwany, jeśli lista jest pełna, zachowując jej stałą długość — czas trwania tabu. Jeśli nowe rozwiązanie jest lepsze od najlepszego zapisanego rozwiązania, najlepsze rozwiązanie jest aktualizowane. Opcjonalne struktury pamięci długoterminowej mogą śledzić częstotliwość lub aktualność rozwiązań, aby kierować dywersyfikacją w mniej odwiedzane regiony lub intensyfikacją wokół obiecujących.

6

Algorytm kontynuuje iteracje do momentu spełnienia kryterium zatrzymania: maksymalnej liczby iteracji, docelowej wartości celu lub ustalonej liczby iteracji bez poprawy. Jako wynik zwracane jest najlepsze rozwiązanie znalezione podczas całego poszukiwania. Wybór odpowiedniego budżetu iteracji jest kluczowy — zbyt mało iteracji uniemożliwia wystarczającą eksplorację sąsiedztwa.

Częste pułapki

  • Ustawienie zbyt krótkiego czasu trwania tabu pozwala na powrót cykliczności, niwecząc cel mechanizmu tabu; czas trwania powinien być dostosowany do rozmiaru problemu.
  • Ustawienie zbyt długiego czasu trwania nadmiernie ogranicza poszukiwania i uniemożliwia algorytmowi ponowne odwiedzanie regionów, które mogą zawierać ulepszenia.
  • Uruchomienie mniej niż około 1000 iteracji oznacza, że poszukiwania nie zbadały wystarczająco sąsiedztwa — jeśli zasoby obliczeniowe są ograniczone, należy wrócić do wyżarzania symulowanego, które może szybciej dać użyteczne wyniki przy mniejszej liczbie iteracji.
  • Użycie zbyt wąskiego sąsiedztwa (np. tylko pojedynczych zamian w złożonej strukturze) prowadzi do płytkich poszukiwań; należy upewnić się, że sąsiedztwo jest wystarczająco bogate, aby połączyć wszystkie obiecujące regiony przestrzeni rozwiązań.
  • Zignorowanie kryterium aspiracji może trwale zablokować ścieżkę do globalnego optimum, jeśli ten ruch przypadkiem jest tabu; zawsze należy zaimplementować przynajmniej standardowe uchylenie blokady dla najlepszego rozwiązania.

Najczęściej zadawane pytania

Czym przeszukiwanie tabu różni się od wyżarzania symulowanego?

Obie metody akceptują pogarszające ruchy w celu ucieczki z lokalnych minimów, ale różnią się mechanizmem. Wyżarzanie symulowane akceptuje gorsze ruchy probabilistycznie, kierowane przez parametr temperatury chłodzenia. Przeszukiwanie tabu akceptuje najlepszy dostępny ruch niebędący tabu deterministycznie, kierowane przez jawną pamięć o ostatnich ruchach. Przeszukiwanie tabu jest zazwyczaj bardziej efektywne w problemach kombinatorycznych o ustrukturyzowanej przestrzeni; wyżarzanie symulowane może być łatwiejsze do dostrojenia w problemach z krajobrazami ciągłymi lub prawie ciągłymi i jest preferowane, gdy budżet iteracji jest mały (poniżej około 1000 iteracji).

Jak długa powinna być lista tabu?

Czas trwania tabu — liczba iteracji, przez którą ruch pozostaje zabroniony — zależy od problemu. Powszechnie cytowanym punktem wyjścia jest czas trwania proporcjonalny do pierwiastka kwadratowego z rozmiaru problemu, ale powinien on być dostrojony empirycznie. Zbyt krótki czas trwania pozwala na cykliczność; zbyt długi czas trwania nadmiernie ogranicza poszukiwania. Adaptacyjne lub losowe strategie czasu trwania mogą zmniejszyć wrażliwość na ten wybór.

Czy przeszukiwanie tabu gwarantuje znalezienie globalnego optimum?

Nie. Przeszukiwanie tabu jest metaheurystyką i nie daje gwarancji optymalności. Ma na celu efektywne znalezienie wysokiej jakości rozwiązań, ale wynik zależy od struktury sąsiedztwa, czasu trwania tabu, liczby iteracji i rozwiązania początkowego. Aby uzyskać gwarancję optymalności, wymagana jest metoda dokładna, taka jak programowanie całkowitoliczbowe, chociaż metody dokładne mogą być niewykonalne obliczeniowo dla dużych instancji.

Czym jest kryterium aspiracji i dlaczego jest konieczne?

Kryterium aspiracji to reguła, która uchyla status tabu ruchu w szczególnych warunkach. Najczęstszym kryterium jest: jeśli wykonanie ruchu tabu doprowadziłoby do rozwiązania lepszego niż najlepsze dotychczas znalezione rozwiązanie, ograniczenie tabu jest znoszone, a ruch jest dozwolony. Bez tego uchylenia mechanizm tabu mógłby trwale zablokować ścieżkę do globalnego optimum, jeśli ta ścieżka przebiega przez niedawno wykonany ruch.

Pokrewne metody

Źródła

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Otwórz odnośnik do publikacji
    Skopiowano.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN: 9780792349907
    Skopiowano.