1

(c)

DS, JW

Wyklad 11, str. 1

•

Z. Michalewicz. Algorytmy genetyczne + struktury danych =

programy ewolucyjne.

• D.E. Goldberg. Algorytmy genetyczne i ich zastosowania.

WNT, Warszawa 1995.

• J.R. Koza. Genetic Programming: On the Programming of

Computers by Means of the Natural Selection.

The MIT Press,

1992.

Algorytmy ewolucyjne

1958 (Friedberg) - pierwsze prace zwiazane z programowaniem ewolucyjnym.
1964 (Fogel) - pierwsze prace zwiazane z programowaniem ewolucyjnym automatów
skonczonych zakonczone wzglednym sukcesem.
1965 (Bienert, Rechenberg, Schwefel) - pierwsza wersja strategii ewolucyjnych, pierwsze
zastosowania praktyczne.
1973 (Rechenberg) - podstawy teoretyczne strategii ewolucyjnych.
1975 (Holland) - algorytmy genetyczne i ich teoria.
Lata 80-te - liczne zastosowania algorytmów genetycznych.
Koniec lat 80-tych (Fogel) - poczatek rozwoju wspólczesnej wersji programowania
ewolucyjnego.

(c)

DS, JW

Wyklad 11, str. 2

Podstawowe pojecia

Osobnik - podstawowa jednostka podlegajaca ewolucji. Zakladamy zwykle,
ze ów osobnik przebywa w pewnym srodowisku, do którego moze byc lepiej
lub gorzej przystosowany. “Celem” ewolucji jest stworzenie osobnika
mozliwie dobrze przystosowanego do danego srodowiska.
Fenotyp - ujawniajace sie “na zewnatrz” cechy danego osobnika.
Genotyp - “plan konstrukcyjny”, kompletny i jednoznaczny opis osobnika
zawarty w jego genach.
Populacja - zespól osobników zamieszkujacych wspólne srodowisko i
konkurujacych o jego zasoby.

...-ATC-GCA-GGG-
AGC-ACT-GTT-...

...-ATC-GAA-GGG-
AGC-ACA-GTT-...

Fenotyp

Genotyp

2

(c)

DS, JW

Wyklad 11, str. 3

•

Genotyp danego osobnika w czasie jego zycia nie ulega zmianie, natomiast

ulega on modyfikacjom podczas rozmnazania sie. Zmiany te moga wynikac albo
z niewielkich, losowych mutacji, albo ze zmieszania (skrzyzowania) cech
osobników rodzicielskich.

• Zmiany w genotypie powoduja zmiany fenotypu osobników potomnych, co

wplywa na stopien ich przystosowania do srodowiska. Zmiany fenotypu (nabyte
przez osobnika) nie podlegaja dziedziczeniu w sensie genetycznym.

• Zmiany w genotypie maja charakter przypadkowy. Zmiany korzystne dla

osobnika zdarzaja sie równie czesto, jak niekorzystne lub obojetne.

• Osobniki sa oceniane poprzez porównanie ich przystosowania do danego

srodowiska. Te, które sa lepiej przystosowane, maja wieksza szanse rozmnozyc
sie. Osobniki gorzej przystosowane przegrywaja konkurencje o ograniczone
zasoby srodowiska i gina.

Zmianom (mutacja, krzyzowanie) podlega genotyp osobnika,
podczas gdy selekcji poddawane sa fenotypy. Istota ewolucji jest
polaczenie zjawiska losowych, nieukierunkowanych zmian
genotypu ze scisle ukierunkowana presja srodowiska na fenotyp.

(c)

DS, JW

Wyklad 11, str. 4

Strategie ewolucyjne

Glówny obszar zastosowan: optymalizacja funkcji rzeczywistych
wielowymiarowych.

Zadanie: znalezc maksimum funkcji f : R

n

? R na danym przedziale

[a

1

, b

1

]

? ...? [a

n

, b

n

].

Rozwiazanie: przez x=(x

1

, ... x

n

) oznaczmy przykladowe rozwiazanie

(punkt z przestrzeni stanów, x

i

? [a

i

, b

i

]). Kazdemu wektorowi x

przyporzadkujmy pomocniczy wektor wartosci rzeczywistych dodatnich:

?

=(

?

1

, ...

?

n

). Para (x,

?

) bedzie stanowila kod genetyczny osobnika.

