Seminarium: Algorytmy heurystyczne

Metody heurystyczne stosuje się najczęściej do rozwiązywania trudnych problemow optymalizacyjnych, często ważnych z praktycznego punktu widzenia, dla ktorych nie są znane efektywne algorytmy wielomianowe. W informatyce algorytmy heurystyczne służą do znajdowania rozwiązań dla takich zadań, dla ktorych nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy algorytm pełnego przeglądu jest z przyczyn technicznych zbyt kosztowny, lub gdy jest nieznany. Metod tych używa się też często do znajdowania rozwiązań zbliżonych do optymalnych.

Program:

1. Pojęcie problemu optymalizacyjnego w kontekście teorii złożoności obliczeniowej.
2. Algorytmy pełnego przeglądu zbioru rozwiązań, pojęcie heurystyki, klasyfikacja heurystyk przeszukiwania.
3. Przeszukiwanie lokalne, heurystyki lokalnych ulepszeń.
4. Symulowane wyżarzanie.
5. Przeszukiwanie z tabu.
6. Przeszukiwanie rozproszone.
7. Algorytmy ewolucyjne.
8. Zrandomizowane heurystyki populacyjne.
9. Systemy mrowkowe.
10. Roj cząsteczek.
11. Sztuczne systemy immunologiczne.
12. Algorytmy memetyczne.

Wymagania: algorytmy i struktury danych, programowanie.