1

Algorytmy ewolucyjne

dr inż. Krzysztof Tymburski

Literatura:

1. Arabas J., Wykłady z algorytmów

ewolucyjnych

WNT, Warszawa 2004.

2. Michalewicz Z., Algorytmy genetyczne +

struktury

danych=programy ewolucyjne, WNT,

Warszawa 2003

3. Cader A., i inni, Artificial Intelligence and

Soft

Computing, Exit, Warszawa 2006

4.Michalewicz Z., Fogel D., Jak to rozwiązać,

czyli

nowoczesna heurystyka, WNT,Warszawa 2006

2

Algorytmy ewolucyjne wykład 1

wstęp, algorytmy genetyczne

1.

Optymalizacji globalna, problem i metody
rozwiązania

2.

Ewolucja według Darwina

3.

Algorytmy ewolucyjne

4.

Algorytmy genetyczne

• Twierdzenie o schematach

• Hipoteza cegiełek

• Prosty algorytm genetyczny (SGA)

5.

Podsumowanie i literatura o AG

3

Problem optymalizacji globalnej

metody klasyczne

Zadanie : znalezienie ekstremum
(minimum/ maksimum) funkcji wielu zmiennych.

Metody klasyczne:
. analityczne
. przeglądowe
. probabilistyczne (losowe)

4

Metody klasyczne optymalizacji globalnej

Metody analityczne:
. pośrednie – szukamy lokalnych ekstremów,
rozwiązując równania otrzymane w wyniku
przyrównania do zera gradientu funkcji celu.
.bezpośrednie – poruszamy się w kierunku
maksymalnego wzrostu/spadku funkcji celu.

5

Metody klasyczne optymalizacji globalnej

Wady metod analitycznych:

. konieczna jest jawna znajomość funkcji celu
. lokalny zakres poszukiwań ekstremum
. założona różniczkowalność funkcji celu

6

Metody klasyczne optymalizacji globalnej

Metody przeglądowe (wyliczeniowe, enumeracyjne).
Zalety
. brak ostrych założeń co do funkcji celu

Wady
. przestrzeń przeszukiwań musi być skończona
. niska efektywność co uwydatnia się w przypadku
dużych przestrzeni przeszukiwań

7

Metody klasyczne optymalizacji globalnej

Metody probabilistyczne ( losowe)
Polegają na losowym przglądaniu

przestrzeni
rozwiązań i zapamiętywaniu najlepszego

rozwiązania.

Zalety
. brak ostrych założeń co do funkcji celu

Wady
. niska efektyność

8

Inne metody poszukiwania

ekstremum globalnego

Metoda symulowanego wyżarzania

Modyfikacja błądzenia przypadkowego, w którym punkt
losowo wybrany staje się punktem roboczy wtedy gdy
poprawia wartość funkcji celu. Jezeli jej nie poprawia
akceptacja następuje z prawdopodobieństwem równym
, gdzie jest modułem różnicy
funkcji celu w starym i nowym wygenerowanym

punkcie, T  0 jest parametrem zwanym temperaturą

∣

 f

∣

p

0

=exp

−

∣

 f

∣

T 

9

Inne metody poszukiwania

ekstremum globalnego

Metoda symulowanego wyżarzania cd.

W metodzie tej krytyczne jest dobranie sposobu
obniżania temperatury w kolejnych generacjach.
Zbyt szybkie obniżanie temperatury zmniejsza
dokładnośc algorytmu, zbyt wolne wydłuża
nadmiernie czas obliczeń.
Nazwa metody od procesu hodowania kryształów,
gdzie efekt zależy od szybości zmian temperatury.

10

Inne metody poszukiwania

ekstremum globalnego

Metoda poszukiwania z tabu

