Algorytm symulowanego wyżarzania (ang. Simulated Annealing, SA) jest metaheurystyką inspirowaną procesem fizycznym wyżarzania. Polega on na stopniowym ochładzaniu materiału w celu osiągnięcia minimalnej energii wewnętrznej. Algorytm ten jest stosowany do znajdowania przybliżonych rozwiązań problemów NP-trudnych, które są zbyt złożone do dokładnego rozwiązania w rozsądnym czasie przy użyciu standardowych metod.
Oto kilka kluczowych zastosowań algorytmu symulowanego wyżarzania w problemach NP-trudnych:
1. Problem komiwojażera (Traveling Salesman Problem, TSP)
SA jest szeroko stosowany do znajdowania bliskich optymalnym tras dla problemu komiwojażera. Problem ten polega na znalezieniu najkrótszej możliwej trasy, która odwiedza wszystkie dane miasta dokładnie raz i wraca do miasta startowego.
2. Problem plecakowy (Knapsack Problem)
Algorytm SA może być użyty do znalezienia przybliżonych rozwiązań problemu plecakowego, który polega na maksymalizacji wartości przedmiotów umieszczonych w plecaku o ograniczonej pojemności.
3. Problem szeregowania zadań (Job Scheduling Problem)
SA znajduje zastosowanie w optymalizacji harmonogramów zadań w systemach produkcyjnych i obliczeniowych. Celem jest minimalizacja całkowitego czasu realizacji lub innych kryteriów kosztowych.
4. Optymalizacja struktury sieci (Network Design)
Algorytm ten jest używany do projektowania sieci komputerowych i telekomunikacyjnych, gdzie celem jest minimalizacja kosztów budowy i eksploatacji przy jednoczesnym zapewnieniu odpowiedniego poziomu wydajności i niezawodności.
5. Problemy optymalizacji kombinatorycznej (Combinatorial Optimization Problems)
SA jest stosowany w różnych problemach kombinatorycznych, takich jak problem kolorowania grafów, problem maksymalnego przepływu, czy problem minimalnego drzewa rozpinającego.
6. Inżynieria i projektowanie systemów (Engineering Design)
W inżynierii, algorytm SA jest wykorzystywany do optymalizacji projektów systemów mechanicznych, elektrycznych i innych, gdzie celem jest minimalizacja kosztów produkcji, zużycia energii lub maksymalizacja wydajności.
7. Biologia obliczeniowa (Computational Biology)
Algorytm SA znajduje zastosowanie w problemach takich jak przewidywanie struktury białek, optymalizacja sekwencji DNA, oraz w modelowaniu i symulacjach biologicznych.
Zasada działania algorytmu symulowanego wyżarzania:
- Inicjalizacja: Wybór początkowego rozwiązania i początkowej temperatury.
- Iteracja:
- Generowanie nowego rozwiązania sąsiedniego.
- Obliczanie różnicy w funkcji celu między nowym a obecnym rozwiązaniem.
- Akceptowanie nowego rozwiązania z prawdopodobieństwem zależnym od różnicy funkcji celu i bieżącej temperatury (Metropolis criterion).
- Schładzanie: Stopniowe zmniejszanie temperatury zgodnie z harmonogramem schładzania.
- Zakończenie: Algorytm kończy się, gdy temperatura osiągnie minimalny próg lub spełnione zostaną inne warunki zakończenia.
Algorytm symulowanego wyżarzania jest ceniony za swoją prostotę, elastyczność oraz zdolność do unikania lokalnych minimów, co czyni go użytecznym narzędziem w szerokim zakresie zastosowań optymalizacyjnych.