Symulowanego wyżarzania - Simulated annealing

Symulowane wyżarzanie może być stosowane do rozwiązywania problemów kombinatorycznych. Tutaj stosuje się problem komiwojażera, aby zminimalizować długość trasy, która łączy wszystkie 125 punktów.

Problem komiwojażera w 3D dla 120 punktów rozwiązany za pomocą symulowanego wyżarzania.

Symulowane wyżarzanie ( SA ) to probabilistyczna technika przybliżania globalnego optimum danej funkcji . W szczególności metaheurystyka polega na przybliżaniu globalnej optymalizacji w dużej przestrzeni wyszukiwania dla problemu optymalizacji . Jest często używany, gdy przestrzeń poszukiwań jest dyskretny (na przykład problem komiwojażera The problem spełnialności , przewidywania struktury białek , a job-shop planowania ). W przypadku problemów, w których znalezienie przybliżonego optimum globalnego jest ważniejsze niż znalezienie dokładnego optimum lokalnego w ustalonym czasie, symulowane wyżarzanie może być lepsze niż dokładne algorytmy, takie jak opadanie gradientu lub rozgałęzienie i ograniczenie .

Nazwa algorytmu pochodzi od wyżarzania w metalurgii , techniki polegającej na ogrzewaniu i kontrolowanym chłodzeniu materiału w celu zmiany jego właściwości fizycznych. Oba są atrybutami materiału, które zależą od ich swobodnej energii termodynamicznej. Ogrzewanie i chłodzenie materiału wpływa zarówno na temperaturę, jak i na termodynamiczną energię swobodną lub energię Gibbsa. Symulowane wyżarzanie może być stosowane w przypadku bardzo trudnych problemów optymalizacji obliczeniowej, w których zawodzą dokładne algorytmy; mimo że zwykle osiąga przybliżone rozwiązanie globalnego minimum, może wystarczyć na wiele praktycznych problemów.

Problemy rozwiązywane przez SA są obecnie formułowane przez obiektywną funkcję wielu zmiennych, podlegającą kilku ograniczeniom. W praktyce ograniczenie może być karane w ramach funkcji celu.

Podobne techniki zostały niezależnie wprowadzone przy kilku okazjach, w tym Pincus (1970), Khachaturyan i in. (1979, 1981), Kirkpatrick, Gelatt i Vecchi (1983) oraz Cerny (1985). W 1983 roku Kirkpatrick, Gelatt Jr., Vecchi zastosował to podejście do rozwiązania problemu komiwojażera. Zaproponowali również jego obecną nazwę, symulowane wyżarzanie.

To pojęcie powolnego chłodzenia zaimplementowane w algorytmie symulowanego wyżarzania jest interpretowane jako powolny spadek prawdopodobieństwa akceptacji gorszych rozwiązań w miarę eksploracji przestrzeni rozwiązań. Przyjmowanie gorszych rozwiązań pozwala na szersze poszukiwanie globalnego optymalnego rozwiązania. Ogólnie algorytmy symulowanego wyżarzania działają w następujący sposób. Temperatura stopniowo spada od początkowej wartości dodatniej do zera. W każdym kroku czasowym algorytm losowo wybiera rozwiązanie zbliżone do aktualnego, mierzy jego jakość i przesuwa się do niego zgodnie z temperaturowymi prawdopodobieństwami wyboru lepszych lub gorszych rozwiązań, które podczas wyszukiwania odpowiednio pozostają na poziomie 1 (lub dodatnim). ) i zmniejsz do zera.

Symulację można przeprowadzić albo przez rozwiązanie równań kinetycznych dla funkcji gęstości, albo metodą próbkowania stochastycznego. Metoda jest adaptacją algorytmu Metropolis-Hastings , metody Monte Carlo do generowania przykładowych stanów układu termodynamicznego, opublikowanej przez N. Metropolis et al. w 1953 roku.