. metoda ta unika wielokrotnego powracania do
już przejrzanych rozwiązań. Algorytm jest
wyposażony wpamięć już odwiedzanych punktów.
Punkty znajdujące się w pamięci są tabu – zakazane
jest ponowne ich odwiedzenie. Aby tabu nie
absorbowało zbyt dużo pamięci jest zapisywane w
pamięci cyklicznej i wymazywane zgodnie z metodą
FIFO.

11

Ewolucja według Darwina

Gatunki z upływem czasu i wymiana pokoleń

zmieniają się.
Sama śmiertelność i rozmnażanie nie tłumaczą

zmienności gatunkowej.
Przyczyną ewolucji są niewielkie zmiany cech

osobniczych u potomstwa (mutacja).
W środowisku o ograniczonych zasobach wzrastają

szanse przeżycia osobników najlepiej

przystosowanych.

12

Teoria Darwina a algorytmy ewolucyjne

Problem znalezienie ekstremum globalnego funkcji
wielu zmiennych.

. Przestrzeń w której poszukujemy rozwiązań

traktujemy jako populację rozwiązań.
. Każde rozwiązanie przedstawia sobą jednego

osobnika z populacji rozwiązań, lepiej lub gorzej

przystosowanego do środowiska.
. Miarą przystosowania jest wartość funkcji ,której

ekstremum poszukujemy.
. Do następnego pokolenia rozwiązań mają większe

szanse przekazać swoje cechy osobniki lepsze.

13

Algorytmy ewolucyjne

. Algorytmy genetyczne
. Strategie ewolucyjne
. Programowanie ewolucyjne
. Programowanie genetyczne

14

Algorytmy Genetyczne AG

AG

=

Poszukiwanie maksymalnej wartości funkcji

przystosowania oparte na mechanizmach doboru

naturalnego oraz dziedziczności. Łączy ewolucyjną

zasadę przeżycia najlepiej przystosowanych

z systematyczną i po części losową wymianą

informacji

.

15

2. Wiadomości podstawowe o AG

AG

=

Poszukiwanie maksymalnej wartości funkcji

przystosowania oparte na mechanizmach doboru

naturalnego oraz dziedziczności. Łączy ewolucyjną

zasadę przeżycia najlepiej przystosowanych

z systematyczną i po części losową wymianą

informacji

.

16

2. Wiadomości podstawowe o AG

Kodowanie:

binarne

Selekcja:

probabilistyczna

Operatory genetyczne :

.

krzyżowanie

( wymiana łańcuchów kodowych )

prawdopodobieństwo bliskie jedności

.

mutacja

( odwrócenie) wartości elementu

łańcucha kodowego, prawdopodobieństwo bliskie

zera.

17

1957-62: Barricelli, Fraser, Martin, Cockerham

– modelowanie procesów genetycznych

1960: Holland (Uniw. Michigan) – systemy
adaptacyjne  AG
1967: Bagley – program gry w 6 pionków
1971: Hollstien; 1975: De Jong – optymalizacja
funkcji
1985: Goldberg – optymalizacja pracy gazociągu

Historia algorytmów genetycznych

18

Podstawowe pojęcia w algorytmach genetycznych

W genetyce za pojedyncze cechy osobnika odpowiada gen,

mający wiele możliwych postaci zwanych allelami.

Gen identyfikujemy podając jego miejsce w chromosomie (locus)

oraz jego funkcję. Mówimy przykładowo, ze gen określający kolor

oczu, ma pozycję 10 i allel odpowiadajacy kolorowi niebieskiemu.

W algorytmach genetycznych interesujące nas cechy

badanego układu są zakodowane w ciągi kodowe.Cechy mogą być

umiejscowione na różnych pozycjach ciągu kodowego.

W genetyce genotyp – postać genów, fenotyp – zespól cech

osobnika o danym genotypie.

W algorytmach genetycznych genotypowi odpowiada

struktura kodu, a fenotypowi zbiór parametrów, rozwiązanie albo

punkt w przestrzeni rozwiązań.

19

wymiana ciągów bitów

krzyżowanie

negacja bitów

