Co to jest symulowane wyżarzanie?
Symulowane wyżarzanie to technika komputerowa, która może znaleźć dobre - choć niekoniecznie optymalne - rozwiązania problemu. Jest tak nazwany, ponieważ naśladuje metalurgiczny proces wyżarzania. W metalach wyżarzanie jest procesem oczyszczania poprzez ogrzewanie metalu, a następnie jego powolne chłodzenie. Program komputerowy „oczyszcza” przestrzeń rozwiązania, dopóki nie pozostaną rozwiązania najlepsze lub prawie najlepsze.
Istnieją dwa krytyczne czynniki, które użytkownik symulowanego programu wyżarzania musi określić: temperatura początkowa lub procent gorszych rozwiązań, które można zbadać; oraz szybkość chłodzenia, która jest szybkością zmniejszania tego procentu. Niska temperatura początkowa często kończy się wynikiem daleko odbiegającym od optymalnego. Rozpoczęcie w bardzo wysokiej temperaturze może spowodować, że wyszukiwanie zajmie znacznie więcej czasu niż to konieczne. Podobnie zbyt wysokie tempo chłodzenia spowoduje słabe wyniki, natomiast bardzo niskie tempo chłodzenia spowoduje, że program będzie działał przez bardzo długi czas.
Stan „wysokiej temperatury” dla symulowanego programu wyżarzania jest ustawieniem, które pozwala mu spojrzeć na szeroki zakres rozwiązań, w tym wiele gorszych niż rozwiązania, które już znalazł. Komputer może spojrzeć na wiele rozwiązań gorszych niż obecne rozwiązanie, aby uniknąć trzymania się lokalnego minimum, które jest znacznie gorsze niż najlepsze. Jako przykład można wyobrazić sobie rozpoczęcie od szczytu wzgórza lub góry w celu dotarcia do bazy. Po drodze mogą znajdować się wąwozy lub przepaści. Jeśli komputer nie będzie mógł podjechać wystarczająco daleko, aby się wydostać, utknie, nawet jeśli nie jest daleko od bazy.
To, jak daleko pod górę może się posunąć program, zależy od procentu gorszych rozwiązań, które program może zbadać. Z biegiem czasu znajdują się coraz lepsze rozwiązania, a ryzyko głębokiej otchłani maleje, przez co zmniejsza się odsetek gorszych rozwiązań, które komputer może eksplorować. Zmniejszenie tej frakcji nazywa się „chłodzeniem”. Gdy temperatura osiągnie ustaloną frakcję - która nie musi wynosić 0 - wyszukiwanie kończy się.
Powodem zastosowania symulowanego wyżarzania lub innych technik wyszukiwania sztucznej inteligencji jest skrócenie do możliwego do opanowania czasu potrzebnego na znalezienie prawie optymalnego rozwiązania. W przypadku wielu problemów wyczerpujące poszukiwanie - testowanie każdego możliwego rozwiązania względem siebie - może zająć miesiące lub lata. Najbardziej znaną alternatywą dla symulowanego wyżarzania są algorytmy genetyczne. Inne popularne algorytmy wyszukiwania sztucznej inteligencji obejmują optymalizację kolonii mrówek, optymalizację roju cząstek, najbliższego sąsiada i klasyfikatory bayesowskie.