Podstawy algorytmów ewolucyjnych

Podstawy algorytmów

ewolucyjnych

Dariusz Badura

Ewolucyjne projektowanie

Fitness

2. Evaluate Circuit

3. Select Breeding Pairs

1. Create New Population

4. Cross Over

5. Mutate

6. Insert Into New Population

Iterate until

stopping conditions

are met

Ewolucyjne przeszukiwanie

... oznaczać będzie poszukiwanie rozwiązania problemu –
zadania poprzez wprowadzenie losowego generowania
rozwiązań z wykorzystaniem operatorów genetycznych.

W celu porównania skuteczności ewolucyjnego i losowego
przeszukiwania należałoby porównać czas poszukiwania
satysfakcjonującego rozwiązania obiema metodami.

Aktywne przeszukiwane nazywać będziemy aktywnym, jeżeli w
poszukiwaniu rozwiązania będzie wykorzystana wiedza o
problemie ułatwiająca podjęcie decyzji o kierunku poszukiwań
rozwiązania.

Metody ewolucyjne

... algorytmy ewolucyjne obejmują następujące

metody rozwiązywania problemów:

• algorytmy ewolucyjne „ciągłe”,
• algorytmy genetyczne,
• programowanie genetyczne,
• projektowanie ewolucyjne DNA
• inne pokrewne, w których występuje ewoluująca

np.. metoda sztucznej immunologii.

Kodowanie rozwiązania

• EA – algorytmy ewolucyjne

• GA – algorytmy genetyczne

• GP – programowanie genetyczne

• DNA – algorytmy oparte o mechanizmy

biologiczno-chemiczne DNA-RNA

Rozwiązanie problemu z

wykorzystaniem algorytmów

ewolucyjnych

Problem

Kodowanie
rozwiązania

funkcja

oceniająca

operatory

genetyczne

wiedza

genetyczne
poszukiwanie

ocena

osobników

Rozwiązanie

selekcja

replikacja

operacje
genetyczne

mutacja

Algorytm ewolucyjny

Inicjacja
populacji

Ocena
populacji

Selekcja
osobników

Tworzenie
nowej
populacji

Operacje
genetyczne

Rozwią-

zanie

czy spełniony
war. term. ?

Elementy algorytmu – selekcja

• proporcjonalne przypisanie wartości

dostosowania

• przypisanie wartości dostosowania na podstawie

rankingu

Selekcja – ogólne zasady

Podczas selekcji wyznaczane są osobniki biorące

udział w tworzeniu potomstwa.

W pierwszym kroku przypisywana zostaje wartość

przystosowania. Każdy osobnik z puli selekcyjnej
otrzymuje prawdopodobieństwo reprodukcji zależne od
własnej obiektywnej wartości oraz od obiektywnej
wartości pozostałych osobników puli selekcyjnej.

To przystosowanie stosowane jest do aktualnej

selekcji następnego kroku.

Selekcja

Osobniki rodzicielskie są wybierane na podstawie

wartości funkcji dostosowania za pomocą
następujących algorytmów:

• selekcja koła ruletki,

• stochastycznego uniwersalnego próbkowania,

• selekcja lokalna,

• selekcji odcięcia lub

• selekcji turniejowej.

Selekcja – parametry

Presja selekcji – selective pressure:

Prawdopodobieństwo najlepszego osobnika będącego w selekcji
porównane do średniego prawdopodobieństwa selekcji
wszystkich osobników.

Skłonność – bias:

Wartość absolutna różnicy pomiędzy znormalizowaną wartością
przystosowania osobnika i jego oczekiwanego
prawdopodobieństwa reprodukcji.

Rozpostarcie – spread:

Zakres możliwych wartości liczby potomstwa pochodzących od
osobników.

Selekcja – parametry