mutacja

zbiór punktów

populacja

punkt w przestrzeni rozwiązań

osobnik

ciąg bitów

chromosom

bit

gen

komputer (AG)

biologia (genetyka)

DNA

00101010101011100

liczby
tekst

(ASCII, tex, doc)

grafika

(bmp, gif, jpeg)

dźwięk

(wav, midi, mp3)

wideo

(avi, mpeg)

kod binarny

Operowanie

na kodzie!

20

Kodowanie liniowe za pomocą

n

bitów x



[a, b]:



podział [a, b] na

2

n

podprzedziałów



wartości z

k

-tego podprzedziału 

k-1

w postaci binarnej

Kodowanie logarytmiczne x
= kodowanie liniowe log|x|

gen

chromosom

Kodowanie wielu zmiennych

 sklejanie łańcuchów

zmienna 1

zmienna 2

zmienna rzeczywista x

0,00

0,25

0,50

0,75

1,00

k

o

d

b

in

a

rn

y

0

1

10

11

100

101

110

111

1000

1001

1010

1011

1100

1101

1110

1111

Kodowanie binarne liczb rzeczywistych

21

Metoda ruletki – prawdopodobieństwo
wyboru osobnika proporcjonalne do
wartości

FP

1. pokolenie

nowe pokolenie

obliczenie

FP

dla

każdego osobnika

mutacja

krzyżowanie

selekcja

FP

= funkcja przystosowania

2  4

3  3

3  1

Operatory genetyczne: selekcja

22

1. pokolenie

nowe pokolenie

obliczenie

FP

dla

każdego osobnika

mutacja

krzyżowanie

selekcja

FP

= funkcja przystosowania

mutacja

negacja bitów z małym

prawdopodobieństwem

krzyżowanie jednopunktowe

wymiana fragmentów chromosomów

rodzice



dzieci

Operatory genetyczne: krzyżowanie i mutacja

23

FP

maksimum globalne

1. pokolenie

2. pokolenie

itd.

Ewolucja – dążenie do optymalnego rozwiązania

24

Schematy w algorytmach genetycznych

Schematem S nazywamy zbiór chromosomów jednoznacznie

zdefiniowany przez wzorzec podobieństwa , określający cechy

wspólne tego zbioru. W przypadku kodowania binarnego wzorzec

podobieństwa określa się przy pomocy trzech symboli { 0,1, #}, przy

czym symbol # oznacza dowolną z dwóch wartości 0 lub 1.

Do schematu S należą chromosomy o wartościach

identycznych jak we wzorcu na pozycjach na których nie występuje

symbol #. Przykładowo wzorcowi 01##10 odpowiadają chromosomy

010010, 010110, 011010, 011110.

P

S

25

Schematy w algorytmach genetycznych

Rzędem schematu o(S) jest liczba symboli

różnych od #

we wzorcu .

Przykładowo dla schematu 0#101100# o(S)=7.

Długością definiującą schematu

( rozpiętością schematu)

dS)jest odległość pomiedzy skrajnymi pozycjami

schematu różnymi od #.

Przykładowo dla schematu 0#101100# S)= 8-

1=7.

W niektórych publikacjach rozpiętość jest

definiowana jako odle-

głosć skrajnych określonych pozycji +1, co

odpowiada liczeniu lewej skrajnej pozycji od 0 a nie

od 1.

P

S

26

Schematy w algorytmach genetycznych

Funkcją przystosowania (x) nazywamy odwzorowanie

kodu x osobnika w wartość mówiąca o jego przystosowaniu do

środowiska.

Jeżeli szukamy wartości maksymalnej funkcji wielu

zmiennych to funkcja przystosowania jest tożsama z funkcją,

której ekstremum poszukujemy.

Wartością przystosowania schematu (S) jest średnia

wartość funkcji przystosowania wszystkich chromosomów

należących do danego schematu.

(S) = (x)

1

n



x∈S

