1

 

Algorytmy genetyczne

i ich zastosowanie

2

 

1.

Problem optymalizacji globalnej                              

2.

Algorytmy genetyczne                                            
 

3.

Przykład zastosowanie AG w interpretacji danych 
pomiarowych                                                      

4.

Podsumowanie i literatura o AG

3

1. Problem optymalizacji globalnej

– analityczne

– numeryczne (np. gradientowe)

– enumeracyjne

Metody klasyczne

Jak znaleźć

globalne maksimum

(globalne minimum)

– błądzenie przypadkowe

– symulowane wyżarzanie

– sieci neuronowe

– logika rozmyta

– algorytmy genetyczne

Nowe metody

f(x)

x

maksimum globalne

maksimum
lokalne

?

Np.: wieloparametrowe dopasowanie
krzywych teoretycznych do
punktów eksperymentalnych  parametry modelu

4

2. Wiadomości podstawowe o AG

AG

 =

 Poszukiwanie maksymalnej wartości funkcji 

przystosowania oparte na mechanizmach doboru 

naturalnego oraz dziedziczności łączące ewolucyjną 

zasadę przeżycia najlepiej przystosowanych   

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

informacji

.

5

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

6

 

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ń.

7

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!

8

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

9

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

10

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

11

FP

maksimum globalne

1. pokolenie

2. pokolenie

itd.

Ewolucja – dążenie do optymalnego rozwiązania

12

 

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

13

 

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

14

 

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

15

 

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.

16

 

Twierdzenie o schematach

Teza:

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

danego schematu w kolejnej genaracji                jest 

szacowana zgodnie ze wzorem:

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

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

chromosomu.

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∣

17

 

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.       

18

 

Reprodukcja proporcjonalna (metoda 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.      

19

 

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ństworeprodukcji 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,

20

 

Reprodukcja turniejowa

Wybieramy z jednakowym prawdopodobieństwem q 

osobników z populacji bazowej. Nastepnie z tak utworzonej 

populacji Q wybieramy najlepszego osobnika do populacji 

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

Losowanie do populacji Q mozemy prowadzić ze 

zwracaniem  oraz bez zwracania. 

      

21

 

Sukcesja z całkowitym zastępowaniem

Jest to najczęściej stosowanym sposobem tworzenia kolejnej 

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

Sukcesja tan nie wprowadza mechanizmu nacisku 

selektywnego.

      

22

 

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 najgprzej przystosowane osobniki,

- usuwamy osobniki najbardziej podobne do potomnych,  należy 

  wprowadzić miarę podobieństwa osobników.

- usuwamy losowo wybrane osobniki.

      

23

 

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

24

3. Zastosowanie AG w dopasowaniu…

na przykładzie metody PLS

3

próbka
temp. pokojowa

E

C

E

V

E

g

fotodetektor



laser

filtr

Y

PL

=

I

PL

/



natężenie światła wzbudzającego



w

y

d

a

jn

o

ś

ć

 k

w

a

n

to

w

a

 P

L

N

SS

(E)

eV

-1

cm

-2

E

C

E

V

energia, eV

Analiza

ilościowa

!

E

PL

E

g



1

>



2

25

Schemat analizy danych w PLS

3

Procedura

dopasowująca

Dane

eksperymentalne

Zależność

teoretyczna Y

PL

()

5 parametrów

N

SS

(E)

Wyznaczenie

N

SS

(E)

dobrze

źle

1. dobór 

procedury dopasowującej

2. definicja 

błędu dopasowania

:

 pomiary w jednostkach względnych

 jednoczesna analiza wielu zależności eksperymentalnych

2 kluczowe problemy

Ad 1. Wybór algorytmu genetycznego:

 metoda bezgradientowa (szybkość obliczeń)

 brak wstępnych danych o N

SS

(E)

Symulator

Dopasowanie

 =

= minimalizacja

błędu dopasowania

26

Definicja funkcji błędu dopasowania (FBD)

































































2

1

1

2

2

2

2

2

1

2

1

1

1

1

1

1

2

1

N

i

i

e

i

t

i

e

N

i

i

e

i

t

i

e

y

y

y

N

y

y

y

N

FBD

 

1

,

0

1

1

1

1

2

1

1

0

d

d

2

1

2

1

1

2

2

2

2

1

2

1

1

1

2

1

2

2

2

1

1

1

1







































































N

i

i

e

i

t

N

i

i

e

i

t

N

i

i

e

i

t

N

i

i

e

i

t

y

y

N

y

y

N

y

y

N

y

y

N

FBD

FBD





FBD

E

N

FP

SS

1

)

(



·y

t1

(x)

·y

t2

(x)

y

x

1

100

zmodyfikowana

metoda

najmniejszych

kwadratów

PLS

3

: x, yY

PL

,

 – czynnik geometryczny

27

Proces dopasowania za pomocą 

AG

FBD

5 parametrów N

ss

(E)

Y

PL



*

*

*

*  *  * *

pokolenie

pierwsze

końcowe

pośrednie

28

Przykłady dopasowań

F  [foton cm

-2

 s

-1

]

10

20

10

21

10

22

10

23

10

24

Y

P

L

 [j

ed

n.

 w

zg

l�

dn

e]

10

-3

10

-2

10

-1

polerowana
bombardowana
wygrzewana w As

Moison i inni

Appl. Phys. Lett. 1986

N

SS

 [eV

-1

 cm

-2

]

10

11

10

12

10

13

10

14

E

C

E

HO

E

V

s

n

=10

-14

 cm

2

s

n

=s

p

=10

-13

 cm

2

E

Fs

dopasowani

e

Powierzchnia InP(100) poddana cyklowi obróbek

M. Miczek: praca doktorska

29

Przykłady dopasowań

Powierzchnia GaAs(100) przed i po siarkowaniu w Na

2

S

(aq)

N

SS

 [eV

-1

cm

-2

]

10

11

10

12

10

13

10

14

E

C

E

V

E

HO

E

Fs

F  [foton cm

-2

 s

-1

]

10

16

10

18

10

20

10

22

Y

PL

0.1

1.0

10.0

przed Na

2

S

po Na

2

S

Liu, Kauffman

Appl. Phys. Lett. 1995

dopasow

ani

e

M. Miczek: praca doktorska

30

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.

31

 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.