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 podgrzewanie metalu, a następnie chłodzenie go powoli. Program komputerowy „oczyszcza” przestrzeń rozwiązania, dopóki pozostanie wszystko, które są najlepsze lub bardzo najlepsze.
Istnieją dwa krytyczne czynniki, które użytkownik symulowanego programu wyżarzania musi określić: temperaturę początkową lub odsetek gorszych rozwiązań, które można zbadać; oraz szybkość chłodzenia, która jest szybkością, w której procent ten jest zmniejszony. Niska temperatura początkowa często kończy się z dalekim wynikiem od optymalnego. Rozpoczęcie od bardzo wysokiej temperatury może spowodować, że wyszukiwanie zajmuje znacznie więcej czasu niż to konieczne. Podobnie szybkość chłodzenia, która jest zbyt wysoka, wygeneruje słabe wyniki, podczas gdy bardzo niski wskaźnik chłodzenia spowodujeprogram, który działa bardzo długo.
Stan „wysokiej temperatury” programu symulowanego wyżarzania jest ustawieniem, które pozwala spojrzeć na szeroki zakres rozwiązań, w tym wiele, które są gorsze niż rozwiązania, które już znalazł. Komputer może patrzeć na wiele rozwiązań, które są gorsze niż obecne rozwiązanie, aby uniknąć przyklejania się do lokalnego minimum, które jest znacznie gorsze niż najlepsze. Jako przykład można sobie wyobrazić, że zaczynam od szczytu wzgórza lub góry w celu dotarcia do bazy. Po drodze mogą występować wwchy lub przepaści. Jeśli komputer nie może pójść pod górę wystarczająco daleko, aby się wydostać, utknie, mimo że nie jest blisko bazy.
Jak daleko w górę program może odejść, zależy od odsetka gorszych rozwiązań, które program może zbadać. Wraz z upływem czasu znajdują się stopniowo lepsze rozwiązania i ryzyko głębokościChasm zmniejsza się, więc odsetek gorszych rozwiązań, które komputer może zbadać, jest zmniejszony. Zmniejszenie tej frakcji jest określane jako „chłodzenie”. Gdy temperatura osiągnie frakcję przed ustawioną-która nie musi być 0-wyszukiwanie kończy się.
Powodem stosowania symulowanego wyżarzania lub innych technik wyszukiwania sztucznej inteligencji jest skrócenie do możliwej do opanowania ilości czasu potrzebnego na znalezienie niemal optymalnego rozwiązania. W przypadku wielu problemów wyczerpujące wyszukiwanie - testowanie każdego możliwego rozwiązania wobec siebie możliwego rozwiązania - może potrwać miesiące lub lata. Najczęściej znaną algorytmem dla symulowanego wyżarzania są algorytmy genetyczne. Inne popularne algorytmy wyszukiwania sztucznej inteligencji obejmują optymalizację kolonii mrówek, optymalizację roju cząstek, klasyfikatory najbliższych sąsiadów i bayesowskich.