Wykonał :

Piotr Sędziak 126999

Wydział EEIA

Politechnika Łódzka

Kwiecień 2010





Algorytmy ewolucyjne - historia

�ó Jest to ogólny termin łączący:

– Algorytmy genetyczne

– Programowanie genetyczne/ewolucyjne

– Strategie ewolucyjne

�ó Po

P cząt

ą ek

k to la

l t

a a

a 50

5 -

0 te, pie

i rwsze prac

a e dot.

programowania ewolucyjnego

(R. Frideberg).

�ó Praktyka: 1965, Bienert, Recgenberg,

Schewefel, pierwsze wersje EA.

�ó Teoria do algorytmów genetycznych to

przełom lat 60-tych i 70-tych (J.Holland).





Algorytmy genetyczne

służą głównie do tego,

że

ż b

e y

b r

o

r z

o w

z i

w ązy

z wa

w ć

ć z

a

z dania

optymalizacji





Wiele problemów optymalizacji tym się cechuje, że znalezienie dokładnego rozwiązania

może zajmować bardzo dużo czasu

Przykład: Problem Komiwojażera

Czas potrzebny do rozwiązania

pr

p o

r b

o l

b em

e u

u ko

k m

o iwoj

o aż

a e

ż r

e a

r

a w

zależności od ilości miast (przy

założeniu, że komputer przetwarza

milion instrukcji na sekundę)

Ilość miast

10

50

100

300

Czas

[mikrosekundy]

�ź3,6 * 106

�ź1016

�ź1031

�ź10623



Dla porównania – liczba mikrosekund od wielkiego wybuchu, w którym narodził się nasz Wszechświat jest rzędu 1024.





Na bazie obserwacji

natury powstała

koncepcja, żeby

poszukiwaniami

opty

t m

y al

a n

l ego

rozwiązania

(uzyskiwanego za

pomocą komputera)

kierował proces

ewolucji.





Obliczenia ewolucyjne powstały

w wyniku kombinacji kilku elementów:

Rozwoju technik obliczeniowych

Postępu wiedzy o ewolucji biologicznej

Osiągnięć nowych teorii optymalizacji





Obliczenia ewolucyjne są dziś

ważną częścią sztucznej inteligencji

Inteligencja

Alg

l or

o y

r tm

t y

m g

enety

t c

y z

c ne

Komputerowa

Pro

r g

o .

. ewo

w l

o u

l cy

c jn

j e

Oblicz

c e

z n

e ia

ewolucyjne

Strategie rozwoju

Sieci neuronowe

Prog. genetyczne

Logika rozmyta





Najpopularniejsze są Algorytmy

Genetyczne





Zapis algorytmu

Najczęściej działanie algorytmu przebiega następująco: 1. Losowana jest pewna populacja początkowa.

2. Populacja poddawana jest ocenie (selekcja). Najlepiej przystosowane osobniki biorą udział w procesie reprodukcji.

3.

3

Ge

G no

n ty

t p

y y

p

y w

yb

y r

b a

r ny

n c

y h

c

h o

sobn

b i

n k

i ó

k w p

o

p dd

d a

d w

a a

w ne

n s

ą o

pe

p ra

r toro

r m

o

m

ewolucyjnym:

- są sobą kojarzone poprzez złączanie genotypów rodziców (krzyżowanie),

- przeprowadzana jest mutacja, czyli wprowadzenie drobnych losowych zmian.

4. Rodzi się drugie (kolejne) pokolenie i algorytm powraca do kroku drugiego, jeżeli nie znaleziono dostatecznie dobrego rozwiązania.

W przeciwnym wypadku uzyskujemy wynik.





Kolejność czynności

w trakcie

symulowanej

ewolucji





Klasyczny algorytm genetyczny

Wyróżnikiem k.a.g. jest prostota: prosty sposób kodowania, proste operatory, proste reguły tworzenia populacji i oceniania osobników.

�óChromosom jest to po prostu ciąg bitów. Każdy pojedynczy bit jest odpowiednikiem pojedynczego genu.

�óOperacja krzyżowania polega na losowym przecięciu dwóch chromosomów (ciągów bitów) w jednym punkcie i zamianie podzielonych części między chromosomami. Powstają dwa nowe chromosomy.