Przegląd

Stan niektórych układów fizycznych i funkcja e ( y ) być zminimalizowane jest analogiczna do energii wewnętrznej układu, w tym stanie. Celem jest doprowadzenie układu z dowolnego stanu początkowego do stanu z minimalną możliwą energią.

Symulowane poszukiwanie wyżarzania dla maksimum. Celem jest dotarcie do najwyższego punktu. W tym przykładzie nie wystarczy użyć prostego algorytmu wznoszenia się na wzniesienia , ponieważ istnieje wiele lokalnych maksimów . Powolne schładzanie temperatury osiąga globalne maksimum.

Podstawowa iteracja

Na każdym kroku heurystyka symulowanego wyżarzania bierze pod uwagę sąsiednie stany s* obecnego stanu s i probabilistycznie decyduje o przesunięciu systemu do stanu s* lub pozostaniu w stanie s . Te prawdopodobieństwa ostatecznie prowadzą system do przejścia do stanów o niższej energii. Zazwyczaj ten krok jest powtarzany, dopóki system nie osiągnie stanu, który jest wystarczająco dobry dla aplikacji lub do wyczerpania danego budżetu obliczeniowego.

Sąsiedzi państwa

Optymalizacja rozwiązania polega na ocenie sąsiadów stanu problemu, którymi są nowe stany wytworzone poprzez konserwatywne przekształcenie danego stanu. Na przykład w zagadnieniu komiwojażera każdy stan jest zwykle definiowany jako kombinacja miast, które mają być odwiedzone, a sąsiedzi dowolnego stanu są zbiorem kombinacji powstałych przez zamianę dowolnych dwóch z tych miast. Dobrze zdefiniowany sposób, w jaki stany są zmieniane w celu wytworzenia sąsiednich stanów, nazywa się „ruchem”, a różne ruchy dają różne zestawy sąsiednich stanów. Te posunięcia zwykle skutkują minimalnymi zmianami ostatniego stanu, próbując stopniowo ulepszać rozwiązanie poprzez iteracyjne ulepszanie jego części (takich jak połączenia miejskie w problemie komiwojażera).

Proste heurystyki, takie jak wspinaczka górska , które poruszają się poprzez znajdowanie lepszego sąsiada za lepszym sąsiadem i zatrzymują się, gdy osiągną rozwiązanie, które nie ma sąsiadów, które są lepszymi rozwiązaniami, nie mogą zagwarantować, że doprowadzą do żadnego z istniejących lepszych rozwiązań – ich wynik może łatwo być po prostu lokalnego optimum , podczas gdy rzeczywista najlepszym rozwiązaniem byłoby optimum globalnego , które mogą być różne. Metaheurystyki wykorzystują sąsiadów rozwiązania jako sposób na zbadanie przestrzeni rozwiązań i chociaż wolą lepszych sąsiadów, akceptują również gorszych sąsiadów, aby uniknąć utknięcia w lokalnym optimie; mogą znaleźć globalne optimum, jeśli działają przez wystarczająco długi czas.

Prawdopodobieństwo akceptacji

Prawdopodobieństwo przejścia z obecnego stanu do kandydującego nowego stanu jest określone przez funkcję prawdopodobieństwa akceptacji , która zależy od energii i obu stanów oraz od globalnego parametru zmiennego w czasie zwanego temperaturą . Stany o mniejszej energii są lepsze niż te o większej energii. Funkcja prawdopodobieństwa musi być dodatnia, nawet jeśli jest większa niż . Ta cecha zapobiega zablokowaniu metody na lokalnym minimum, które jest gorsze niż globalne. ${\displaystyle s}$${\displaystyle s_{\mathrm {nowy}}}$ ${\ Displaystyle P (e, e_ {\ operatorname {nowy}}, T)}$${\ Displaystyle e = E (s)}$${\ Displaystyle e_ {\ operatorname {nowy}} = E (s_ {\ operatorname {nowy}})}$${\displaystyle T}$${\displaystyle P}$${\displaystyle e_{\mathrm {nowy}}}$${\displaystyle e}$

