Multi-objective Tabu Search (MOTS) — Metaheurystyka dla rozwiązań Pareto-optymalnych
- Autor metody
- Hansen, M. P.; building on Glover (1989) Tabu Search
- Rok
- 1997
- Typ
- Metaheuristic multi-objective optimization
- Rodzina
- Simulation / optimization
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Multi-objective Tabu Search (MOTS) to algorytm metaheurystyczny, który rozszerza klasyczne ramy Tabu Search w celu jednoczesnej optymalizacji dwóch lub więcej sprzecznych funkcji celu.
Zamiast pojedynczego optimum, dąży do aproksymacji frontu Pareto — zbioru rozwiązań, w których żaden cel nie może zostać poprawiony bez pogorszenia innego — co czyni go odpowiednim dla złożonych problemów optymalizacji kombinatorycznej i ciągłej w inżynierii, logistyce i badaniach operacyjnych.
Intuicja stojąca za metodą
Wyobraźmy sobie eksplorację nierównego terenu z wieloma wzgórzami i dolinami, ale posiadamy kilka map pokazujących różne tereny (jedną na cel), które sobie przeczą. MOTS nawiguje w tej przestrzeni, przechodząc do sąsiednich rozwiązań, utrzymując krótkoterminową listę pamięci (listę tabu) ostatnio odwiedzonych miejsc, aby uniknąć cykliczności, i przechowując archiwum niedominowanych rozwiązań znalezionych do tej pory. Okresowo strategiczna dywersyfikacja popycha poszukiwania w nieprzeszukane regiony frontu Pareto, równoważąc eksploatację obiecujących obszarów z globalną eksploracją.
Historia
Multi-objective Tabu Search rozszerza Tabu Search dla pojedynczego celu, wprowadzone przez Freda Glovera w 1989 roku. Pierwsza systematyczna formuła MOTS — obejmująca archiwizację Pareto i wielokryterialne kryteria aspiracji — została przedstawiona przez M. P. Hansena na konferencji MCDM w 1997 roku. Kolejne prace Gandibleux, Teghema i innych sformalizowały warianty dla problemów kombinatorycznych, a MOTS od tego czasu jest stosowany w harmonogramowaniu, logistyce i projektowaniu inżynieryjnym jako konkurencyjna alternatywa dla ewolucyjnych algorytmów wielokryterialnych.
Kiedy stosować
Używaj MOTS, gdy masz do czynienia z problemem optymalizacji kombinatorycznej lub mieszanej całkowitoliczbowej z dwoma lub więcej sprzecznymi celami (np. koszt vs. jakość, czas vs. ryzyko), a metody dokładne są obliczeniowo niewykonalne. Doskonale sprawdza się w problemach harmonogramowania, trasowania pojazdów, projektowania sieci i wyboru portfela, gdzie przestrzeń poszukiwań jest zbyt duża dla wyczerpującej enumeracji. Preferuj MOTS nad czysto losowym przeszukiwaniem, gdy struktura sąsiedztwa jest znacząca, a operatory ruchu można zdefiniować jasno. NIE używaj MOTS, gdy: problem ma pojedynczy cel (wystarczy zwykły Tabu Search); gdy front Pareto można wyliczyć dokładnie; gdy dostępna jest informacja o gradiencie, a teren jest wypukły (użyj programowania matematycznego zamiast tego); lub gdy decyzje w czasie rzeczywistym wymagają deterministycznych, powtarzalnych wyników bez zmienności stochastycznej.
Ograniczenia i uwagi
- Wydajność jest wysoce wrażliwa na długość listy tabu, definicję sąsiedztwa i strategię dywersyfikacji — wymaga starannego dostrajania parametrów.
- Brak gwarancji zbieżności do prawdziwego frontu Pareto; jakość rozwiązania zależy od długości przebiegu i struktury problemu.
- Obliczeniowo kosztowny na iterację, gdy sąsiedztwa są duże lub ewaluacje celów są kosztowne.
- Utrzymanie i aktualizacja archiwum Pareto może stać się kosztowne wraz ze wzrostem liczby celów i rozmiaru archiwum.
- Implementacja równoległa nie jest trywialna ze względu na sekwencyjny, oparty na pamięci charakter mechanizmu tabu.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Unika ponownego odwiedzania ostatnich rozwiązań za pomocą listy tabu, zmniejszając ryzyko cykliczności w złożonych przestrzeniach.
- Kryteria aspiracji pozwalają na nadpisanie ograniczeń tabu, gdy ruch prowadzi do wyjątkowej poprawy, równoważąc pamięć z elastycznością.
- Nie wymaga informacji o gradiencie, co czyni go stosowalnym do funkcji celu niedyferencjowalnych, dyskretnych lub typu „czarna skrzynka”.
- Generuje aproksymację całego frontu Pareto w jednym przebiegu, wspierając podejmowanie decyzji wielokryterialnych.
- Elastyczna definicja sąsiedztwa i operatorów ruchu pozwala na dostosowanie do specyfiki problemu.
- Mechanizmy dywersyfikacji umożliwiają ucieczkę z lokalnych optimów i lepsze pokrycie frontu Pareto.
Zastosowania
- Wielokryterialne trasowanie pojazdów i harmonogramowanie logistyczne (jednoczesne minimalizowanie kosztów i czasu dostawy)
- Dwukryterialne harmonogramowanie projektów: minimalizacja czasu wykonania i kosztu zasobów przy ograniczeniach predykcji
- Optymalizacja portfela: równoważenie oczekiwanego zwrotu z ryzykiem w wielu klasach aktywów
- Projektowanie sieci: minimalizacja kosztów instalacji przy jednoczesnym maksymalizowaniu niezawodności lub przepustowości
- Planowanie procesów produkcyjnych: jednoczesna optymalizacja czasu cyklu, zużycia energii i wskaźników jakości
- Zarządzanie środowiskiem: równoważenie produkcji gospodarczej z zanieczyszczeniem lub wpływem na ekosystem
Jak to działa
Jak to działa
Zainicjuj poszukiwania z jednym lub kilkoma rozwiązaniami początkowymi (wygenerowanymi losowo lub skonstruowanymi heurystycznie). Ustaw pustą listę tabu o ustalonej długości L i zainicjuj archiwum Pareto niedominowanymi rozwiązaniami z populacji początkowej.
Wygeneruj sąsiedztwo N(s) bieżącego rozwiązania s, stosując operatory ruchu (zamiany, wstawienia, perturbacje). Oceń wszystkie sąsiednie rozwiązania dla każdej funkcji celu, aby zidentyfikować kandydatów do postępu.
Zastosuj filtr tabu: wyklucz sąsiadów, których definiujące ruchy znajdują się na liście tabu, chyba że spełniają kryterium aspiracji — zazwyczaj takie, że sąsiad dominuje wszystkich obecnych członków archiwum lub poprawia najlepszą znaną wartość co najmniej jednego celu. Zapobiega to cykliczności i wymusza eksplorację.
Wybierz najlepszego nie-tabu sąsiada (lub zwycięzcę kryterium aspiracji) jako następne bieżące rozwiązanie. Zaktualizuj archiwum Pareto, dodając nowe rozwiązanie, jeśli jest ono niedominowane; usuń wszelkich członków archiwum, którzy są zdominowani przez nowy wpis.
Zastosuj strategie dywersyfikacji, gdy poszukiwania utkną w martwym punkcie: długoterminowa pamięć częstotliwości identyfikuje rzadko odwiedzane regiony; restart z elitarnych rozwiązań archiwum lub losowo perturbowanych rozwiązań w celu rozszerzenia pokrycia frontu Pareto.
Powtarzaj kroki sąsiedztwa, filtrowania i archiwizacji, aż zostanie spełnione kryterium zatrzymania — zazwyczaj maksymalna liczba iteracji, ewaluacji funkcji lub upływający czas CPU. Zwróć archiwum Pareto jako aproksymowany front Pareto-optymalny.
Częste pułapki
- Ustawienie listy tabu zbyt krótko powoduje cykliczność; ustawienie jej zbyt długo nadmiernie ogranicza poszukiwania i powoduje pominięcie dobrych rozwiązań — niezbędna jest kalibracja empiryczna.
- Zaniedbanie dywersyfikacji prowadzi do przedwczesnej zbieżności do jednego regionu frontu Pareto, dając słabą aproksymację.
- Zastosowanie MOTS z więcej niż trzema celami pogarsza wydajność, ponieważ zarządzanie archiwum i utrzymanie różnorodności stają się kosztowne obliczeniowo; rozważ metody oparte na dekompozycji dla problemów z wieloma celami.
- Użycie ogólnych operatorów ruchu bez specyficznego dla problemu projektu znacznie ogranicza jakość rozwiązania w porównaniu do dedykowanych implementacji.
- Raportowanie tylko końcowego archiwum bez analizy historii zbieżności może maskować przedwczesne stagnację.
Najczęściej zadawane pytania
Jak MOTS obsługuje listę tabu, gdy istnieje wiele celów?
Lista tabu przechowuje ruchy (nie rozwiązania), więc działa tak samo jak w Tabu Search dla pojedynczego celu. Kluczową różnicą jest to, że wybór spośród sąsiadów nie-tabu wykorzystuje dominację wielokryterialną lub funkcję skalaryzującą, a kryterium aspiracji jest redefiniowane, aby zezwolić na ruch tabu, jeśli wynikowe rozwiązanie nie jest zdominowane przez wszystkich obecnych członków archiwum.
Czym jest archiwum Pareto i jak duże powinno być?
Archiwum Pareto przechowuje wszystkie niedominowane rozwiązania znalezione podczas poszukiwań. Jego maksymalny rozmiar jest zazwyczaj ograniczony (np. 100–500 rozwiązań), aby utrzymać koszty pamięci i aktualizacji na rozsądnym poziomie. Gdy archiwum jest pełne, przycinanie oparte na odległości między punktami lub siatce usuwa rozwiązania z zatłoczonych regionów, aby utrzymać różnorodność.
Jak MOTS porównuje się do NSGA-II w problemach wielokryterialnych?
NSGA-II wykorzystuje populacyjne podejście ewolucyjne z krzyżowaniem i mutacją, co czyni go lepszym w globalnej eksploracji na wczesnym etapie poszukiwań. MOTS opiera się na ruchach w sąsiedztwie i pamięci, co często daje lepszą jakość lokalnego przeszukiwania. W praktyce MOTS ma tendencję do przewyższania algorytmu NSGA-II w problemach kombinatorycznych z silną strukturą sąsiedztwa, podczas gdy NSGA-II jest szerzej stosowany w problemach ciągłych.
Ile iteracji jest zazwyczaj potrzebnych?
Nie ma uniwersalnej zasady. Powszechną praktyką jest budżetowanie ewaluacji funkcji, a nie iteracji — zazwyczaj 10 000 do 100 000 ewaluacji w zależności od rozmiaru problemu — i przeprowadzanie wielu niezależnych startów w celu oceny jakości rozwiązania i stabilności frontu Pareto.
Czy MOTS może obsługiwać więcej niż dwa cele?
Tak, ale skuteczność spada wraz ze wzrostem liczby celów powyżej trzech (tzw. „przekleństwo wymiarowości” w przestrzeni celów). Dla czterech lub więcej celów rozmiar archiwum gwałtownie rośnie, a utrzymanie różnorodności staje się trudne; często preferowane są podejścia oparte na dekompozycji lub wskaźnikach.
Pokrewne metody
Źródła
Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.
Otwórz odnośnik do publikacjiSkopiowano.Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Otwórz odnośnik DOISkopiowano.