Utrata różnorodności – loss of diversity:
Proporcja osobników populacji, które nie zostały
wyselekcjonowane w fazie selekcji.
Intensywność selekcji – selection intensity:
Oczekiwana średnia wartość dostosowania populacji po
zastosowaniu metody selekcji do znormalizowanego rozkładu
Gaussa.
Wariancja selekcji – selection variance:
Oczekiwana wariancja rozkładu dostosowania populacji po
zastosowaniu metody selekcji do znormalizowanego rozkładu
Gaussa.

Metoda rankingu

ind

– liczba osobników w populacji,

Pos – pozycja osobnika w rozpatrywanej populacji. (najmniej
dostosowany osobnik ma wartość Pos=1, a najlepiej
dostosowany osobnik wartość Pos=Nind)
SP – presja selekcji.
Ranking liniowy:
Wartość funkcji dostosowania dla dowolnego osobnika jest
wyznaczana wzorem:

Wartość SP (presji selekcji) mieści się w zakresie [1.0, 2.0].

)

(

)

(

)

(









Nind

Pos

Fitness

Ranking nieliniowy

Dopuszcza większe wartości presji selekcji, przy funkcji
dostosowania określonej wzorem:

X jest pierwiastkiem wielomianu:

lub w innej postaci:

Ranking nieliniowy pozwala kształtować wartości presji selekcji
(SP) w zakresie [1.0, N

ind

- 2.0].









Nind

Pos

Nind

Pos

Fitness

)

(

)

(

Nind









)

(







Nind

Funkcja dostosowania

liniowego i nieliniowego rankingu

Wartość oceny

wartość dostosowania (param.: presja selekcji)

ranking liniowy

bez rank.

ranking nieliniowy

2,0

1,1

1,0

3,0

2,0

1,10

1.0

3,00

2,00

1,8

1,08

1.0

2,21

1,69

1,6

1,06

1.0

1,62

1,43

1,4

1,04

1.0

1,16

1,21

1,2

1,02

1.0

0,88

1,03

1,0

1,00

1.0

0,65

0,87

0,8

0,98

1.0

0,48

0,74

0,6

0,96

1.0

0,35

0,62

0,4

0,94

1.0

0,26

0,53

0,2

0,92

1.0

0,19

0,45

0,0

0,90

1.0

0,14

0,38

Funkcja dostosowania

liniowego i nieliniowego rankingu

0,0

0,5

1,0

1,5

2,0

2,5

Serie1

Serie2

Funkcja dostosowania

liniowego i nieliniowego rankingu

0,00

0,50

1,00

1,50

2,00

2,50

3,00

3,50

1.0

1,10

1,08

1,06

1,04

1,02

1,00

0,98

0,96

0,94

0,92

0,90

2,0

1,8

1,6

1,4

1,2

1,0

0,8

0,6

0,4

0,2

0,0

ania

Ranking nieliniowy

Serie1

Serie2

Właściwości selekcji

rankingowej



)

(

)

(



 SP

SelInt

Rank

)

(





LossDiv

Rank

))

(

)

(

)