x

f(x)

(x,

?

)

Fenotyp osobnika

Genotyp osobnika

3

(c)

DS, JW

Wyklad 11, str. 5

Strategie ewolucyjne - schemat dzialania

1. Tworzymy losowa populacje zlozona z N osobników postaci (x,

?

).

2. Dopisujemy do niej M osobników potomnych, tworzonych na

podstawie losowo wybranych osobników z poprzedniego pokolenia
za pomoca mutacji i procesu krzyzowania.

3. Dla kazdego osobnika w populacji posredniej (N+M osobników)

liczymy odpowiadajaca mu wartosc optymalizowanej funkcji.

4. Sposród N+M osobników wybieramy te, które przezyja i utworza

nastepne pokolenie. W tym celu sortujemy osobniki wzgledem
odpowiadajacych im wartosci funkcji f i wybieramy N najlepszych.

5. Powtarzamy od punktu 2. z aktualna populacja N-osobnikowa.

N

N

M

N

f(x)

...
...

f(x)

Poprzednie

pokolenie

Nastepne
pokolenie

bez zmian

mutacje,
krzyzowanie

wybór N najlepszych

(c)

DS, JW

Wyklad 11, str. 6

Strategie ewolucyjne - operatory

Mutacji podlegaja zwykle wszystkie osobniki dodawane do populacji
posredniej. Mutacja polega na zmianie parametrów (x,

?

) zgodnie ze

wzorami:

? ?

? ?

?

?

?

i

i

N

i

i

i

e

x

x

N

?

?

?

?

0

0

,

,

?

gdzie N(0,

?

) oznacza liczbe losowa wygenerowana

zgodnie z rozkladem normalnym o wart.
oczekiwanej 0 i odchyleniu standardowym

?

.

Krzyzowaniu podlega czesc (np. 25%) osobników dodawanych do
populacji posredniej. Osobnik potomny skladany jest z genów dwóch
losowo wybranych osobników rodzicielskich.