�óOp

O er

e a

r cj

c a

j mu

m ta

t cj

c i

j poleg

e a

a n

a

a za

z m

a i

m an

a ie

e na

a prz

r e

z c

e i

c wn

w y

y losowo

w w

y

w b

y ra

r n

a eg

e o bitu.

.

�óSelekcja osobników do krzyżowania następuje na drodze losowania metodą koła ruletki, która przydziela prawdopodobieństwa wylosowania każdego osobnika bezpośrednio na podstawie jednej funkcji oceny.

�ó

Populacja ma stały rozmiar, a w kolejnych cyklach ewolucji wszystkie chromosomy podlegają wymianie na nowe (dzieci całkowicie zastępują rodziców).

�ó

Rozwiązaniem problemu jest najlepiej przystosowany osobnik z ostatniej wygenerowanej populacji. Należy dodać, że musimy z góry określić warunek zatrzymania ewolucji (np.

uzyskanie osobnika o wystarczająco dobrych parametrach albo po z góry określonej maksymalnej liczbie iteracji).





Kodowanie

Kodowanie jest bardzo istotnym etapem projektowania algorytmu. Sposób zakodowania w chromosomie informacji o proponowanym rozwiązaniu wydatnie wpływa na szybkość i jakość znajdywanych wyników. Przyczyną takiego zjawiska jest wpływ kodowania na sposób w jaki przeszukiwana jest przestrzeń rozwiązań.

Złe kodowanie może spowodować, że nigdy nie zostanie przeszukany fr

f a

r gm

g e

m nt

n p

r

p z

r e

z strz

r e

z ni

n ,

i w

kt

k óry

r m

y

m z

n

z a

n jdu

d j

u ą s

ię

i n

a

n jle

l ps

p ze

z r

o

r zw

z ią

i za

z ni

n a

i !

Ze względu na wartości przechowywane w genach można wyróżnić trzy podstawowe sposoby kodowania:

�ó Klasyczne czyli binarne

�ó Oparte na liczbach całkowitych

�ó Oparte na liczbach zmiennoprzecinkowych





Znaczenie doboru

funkcji oceniającej





Funkcja przystosowania

Proces wyboru osobników poddanych ocenie według

określonych kryteriów. Kryteria te zapisuje się w postaci funkcji oceny albo inaczej funkcji przystosowania. Algorytm genetyczny dąży zwykle do jej minimalizacji (maksymalizacji). Jako kryterium często przyjmowana jest funkcja celu rozważanego problemu optymalizacji.

Fu

F n

u k

n cj

c a oc

o e

c ny

n

Funkcja oceny to miara jakości dowolnego osobnika (fenotypu, rozwiązania) w populacji. Dla każdego osobnika jest ona obliczana na podstawie pewnego modelu rozwiązywanego problemu.

Załóżmy dla przykładu, że chcemy zaprojektować obwód elektryczny o pewnej charakterystyce. Funkcja oceny będzie premiowała rozwiązania najbardziej zbliżonej do tej charakterystyki, zbudowane z najmniejszej liczby elementów. W procesie selekcji faworyzowane będą najlepiej przystosowane osobniki. One staną się "rodzicami" dla nowej populacji.





Metody selekcji