(

SelInt

SelVar

Rank











Intensywność selekcji:

Utrata różnorodności:

Wariancja selekcji:

Właściwości selekcji rankingowej

Selekcja koła ruletki

Number of
individual

fitness value

2.0

1.8

1.6

1.4

1.2

1.0

0.8

0.6

0.4

0.2 0.0

selection
probability

0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.02 0.0

Próbka 6 wylosowanych liczb:
0.81, 0.32, 0.96, 0.01, 0.65, 0.42.

Po selekcji tworzona populacja rodzicielska obejmuje
osobników: 1, 2, 3, 5, 6, 9.

Stochastyczne uniwersalne

próbkowanie

Dla wyselekcjonowania 6 osobników odległość pomiędzy
wskaźnikami wynosi 1/6=0.167.
Zatem próbka jednej liczby w zakresie [0, 0.167]:

0.1.

Po selekcji populacja rodzicielska zawiera następujące
osobniki:

1, 2, 3, 4, 6, 8.

Selekcja lokalna

Selekcja odcięcia

truncation
threshold

10
%

20
%

40
%

50
%

80
%

Selection
intensity

2.66 1.76 1.2 0.97 0.8 0.34

Zależność pomiędzy
pomiędzy poziomem
odcięcia a
intensywnością
selekcji

c(Trunc)

SelIntTrun



Trunc



Utrata różnorodności:

LossDiv

Trunc

(Trunc) = 1-Trunc.

Wariancja selekcji:

SelVar

Trunc

(Trunc) = 1-SelInt

Trunc

(Trunc)·(SelInt

Trunc

(Trunc)-f

Selekcja turniejowa

W selekcji turniejowej pewna liczba Tour osobników zostaje
losowo wybrana z populacji, a następnie wybieramy najlepszego
osobnika do populacji rodzicielskiej. Proces może być powtarzany
do momentu wypełnienia populacji rodzicielskiej. Osobniki
rodzicielskie wytwarzają losowo w sposób jednolity
osobnikipotomne.

Parametry: wielkość turnieju Tour. Tour przyjmuje wartość z
zakresu 2 - N

ind

Tournament size

selection intensity

0.56

0.85

1.15

1.53

2.04

Selekcja turniejowa

Rekombinacja

• Rekombinacja wartości rzeczywistych:

o rekombinacja dyskretna,
o rekombinacja pośrednia,
o rekombinacja liniowa,
o poszerzona rekombinacja liniowa.

• Rekombinacja binarna/dyskretna (krzyżowanie):

o krzyżowanie jednopunktowe,
o krzyżowanie wielopunktowe,
o krzyżowanie unormowane,
o krzyżowanie typu tasowanie,
o krzyżowanie ze zredukowanym surogatem.

Rekombinacja wartości rzeczywistych

– rekombinacja dyskretna

Rekombinacja dyskretna dokonuje wymiany wartości zmiennych
pomiędzy osobnikami.
Przykład: dwa osobniki z trzema zmiennymi (3 wymiary):
osobnik 1      12     25      5
osobnik 2     123      4     34
Dla każdej zmiennej wybór wartości jednego z rodziców jest
dokonywana w sposób losowy z równym pradopodobieństwem
dla każdego z rodziców.
próbka 1         2     2      1
próbka 2         1     2      1
Po rekombinacji tworzone są nowe osobniki:
potomek 1      123      4      5
potomek 2       12      4     5

Rekombinacja dyskretna

Rekombinacja pośrednia

Potomne osobniki są zgodnie z następującą regułą:
potomek = rodzic 1 +



(rodzic 2 – rodzic 1),

gdzie  jest współczynnikiem skalującym wybieranym w sposób
losowy z równym prawdopodobieństwem z zakresu [-d, 1 + d].
Dla rekombinacji pośredniej d = 0, dla rozszerzonej rekombinacji
pośredniej d > 0. Dobrą wartością jest d = 0.25. Dla każdej
zmiennej współczynnik  jest losowany oddzielnie.

Rekombinacja pośrednia

Przykład: Dwa osobniki, trzy zmienne:
osobnik 1      12     25    5
osobnik 2     123      4     34
Przykładowy wybór  :
próbka 1      0.5   1.1   -0.1
próbka 2        0.1   0.8    0.5

Nowe osobniki – potomne :
potomek 1   67.5 1.9   2.1
potomek 2 23.1 8.2   19.5

Rekombinacja liniowa

Współczynnik  dla wszystkich zmiennych taki sam

Rekombinacja liniowa rozszerzona jest poszerzeniem
podprzestrzeni osobników potomnych wokół linii
osobników rodzicielskich.

Krzyżowanie jednopunktowe

Dwa osobniki z 11 wartościami binarnymi:

individual 1 0 1 1 1 0 0 1 1 0 1 0

individual 2 1 0 1 0 1 1 0 0 1 0 1

Wybrany zostaje punkt krzyżowania:

punkt krzyżowania 5

Po krzyżowaniu otrzymamy następujące osobniki potomne:

offspring 1 0 1 1 1 0| 1 0 0 1 0 1

offspring 2 1 0 1 0 1| 0 1 1 0 1 0

Krzyżowanie wielopunktowe

Osobniki z 11 binarnymi zmiennymi:

individual 1 0 1 1 1 0 0 1 1 0 1 0

individual 2 1 0 1 0 1 1 0 0 1 0 1

Wybieramy 3 punkty krzyżowania:

cross pos. (m=3) 2 6 10

Po krzyżowaniu otrzymujemy osobniki:

offspring 1 0 1| 1 0 1 1| 0 1 1 1| 1

offspring 2 1 0| 1 1 0 0| 0 0 1 0| 0

Krzyżowanie unormowane

Osobniki z 11 binarnymi zmiennymi:

individual 1 0 1 1 1 0 0 1 1 0 1 0

individual 2 1 0 1 0 1 1 0 0 1 0 1

Dla każdej zmiennej losujemy osobnika rodzicielskiego z

którego potomek otrzyma wartość binarną. W rezultacie
otrzumujemy dwa słowa binarne o długości 11 dla każdego
osobnika potomnego.

sample 1 0 1 1 0 0 0 1 1 0 1 0

sample 2 1 0 0 1 1 1 0 0 1 0 1

Po krzyżowaniu otrzymamy:

offspring 1 1 1 1 0 1 1 1 1 1 1 1

offspring 2 0 0 1 1 0 0 0 0 0 0 0

Inne metody krzyżowania

o krzyżowanie typu tasowanie,
o krzyżowanie ze zredukowanym surogatem.

Mutacja

Mutacja zmiennej rzeczywistej

Mutacja binarna/dyskretna

przed

mutacją

0 1 1

0 0 1 1 0 1 0

po mutacji

0 1 1

0 0 1 1 0 1 0

Tworzenie nowej populacji

• strategia globalna
• strategia lokalna

Strategia globalna

• wytworzenie takiej samej liczby potomków co osobników

rodzicielskich i zastąpienie osobników rodzicielskich przez
osobniki potomne (uboga strategia).

• wytworzenie mniejszej liczby potomków niż osobników

rodzicielskich i zastąpienie tych osobników w sposób losowy
jednolity (jednolita strategia).

• wytworzenie mniejszej liczby potomków niż osobników

rodzicielskich i zastąpienie najgorszych osobników osobnikami
potomnymi (elitarna strategia).

• wytworzenie większej liczby potomków niż potrzeba do

zastąpienia osobników rodzicielskich i zastąpienie osobnikami
najlepszymi (strategia oparta na dostosowaniu).

Strategia lokalna

W selekcji lokalnej osobniki są dobierane w granicach sąsiedztwa. Strategia

wymiany osobników odbywa się dokładnie w tym samym sąsiedztwie.
Występują następujące schematy:

• podmiana wszystkich osobników na osobniki potomne w sposób jednolity

losowy,

• podmiana osobników słabszych sąsiedztwa osobnikami potomnymi,
• wstawienie osobników potomnych lepiej dostosowanych niż najsłabsze

osobniki sąsiedztwa,

• wstawienie osobników potomnych lepiej dostosowanych niż najgorsze

osobniki i podmiana osobników rodzicielskich,

• wstawienie osobników potomnych lepiej dostosowanych niż najgorsze

osobniki i podmiana osobników w sposób jednolity losowy,

• wstawienie osobników potomnych lepiej dostosowanych niż rodzicielskie

oraz ich podmiana.

Algorytmy genetyczne

Szczególny przypadek algorytmów

ewolucyjnych

Podstawy

Przetwarzane populacje:

• P

- populacja bazowa

• O

- populacja potomna

• T

- populacja tymczasowa

W populacjach jest jednakowa liczba osobników.

Populacja początkowa powstaje przez losowe
wygenerowanie odpowiedniej liczby osobników.

Schematy

• Schematem jest dowolne słowo nad alfabetem {0, 1, *}. Przykład:

010*1, *110*, ***** , 10101, ...

• Znak * jest symbolem uniwersalnym oznaczającym dowolny znak.

• Schemat jest wzorcem opisującym wiele ciągów bitowych. np.

• *10*1 reprezentuje 01001, 01011, 11001, 11011

• o(H) – rząd schematu H = liczba pozycji ustalonych (nie “*”) w

schemacie H.

• (H) – rozpiętość schematu H = Odległość między skrajnymi

pozycjami ustalonymi (nie-gwiazdkowymi) w schemacie H

Algorytm genetyczny- schemat

begin
t := 0
inicjalizacja P

ocena P

  while (not warunek stopu) do
   begin

:= reprodukcja P

:= krzyżowanie i mutacja T

ocena O

t+1

:= O

t:=t+1

end
end

Kodowanie osobników

Kodowanie binarne - chromosom jest n-

elementowym wektorem genów, z których
każdy jest zerem lub jedynką.

0 1 0 0 0 1 0 1 1 0

gen

chromosom:

Operacje genetyczne:

• Mutacja jest operatorem wykonywanym dla

każdego genu osobno (z prawdo-
podobieństwem p

wartość genu zmienia się

na przeciwną).

0 1 1 0 0 0 0 1 1 0

osobnik potomny:

0 1 0 0 0 1 0 1 1 0

osobnik rodzicielski:

Operacje genetyczne:

• W krzyżowaniu biorą udział dwa osobniki

rodzicielskie. Jest ono jednopunktowe, a
miejsce rozcięcia jest wybierane losowo z
rozkładem równomiernym.

0 1 0 0 0 1 0 1 1 0

osobniki rodzicielskie:

1 1 0 1 0 1 1 1 0 0

0 1 0 0 0 1 1 1 0 0

osobniki potomne:

1 1 0 1 0 1 0 1 1 0

miejsce rozcinania

Reprodukcja

• Populacja T

jest tworzona przy użyciu reprodukcji

proporcjonalnej (ruletkowej).

• Prawdopodobieństwo skopiowania (reprodukcji) osobnika

X ze zbioru P

do zbioru T

wynosi:

gdzie: X , Y – osobniki,



– funkcja przystosowania

 









Strategie ewolucyjne

Strategia ewolucyjna polega na mutowaniu

pewnego początkowego rozwiązania.

strategia (1+1)

• W algorytmie strategii (1+1) występuje mechanizm

adaptacji zasięgu mutacji zwany regułą 1/5 sukcesów.

• Chromosomy: bazowy X

oraz tymczasowy Y

• Gen w chromosomie jest liczbą rzeczywistą.

Strategia ewolucyjna (1+1) -

schemat

begin
t := 0
inicjacja X

ocena X

  while (not warunek stopu) do
   begin

:= mutacja X

ocena Y

if ((Y

) > (X

)) than X

t+1

:= Y

else X

t+1

:= X

t:=t+1

end
end

Strategia ewolucyjna (1+1) - mutacja

gdzie:  - zasięg mutacji
 - wartość zmiennej losowej o rozkładzie normalnym

Chromosom Y

jest generowany przez dodanie losowej

modyfikacji do każdego genu chromosomu X

 







Reguła 1/5 sukcesów

• Jeżeli przez kolejnych k generacji liczba mutacji zakończonych sukcesem

jest większa niż 1/5, to należy zwiększyć zasięg mutacji (



:= c



• Gdy dokładnie 1/5 mutacji kończy się sukcesem, wartość



nie wymaga

modyfikacji.

• W przeciwnym przypadku należy zawęzić zasięg mutacji (



:= c



• Wartości parametrów modyfikujących:
c

= 0.82, c

= 1/0.82.

Strategia (1+1) ma niewielką odporność na minima lokalne, w związku z tym

powstały nowe schematy:

– strategia (1+)
– strategia ( + )
– strategia (, )

Strategia ( + )

Każdy osobnik składa się z dwóch chromosomów:

1. wektor X wartości zmiennych niezależnych

2. wektor



zawierający wartości odchyleń

standardowych wykorzystywanych podczas
mutacji

Strategia ( + ) – operacje

genetyczne

Mutacja

• Podczas mutacji najpierw modyfikowane są elementy

wektora



, a następnie na podstawie tego wektora

mutowany jest chromosom X.

• Dokonuje się samoczynna adaptacja zasięgu mutacji.

Krzyżowanie (rekombinacja)

• Najczęściej używa się operatora polegającego na

uśrednianiu lub na wymianie wartości wektorów X i



chromosomów macierzystych.

Strategia ( + ) – schemat

begin
t := 0
inicjacja P

ocena P

while (not warunek stopu) do

begin

:= reprodukcja P

:= krzyżowanie i mutacja T

ocena O

t+1

:=  najlepszych osobników z P



t:=t+1

end

end

Strategia ( , )

• ... zachowuje mechanizm ewolucyjny i strukturę kodowania

osobników strategii ( + ) , z wyjątkiem etapu tworzenia nowej
populacji bazowej P

t+1

• W przeciwieństwie do strategii ( + ) , nowa populacja bazowa P

t+1

tworzona jest wyłącznie z doboru najlepiej przystosowanych
osobników populacji tymczasowej O

(bez udziału poprzedniej

populacji bazowej P

• Zmiana mechanizmu tworzenia kolejnej populacji bazowej P

eliminuje

problem osobliwości dominującego osobnika, występującego w
strategii ( + ) . Ten rodzaj strategii powinien być bardziej odporny
na oddziaływanie zbioru przyciągania lokalnego ekstremum.

Równoległość w algorytmach

ewolucyjnych

Dlaczego równoległość ?

• Współbieżność obliczeń –

– Przyspieszenie algorytmu
– Poszerzenie obszaru przeszukiwań

• Poszukiwanie wielu rozwiązań – wiele

minimów lokalnych

• Zwiększenie efektywności poszukiwania

Migracja

Topologia nieograniczonej migracji (topologia

pełnej sieci)

Topologia migracji pierścieniowej

Topologia migracji sąsiedztwa
(implementacja 2-D)

Topologia pełnej sieci

Schemat migracji osobników pomiędzy

subpopulacjami

Migration

Topologia migracji pierścieniowej

Topologia migracji sąsiedztwa

Worker / Farmer genetic algorithm

Migracja osobników

Algorytm dyfuzyjno – genetyczny

Programowanie

genetyczne

Programowanie genetyczne

•

genetycznych

•

różnica pomiędzy GP GA

– reprezentacja rozwiązania.

Programowanie genetyczne

Tworzenie rozwiązań jako
programy lub schematy w
językach programowania

Algorytmy genetyczne

Tworzenie rozwiązań jako
łańcuchy liczb

Postacie osobników

• Osobnik jako sekwencja rozkazów

(instrukcji);

• Osobnik jako graf – drzewo (strukturalny

program, wyrażenie arytmetyczne /
algebraiczne)

4. Najlepszy utworzony w dowolnej populacji program, najlepsze
z możliwych rozwiązań, traktowane jest jako rezultat
programowania genetycznego [Koza 1992]

GP – cztery kroki tworzące algorytm

1. Tworzenie populacji początkowej jako losowej konstrukcji funkcji
i terminałów dla zadanego problemu (program komputerowy)

2. Wykonanie każdego z programów i przyznanie wartości
dostosowania stosownie do stopnia zdolności do rozwiązania
problemu

3. Tworzenie nowej populacji programów

- kopiowanie najlepszych programów populacji
- tworzenie nowych programów poprzez mutację

- tworzenie nowych programów poprzez krzyżowanie

(sexual reproduction).