(x

1

, x

2

, x

3

, x

4

, x

5

,

?

?

???

2

,

?

?

???

?

???

?

?

(y

1

, y

2

, y

3

, y

4

, y

5

,

?

?

???

2

,

?

?

???

?

???

?

?

(x

1

, y

2

, y

3

, x

4

, y

5

,

?

?

???

2

,

?

?

???

?

???

?

?

Uwaga: wartosci x

i

sa dziedziczone zawsze razem z

odpowiadajacymi im wartosciami pomocniczymi

?

?

?

4

(c)

DS, JW

Wyklad 11, str. 7

Algorytmy genetyczne

N

1. Tworzymy N osobników losowych.

krzyzowanie

mutacje

2. Stosujemy operacje mutacji i krzyzowania

f(x)

...
...

f(x)

3. Liczymy wartosci funkcji celu.

N

4. Dokonujemy selekcji.

5. Powtarzamy od punktu 2.

Cel: znalezc maksimum funkcji f(x).

Zalozenie: funkcja ta jest dodatnia.

Osobnik:
ciag zerojedynkowy

(c)

DS, JW

Wyklad 11, str. 8

Algorytmy genetyczne - szczególy

Etap wstepny: kodowanie problemu

Osobnik w klasycznej wersji algorytmów genetycznych jest ciagiem binarnym
stalej dlugosci. Aby rozwiazac konkretne zadanie, musimy zakodowac przestrzen
stanów (czyli wszystkie potencjalne rozwiazania) w jezyku binarnym.
Jezeli zadanie polega na znalezieniu maksimum jakiejs funkcji, mozemy owej
funkcji uzyc bezposrednio w algorytmie. Jezeli zadanie brzmi inaczej (np. znalezc
obiekt spelniajacy pewne kryteria), czesto musimy sami taka funkcje
skonstruowac.

Drugi krok algorytmu: mutacje i krzyzowania

Mutacja: losujemy osobnika, nastepnie jeden z jego bitów. Zamieniamy wartosc
tego bitu na przeciwna. Mutacja dotyka srednio 0.1% bitów w populacji.

100100110010

100101110010

5

(c)

DS, JW

Wyklad 11, str. 9

Algorytmy genetyczne - szczególy

Krzyzowanie (crossing-over): laczymy osobniki w pary. Dla kazdej pary ustalamy
(w drodze losowania, prawdopodobienstwo rzedu 20-50%), czy dojdzie do ich
skrzyzowania. Jesli tak, losujemy miejsce (bit) w chromosomie jednego z
rodziców, po czym zamieniamy miejscami fragmenty chromosomów poczynajac
od wylosowanego miejsca.

10001101 00100

01101011 10011

10001101

00100

01101011

10011

losowy punkt przeciecia

(ten sam w obu osobnikach)

Rodzic 1

Rodzic 2

Potomek 1

Potomek 2

Inaczej niz w przypadku strategii ewolucyjnych, krzyzowanie w

algorytmie genetycznym odgrywa role duzo wazniejsza, niz mutacje.

(c)

DS, JW

Wyklad 11, str 10

Algorytmy genetyczne - szczególy

Czwarty krok algorytmu: selekcja

Liczymy wartosci funkcji celu dla wszystkich osobników. Nastepnie, sposród N
osobników populacji posredniej wybieramy N osobników populacji koncowej
(niektóre osobniki beda wystepowaly w kilku kopiach, inne znikna), za pomoca
algorytmu “kola ruletki”:
1. Liczymy sume wartosci funkcji celu: f

sum

= f(x

1

)+...+f(x

N

).

2. Liczymy procentowy wklad kazdego osobnika w ogólna sume: p(x

i

) = f(x

i

)/f

sum

3. Traktujemy wartosci p(x

i

) jako rozklad prawdopodobienstwa (“kolo ruletki”) i

dokonujemy N-krotnego losowania osobników zgodnie z tym rozkladem

f(x)

...
...

f(x)

N

20%

18%

12%

35%

6

(c)

DS, JW

Wyklad 11, str 11

Twierdzenie o schematach

Schemat - fragment chromosomu (niekoniecznie spójny) o ustalonych
wartosciach. Np: ***10*01** oznacza schemat z czterema ustalonymi
pozycjami (gwiazdka oznacza dowolna wartosc).
Zalózmy, ze pewne schematy maja srednio wieksze wartosci funkcji celu,
niz inne (usredniamy po wszystkich mozliwych wartosciach na pozycjach
nieustalonych). Oznaczmy przez H - schemat, przez o(H) - liczbe jego
miejsc ustalonych, przez d(H) - odleglosc miedzy skrajnymi miejscami
ustalonymi, przez l - dlugosc chromosomu, przez p

m

- prawd. mutacji

pojedynczego bitu, przez p

c

- prawd. krzyzowania pary. Wtedy:

? ?

? ?

? ?

p H

p

d H

l

o H p

c

m

? ?

?

?

1

1

- stanowi prawdopodobienstwo, ze

dany schemat pozostanie
nienaruszony w wyniku mutacji i
krzyzowania.

(c)

DS, JW

Wyklad 11, str 12

Twierdzenie o schematach - c.d.

Jezeli przez m(H,t) oznaczymy liczbe (procent) osobników w populacji,
które w chwili t pasuja do schematu H, to srednia liczba takich osobników
w nastepnym kroku moze byc oszacowana jako:

?

?

?

?

? ?

? ? ? ?

E m H t

m H t

f H

f

p H

,

,

?

?

1

gdzie f(H) oznacza srednia wartosc funkcji celu osobników pasujacych do
danego schematu, oznacza srednia wartosc funkcji celu w populacji.

f

Wniosek: jesli schematy sa krótkie i zwarte (czyli maja duze p(H)),
oraz jesli maja srednia wartosc funkcji celu wyzsza, niz przecietna, to
ich reprezentacja w populacji bedzie rosla wykladniczo.

7

(c)

DS, JW

Wyklad 11, str 13

Hipoteza cegielek

Algorytmy genetyczne dzialaja najskuteczniej wtedy, gdy sposób
zakodowania problemu i ksztalt funkcji celu pozwalaja na istnienie
“cegielek”: niewielkich i zwartych schematów o ponadprzecietnej wartosci
funkcji. Jesli z takich schematów da sie zbudowac rozwiazanie optymalne,
algorytm genetyczny latwo je znajdzie.

********10

***1*00***

010*******

0101100010

Wniosek praktyczny: jesli kilka bitów koduje pojedyncza ceche,

powinny one lezec blisko siebie.

Skutecznosc algorytmów genetycznych opiera sie na ukrytym
równoleglym przetwarzaniu wielkiej liczby schematów.