Kiedy dąży do zera, prawdopodobieństwo musi zmierzać do zera, jeśli i do wartości dodatniej w przeciwnym razie. Przy wystarczająco małych wartościach , system będzie wówczas coraz bardziej faworyzował ruchy, które idą „w dół” (tj. do niższych wartości energii) i unikał ruchów, które idą „w górę”. Dzięki temu procedura sprowadza się do zachłannego algorytmu , który wykonuje tylko przejścia z górki. ${\displaystyle T}$${\ Displaystyle P (e, e_ {\ operatorname {nowy}}, T)}$${\displaystyle e_{\mathrm {nowy}}>e}$${\displaystyle T}$${\ Displaystyle T = 0}$

W pierwotnym opisie symulowanego wyżarzania prawdopodobieństwo było równe 1, gdy — tj. procedura zawsze przesuwała się w dół, gdy znalazła na to sposób, niezależnie od temperatury. Wiele opisów i implementacji symulowanego wyżarzania nadal przyjmuje ten warunek jako część definicji metody. Jednak warunek ten nie jest niezbędny do działania metody. ${\ Displaystyle P (e, e_ {\ operatorname {nowy}}, T)}$${\displaystyle e_{\mathrm {nowy}}<e}$

Funkcja zwykle jest dobrane tak, że prawdopodobieństwo przyjęcia ruch zmniejsza się, gdy różnica wzrasta, to znaczy małe ruchy wyciągów są bardziej prawdopodobne niż w dużych. Wymóg ten nie jest jednak bezwzględnie konieczny, pod warunkiem spełnienia powyższych wymagań. ${\displaystyle P}$${\displaystyle e_{\mathrm {nowy}}-e}$

Biorąc pod uwagę te właściwości, temperatura odgrywa kluczową rolę w kontrolowaniu ewolucji stanu systemu w odniesieniu do jego wrażliwości na zmiany energii systemu. Aby być precyzyjnym, dla dużego , ewolucja jest wrażliwa na większe zmiany energii, podczas gdy jest wrażliwa na mniejsze zmiany energii, gdy jest mała. ${\displaystyle T}$${\displaystyle s}$${\displaystyle T}$${\displaystyle s}$${\displaystyle T}$

Harmonogram wyżarzania

Szybko

Wolny

Przykład ilustrujący wpływ harmonogramu chłodzenia na wydajność symulowanego wyżarzania. Problem polega na tym, aby zmienić rozmieszczenie pikseli obrazu, aby zminimalizować pewną funkcję energii potencjalnej , co powoduje, że podobne kolory przyciągają się z bliskiej odległości i odpychają z nieco większej odległości. Ruchy elementarne zamieniają dwa sąsiednie piksele. Obrazy te uzyskano w trybie szybkiego schładzania (po lewej) i powolnego schładzania (po prawej), dając wyniki podobne odpowiednio do amorficznych i krystalicznych ciał stałych .

Nazwa i inspiracja algorytmu wymaga osadzenia w charakterystyce operacyjnej algorytmu interesującej cechy związanej ze zmiennością temperatury. Wymaga to stopniowego obniżania temperatury w miarę postępu symulacji. Algorytm zaczyna się początkowo od ustawienia na wysoką wartość (lub nieskończoność), a następnie jest zmniejszany na każdym kroku zgodnie z pewnym harmonogramem wyżarzania — który może być określony przez użytkownika, ale musi się kończyć pod koniec przydzielonego budżetu czasu. W ten sposób oczekuje się, że system będzie wędrował początkowo w kierunku szerokiego obszaru przestrzeni poszukiwań zawierającej dobre rozwiązania, ignorując drobne cechy funkcji energii; następnie dryfuj w kierunku regionów o niskiej energii, które stają się coraz węższe; i wreszcie ruszyć w dół zgodnie z najbardziej stromą heurystyką zejścia . ${\displaystyle T}$${\ Displaystyle T = 0}$