¿

27

Twierdzenie o schematach

Założenia:

1. osobniki nalezą do nieskończenie dużej populacji.

2. w populacji tej znajdują się osobniki o chromosomach

należących do wszystkich schematów.

3. selekcja jest proporcjonalna do wartości funkcji

przystosowania.

4. kodowanie binarne, krzyżowanie jednopunktowe, mutacja

bitowa o bardzo małym prawdopodobieństwie.

28

Twierdzenie o schematach

Teza:

Wartość oczekiwana liczby chromosomów należących do

danego schematu w kolejnej generacji jest

szacowana zgodnie ze wzorem:

gdzie: liczebnosć osobników należących do schematu S w

populacji t+1, prawdopodobieństwo krzyżowania, długość

chromosomu, średnie przystosowanie całej populacji.

E∣S∣

P

t1

≥

∣

S

P

t

∣

S



S

1− p

c

dS

n−1

−oS p

m



E∣S∣

P

t1

p

c

∣S∣



 S

29

Metody selekcji

Selekcja następuje

1. na etapie reprodukcji czyli wyboru rodziców z populacji

bazowej P do operacji genetycznych ,w wyniku których powstaje

populacja tymczasowa T, dająca w rezultacie kolejnych operacji

genetycznych populację potomną O.

2. na etapie sukcesji czyli tworzenia nowej populacji w oparciu

o starą populację P i populację potomną O.

Jeżeli do nowej populacji wchodzą tylko osobniki z O to nie

zawsze przejdą do następnej populacji najlepsze osobniki ze starej

populacji bazowej. Wady tej nie ma selekcja elitarna , w której do

następnego populacji bazowej przechodzą najlepsze osobniki ze

starej populacji bazowej oraz z polulacji O.

30

Reprodukcja proporcjonalna (metoda koła

ruletki)

Prawdopodobieństwo wylosowania osobnika do reprodukcji jest

wprost proporcjonalne do wartości jego funkcji przystosowania.

Przykład. Mamy 4 osobniki odpowiednio o wartościach funkcji

przystosowania f1=15 , f2=45 , f3=6, f4=55.

Sumujemy wartości funkcji przystosowania fs=15+45+6+55=121.

Do reprodukcji losujemy osobniki odpowiednio z

prawdopodobieństwem p1=15/121, p2=45/121, p3=6/121,

p4=55/121.

31

Reprodukcja rangowa

Każdemu osobnikowi w populacji bazowej nadaje się numer

-rangę równą jego miejscu w uporządkowanej względem malejącej

wartości funkcji przystosowania populacji.( osobnik najlepszy ma

rangę 1).

Następnie definiuje się zmienną losową przypisując każdemu

osobnikowi prawdopodobieństwo reprodukcji na podstawie

jego rangi. Funkcja ta musi byc nierosnąca wzgledem rangi.

Przykładowa funkcja:

gdzie:

a oraz k wybieramy aby

p

r

 X =ak1−

r X 

r

max



r

max

=max

X ∈P

t

r X



i=1



p

r

 X=1,

0≤ p

r

 X ≤1,

32

Reprodukcja turniejowa

Wybieramy z jednakowym prawdopodobieństwem q

osobników z populacji bazowej. Nastepnie z tak utworzonej

populacji Q wybieramy najlepszego osobnika do populacji

tymczasowej T. Proces powtarzamy aż do zapełnienia populacji T.

Losowanie do populacji Q możemy prowadzić ze

zwracaniem oraz bez zwracania.

Zazwyczaj q=2.

33

Reprodukcja elitarna

Gwarantuje ona przejscie do następnego etapu osobników

należących do określonego w pewien sposób zbioru E.

Pozostałe osobniki są wybierane zgodnie z innymi zasadami,

na przykład w oparciu o metodę koła ruletki.

34

Sukcesja

Sukcesją nazywamy proces ustalania kolejnej populacji

