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

Stochastyczne przeszukiwanie z tabu — randomizowana metaheurystyka z pamięcią

Autor metody
Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
Rok
1990s
Typ
Stochastic metaheuristic optimizer
Rodzina
Simulation / optimization

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

Rozmiar czcionki

Do czego służy?

Stochastyczne przeszukiwanie z tabu (STS) to rozszerzenie klasycznego przeszukiwania z tabu, które wprowadza losowość do faz eksploracji sąsiedztwa i wyboru ruchu.

Łącząc pamięć tabu — która zabrania niedawno odwiedzonych rozwiązań — z probabilistyczną akceptacją lub losowym próbkowaniem kandydatów, STS skuteczniej unika lokalnych optimów i eksploruje złożone przestrzenie rozwiązań, w których deterministyczne TS może zawieść.

Intuicja stojąca za metodą

Klasyczne przeszukiwanie z tabu porusza się w przestrzeni rozwiązań, zawsze przechodząc do najlepszego dozwolonego sąsiada, używając krótkoterminowej pamięci (listy tabu) w celu zapobiegania cyklom. W praktyce jednak najlepszy dozwolony ruch może nadal uwięzić algorytm w pewnym obszarze przestrzeni. Stochastyczne przeszukiwanie z tabu wprowadza kontrolowaną losowość: następny ruch jest wybierany probabilistycznie z zestawu kandydatów na sąsiadów, a nie zachłannie, a losowe perturbacje są sporadycznie wprowadzane w celu dywersyfikacji przeszukiwania. Zachowuje to dyscyplinę TS kierowaną pamięcią, dodając jednocześnie moc eksploracyjną, której brakuje czysto deterministycznemu spadkowi.

Historia

Przeszukiwanie z tabu zostało formalnie wprowadzone przez Freda Glovera w 1986 roku i rozwinięte w przełomowych artykułach w latach 1989-1990. Rozszerzenia stochastyczne pojawiły się w latach 90., gdy badacze zdali sobie sprawę, że deterministyczna ocena sąsiedztwa stanowiła wąskie gardło w problemach na dużą skalę. Losowe próbkowanie kandydatów, probabilistyczna akceptacja ruchu i wprowadzanie szumu zostały włączone w celu poprawy dywersyfikacji, co doprowadziło do powstania tego, co ogólnie nazywa się stochastycznym przeszukiwaniem z tabu. Technika ta jest szeroko stosowana w badaniach operacyjnych, projektowaniu inżynierskim i optymalizacji hiperparametrów uczenia maszynowego.

Kiedy stosować

Używaj stochastycznego przeszukiwania z tabu podczas rozwiązywania kombinatorycznych lub ciągłych problemów optymalizacji typu black-box z nierównymi, multimodalnymi krajobrazami, gdzie deterministyczne przeszukiwanie lokalne konsekwentnie ulega uwięzieniu (np. harmonogramowanie, trasowanie, selekcja cech). Jest to szczególnie cenne, gdy pełna ocena sąsiedztwa jest kosztowna obliczeniowo, co sprawia, że losowe próbkowanie jest konieczne. NIE używaj STS, gdy problem jest wypukły lub unimodalny — metody oparte na gradientach lub metody dokładne są szybsze i optymalne. Unikaj go, gdy potrzebujesz gwarantowanej globalnej optymalności, ponieważ STS nie oferuje gwarancji zbieżności poza heurystycznie znalezionymi najlepszymi rozwiązaniami. Unikaj również, gdy funkcja celu jest tania do całkowitej oceny, a deterministyczne TS z wyczerpującym przeszukiwaniem sąsiadów jest wykonalne.

Ograniczenia i uwagi

  • Brak teoretycznej gwarancji znalezienia globalnego optimum; jakość rozwiązania zależy w dużej mierze od ustawień parametrów.
  • Czas trwania tabu i rozmiar listy kandydatów wymagają dostrojenia specyficznego dla problemu; złe wybory prowadzą do przedwczesnej konwergencji lub powolnego postępu.
  • Stochastyczne uruchomienia są niereprodukowalne bez ustalonego ziarna losowego, co komplikuje benchmarking i audyt.
  • Narzut pamięci rośnie wraz z rozmiarem listy tabu; dla dużych przestrzeni rozwiązań potrzebne są reprezentacje tabu oparte na atrybutach.

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

Mocne strony

  • Skuteczniej unika lokalnych optimów niż deterministyczne przeszukiwanie z tabu, łącząc pamięć z probabilistyczną eksploracją.
  • Skaluje się do dużych struktur sąsiedztwa poprzez próbkowanie kandydatów, zmniejszając koszt obliczeniowy na iterację.
  • Pamięć tabu zapobiega cyklom, co jest częstym trybem awarii czysto stochastycznych metod, takich jak wspinaczka po wzgórzu z losowym restartem.
  • Elastyczna struktura: prawdopodobieństwo perturbacji i czas trwania tabu można dostosować, aby zrównoważyć intensyfikację i dywersyfikację.
  • Ma zastosowanie zarówno do problemów kombinatorycznych (TSP, harmonogramowanie), jak i optymalizacji ciągłej z niewielkimi adaptacjami.

