Genealogia metaheurystyk
Zaawansowane programowanie
Genealogia wg [El-Ghazali Talbi, Metaheuristics: From Design to
wykład 4: jeszcze o metaheurystykach
Implementation, 2009]  wybór
1940
LS1947
1950
GA1962 EP1962
1960
GREEDY1971
1970
dr hab. inż. Marta Kasprzak, prof. nadzw.
1980
Instytut Informatyki, Politechnika Poznańska
1990 ACO1992
TS1986
GRASP1989
ILS1991
GP1992 PSO1995
2000
GLS1995
2
Genealogia metaheurystyk Klasyfikacja metaheurystyk
Genealogia wg [El-Ghazali Talbi, Metaheuristics: From Design to
Klasyfikacja wg [F. Glover, M. Laguna, Tabu Search, 1997]
Implementation, 2009]  legenda
 uzupełniona
�% LS  local search, jako pierwszy algorytm tego typu zaliczona metoda
simplex [Dantzig 1947], brak wskazania na pierwszą typową metodę LS
Tabu search A / N / 1
�% GA  genetic algorithms, pierwszy zarys metody [Holland, 1962]
Scatter search M / N / P
�% EP  evolutionary programming, pierwszy zarys metody [Fogel, 1962]
Genetic algorithms M / S / P
�% GREEDY  greedy algorithm [Edmonds, 1971]
�% TS  tabu search, pierwszy zarys metody [Glover, 1986]
GRASP M / N / 1
�% GRASP  greedy randomized adaptive search procedures [Feo, Resende,
Ant colony optimization A / S / P
1989]
�% ILS  iterated local search [Martin, Otto, Felten, 1991]; także [Baum, 1986] Particle swarm optimization M / S / P
�% GP  genetic programming [Koza, 1992]
�% ACO  ant colony optimization [Dorigo, 1992] Legenda: A  adaptive memory, M  memoryless
�% GLS  guided local search [Voudouris, Tsang, 1995] N  neighborhood search, S  random sampling
P  population-based, 1  single solution
�% PSO  particle swarm optimization [Eberhart, Kennedy, 1995]
3 4
GRASP GRASP
[T.A. Feo, M.G.C. Resende, Operations Research Letters 8, 1989, Wybór jednego z najbardziej obiecujących elementów
67 71; Journal of Global Optimization 6, 1995, 109 133] dokonywany jest losowo, przez co w każdej iteracji
tej metaheurystyki jest szansa na wygenerowanie
Metaheurystyka GRASP (ang. greedy randomized adaptive
innego rozwiązania początkowego
search procedures) przypomina podejście multistart local
search. W kolejnych iteracjach najpierw konstruowane jest Parametry metaheurystyki:
rozwiązanie początkowe heurystyką zachłanną, następnie
�%
liczba iteracji
jest ono poprawiane metodą przeszukiwania lokalnego
�%
liczność podzbioru najbardziej obiecujących elementów
Heurystyka zachłanna użyta w GRASP różni się
(może zmieniać się w kolejnych iteracjach)
od zwyczajowego podejścia, gdyż zamiast wybierać
�%
ew. inne
w każdym kroku element najbardziej poprawiający
w danym momencie funkcję celu, wybiera jeden z najbardziej
obiecujących elementów
5 6
1
Ogólny schemat metaheurystyki GRASP Evolutionary programming
[L.J. Fogel, Proceedings of IFIPC, Munich 1962, 395 399;
L.J. Fogel, A.J. Owens, M.J. Walsh, Artificial Intelligence
through Simulated Evolution, Wiley, New York 1966]
Evolutionary programming jest metaheurystyką o schemacie
wygenerowanie rozwiązania początkowego
nie zbliżonym do algorytmów genetycznych. Zmienność
probabilistycznym algorytmem zachłannym
osobników opiera się tu jedynie na mutacjach i nie ma
rekombinacji
tak
uruchomienie lokalnego przeszukiwania
warunek
W typowym podejściu każdy rodzic produkuje jednego
aktualizacja najlepszego rozwiązania
stopu
potomka poprzez losową mutację, po czym następną populację
ustala się wybierając połowę najlepszych osobników spośród
połączonej puli rodziców i potomków. Selekcja najlepszych
osobników odbywa się z użyciem metody turniejowej
(ang. tournament selection)
7 8
Evolutionary programming Ogólny schemat metaheurystyki EP
Brak operatora krzyżowania pozwala na dowolny sposób
reprezentacji osobnika, nie musi już być liniowa
Parametry metaheurystyki:
wygenerowanie populacji początkowej
�%
liczba iteracji lub inny warunek stopu
�%
rozmiar populacji
tak
�%
stopień mutacji obliczenie wartości przystosowania
warunek
aktualizacja najlepszego rozwiązania
stopu
�%
rozmiar  drużyny turniejowej
�%
ew. inne
nie
selekcja populacji potomnej mutacja
9 10
Genetic programming Genetic programming
[J. Koza, Genetic Programming, MIT Press, Cambridge, MA, 1992] Przykładowy fragment kodu w języku LISP:
Genetic programming jest metaheurystyką przeznaczoną
do automatycznego generowania programów rozwiązujących
zadany problem. Jej schemat przypomina algorytmy genetyczne,
z tym, że populacja składa się tutaj z zapisanych w postaci
drzew programów komputerowych (podejście używane w AI)
Zapis drzewiasty programów został zaczerpnięty ze struktury
języka programowania LISP. Charakteryzuje się on jednolitą
formą zapisu struktur danych i funkcji w notacji polskiej
nawiasowej (tzw. S-wyrażenia). Funkcja jest listą z nazwą
funkcji jako pierwszym elementem i jej argumentami w dalszej
części listy (ciało funkcji definiowane osobną funkcją). Oprócz
list/funkcji podstawowym elementem składni języka są atomy
(stałe, zmienne)
11 12
2
wikipedia.org
Genetic programming Genetic programming
Przełożenie operacji z programu na postać drzewiastą: Programy składane są z elementów zamieszczonych
w predefiniowanych zbiorach dostępnych funkcji i atomów.
(= (- a b) (define (counter) (set!
Należy zapewnić kompletną z punktu widzenia
(+ c (* 3 d))) count (+ count 1)) count)
rozwiązywanego problemu zawartość tych zbiorów
Populacja początkowa generowana jest w dużej mierze
= define
losowo, zawiera drzewa o różnym kształcie. Wszystkie
wygenerowane programy muszą być wykonywalne
(poprawne syntaktycznie). Liczność populacji powinna
- + counter set! count
być bardzo duża (tysiące osobników)
Parametry tej metaheurystyki i jej schemat są takie same,
a b c * count +
jak w przypadku algorytmów genetycznych, z dodatkowymi
predefiniowanymi zbiorami dostępnych składników kodu
z
ródłowego programu oraz z dopuszczalną głębokością
count 1
3 d
drzewa
13 14
Genetic programming Genetic programming
Należy w szczególny sposób zadbać o poprawność programu, Selekcja w GP odbywa się na podstawie wartości funkcji
utrzymującą się niezależnie od zastosowanych rekombinacji przystosowania. Funkcję tę oblicza się uruchamiając programy
i mutacji, czyli: i porównując wynik z oczekiwanym dla badanych instancji
�%
wszystkie funkcje i argumenty powinny być tego samego Krzyżowanie to zamiana miejscami losowo wybranych
typu (np. liczby całkowite) lub ewentualnie należy zapewnić poddrzew u dwóch osobników w populacji (dwóch programów)
konwersję typów
Mutacja to losowa zmiana w drzewie osobnika
�%
funkcje powinny być dostosowane do przyjęcia dowolnych
Prawdopodobieństwo krzyżowania jest często ustawiane
argumentów i nie powinny zawieść w żadnym przypadku
na wartość mniejszą niż 1 (czyli część osobników przechodzi
(np. w dzieleniu przez 0)  należy w razie potrzeby zapewnić
bez zmian do następnego pokolenia)
zastępczą wartość funkcji
Obecnie implementacje wychodzą poza tradycyjny język LISP,
�%
dopuszczalna głębokość drzewa lub dopuszczalny rozmiar
także dopuszcza się zamianę struktury drzewiastej na grafową
programu nie powinny zostać przekroczone
lub liniową
15 16
Scatter search Scatter search
[F. Glover, Decision Sciences 8, 1977, 156 166; New Ideas in W  rekombinacji uczestniczą jedynie osobniki ze zbioru
Optimization, McGraw-Hill, New York, 1999, 297 316] referencyjnego. Wewnątrz tego zbioru wybór zazwyczaj
nie opiera się już na ich wartości funkcji celu i wszystkie
Scatter search jest metaheurystyką opartą na populacji lecz
osobniki biorą udział w tworzeniu nowych
 w przeciwieństwie do innych tego typu metod  w dużej
