Wyżarzanie symulowane — probabilistyczne optymalizowanie
- Rok
- 1983
- Typ
- Probabilistic metaheuristic / local search
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Wyżarzanie symulowane jest probabilistyczną metaheurystyką lokalnego przeszukiwania, wprowadzoną przez Kirkpatricka, Gelatta i Vecchiego w 1983 roku.
Modeluje ona fizyczny proces wyżarzania w metalurgii — gdzie materiał jest podgrzewany, a następnie powoli schładzany, aby osiągnąć stan krystaliczny o niskiej energii — i wykorzystuje tę analogię do ucieczki z lokalnych minimów w kombinatorycznych i ciągłych problemach optymalizacyjnych.
Intuicja stojąca za metodą
Wyobraźmy sobie próbę znalezienia najniższego punktu w pagórkowatym terenie z zasłoniętymi oczami. Czysto zachłanne przeszukiwanie zawsze schodzi w dół i utyka w pierwszej napotkanej dolinie — która może nie być najgłębsza. Wyżarzanie symulowane wprowadza kontrolowaną losowość: na początku, gdy 'temperatura' jest wysoka, algorytm jest skłonny okazjonalnie zrobić krok pod górę, akceptując przez przypadek gorsze rozwiązanie. W miarę spadku temperatury zgodnie z harmonogramem chłodzenia, algorytm staje się coraz bardziej selektywny, zbiegając do rozwiązania. Ta gotowość do akceptowania gorszych ruchów przy wysokiej temperaturze pozwala metodzie uciec z płytkich lokalnych minimów i dokładniej zbadać przestrzeń poszukiwań.
Historia
Wyżarzanie symulowane zostało wprowadzone przez Kirkpatricka, Gelatta i Vecchiego w ich przełomowym artykule z 1983 roku w czasopiśmie Science, który przedstawił wyraźną analogię między wyżarzaniem termodynamicznym ciał stałych a optymalizacją kombinatoryczną. Ta sama idea została niezależnie zaproponowana przez Cerny'ego (1985) w kontekście problemu komiwojażera. van Laarhoven i Aarts (1987) przedstawili pierwsze rygorystyczne ujęcie teoretyczne, dowodząc właściwości zbieżności przy różnych harmonogramach chłodzenia. Od tego czasu metoda stała się jedną z najszerzej badanych i stosowanych metaheurystyk, wykorzystywaną w projektowaniu inżynierskim, badaniach operacyjnych, układzie VLSI i dostrajaniu hiperparametrów uczenia maszynowego.
Kiedy stosować
Wyżarzanie symulowane ma zastosowanie do każdego problemu, w którym można zdefiniować strukturę sąsiedztwa w przestrzeni rozwiązań, niezależnie od tego, czy funkcja celu jest różniczkowalna, wypukła, czy nawet analitycznie wyrażalna. Jest szczególnie dobrze przystosowane do problemów kombinatorycznych (harmonogramowanie, trasowanie, problemy grafowe) i ciągłej optymalizacji typu black-box. Nie wymaga danych treningowych ani założeń o normalności. Harmonogram chłodzenia i struktura sąsiedztwa muszą być dostrojone do problemu; wykonanie mniej niż około 1 000 iteracji grozi przedwczesną zbieżnością do lokalnego optimum, w którym to przypadku należy preferować prostsze deterministyczne przeszukiwanie lokalne.
Ograniczenia i uwagi
- Jakość rozwiązania jest wrażliwa na harmonogram chłodzenia; zły harmonogram może dać wyniki nie lepsze niż losowe przeszukiwanie.
- Struktura sąsiedztwa musi być zaprojektowana dla każdej klasy problemów, co wymaga wiedzy domenowej.
- Zbieżność do globalnego optimum wymaga w praktyce niezwykle wolnego chłodzenia, co sprawia, że czas obliczeń jest długi dla gwarancji wysokiej jakości.
- Nie wykorzystuje informacji o gradiencie ani strukturalnej, więc metody oparte na gradiencie przewyższają ją w przypadku gładkich, różniczkowalnych problemów.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Może uciekać z lokalnych minimów poprzez probabilistyczną akceptację gorszych rozwiązań, w przeciwieństwie do czystego hill-climbingu.
- Ma zastosowanie do praktycznie każdego typu problemu — kombinatorycznego, ciągłego, mieszanego — pod warunkiem zdefiniowania struktury sąsiedztwa.
- Nie wymaga informacji o gradiencie i jest obojętne na strukturę matematyczną funkcji celu.
- Posiada teoretyczną gwarancję zbieżności do globalnego optimum przy wystarczająco wolnym chłodzeniu (Hajek 1988).
- Niewiele hiperparametrów: temperatura początkowa, tempo chłodzenia i struktura sąsiedztwa.
Zastosowania
- Kombinatoryczne problemy harmonogramowania i tworzenia rozkładów jazdy, gdzie przestrzeń rozwiązań jest zbyt duża dla przeszukiwania wyczerpującego.
- Problemy komiwojażera i trasowania pojazdów w logistyce i badaniach operacyjnych.
- Układ obwodów VLSI i planowanie rozmieszczenia chipów w inżynierii elektrycznej.
- Problemy fałdowania białek i konformacji molekularnej w biologii obliczeniowej.
- Optymalizacja hiperparametrów dla modeli uczenia maszynowego, gdy informacje o gradiencie są niedostępne.
- Problemy alokacji i przypisania zasobów w inżynierii i naukach o zarządzaniu.
Jak to działa
Jak to działa
Algorytm rozpoczyna się od początkowego rozwiązania — dowolnego dopuszczalnego punktu w przestrzeni poszukiwań — i wysokiej temperatury początkowej. Rozwiązanie początkowe może być losowe lub specyficzne dla problemu; temperatura początkowa jest zazwyczaj ustawiana na tyle wysoko, że prawie każde sąsiednie rozwiązanie zostałoby zaakceptowane na początku.
Sąsiednie rozwiązanie jest generowane przez zastosowanie małej losowej zmiany (tzw. 'ruchu') do bieżącego rozwiązania. Struktura sąsiedztwa musi być dostosowana do problemu: w przypadku problemu harmonogramowania ruch może polegać na zamianie dwóch zadań; w przypadku funkcji ciągłej może polegać na dodaniu małej losowej perturbacji do bieżącego wektora parametrów.
Obliczana jest różnica w wartości celu między nowym a bieżącym rozwiązaniem. Jeśli nowe rozwiązanie jest lepsze, jest ono zawsze akceptowane. Jeśli jest gorsze, jest akceptowane z prawdopodobieństwem, które maleje wraz z wielkością pogorszenia i bieżącą temperaturą — zazwyczaj exp(−ΔE / T). Ta probabilistyczna akceptacja jest kluczowym mechanizmem zapobiegającym przedwczesnej zbieżności.
Po każdej iteracji (lub po ustalonej liczbie ruchów przy tej samej temperaturze), temperatura jest redukowana zgodnie z harmonogramem chłodzenia — powszechnie stosuje się harmonogram geometryczny T ← α·T, gdzie α jest nieco mniejsze od 1. Wybór harmonogramu chłodzenia silnie wpływa na jakość rozwiązania: zbyt szybkie chłodzenie uwięzi przeszukiwanie w lokalnym optimum; zbyt wolne chłodzenie marnuje czas obliczeniowy.
Algorytm zatrzymuje się, gdy temperatura spadnie poniżej minimalnego progu, zostanie osiągnięta maksymalna liczba iteracji lub rozwiązanie nie poprawia się przez określony czas. Jako najlepsze rozwiązanie napotkane w całym przebiegu — nie tylko stan końcowy — jest zwracane jako wynik.
Częste pułapki
- Uruchomienie zbyt małej liczby iteracji (około poniżej 1 000) uniemożliwia prawidłowe działanie harmonogramu chłodzenia i pozostawia przeszukiwanie uwięzione w lokalnym optimum — preferuj przeszukiwanie tabu lub deterministyczne przeszukiwanie lokalne, jeśli czas obliczeń jest mocno ograniczony.
- Ustawienie zbyt niskiej temperatury początkowej oznacza, że algorytm natychmiast zachowuje się jak zachłanny hill-climbing i traci zdolność ucieczki z lokalnych minimów.
- Zbyt agresywne ustawienie tempa chłodzenia (np. α poniżej 0.9) powoduje przedwczesną zbieżność; weryfikuj jakość końcowego rozwiązania, restartując z wielu początkowych rozwiązań.
- Zastosowanie ruchu sąsiedztwa zaprojektowanego dla jednego typu problemu do innego problemu może sprawić, że ruchy będą niedopuszczalne lub bezsensowne — zawsze weryfikuj, czy każdy wygenerowany sąsiad jest prawidłowym rozwiązaniem.
- Raportowanie tylko stanu końcowego zamiast najlepszego kiedykolwiek znalezionego rozwiązania podczas przebiegu może spowodować pominięcie prawdziwego optimum znalezionego w pośrednim kroku.
Najczęściej zadawane pytania
Jak wybrać harmonogram chłodzenia?
Najczęściej stosowanym punktem wyjścia jest harmonogram geometryczny T ← α·T z α między 0.90 a 0.99. Praktyczne podejście polega na ustawieniu temperatury początkowej na tyle wysokiej, aby na początku akceptowano około 80% ruchów, a następnie obniżaniu jej, aż do momentu, gdy akceptuje się mniej niż 1% ruchów pod górę. Jeśli jakość końcowego rozwiązania jest niska, spowolnij tempo chłodzenia (zwiększ α); jeśli czas obliczeń jest zbyt długi, przyspiesz je. Zawsze uruchamiaj algorytm kilkakrotnie z różnych punktów startowych, aby ocenić jego odporność.
Czym wyżarzanie symulowane różni się od algorytmów genetycznych lub optymalizacji rojem cząstek?
Wyżarzanie symulowane utrzymuje pojedyncze rozwiązanie i eksploruje sąsiedztwo poprzez losowe perturbacje, akceptując probabilistycznie gorsze rozwiązania. Algorytmy genetyczne i optymalizacja rojem cząstek utrzymują populację rozwiązań i wykorzystują krzyżowanie, mutację lub ruch roju do ewolucji populacji. Wyżarzanie symulowane jest zazwyczaj prostsze w implementacji dla problemów z naturalną strukturą sąsiedztwa, podczas gdy metody oparte na populacji mogą być skuteczniejsze w przypadku problemów o wysokiej wymiarowości i ciągłych.
Czy globalne optimum jest gwarantowane?
Teoretycznie tak, pod warunkiem, że temperatura spada wystarczająco wolno (chłodzenie logarytmiczne). W praktyce takie chłodzenie jest niewykonalne obliczeniowo, więc algorytm znajduje rozwiązanie bliskie optymalnemu. Jakość wyniku poprawia się wraz z wolniejszym chłodzeniem i większą liczbą iteracji, ale nie ma gwarancji w skończonym czasie. Uruchamianie wielu restartów i zachowywanie najlepszego znalezionego rozwiązania jest praktycznym sposobem na zwiększenie pewności.
Kiedy powinienem wybrać przeszukiwanie tabu lub algorytm genetyczny zamiast tego?
Wybierz przeszukiwanie tabu, gdy potrzebujesz deterministycznego, kierowanego pamięcią przeszukiwania, które unika powtarzania ostatnich rozwiązań i może efektywnie wykorzystać strukturę problemu w krótszym czasie. Wybierz algorytm genetyczny lub optymalizację rojem cząstek, gdy problem ma wysoką wymiarowość i jest ciągły, lub gdy potrzebna jest populacja zróżnicowanych rozwiązań do mapowania krajobrazu optimum. Wyżarzanie symulowane jest silnym domyślnym wyborem dla problemów kombinatorycznych z wyraźną strukturą sąsiedztwa i gdy ważna jest prostota implementacji.
Pokrewne metody
Źródła
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
Otwórz odnośnik DOISkopiowano.van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
ISBN: 9789027725431Skopiowano.