Dla dowolnego problemu skończonego prawdopodobieństwo, że algorytm symulowanego wyżarzania zakończy się globalnym rozwiązaniem optymalnym , zbliża się do 1 w miarę rozszerzania harmonogramu wyżarzania. Wynik ten teoretyczny, jednak nie jest szczególnie pomocne, ponieważ czas potrzebny, aby zapewnić znaczny prawdopodobieństwo sukcesu zwykle przekroczy czas potrzebny do pełnego wyszukiwania w przestrzeni rozwiązań .

Pseudo kod

Poniższy pseudokod przedstawia opisaną powyżej heurystykę symulowanego wyżarzania. Rozpoczyna się od stanu s ₀ i trwa aż do wykonania maksymalnie k _max kroków. W tym procesie sąsiad( y ) wywołania powinien generować losowo wybranego sąsiada danego stanu s ; wywołanie random(0, 1) powinno wybrać i zwrócić wartość z zakresu [0, 1] , równomiernie losowo . Harmonogram wyżarzania jest określony przez temperaturę wywołania ( r ) , która powinna dać temperaturę do zastosowania, biorąc pod uwagę ułamek r budżetu czasu, który został dotychczas wykorzystany.

Wybór parametrów

Aby zastosować metodę symulowanego wyżarzania do konkretnego problemu, należy określić następujące parametry: przestrzeń stanów, funkcję energii (celu) E(), procedurę generatora kandydatów neighbour(), funkcję prawdopodobieństwa akceptacji P(), harmonogram wyżarzania temperature()ORAZ temperaturę początkową <init temp>. Te wybory mogą mieć znaczący wpływ na skuteczność metody. Niestety nie ma wyborów tych parametrów, które będą dobre dla wszystkich problemów i nie ma ogólnego sposobu na znalezienie najlepszych wyborów dla danego problemu. Poniższe sekcje zawierają kilka ogólnych wskazówek.

Wystarczająco blisko sąsiada

Symulowane wyżarzanie może być modelowane jako błądzenie losowe na grafie poszukiwań, którego wierzchołkami są wszystkie możliwe stany, a krawędziami są ruchy kandydujące. Istotnym wymaganiem neighbour()funkcji jest zapewnienie wystarczająco krótkiej drogi na tym grafie od stanu początkowego do dowolnego stanu, który może być globalnym optimum – średnica grafu poszukiwań musi być mała. Na przykład w powyższym przykładzie komiwojażera przestrzeń wyszukiwania dla n = 20 miast ma n! = 2 432 902 008 176 640 000 (2,4 kwintyliona) stanów; jednak liczba sąsiadów każdego wierzchołka to krawędzie (pochodzące z n wybierz 2), a średnica grafu to . ${\ Displaystyle \ suma _ {k = 1} ^ {n-1} k = {\ Frac {n (n-1)} {2}} = 190}$${\displaystyle n-1}$

Prawdopodobieństwo przejścia

