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

Rok akademicki 2008/09

Instrukcja do ćwiczeń laboratoryjnych

Temat

Algorytmy genetyczne

Opracował: dr inż. G. Urbanek

- 1/6 -

1. Cel ćwiczenia

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

zastosowaniem.

2. Wprowadzenie teoretyczne

Poszukiwanie rozwiązania optymalnego według algorytmu genetycznego odbywa się poprzez

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

netycznych. Zbiór elementów (osobników) w danej chwili czasu 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. Każdy element (osobnik) zawiera

informację stanowiącą jego genotyp, który jest przepisem na utworzenie w wyniku oddziaływa-

nia środowiska fenotypu, czyli zbioru cech, na podstawie których funkcja oceniająca (funkcja

przystosowania), określa przystosowanie osobnika. Celem algorytmu genetycznego jest mak-

symalizacja funkcji przystosowania, tzn. rozwiązaniem optymalnym jest osobnik o największej

wartości funkcji przystosowania.

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 (poszukiwaniu

maksimum) funkcji f, genotypem osobnika są współrzędne punktu, fenotypem jest wartość

funkcji f w tym punkcie. Wartość funkcji przystosowania jest wyliczana 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:

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

- 2/6 -

• podstawowej reprezentacji potencjalnych rozwiązań zadania,

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

- 3/6 -

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ę 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, zwana również metodą ruletki (nazwa pochodzi od najprostszej

realizacji algorytmicznej tego operatora), jest procesem, w którym chromosomy zostają

powielone w stosunku 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 polega na powtarzaniu dwóch kroków: losowania par osobników wg

metody ruletki, po wylosowaniu pary, osobnik o wyższym przystosowaniu zostaje ogło-

szony zwycięzcą i umieszczony w nowej populacji; proces jest kontynuowany aż do cał-

kowitego wypełnienia populacji.

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 chromosomó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) 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

- 4/6 -

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;

• rekombinacja puli genów: kilku rodziców tworzy jednego potomka w ten sposób, że

kolejne geny potomka są wybierane losowo z puli genów wybranych rodziców;

• krzyżowanie arytmetyczne definiuje się jako liniową kombinację dwóch wektorów: jeżeli

krzyżowaniu mają podlegać r

1

i r

2

, to potomkowie wyznaczani są następująco: d

1

=

ar

1

+ (1 − a)r

2

oraz d

2

= ar

2

+ (1 − a)r

1

; wartość a dobiera się losowo z przedziału

[0,1];

• krzyżowanie uśredniające jest operatorem przeznaczonym dla reprezentacji liczbowej;

w metodzie tej wartość każdego genu chromosomu potomnego jest liczbą zawierającą

się między największą i najmniejszą wartością genu chromosomów rodzicielskich. Jeśli

krzyżowanie uśredniające przebiega zgodnie ze schematem, że z pary chromosomów ro-

dzicielskich powstaje para potomnych, wówczas chromosomy potomne będą symetryczne

względem środka odcinka łączącego chromosomy rodzicielskie.

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.

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,

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

- 5/6 -

2.7. Parametry algorytmu genetycznego

Tradycyjnie algorytmy genetyczne, operują na populacji, której liczebność w czasie optymaliza-

cji nie zmienia się. Można 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”.

Tak więc wiek chromosomu pozwala na szczególne definiowanie pojęcia selekcji i, ponieważ

zależy on od dopasowania osobnika, wpływa na liczebność populacji w każdym kroku proce-

su [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. Przygotowanie do ćwiczenia

Przygotowanie do ćwiczenia obejmuje szczegółowe zapoznanie się z niniejszą instrukcją. W cza-

sie ćwiczenia zostanie przedstawione, na prostym przykładzie, działanie algorytmu genetycz-

nego; zostanie sprawdzone przygotowanie studentów do zajęć.

4. Przykłady do samodzielnego rozwiązania

Opracować algorytm genetyczny do optymalizacji funkcji dwóch zmiennych. Zastosować ko-

dowanie liczbowe z liniowo ułożonymi genami w chromosomie.

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/6 -