(n+1) w oparciu o poprzednią populację (n) oraz jej potomstwo.

Sposób sukcesji powinien zapewnić spełnienie dwóch przeciwsta

wnych celów:

1. Poprawić wartość funkcji przystosowania kolejnej populacji.

Odpowiada to tzw eksploatacji czyli poszukiwaniu lokalnego

ekstremum funkcji przystosowania.

2.Zapewnić róznorodność genetyczną populacji co w przyszłości

zwiększa prawdopodobieństwo znalezienia estremu globalnego.

Odpowiada to tzw eksploracji przestrzeni rozwiązań.

Wzajemny stosunek eksploatacji do eksploracji określa tzw nacisk

selektywny.

35

Sukcesja z całkowitym zastępowaniem

Jest to najczęściej stosowanym sposobem tworzenia kolejnej

populacji bazowej. Staje się nią cała populacja potomna.

Sukcesja ta nie wprowadza mechanizmu nacisku

selektywnego, ponieważ do kolejnej populacji nie muszą

przechodzić najlepsze osobniki z poprzedniej populacji. W sukcesji

takiej eksploracja przeważa nad eksploatacją.

36

Sukcesja z częściowym zastępowaniem

W najprostszym wariancie przyjmuje się współczynnik

wymiany owa populacja bazowa składa się z  osobników

z populacji potomnej oraz z (1- osobników ze starej populacji

bazowej. Część osobników ze starej populacji bazowej usuwamy

korzystając z jednej z poniższych metod;

- usuwamy najgorzej przystosowane osobniki,

- usuwamy osobniki najbardziej podobne do potomnych, należy

przedtem wprowadzić miarę podobieństwa osobników,

- usuwamy losowo wybrane osobniki.

Zmieniając współczynnik wymiany możemy regulować nacisk

selektywny.

37

Sukcesja elitarna

Polega na tym, że częsć osobników ze starej populacji

bazowej przechodzi do nawej populacji, w taki sposób, aby

zagwarantować przeżycie co najmniej najlepszego osobnika.

Najpierw sortuje się populację bazową i wybiera 

najlepszych osobników tworząc populację . W drugim kroku

tworzy się nastepną populację bazową wybierając  najlepszych

osobników z sumy populacji potomnej i populacji .

P



t

T

t

P

t

P

t1

P



t

38

Prosty algorytm genetyczny (SGA) (Goldberg)

1. Wybór z aktualnej populacji P(n) o liczebności N

dwóch osobników x,y P(n).

2. Utworzenie w wyniku operacji krzyżowania dwóch

osobników potomnych.

3. Powtórzenie punktów 1,2 aż do uzyskania N osobników

potomnych.

4. Przeprowadzenie na osobnikach potomnych operacji

mutacji w wyniku czego otrzymujemy populację potomną

P(n+1) o liczebności N.

39

4a. Podsumowanie

+ odporność na lokalne ekstrema
+ niepotrzebna wstępna wiedza

(punkt startowy)
+ słabe założenia co do FP
+ wydajność
+ prostota pojęciowa

Zalety AG

– słabsza podbudowa teoretyczna

– kodowanie (czasem konieczność
naprawy chromosomów)

– często koniecznośc skalowania FP

Wady AG



rozpoznawanie obrazów



synteza i optymalizacja układów

(mechanicznych, elektronicznych)



sterowanie



strategia gier



klasyfikacja i automatyczne wnioskowanie



analiza danych (dopasowanie, modelowanie)

Zastosowania

sztuczny

mózg

… ale na razie

ostatnie słowo

ma człowiek.

40

Literatura

1.

D. E. Goldberg, Algorytmy genetyczne i ich zastosowania, WNT, Warszawa,

1998

2.

Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy

ewolucyjne, WNT, Warszawa, 1996

3.

J. Arabas, Wykłady z algorytmów ewolucyjnych, WNT, Warszawa, 2001.

Dziękuję za uwagę