Zastosowania

  • Trasowanie pojazdów i optymalizacja logistyki w warunkach niepewnego popytu
  • Harmonogramowanie zadań i harmonogramowanie otwarte z losowymi czasami przetwarzania
  • Selekcja cech w wysokowymiarowych zbiorach danych uczenia maszynowego
  • Projektowanie sieci i optymalizacja topologii
  • Optymalizacja portfela z kombinatorycznymi ograniczeniami wyboru aktywów
  • Dostrajanie hiperparametrów dla złożonych modeli symulacyjnych

Jak to działa

Jak to działa

1

Wygeneruj rozwiązanie początkowe x0 (losowo lub heurystycznie). Ustaw listę tabu T jako pustą, zdefiniuj czas trwania tabu tau, limit iteracji I_max oraz parametry stochastyczne (np. rozmiar listy kandydatów k, prawdopodobieństwo perturbacji p_perturb).

2

W każdej iteracji losowo próbuj podzbiór N_s pełnego sąsiedztwa N(x_current) zamiast oceniać wszystkich sąsiadów. Zmniejsza to koszt na iterację i wprowadza stochastyczność w eksplorowanych regionach przestrzeni.

3

Wybierz następne rozwiązanie x_next z N_s: albo (a) wybierz najlepszego kandydata nieobjętego tabu z prawdopodobieństwem 1-p_perturb, albo (b) z prawdopodobieństwem p_perturb wybierz losowego kandydata nieobjętego tabu w celu dywersyfikacji. Kryteria aspiracji mogą nadpisać status tabu, jeśli x_next poprawia najlepsze znane rozwiązanie.

4

Dodaj x_current (lub atrybut ruchu) do listy tabu T. Usuń najstarszy wpis, jeśli |T| > tau. Zaktualizuj bieżące najlepsze rozwiązanie x_best, jeśli f(x_next) < f(x_best).

5

Powtarzaj próbkowanie_sąsiedztwa poprzez aktualizację_tabu, aż osiągnięta zostanie I_max iteracji, spełniona zostanie docelowa wartość funkcji celu, lub nie nastąpiła poprawa przez okno cierpliwości. Zwróć x_best jako ostateczne rozwiązanie.

Częste pułapki

  • Ustawienie zbyt krótkiego czasu trwania tabu pozwala na cykle pomimo listy tabu; zbyt długie niepotrzebnie blokuje obiecujące regiony.
  • Użycie zbyt małej listy kandydatów (agresywne próbkowanie) może sprawić, że przeszukiwanie będzie konsekwentnie pomijać dobre sąsiadujące rozwiązania.
  • Zaniedbanie kryteriów aspiracji powoduje, że algorytm odrzuca globalnie poprawiające ruchy, które akurat są objęte tabu.
  • Raportowanie tylko jednego uruchomienia bez wielu restartów lub ziaren daje mylący obraz typowej jakości rozwiązania.
  • Mylenie stochastycznego przeszukiwania z tabu z symulowanym wyżarzaniem: obie są stochastyczne, ale różnią się fundamentalnie — STS używa jawnej pamięci, podczas gdy SA używa probabilistycznej akceptacji opartej na temperaturze bez pamięci.

Najczęściej zadawane pytania

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

Obie są metaheurystykami stochastycznymi, ale STS wykorzystuje jawną pamięć tabu do zabraniania niedawno odwiedzonych ruchów, zapobiegając cyklom. SA nie ma pamięci — akceptuje gorsze rozwiązania z prawdopodobieństwem, które maleje w czasie (harmonogram temperatury). STS jest generalnie silniejszy w problemach kombinatorycznych, gdzie ponowne odwiedzanie ruchów jest wyraźnym zagrożeniem.

Ile iteracji (I_max) powinienem uruchomić?

Nie ma uniwersalnej zasady. Powszechną praktyką jest przeprowadzanie wielu niezależnych prób (np. 10-30 restartów) z budżetem proporcjonalnym do rozmiaru problemu, a następnie raportowanie najlepszych i średnich wyników. W przypadku benchmarkingu należy dopasować całkowity budżet oceny funkcji używany przez konkurencyjne metody.

Czy stochastyczne przeszukiwanie z tabu może obsługiwać zmienne ciągłe?

Tak, ale wymaga to zdefiniowania ciągłego sąsiedztwa (np. perturbacji Gaussa wokół bieżącego rozwiązania) i odpowiedniego atrybutu dla listy tabu (np. regionu lub kierunku). Większość literatury STS dotyczy problemów kombinatorycznych; dla przestrzeni ciągłych, ewolucja różnicowa lub CMA-ES są często bardziej naturalnymi alternatywami.

Jaka jest rola kryteriów aspiracji?

Kryteria aspiracji nadpisują status tabu ruchu, jeśli jego akceptacja prowadzi do rozwiązania lepszego niż najlepsze znalezione do tej pory. Bez aspiracji algorytm mógłby trwale odrzucać globalnie poprawiające ruchy, które akurat są objęte tabu, poważnie ograniczając jakość rozwiązania.

Czy powinienem ustalić ziarno losowe dla reprodukowalności?

Tak, ustal ziarno podczas raportowania wyników w badaniach, aby zapewnić reprodukowalność. W praktyce uruchom z wieloma ziarnami i raportuj statystyki (średnia, najlepsze, odchylenie standardowe), aby uzyskać wiarygodny obraz wydajności algorytmu w stochastycznym krajobrazie.

Pokrewne metody

Źródła

  1. Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.

    Otwórz odnośnik DOI
    Skopiowano.