Aby zbadać zachowanie symulowanego wyżarzania w konkretnym problemie, przydatne może być rozważenie prawdopodobieństw przejścia, które wynikają z różnych wyborów projektowych dokonanych podczas implementacji algorytmu. Dla każdej krawędzi grafu wyszukiwania prawdopodobieństwo przejścia jest definiowane jako prawdopodobieństwo, że algorytm symulowanego wyżarzania przejdzie do stanu, gdy jego bieżący stan to . Prawdopodobieństwo to zależy od aktualnej temperatury określonej przez , kolejności generowania ruchów kandydata przez funkcję oraz od funkcji prawdopodobieństwa akceptacji . (Zauważ, że prawdopodobieństwo przejścia nie jest po prostu , ponieważ kandydaci są testowani seryjnie.) ${\displaystyle (s,s')}$${\displaystyle s'}$${\displaystyle s}$temperature()neighbour()P()${\displaystyle P(e,e',T)}$

Prawdopodobieństwo akceptacji

Specyfikacji neighbour(), P()i temperature()jest częściowo zbędne. W praktyce często używa się tej samej funkcji akceptacji P()dla wielu problemów i dostosowuje pozostałe dwie funkcje do konkretnego problemu.

W sformułowaniu metody przez Kirkpatricka i in. funkcję prawdopodobieństwa akceptacji zdefiniowano jako 1 jeśli i inaczej. Formuła ta została powierzchownie uzasadniona przez analogię z przejściami systemu fizycznego; odpowiada algorytmowi Metropolis-Hastings , w przypadku gdy T=1 i rozkład propozycji Metropolis-Hastings jest symetryczny. Jednak to prawdopodobieństwo akceptacji jest często używane do symulowanego wyżarzania, nawet gdy funkcja, która jest analogiczna do rozkładu propozycji w Metropolis-Hastings, nie jest symetryczna lub wcale nie jest probabilistyczna. W efekcie prawdopodobieństwa przejścia symulowanego algorytmu wyżarzania nie odpowiadają przejściom analogicznego układu fizycznego, a długookresowy rozkład stanów w stałej temperaturze nie musi mieć żadnego podobieństwa do termodynamicznego rozkładu równowagi nad stanami tego układu. system fizyczny, w dowolnej temperaturze. Niemniej jednak większość opisów symulowanego wyżarzania zakłada pierwotną funkcję akceptacji, która jest prawdopodobnie zakodowana na stałe w wielu implementacjach SA. ${\displaystyle P(e,e',T)}$${\displaystyle e'<e}$${\displaystyle \exp(-(e'-e)/T)}$neighbour()${\displaystyle T}$

W 1990 roku Moscato i Fontanari oraz niezależnie Dueck i Scheuer zaproponowali, że aktualizacja deterministyczna (tj. taka, która nie opiera się na probabilistycznej regule akceptacji) może przyspieszyć proces optymalizacji bez wpływu na końcową jakość. Moscato i Fontanari wnioskują z obserwacji analogicznej krzywej „ciepła właściwego” wyżarzania „aktualizacji progu” pochodzącej z ich badań, że „stochastyczność aktualizacji Metropolis w algorytmie symulowanego wyżarzania nie odgrywa większej roli w poszukiwaniu bliskiego -optymalne minima". Zamiast tego zaproponowali, że „wygładzenie krajobrazu funkcji kosztów w wysokiej temperaturze i stopniowe definiowanie minimów podczas procesu chłodzenia są podstawowymi składnikami powodzenia symulowanego wyżarzania”. Metoda została następnie spopularyzowana pod nazwą „progowej akceptacji” ze względu na denominację Duecka i Scheuera. W 2001 roku Franz, Hoffmann i Salamon wykazali, że deterministyczna strategia aktualizacji jest rzeczywiście optymalna w ramach dużej klasy algorytmów symulujących błądzenie losowe w krajobrazie kosztów/energii.

Efektywne pokolenie kandydatów

Przy wyborze generatora kandydującego neighbour()należy wziąć pod uwagę, że po kilku iteracjach algorytmu symulowanego wyżarzania oczekuje się, że stan bieżący będzie miał znacznie niższą energię niż stan losowy. Dlatego generalnie należy pochylić generator w kierunku ruchów kandydujących, w których energia stanu docelowego będzie prawdopodobnie zbliżona do stanu obecnego. Ta heurystyka (która jest główną zasadą algorytmu Metropolis-Hastings ) ma tendencję do wykluczania „bardzo dobrych” ruchów kandydujących, a także „bardzo złych”; jednak te pierwsze są zwykle znacznie rzadsze niż drugie, więc heurystyka jest ogólnie dość skuteczna. ${\displaystyle s'}$

Na przykład w powyższym problemie komiwojażera zamiana dwóch kolejnych miast podczas trasy o niskim zużyciu energii ma niewielki wpływ na jej energię (długość); podczas gdy zamiana dwóch dowolnych miast jest znacznie bardziej prawdopodobna, aby zwiększyć jej długość niż ją zmniejszyć. Zatem oczekuje się, że generator sąsiadów z następną zamianą będzie działał lepiej niż generator z arbitralną zamianą, nawet jeśli ten drugi może zapewnić nieco krótszą ścieżkę do optimum (z zamianami zamiast ). ${\displaystyle n-1}$${\displaystyle n(n-1)/2}$

Bardziej precyzyjnym stwierdzeniem heurystyki jest to, że należy wypróbować pierwsze stany kandydujące, dla których jest duża. Dla "standardowej" funkcji akceptacji powyżej oznacza to, że jest rzędu lub mniej. Tak więc w powyższym przykładzie komiwojażera można by użyć funkcji, która zamienia dwa losowe miasta, gdzie prawdopodobieństwo wyboru pary miast znika wraz ze wzrostem odległości powyżej . ${\displaystyle s'}$${\ Displaystyle P (E (s), E (s'), T)}$${\displaystyle P}$${\ Displaystyle E (s')-E (s)}$${\displaystyle T}$neighbour()${\displaystyle T}$

Unikanie barier

Wybierając kandydata na generator neighbour()należy również starać się zmniejszyć liczbę „głębokich” lokalnych minimów – stanów (lub zbiorów stanów połączonych), które mają znacznie niższą energię niż wszystkie sąsiednie stany. Takie „zamknięty zlewni dorzecza” funkcji energii może pułapka symulowanej algorytm wyżarzania z wysokim prawdopodobieństwem (w przybliżeniu proporcjonalna do liczby państw w basenie) i przez bardzo długi czas (w przybliżeniu wykładniczo od różnicy energii pomiędzy okolicznych członkowskich oraz dno basenu).

Z reguły niemożliwe jest zaprojektowanie generatora kandydata, który spełni ten cel, a także nadania priorytetu kandydatom o podobnej energii. Z drugiej strony, często można znacznie poprawić wydajność symulowanego wyżarzania przez stosunkowo proste zmiany w generatorze. Na problem komiwojażera, na przykład, nie jest to trudne do wykazania dwie wycieczki , z prawie równych długościach, takie, że (1) jest optymalny, (2) każda sekwencja swap parą miast, które konwertuje do przechodzi wycieczki, które są znacznie dłużej niż oba, a (3) można przekształcić w odwracając (w odwrotnej kolejności) zbiór kolejnych miast. W tym przykładzie i leżą w różnych „głębokich basenach”, jeśli generator wykonuje tylko losową zamianę par; ale będą w tym samym basenie, jeśli generator wykona losowe przerzucanie segmentów. ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$

Harmonogram chłodzenia

Fizyczna analogia użyta do uzasadnienia symulowanego wyżarzania zakłada, że ​​szybkość chłodzenia jest wystarczająco niska, aby rozkład prawdopodobieństwa obecnego stanu był przez cały czas zbliżony do równowagi termodynamicznej . Niestety czas relaksacji — czas, w którym trzeba czekać na przywrócenie równowagi po zmianie temperatury — silnie zależy od „topografii” funkcji energii i aktualnej temperatury. W algorytmie symulowanego wyżarzania czas relaksacji zależy również od generatora kandydującego w bardzo skomplikowany sposób. Należy zauważyć, że wszystkie te parametry są zwykle dostarczane jako funkcje czarnej skrzynki algorytmowi symulowanego wyżarzania. Dlatego nie można z góry określić idealnej szybkości chłodzenia i należy ją empirycznie dostosować do każdego problemu. Adaptacyjne algorytmy symulowanego wyżarzania rozwiązują ten problem, łącząc harmonogram chłodzenia z postępem wyszukiwania. Inne podejście adaptacyjne, takie jak termodynamiczne symulowane wyżarzanie, automatycznie dostosowuje temperaturę na każdym etapie w oparciu o różnicę energii między dwoma stanami, zgodnie z prawami termodynamiki.

Ponowne uruchamianie

Czasami lepiej jest wrócić do rozwiązania, które było znacznie lepsze, niż zawsze przechodzić z obecnego stanu. Proces ten nazywa się ponownym uruchomieniem symulowanego wyżarzania. Aby to zrobić, możemy ustawić si edo sbesti ebestbyć może ponownie uruchomić harmonogram wyżarzania. Decyzja o ponownym uruchomieniu może opierać się na kilku kryteriach. Godne uwagi wśród nich są ponowne uruchamianie oparte na stałej liczbie kroków, w oparciu o to, czy aktualna energia jest zbyt wysoka w porównaniu z najlepszą dotychczas uzyskaną energią, ponowne uruchamianie losowe itp.

Powiązane metody

• Interakcyjne algorytmy Metropolis-Hasting ( znane również jako sekwencyjne Monte Carlo ) łączyły symulowane ruchy wyżarzania z akceptacją i odrzuceniem najlepiej dopasowanych osób wyposażonych w interaktywny mechanizm recyklingu.
• Wyżarzanie kwantowe wykorzystuje „fluktuacje kwantowe” zamiast fluktuacji termicznych, aby przejść przez wysokie, ale cienkie bariery w funkcji celu.
• Próby tunelowania stochastycznego, mające na celu pokonanie rosnącej trudności symulowanych przebiegów wyżarzania, polegają na ucieczce od lokalnych minimów wraz ze spadkiem temperatury, poprzez „tunelowanie” przez bariery.
• Przeszukiwanie Tabu zwykle przenosi się do sąsiednich stanów o niższej energii, ale wykonuje ruchy pod górę, gdy utknie w lokalnym minimum; i unika cykli, utrzymując „listę tabu” już widzianych rozwiązań.
• Ewolucja dwufazowa to rodzina algorytmów i procesów (do których należy symulowane wyżarzanie), które pośredniczą między wyszukiwaniem lokalnym i globalnym, wykorzystując zmiany fazowe w przestrzeni wyszukiwania.
• Reaktywna optymalizacja wyszukiwania skupia się na połączeniu uczenia maszynowego z optymalizacją, poprzez dodanie wewnętrznej pętli sprzężenia zwrotnego w celu samodzielnego dostrojenia dowolnych parametrów algorytmu do charakterystyki problemu, instancji i lokalnej sytuacji wokół bieżącego rozwiązania.
• Algorytmy genetyczne utrzymują pulę rozwiązań, a nie tylko jedno. Nowe rozwiązania kandydujące są generowane nie tylko przez „mutację” (jak w SA), ale także przez „rekombinację” dwóch rozwiązań z puli. Kryteria probabilistyczne, podobne do tych stosowanych w SA, są wykorzystywane do selekcji kandydatów do mutacji lub kombinacji oraz do odrzucania nadmiaru roztworów z puli.
• Algorytmy memetyczne poszukują rozwiązań, wykorzystując zestaw agentów, które zarówno współpracują, jak i konkurują w procesie; czasami strategie środków obejmują symulowane procedury wyżarzania w celu uzyskania wysokiej jakości roztworów przed ich ponownym połączeniem. Sugerowano również wyżarzanie jako mechanizm zwiększający różnorodność poszukiwań.
• Stopniowa optymalizacja degresywnie „wygładza” funkcję docelową podczas optymalizacji.
• Optymalizacja kolonii mrówek (ACO) wykorzystuje wiele mrówek (lub agentów) do przemierzania przestrzeni rozwiązań i znajdowania obszarów produktywnych lokalnie.
• Sposób przekrój entropia (CE) generuje kandydatów rozwiązania przez sparametryzowany rozkładu prawdopodobieństwa. Parametry są aktualizowane poprzez minimalizację entropii krzyżowej, aby generować lepsze próbki w następnej iteracji.
• Poszukiwanie harmonii naśladuje muzyków w procesie improwizacji, w którym każdy muzyk gra nutę, aby wspólnie znaleźć najlepszą harmonię.
• Optymalizacja stochastyczna to zbiór metod obejmujący symulowane wyżarzanie i wiele innych podejść.
• Optymalizacja roju cząstek to algorytm oparty na inteligencji roju, który znajduje rozwiązanie problemu optymalizacji w przestrzeni wyszukiwania lub modeluje i przewiduje zachowanie społeczne w obecności celów.
• Algorytm runner-root (RRA) to metaheurystyczny algorytm optymalizacji do rozwiązywania jednomodalnych i multimodalnych problemów inspirowanych rozłogami i korzeniami roślin w przyrodzie.
• Inteligentny algorytm kropel wody (IWD), który naśladuje zachowanie naturalnych kropel wody w celu rozwiązania problemów optymalizacyjnych
• Hartowanie równoległe to symulacja kopii modelu w różnych temperaturach (lub hamiltonianach ) w celu pokonania potencjalnych barier.
• Multiobjective Simulated Annealing zostały zaprojektowane z myślą o problemach ( optymalizacji wielokryterialnej ) i prawdopodobnie niektóre z nich mogą rozwiązać bardziej obiektywnymi funkcjami niż inne strategie.

Zobacz też

Bibliografia

Dalsza lektura

• A. Das i BK Chakrabarti (red.), Wyżarzanie kwantowe i powiązane metody optymalizacji , Notatka z fizyki, tom. 679, Springer, Heidelberg (2005)
• Weinberger, E. (1990). „Skorelowane i nieskorelowane krajobrazy sprawnościowe i jak odróżnić”. Cybernetyka biologiczna . 63 (5): 325–336. doi : 10.1007/BF00202749 . S2CID  851736 .
• Prasa, WH; Teukolski SA; Vetterling, WT; Flannery, BP (2007). „Punkt 10.12. Metody symulowanego wyżarzania” . Przepisy numeryczne: The Art of Scientific Computing (3rd ed.). Nowy Jork: Cambridge University Press. Numer ISBN 978-0-521-88068-8.
• Strobl, MAR; Barker, D. (2016). „O symulowanych przejściach fazowych wyżarzania w rekonstrukcji filogenezy” . Filogenetyka molekularna i ewolucja . 101 : 46–55. doi : 10.1016/j.ympev.2016.05.001 . PMC  4912009 . PMID  27150349 .
• V.Vassilev, A.Prahova: „Zastosowanie symulowanego wyżarzania w kontroli elastycznych systemów produkcyjnych”, International Journal INFORMATION THEORIES & APPLICATIONS, TOM 6/1999

Zewnętrzne linki

• Symulowane wyżarzanie Aplikacja JavaScript, która umożliwia eksperymentowanie z symulowanym wyżarzaniem. Zawiera kod źródłowy.
• „General Simulated Annealing Algorithm” Otwarty program MATLAB do ogólnych ćwiczeń symulowanego wyżarzania.
• Samodzielna lekcja na temat symulowanego wyżarzania Projekt Wikiversity.
• Google w superpozycji używania, a nie używania komputera kwantowego Ars Technica omawia możliwość, że komputer D-Wave używany przez Google może w rzeczywistości być wydajnym koprocesorem symulowanego wyżarzania.
• [1] Algorytm optymalizacji wielokryterialnej opartej na symulowanym wyżarzaniu: AMOSA.