Katedra
Podstaw
Konstrukcji
Maszyn
Wydział
Mechaniczny
Technologiczny
Metody Sztucznej
Politechnika
Inteligencji
Śląska
Kierunek studiów AiR, semestr IV
Prowadzący przedmiot
dr inż. Krzysztof Ciupke
Rok akademicki 2010/11
Temat:
Algorytmy ewolucyjne. Zadanie
optymalizacji.
Opracował: dr inż. G.Urbanek, dr inż. P.Chrzanowski
ul. Konarskiego 18a
44-100 Gliwice
tel. [phone]
fax. [phone]
http://kpkm.polsl.pl
MSI-AG-R Gliwice 2011-03-29 - 1/7 -
1. Cel ćwiczenia
Celem ćwiczenia jest zapoznanie się z algorytmami genetycznymi oraz z ich praktycznym
zastosowaniem w szczególności w zagadnieniach optymalizacji.
2. Wprowadzenie teoretyczne
Algorytmy ewolucyjne (ang. Evolutionary Algorithms), służą do przeszukiwania przestrzeni
alternatywnych rozwiązań problemu w celu odnalezienia rozwiązań najlepszych lub potencjal-
nie najlepszych. Zalicza się je do klasy algorytmów heurystycznych. Przeszukiwanie odbywa
się za pomocą mechanizmów ewolucji oraz doboru naturalnego poprzez odpowiednie prze-
kształcanie zbioru elementów (osobników) za pomocą tzw. operatorów genetycznych. Zbiór
elementów (osobników) nazywany jest pokoleniem. Zbiór ten przekształcony za pomocą opera-
torów genetycznych stanowi kolejne pokolenie. Działania te powtarzane są w sposób iteracyjny.
Elementy (osobniki) przekształcanego zbioru należą do przestrzeni zadania i są potencjalnymi
rozwiązaniami. Celem algorytmu genetycznego jest wyszukanie osobnika najlepiej spełniające-
go kryterium określonego w funkcji oceniającej.
Genotyp osobnika składa się z chromosomów (najczęściej jednego), które składają się z
elementarnych części, zwanych genami. Przykładowo, w zadaniu optymalizacji funkcji f, ge-
notypem osobnika są współrzędne punktu, fenotypem jest wartość funkcji f w tym punkcie.
Wartość funkcji oceniającej wyliczana jest na podstawie fenotypu.
Ogólną postać algorytmu genetycznego przedstawia rys. 1.
Przeprowadzenie optymalizacji za pomocą algorytmu genetycznego wymaga określenia na-
stępujących elementów:
" reprezentacji potencjalnych rozwiązań zadania,
Rys. 1: Podstawowy algorytm genetyczny; oznaczenia: t  czas (licznik kroków), P  populacja,
R  rodzice, D  dzieci [5], [3]
MSI-AG-R Gliwice 2011-03-29 - 2/7 -
" sposobu tworzenia początkowej populacji potencjalnych rozwiązań,
" funkcji oceniającej,
" sposobu prowadzenia selekcji i sukcesji,
" sposobu prowadzenia reprodukcji (operatory krzyżowania i mutacji),
" wartości różnych parametrów używanych w algorytmie genetycznym (rozmiar populacji,
prawdopodobieństwa użycia operatorów genetycznych itp.).
2.1. Reprezentacja potencjalnych rozwiązań zadania
Metody reprezentacji elementów przestrzeni (nazywanych osobnikami), w której poszukiwane
jest rozwiązanie optymalne można podzielić na dwie grupy [3]:
1. z chromosomami, w których geny są ułożone liniowo,
2. z chromosomami, w których geny są złożonymi strukturami.
Powszechnie w algorytmach genetycznych stosowane są chromosomy z liniowo ułożonymi
genami kodowanymi binarnie. Wartości wszystkich cech (genów) każdego osobnika zostają
przedstawione za pomocą liczb binarnych;  sklejone razem stanowią chromosom. Reprezen-
tacja ta ułatwia analizę teoretyczną i umożliwia wprowadzenie bardzo prostych operatorów
genetycznych. Główną jej wadą jest bardzo duża długość chromosomu dla wielowymiarowych
zadań wymagających dużej dokładności, co prowadzi do bardzo dużej liczebności przestrzeni
przeszukiwania [5].
Innym sposobem jest zapis wartości cech (genów) w postaci dziesiętnej. Chromosom ma
wtedy postać macierzy liczb, każda liczba jest wartością jednej z rozpatrywanych cech. Taki
zapis eliminuje konieczność kodowania chromosomów (przestrzeń reprezentacji jest przestrze-
nią zadania). Stosowanie chromosomów, będących złożonymi strukturami genów, wymaga
opracowania odpowiednich operatorów genetycznych.
2.2. Generowanie rozwiązania początkowego
Populacja początkowa najczęściej (chyba że są uzasadnione podstawy, żeby postąpić inaczej)
generowana jest w sposób losowy. W przypadku kodowania binarnego losuje się wartość każdego
genu i w ten sposób tworzy się całą populację. W przypadku kodowania liczbowego, wartość
każdego genu jest losowana z przedziału zmienności wartości cechy, którą on reprezentuje.
2.3. Funkcja oceniająca
Funkcja oceniająca jest jednym z najważniejszych elementów warunkujących skuteczne działa-
nie algorytmu genetycznego. Nieodpowiednia funkcja oceniająca prowadzi do błędnego działa-
nia. Niestety, nie istnieje ogólny  przepis na opracowanie dobrej funkcji oceniającej. Funkcję
taką zwykle wyznacza się indywidualnie do danego zadania.
MSI-AG-R Gliwice 2011-03-29 - 3/7 -
2.4. Selekcja i sukcesja
Selekcja określa sposób wyłaniania z rozpatrywanej populacji zbioru rodziców, który poddawany
działaniu operacji genetycznych, daje zbiór dzieci. Sukcesja wyznacza dla pokolenia rodziców
i potomków nową populację bazową dla kolejnego kroku algorytmu genetycznego.
Przykłady metod selekcji:
" selekcja proporcjonalna: jest procesem, w którym chromosomy zostają powielone w sto-
sunku zależnym (wprost proporcjonalnie) od wartości, jakie przybiera dla nich funkcja
oceniająca; stosowanie tej metody jest możliwe tylko wtedy, gdy funkcja oceniająca
przyjmuje wyłącznie wartości dodatnie;
" selekcja turniejowa: populację dzieli się na szereg dowolnie licznych grup. Następnie z
każdej z nich wybieramy osobnika o najlepszym przystosowaniu.
Przykłady metod sukcesji:
" sukcesja trywialna polega na tym, że nową populacją staje się zbiór dzieci:P[t]:=D[t];
" sukcesja elitarna przeprowadzana jest w dwóch krokach: najpierw wybiera się zP[t-1]
n najlepszych chromosomów:Pn[t-1], następnie populacjaP[t]jest tworzona przez
wybór m najlepszych osobników ze złączeniaPn[t-1]*"Pm[t].
2.5. Reprodukcja
Na reprodukcję składają się dwa operatory: krzyżowania i mutacji.
Najczęściej przyjmuje się, że w krzyżowaniu biorą udział dwa osobniki rodzicielskie, w wy-
niku otrzymuje się jeden lub dwa osobniki potomne.
Przykłady metod krzyżowania:
" krzyżowanie proste (jednopunktowe) przebiega w dwóch etapach: w pierwszej fazie koja-
rzy się w sposób losowy ciągi z puli rodzicielskiej w pary. Następnie każda para przechodzi
proces krzyżowania. Odbywa się to następująco: wybiera się w sposób losowy (z jednako-
wym prawdopodobieństwem) punkt krzyżowania k spośród l - 1 początkowych pozycji
w chromosomie, po czym zamienia się miejscami wszystkie znaki od pozycji k + 1 do
l włącznie w obu elementach pary, tworząc w ten sposób dwa nowe ciągi;
" krzyżowanie wielopunktowe przebiega analogicznie jak krzyżowanie jednopunktowe, z tą
różnicą, że wybiera się więcej niż jeden punkt cięcia;
" krzyżowanie jednorodne przebiega następująco: dla każdego bitu pierwszego potomka
decyduje się (z pewnym prawdopodobieństwem), od którego z rodziców pobierze się
wartość, drugi potomek otrzymuje bit od pozostałego rodzica;
" inne.
MSI-AG-R Gliwice 2011-03-29 - 4/7 -
Rys. 2: Przykład krzyżowania prostego
Przykłady metod mutacji:
" mutacja równomierna zmienia jeden lub więcej bitów na przeciwny z określonym praw-
dopodobieństwem;
" mutacja nierównomierna uwzględnia wiek populacji: wraz ze wzrostem wieku populacji
bity znajdujące się bardziej na prawo w sekwencji kodu chromosomu otrzymują większe
prawdopodobieństwo mutacji, znajdujące się zaś na lewo mniejsze;
" mutacja  rzeczywistoliczbowa stosowana jest wtedy, jeśli geny przyjmują wartości ze
zbioru liczb rzeczywistych, i polega na perturbacji wartości genu przez dodanie liczby
wygenerowanej w sposób losowy.
Rys. 3: Przykład mutacji równomiernej
2.6. Warunki zakończenia działania algorytmu genetycznego
Można określić dwa warunki zakończenia działania algorytmu genetycznego:
" algorytm działa do momentu osiągnięcia osobnika o określonym przystosowaniu wyzna-
czanym wg funkcji oceniającej,
" kolejne kroki w pętliwhile(por. rys. 1 wykonywane są zadaną liczbę razy.
Najczęściej stosuje się obydwa warunki jednocześnie. Algorytm kończy działania, gdy zo-
stanie spełniony jeden z nich.
2.7. Parametry algorytmu genetycznego
Tradycyjnie algorytmy genetyczne, operują na populacji, której liczebność w czasie optyma-
lizacji nie zmienia się. Można również zastosować algorytm genetyczny ze zmienną liczebno-
ścią populacji. Algorytm ten nie zawiera żadnej odmiany mechanizmu selekcji, ale wprowadza
pojęcie  wieku chromosomu, co jest równoważne liczbie pokoleń, przez które chromosom
pozostaje  żywy [5].
MSI-AG-R Gliwice 2011-03-29 - 5/7 -
Nie ma zaleceń co do doboru wartości prawdopodobieństwa krzyżowania i mutacji, najczę-
ściej dokonuje się tego doświadczalnie. Zwykle prawdopodobieństwo krzyżowania zawiera się
w przedziale [0,25; 0,75], zaś prawdopodobieństwo mutacji w przedziale [0,005; 0,05].
3. Zadanie do wykonania
Przeprowadzić optymalizację z użyciem pakietu genalg [6] w środowisku R, polegającą na
znalezieniu maksimum globalnego funkcji o postaci podanej przez prowadzącego.
W tym celu należy m.in.:
1. Narysować wykres podanej funkcji w ustalonym przedziale,
2. Opracować funkcję oceniającą (evaluate),
3. Stosując funkcję evaluate przeprowadzić optymalizację poszukując maksimum globalne-
go dla wskazanej funkcji,
4. Przedstawić uzyskane wyniki w postaci graficznej,
5. Zweryfikować parametry algorytmu genetycznego jak: rozmiar populacji, liczba iteracji,
parametry mutacji,
6. Przeprowadzić obliczenia dla innych konfiguracji parametrów,
7. Dokonać analizy uzyskanych wyników,
8. Opracować zwięzłe sprawozdanie, zawierające uzyskane wyniki oraz wnioski określające
wpływ przyjętych parametrów na wyniki.
4. Przykład w środowisku R [6]:
# funkcja oceniająca dopasowanie do pi oraz sqrt(50)
evaluate <- function(string=c()) {
returnVal = NA;
if (length(string) == 2) {
returnVal = abs(string[1]-pi) + abs(string[2]-sqrt(50));
} else {
stop("Wprowadzono błędną długość chromosomu.");
}
returnVal
}
# algorytm genetyczny dla ustalonych parametrów
rbga.results = rbga(c(1, 1), c(5, 10),
evalFunc=evaluate, verbose=TRUE, mutationChance=0.01)
# prezentacja wyników algorytmu genetycznego
plot(rbga.results)
plot(rbga.results, type="hist")
plot(rbga.results, type="vars")
MSI-AG-R Gliwice 2011-03-29 - 6/7 -
Literatura
[1] Arabas J.: Algorytmy ewolucyjne: przegląd tematyki. AI-Mech 2000, Materiały konferen-
cyjne, Gliwice 2000, s. 3 23.
[2] Arabas J.: Wykłady z algorytmów genetycznych. WNT, Warszawa, 2001.
[3] Cholewa W.: Wykład z przedmiotu metody heurystyczne. Materiały niepublikowane,
Gliwice, 2001.
[4] Goldberg D.E.: Algorytmy genetyczne i ich zastosowania. WNT, Warszawa, 1998.
[5] Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne.
WNT, Warszawa, 1999.
[6] Willighagen E.: genalg: R Based Genetic Algorithm.http://cran.r-project.org/
[7] Algorytmy ewolucyjnehttp://www.eioba.pl/a/7t/algorytmy-ewolucyjne
[8] Życie, modelowanie, symulacjahttp://www.alife.pl/dummies/p/index.html
MSI-AG-R Gliwice 2011-03-29 - 7/7 -