mierze wykorzystującą deterministyczne wybory Powyższe może odbywać się na zasadzie doboru wszystkich
możliwych par osobników. Liczba tak stworzonych nowych
Populacja tworzona jest z najlepszych rozwiązań lub ich
osobników może przekroczyć liczność populacji, wtedy
fragmentów, osiągniętych uprzednio przez zastosowanie innej
wybierane są jedynie najlepsze z nich, z dodatkowym
heurystyki/metaheurystyki. Powinna charakteryzować się
wymogiem na zachowanie różnorodności populacji
dużym zróżnicowaniem osobników. Osobniki nie muszą
tworzyć rozwiązań dopuszczalnych Więcej niż dwa osobniki mogą zostać wybrane do rekombinacji.
Rekombinacja może wyprodukować jednego lub większą
Dodatkowo tworzony jest zbiór referencyjny (ang. reference
liczbę nowych osobników
set), który zawiera wybrane z populacji najlepsze rozwiązania
Nowe rozwiązania są następnie poprawiane heurystyką
Rozmiar zbioru referencyjnego jest niewielki (nie większy
i zastępują te ze zbioru referencyjnego, jeśli są od nich lepsze
niż 20), populacja jest zazwyczaj ok. 10 razy liczniejsza
17 18
3
Scatter search Ogólny schemat metaheurystyki SS
Scatter search jest tradycyjnie łączony z metaheurystyką tabu
search i z inną metodą tego samego autora, path relinking.
Wszystkie preferują determinizm nad losowością
wygenerowanie populacji początkowej
Parametry metaheurystyki:
�%
liczba iteracji lub inny warunek stopu
tak
�%
rozmiar populacji
poprawa osobników heurystyką
warunek
�% aktualizacja najlepszego rozwiązania
rozmiar zbioru referencyjnego stopu
�%
parametry heurystyki/metaheurystyki używanej
do poprawy osobników z populacji
wybór nie
krzyżowanie selekcja
�%
ew. inne podzbiorów
19 20
Ant colony optimization Ant colony optimization
[M. Dorigo, Optimization, learning and natural algorithms, PhD Mrówki poprzez komunikację pomiędzy sobą odnajdują
thesis, Politecnico di Milano, 1992] najkrótszą drogę do pożywienia, dotyczy to także gatunków
o słabym wzroku. Idąc, pozostawiają ślad feromonowy, który
Ant colony optimization jest najbardziej znaną metaheurystyką
wskazuje kolejnym mrówkom trasę. Im większe stężenie
z grupy metod opartych na inteligencji zbiorowej (inteligencji
feromonów na trasie, tym większe prawdopodobieństwo,
roju, ang. swarm intelligence). Odzwierciedla zachowanie
że kolejna mrówka ją wybierze. Z czasem ślad słabnie
kolonii mrówek w procesie zdobywania pożywienia. Inne
metody z tej grupy to np. bee colony optimization i particle Dla dwóch tras pomiędzy dwoma punktami, dłuższej i
swarm optimization krótszej, prawdopodobieństwo ich wyboru przez mrówki
jest początkowo takie same. Po dojściu do celu mrówki
Zaobserwowano, że połączone działanie prostych obiektów
wracają wybraną wcześniej trasą. Przejście trasy krótszej
przekazujących sobie informacje może zostać z sukcesem
wymaga mniej czasu, w dłuższym okresie więcej mrówek
wykorzystane do rozwiązywania problemów optymalizacyjnych.
zdąży więc zostawić na niej swój ślad. Dodatkowo na krótszej
Ruch obiektów w naturze odpowiada w algorytmie
trasie mniejsza ilość feromonu zdąży się ulotnić
przemieszczaniu się w przestrzeni rozwiązań
21 22
Ant colony optimization Ant colony optimization
Zachowanie mrówek w algorytmie imituje losowa heurystyka Ścieżka feromonowa jest rodzajem pamięci w algorytmie,
zachłanna. Przestrzeń rozwiązań problemu jest modelowana magazynuje zdobytą przez mrówki wiedzę
w postaci grafu, w którym ścieżka odpowiada trasie mrówki.
Ulatnianie się feromonu jest realizowane poprzez zastosowanie
Wierzchołkami są elementy składowe rozwiązania
w każdej iteracji wzoru:
Mrówka konstruuje rozwiązanie krok po kroku, wybierając
�ij = (1 �)�ij , "�i,j �� [1,n]
następny wierzchołek ścieżki w oparciu o ślad krawędzi
gdzie ���[0,1] jest współczynnikiem redukcji feromonu,
wychodzących z bieżącego wierzchołka. Przykładowo, można
a �ij jest śladem krawędzi pomiędzy wierzchołkami i oraz j
zastosować prawdopodobieństwo wyboru opisane wzorem:
Wzmocnienie feromonu może zostać zrealizowane przez
pij = �ij/(S�k��S �ik), "�j��S
zastosowanie różnych strategii, np. po przejściu całej ścieżki
gdzie i oraz j to odpowiednio wierzchołek bieżący i rozważany,
przez dodanie wartości proporcjonalnej do jakości rozwiązania,
�ij jest feromonowym śladem krawędzi (i,j), a S jest zbiorem
albo po przejściu wszystkich ścieżek w danej iteracji przez
wierzchołków spoza bieżącej ścieżki. Stosując np. metodę ruletki
uaktualnienie wartości tylko k najlepszych ścieżek
losuje się następnika bieżącego wierzchołka. Okresowo można
dopuścić zupełnie losowy wybór
23 24
4
Ant colony optimization Ogólny schemat metaheurystyki ACO
Parametry metaheurystyki:
�%
liczba iteracji lub inny warunek stopu
�%
liczba mrówek
zainicjalizowanie ścieżek feromonowych
�%
współczynniki redukcji i wzmocnienia feromonu,
ew. liczba k najlepszych ścieżek
tak
�%
ew. inne konstrukcja rozwiązań dla każdej mrówki
warunek
aktualizacja najlepszego rozwiązania
stopu
aktualizacja ścieżek feromonowych nie
(wzmocnienie lub osłabienie feromonu)
25 26
Particle swarm optimization Particle swarm optimization
[J. Kennedy, R.C. Eberhart, Proceedings of IEEE International W podstawowym modelu każda z N cząsteczek (potencjalnych
Conference of Neural Networks, Perth, 1995, 1942 1948] rozwiązań) porusza się w D-wymiarowej przestrzeni rozwiązań.
Ruch cząsteczek opisany jest ich położeniem (wektor xi)
Particle swarm optimization jest kolejną metaheurystyką
i prędkością (wektor vi wskazujący także kierunek/zwrot)
z grupy swarm intelligence. Odzwierciedla sposób poruszania
się obiektów w grupie (zwierząt w stadzie) w sposób Sąsiedztwo jest definiowane dla każdej cząsteczki w celu
skoordynowany i bez centralnego sterowania. Przykładami określenia wpływu otoczenia. W zależności od zastosowanego
tego typu ruchów może być lot ptaków w stadzie lub ruch podejścia, może obejmować cały zbiór, dużą część zbioru
ryb w ławicy w poszukiwaniu pożywienia lub jedynie najbliższych sąsiadów
Potencjalne rozwiązania są w PSO nazywane cząsteczkami Cząsteczki zmieniają położenie w kierunku globalnego
(ang. particles). Trajektoria najlepszych w danym momencie optimum na podstawie informacji o najlepszym swoim
cząsteczek wyznacza trasę pozostałym. Wartość cząsteczki własnym położeniu pi oraz najlepszym położeniu pg spośród
mierzona jest funkcją przystosowania osiągniętych przez wszystkie cząsteczki z sąsiedztwa
27 28
Particle swarm optimization Particle swarm optimization
Prędkość cząsteczki vi jest uaktualniana następującym wzorem: Położenie cząsteczki xi jest uaktualniane następującym wzorem:
vi = vi2 + �1C1 �� (pi  xi2 ) + �2C2 �� (pg  xi2 ) xi = xi2 + vi
gdzie vi2 oznacza poprzednią prędkość, xi2 poprzednie
W każdej iteracji uaktualniane są także wartości pi oraz pg
położenie, �1 i �2 losowe wartości z przedziału [0,1], a C1 i C2
PSO jest metodą dedykowaną głównie problemom
to stałe współczynniki uczenia się (ang. learning factors;
optymalizacji ciągłej. W przypadku problemów
wskazują, czy cząsteczka podąży raczej za własnym sukcesem,
kombinatorycznych należy zadbać o to, żeby nowe położenie
czy sukcesem swoich sąsiadów)
odpowiadało wartościom akceptowalnym w problemie.
Prędkość obliczana powyższym wzorem podlega korekcie,
Nie zawsze jest to łatwe  jeśli N-wymiarowym wektorem
jeśli przekroczy zdefiniowany wcześniej dopuszczalny zakres
opisującym położenie cząsteczki w przestrzeni rozwiązań
wartości. Także można zwiększyć wpływ poprzedniej wartości
byłaby permutacja N elementów, nie wystarczy zaokrąglić
vi2 przez umieszczenie we wzorze tzw. współczynnika inercji
wartości w tym wektorze do najbliższych całkowitych
w (wvi2 )
29 30
5
Particle swarm optimization Ogólny schemat metaheurystyki PSO
Aby rozwiązać problem kombinatoryczny, można zastosować
odmianę metaheurystyki, w której aktualizacja wektorów
odbywa się na zasadzie krzyżowania jak w algorytmach
losowe zainicjalizowanie zbioru cząsteczek
genetycznych. Można także zastąpić wektor prędkości listą
dopuszczalnych ruchów, stosowanych po kolei do wektora
położenia
tak
obliczenie wartości przystosowania
warunek
Parametry metaheurystyki:
aktualizacja najlepszego rozwiązania
stopu
�%
liczba iteracji lub inny warunek stopu
�%
liczba cząsteczek
aktualizacja prędkości, położenia nie
�%
rozmiar sąsiedztwa
oraz wartości pi , pg cząsteczek
�%
współczynniki uczenia się, współczynnik inercji
�%
dopuszczalny zakres wartości prędkości
�%
ew. inne
31 32
Heurystyki hybrydowe Literatura  cd.
Mianem heurystyki hybrydowej określa się algorytm złożony Fred Glover, Gary A. Kochenberger (ed.), Handbook of
z połączenia dwóch lub więcej klasycznych podejść Metaheuristics, Kluwer Academic Publishers, Boston, 2003.
heurystycznych (także z użyciem algorytmów dokładnych)
Często stosowanymi połączeniami są np.:
�%
algorytm genetyczny z heurystyką zachłanną
�%
algorytm genetyczny z lokalnym przeszukiwaniem
�%
tabu search i scatter search
�%
PSO z GA
�%
ACO z PSO
�%
algorytmy populacyjne z losową heurystyką zachłanną
�%
heurystyki z algorytmami dokładnymi
33 34
6