Selekcja jest esencją całej genetyki. W tym miejscu tworzona jest nowa populacja na podstawie już istniejącej. W zależności od wartości funkcji oceny (obliczanej w poprzednim kroku) dany osobnik ma większe (gdy jest �śdobry”') lub mniejsze (gdy jest �śsłaby”) szanse na znalezienie się w

kolejnym

pokoleniu.

Istnieje

kilka

sposobów

obliczania

�śszansy”

poszczególnych osobników:

koło ruletki

r

a

r nk

n i

k n

i g

n

g l

i

l n

i i

n o

i wy

w

turniej





Na czym polega krzyżowanie

Zadaniem kroku krzyżowania jest wymiana "materiału genetycznego"

pomiędzy dwoma rozwiązaniami w populacji. W wyniku krzyżowania na podstawie dwóch rozwiązań (rodzice) tworzone są dwa nowe osobniki (dzieci). Po wykonaniu krzyżowania dzieci zastępują w populacji rodziców. Oczywiście w tym kroku nie wszystkie rozwiązania muszą się ze sobą krzyżować. Liczbę krzyżowań określa tzw. współczynnik krzyżowania (o wartości od 0 do 1), który pokazuje jaka liczba osobników powinna być w jednej iteracji skrzyżowana, bądź określa prawdopodobieństwo z jakim każde rozwiązanie może wsiąść udział w krzyżowaniu.

W przypadku binarnej reprezentacji chromosomu najprostsze krzyżowanie pol

o e

l g

e a na

n pod

o zi

z a

i le

l dwóc

ó h

c ch

c r

h om

o oso

s mów

ó

(rod

o zi

z ce

c )

e na

n dwie

i cz

c ę

z ś

ę c

ś i

c (ni

n e

i k

e o

k n

o ie

i c

e z

c n

z i

n e

i równe

n )

e i z

nich tworzone są dzieci: pierwsze dziecko składa się z początkowej części pierwszego rodzica i końcówki drugiego natomiast drugie dziecko odwrotnie - początek drugiego rodzica i koniec pierwszego.

Przykład

Na

przykładzie

homo

sapiens

może

to

wyglądać

następująco:

Pierwszy

rodzic:

00000000

-

niebieskooka

Polka

o

wzroście

do

140cm

Drugi

rodzic:

11011001

-

wysoki

(190-200)

Niemiec

o

brązowych

oczach.

Jeśli punkt podziału ustalimy pomiędzy czwartym a piątym bitem to dzieci będą wyglądać następująco:

00001001 - Niemka o niebieskich oczach i wzroście 150-160cm 11010000 - Polak o brązowych oczach i wzroście 160-170cm





Mutacja

Mutacja wprowadza do genotypu losowe zmiany. Jej

zadaniem jest wprowadzanie różnorodności w populacji, czyli zapobieganie (przynajmniej częściowe) przedwczesnej zbieżności algorytmu. Mutacja zachodzi z pewnym przyjętym

prawdopodobieństwem - zazwyczaj rzędu 1%. Jest ono niskie, ponieważ zbyt silna mutacja przynosi efekt odwrotny do zamierzonego: zamiast subtelnie różnicować dobre rozwiązania -

niszczy je. Stąd w procesie ewolucji mutacja ma znaczenie dr

d u

r g

u o

g rz

r ę

z dn

d e

n , s

zc

z z

c e

z gó

g ln

l i

n e

i w

p

r

p z

r y

z p

y a

p dk

d u

k

u d

ł

d ug

u i

g c

i h

c

h c

h

c r

h o

r mo

m s

o omó

m w.

w

W przypadku chromosomów kodowanych binarnie losuje się zazwyczaj dwa geny i zamienia się je miejscami bądź np. neguje pewien wylosowany gen.

W przypadku genotypów zakodowanych liczbami całkowitymi stosuje się permutacje.

W przypadku genotypów zakodowanych liczbami

rzeczywistymi wprowadza się do przypadkowych genów losowe zmiany o danym rozkładzie - najczęściej normalnym.





Wady AG

Zalety AG

– słabsza podbudowa teoretyczna

+ odporność na lokalne ekstrema

– kodowanie (czasem konieczność

+ niepotrzebna wstępna wiedza

naprawy chromosomów)

(punkt startowy)

+ słabe założenia co do FP

– często konieczność skalowania FP

+ wydajność

+ prostota pojęciowa

Zastosowania

rozpoznawanie obrazów

synteza i optymalizacja układów

(mechanicznych, elektronicznych)

sterowanie

strategia gier

klasyfikacja i automatyczne wnioskowanie

analiza danych (dopasowanie, modelowanie)





Michalewicz

Z.:

Algorytmy

genetyczne+struktury

danych=programy ewolucyjne, Warszawa, WNT, 1996



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



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



Haupt R. L., Haupt S.E.: Practical Genetic Algorithms. John Wiley

& Sons, 1998



Koza J. R., Rice J. P.: Genetic Programming: The Movie. MIT

Press, 1992