METAHEURYSTYKI PRZESZUKIWANIA

wykład monograficzny+laboratorium, sem. letni 2003/2004
 

W potocznym znaczeniu terminem heurystyka (z greckiego heuriskein --- znaleźć, odkryć) określa się praktyczną, opartą na doświadczeniu, ''inteligentną'' regułę postępowania, która może drastycznie uprościć lub skrócić proces rozwiązywania problemu, gdy metoda rozwiązania nie jest znana lub jest zawiła i czasochłonna. W algorytmice heurystyką nazywa się "niepełnowartościowy" algorytm, który umożliwia znalezienie w akceptowalnym czasie przynajmniej "dostatecznie dobrego" przybliżonego rozwiązania problemu, choć nie gwarantuje tego we wszystkich przypadkach. Metody heurystyczne należą do podstawowych narzędzi sztucznej inteligencji, często używane są też w różnych działach badań operacyjnych.

Podejście heurystyczne można stosować "piętrowo", tworząc metaheurystyki, czyli heurystyki nadrzędne, sterujące w procesie iteracyjnego przeszukiwania heurystykami niższego rzędu. W ostatnich kilkudziesięciu latach opracowano wiele niekonwencjonalnych metod heurystycznego przeszukiwania, inspirowanych często mechanizmami fizycznymi lub biologicznymi, zaliczanych obecnie do rzędu metaheurystyk.

Celem proponowanego wykładu jest syntetyczne przedstawienie i porównanie najważniejszych metaheurystyk przeszukiwania. Uzupełnieniem wykładu są zajęcia laboratoryjne, w ramach których słuchacze będą przeprowadzać samodzielne eksperymenty z implementowanymi algorytmami i prezentować ich wyniki.

Program wykładu w zarysie:

	Zadania optymalizacyjne. Metody heurystyczne jako praktyczne sposoby rozwiązywania trudnych zadań optymalizacyjnych.
	Przeszukiwanie heurystyczne  -- przeszukiwanie lokalne i jego mechanizmy  -- klasyfikacja heurystyk przeszukiwania
	Heurystyki "samotnego poszukiwacza" -- "anatomia" heurystyki samotnego poszukiwacza -- deterministyczne i losowe strategie monotoniczne (SAHC, NAHC, RAHC), metoda wielostartu -- losowe strategie niemonotoniczne (algorytm Metropolisa, symulowane wyżarzanie) -- deterministyczne strategie niemonotoniczne z pamięcią (metaheurystyka tabu search) -- metody mieszane (metaheurystyka GRASP)
	Ewolucyjne heurystyki populacyjne -- "anatomia" ewolucyjnej heurystyki populacyjnej -- przegląd wybranych metaheurystyk: algorytmy genetyczne, algorytmy memetyczne (hybrydowe a.g.), strategie ewolucyjne, przeszukiwanie rozproszone (scatter search)
	Heurystyki populacyjne oparte na spontanicznej samoorganizacji - algorytmy mrówkowe (AS, ACO).
	Aspekty teoretyczne: zbieżność heurystyki do rozwiązania optymalnego, modelowanie procesu przeszukiwania za pomocą łańcuchów Markowa.

Program zajęć laboratoryjnych:

W ramach zajęć słuchacze będą przeprowadzać samodzielne eksperymenty z implementowanymi wariantami algorytmów i prezentować ich wyniki. Zadania krótkie (1-4) polegają na implementacji i testowaniu metod omawianych na wykładzie dla problemu Maximum Weight Partial Coloring  (k=3) lub TSP.

Dane wejściowe (kolorowanie)

Kalendarium (data oznacza termin oddania raportu)

Zadanie 1 (12.03): heurystyka lokalnych ulepszeń dla TSP 
Zadanie 2 (26.03): MWPC, symulowane wyżarzanie
Zadanie 3 (16.04): MWPC, tabu search
Zadanie 4 (7.05): MWPC, algorytm genetyczny / memetyczny
Zadanie końcowe (28.05): TSP, projekt własny      Biblioteka przykładów

Miejsce i termin egzaminu: 3 czerwca 2004 (czwartek), godz. 9:00, s. 3130
Forma egzaminu: egzamin ustny.

Notatki do wykładu
 

Literatura pomocnicza:

Ogólnodostępne podręczniki w jęz. polskim

1. D. E. Goldberg: Algorytmy genetyczne i ich zastosowania.  WNT, Warszawa 2003 (wyd. 3).
2. Z. Michalewicz: Algorytmy genetyczne + struktury danych = programy ewolucyjne.  WNT, Warszawa, 2003 (wyd. 3).
3. J. Arabas: Wykłady z algorytmów ewolucyjnych.  WNT, Warszawa, 2004.

Artykuły uzupełniające dostępne w Internecie (w jęz. angielskim)

Metaheurystyki w optymalizacji kombinatorycznej

Colorni A., M.Dorigo, F.Maffioli, V. Maniezzo, G. Righini & M. Trubian (1996): Heuristics from Nature for Hard Combinatorial Problems
International Transactions in Operational Research, 3, 1, 1-21.

C. Blum and A. Roli (2001): Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison
TR/IRIDIA/2001-13, IRIDIA

GRASP

Thomas A. Feo, Mauricio G.C. Resende  Greedy Randomized Adaptive Search Procedures
Journal of Global Optimization  6 (1995), 109-133.

Tabu Search

A. Hertz, É. D. Taillard, D. de Werra  A Tutorial On Tabu Search
in: E.H.L. Aarts and J. K. Lenstra,
Local search in combinatorial optimization, 1997, J. Wiley & Sons Ltd., 121-136.

Przeszukiwanie rozproszone

M. Laguna "Scatter Search"
In Handbook of Applied Optimization, P. M. Pardalos and M. G. C. Resende (Eds.), Oxford University Press, pp. 183-193 (2002)

F. Glover "A Template for Scatter Search and Path Relinking"
In Artificial Evolution, Lecture Notes in Computer Science, 1363, J.-K. Hao, E. Lutton, E. Ronald , M. Schoenauer and D. Snyers, Eds. Springer, 1998, pp. 13-54

Algorytmy mrówkowe

M. Dorigo, G. Di Caro, and L. M. Gambardella "Ant Algorithms for Discrete Optimization"
Artificial Life, 5(2):137-172. 1999.