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 2009/10

Temat:

Środowisko obliczeniowe R: Algorytmy
genetyczne

Opracował: dr inż. G.Urbanek, dr inż. P.Chrzanowski

MSI-AG-R

Gliwice 2010-04-20

- 1/7 -

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się z algorytmami genetycznymi oraz z ich praktycznym

zastosowaniem.

2. Wprowadzenie teoretyczne

Poszukiwanie rozwiązania optymalnego z zastosowaniem algorytmu genetycznego odbywa się

poprzez odpowiednie przekształcanie zbioru elementów (osobników) za pomocą tzw. opera-

torów genetycznych. Zbiór elementów (osobników) w danej chwili nazywany jest pokoleniem.

Zbiór ten przekształcony za pomocą operatorów genetycznych stanowi kolejne pokolenie. Prze-

kształcenie takie wykonuje się n-razy. Elementy (osobnicy) przekształcanego zbioru należą do

przestrzeni zadania i są potencjalnymi rozwiązaniami. Celem algorytmu genetycznego jest wy-

szukanie osobnika spełniającego minimum bądź maksimum 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 jast na podstawie fenotypu.

Istotę działania algorytmu genetycznego przedstawia rys. 1.

Przeprowadzenie optymalizacji za pomocą algorytmu genetycznego wymaga określenia na-

stępujących elementów:

• podstawowej reprezentacji potencjalnych rozwiązań zadania,

• sposobu tworzenia początkowej populacji potencjalnych rozwiązań,

• funkcji oceniającej,

Rys. 1: Podstawowy algorytm genetyczny; oznaczenia: t – czas (licznik kroków), P – populacja,
R – rodzice, D – dzieci [5], [3]

MSI-AG-R

Gliwice 2010-04-20

- 2/7 -

• 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. chromosomy z liniowo ułożonymi genami:

• kodowanie binarne,

• kodowanie liczbowe,

• kodowanie specjalne,

2. chromosomy będące złożonymi strukturami genów (np. drzewa)

• kodowanie binarne, liczbowe, specjalne.

Powszechnie w algorytmach genetycznych stosowane są chromosomy z liniowo ułożony-

mi genami kodowanymi binarnie. Wartości wszystkich cech (geny) każdego osobnika zostają

przedstawione za pomocą liczb dwójkowych; „sklejone” razem stanowią chromosom. Repre-

zentacja 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

bitu chromosomu (łańcucha binarnego) 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.

MSI-AG-R

Gliwice 2010-04-20

- 3/7 -

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ę metodą „prób i błędów” indywidualnie do konkretnego zadania.

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,

• selekcja turniejowa

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]∪[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)

• krzyżowanie wielopunktowe

• krzyżowanie jednorodne

• inne.

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;

MSI-AG-R

Gliwice 2010-04-20

- 4/7 -

• 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.

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,

• pętla while jest wykonywana 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].

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: f (x) = 10 − (sin((0.75x)

2

) + abs(x)), w

przedziale < −5; 5 >.

W tym celu należy m.in.:

1. Narysować wykres podanej funkcji w ustalonym przedziale,

2. Opracowac funcję oceniającą (evaluate),

3. Stosujac funkcję evaluate przeprowadzić optymalizację puszukują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,

MSI-AG-R

Gliwice 2010-04-20

- 5/7 -

Rys. 2: Optymalizowana funkcja

7. Dokonać analizy uzyskanych wyników,

8. Opracować zwiezłe sprawozdanie, zawierajace uzyskane wyniki oraz wnioski określające

wpływ przyjętych parametrów na wyniki.

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")

Literatura

[1] Arabas J.: Algorytmy ewolucyjne: przegląd tematyki. AI-Mech 2000, Materiały konferen-

cyjne, Gliwice 2000, s. 3–23.

MSI-AG-R

Gliwice 2010-04-20

- 6/7 -

[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/,

MSI-AG-R

Gliwice 2010-04-20

- 7/7 -