lab4.pdf

Katedra

Podstaw

Konstrukcji

Maszyn

Wydział

Mechaniczny

Technologiczny

MetodySztucznej

Inteligencji

Politechnika

l¡ska

Instrukcja do ¢wicze« laboratoryjnych

wiczenie 4

Temat

Algorytmygenetyczne

Opracował: dr in». G. Urbanek

ul.Konarskiego18a

44-100Gliwice

tel.2371467

fax.2371360

https://kpkm.polsl.pl

- 1/6 -

1.Cel¢wiczenia

Celem ¢wiczenia jest zapoznanie si¦ z algorytmami genetycznymi oraz z ich praktycznym

zastosowaniem.

2.Wprowadzenieteoretyczne

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.Reprezentacjapotencjalnychrozwi¡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.Generowanierozwi¡zaniapocz¡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.Funkcjaoceniaj¡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.Selekcjaisukcesja

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 deﬁniuje 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.Warunkizako«czeniadziałaniaalgorytmugenetycznego

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 -

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: