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.