Katedra

Podstaw

Konstrukcji

Maszyn

Wydział

Mechaniczny

Technologiczny

Politechnika

Śląska

ul. Konarskiego 18a

44-100 Gliwice

tel. [phone]

fax. [phone]

http://kpkm.polsl.pl

Metody Sztucznej

Inteligencji

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

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ę z P[t-1]

n najlepszych chromosomów: P

n

[t-1], następnie populacja P[t] jest tworzona przez

wybór m najlepszych osobników ze złączenia P

n

[t-1]∪P

m

[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ętli while (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 ewolucyjne http: // www. eioba. pl/ a/ 7t/ algorytmy-ewolucyjne

[8] Życie, modelowanie, symulacja http: // www. alife. pl/ dummies/ p/ index. html

MSI-AG-R

Gliwice 2011-03-29

- 7/7 -