TEORIA

ALGORYTMÓW

GENETYCZNYCH

Teoria Algorytmów Genetycznych

powstała w oparciu o

analogie do procesów obserwowanych w ewolucji
naturalnej.
Mechanizm ewolucji jest do zaobserwowania w

chromosomach

– łańcuchach

genów

znajdujących się w

jądrach

komórkowych.

Tam

zakodowana

jest

informacja o strukturze danego organizmu żywego.
Procesy rządzące ewolucją naturalną nie zostały jeszcze
po dziś dzień do końca odkryte, jednak niektóre jej

elementy zostały rozpoznane i zaakceptowane w świecie
naukowym.

Ewolucja

to proces odbywający się na chromosomach, w

których „zapisane” jest jak wykreować organizm zdolny
do przetrwania w danym środowisku. W toku naturalnej
selekcji organizmy lepsze, a więc i chromosomy je
opisujące mają większe szanse na reprodukcję.
Reprodukcja z kolei warunkuje ewolucję. W procesie
reprodukcji dzięki

krzyżowaniu się

(czyli łączeniu się

różnych części) chromosomów rodziców, potomek posiada
nową strukturę chromosomu. Może wystąpić również

mutacja

, która spowoduje, iż potomek będzie posiadał

nowe cechy, inne od cech jego biologicznych rodziców.

Ewolucja dąży wiec do

tworzenia organizmów coraz

doskonalszych

, coraz lepiej dostosowanych do

warunków panujących w danym środowisku.

Teoria ewolucji była inspiracją dla twórców
m

atem

atycznej

Teorii Algorytm

ów Genetycznych

J. von N

eum

anna oraz J. Hollanda.

Algorytmy Genetyczne

są algorytmami losowymi, które poczynając od
początkowego zbioru rozwiązań tworzą

zbiory rozwiązań

coraz lepszych

. Nowe rozwiązania generowane są z

zastosowaniem operatorów genetycznych, symulujących
naturalne procesy reprodukcji. Każdy z elementów
przestrzeni rozwiązań (populacji) jest nazywany

chromosomem

, a składowe kodu chromosomu są

nazywane

genami

. Operatory genetyczne noszą zaś nazwy

krzyżowania

bądź też

mutacji

.

MODEL KLASYCZNY
ALGORYTMU
GENETYCZNEGO

PROSTY OPIS KLASYCZNEGO

ALGORYTMU GENETYCZNEGO

(K – AG):

K – AG operuje na zbiorach łańcuchów

złożonych z zer i jedynek.

Pojedynczy element łańcucha przyjmujący

wartości „0” lub „1” nazywamy

genem

.

Łańcuchy genów nazywamy

chromosomami.

Zbiór chromosomów o określonej

liczności

nazywamy

populacją

.

Przyjmuje się, że w ramach określonej populacji

wszystkie chromosomy są tej samej długości.

Długość chromosomu i liczność populacji określane są

na etapie projektowania K – AG dla konkretnego
problemu i zależą od jego charakteru.

Dla określonej populacji określone są następujące

mechanizmy :
 mechanizm generacji populacji początkowej;
 mechanizm oceniający „jakość” konkretnego

chromosomu;

 mechanizm selekcji do dalszego przetwarzania tzw.

reprodukcji;

 mechanizm mutacji;
 mechanizm krzyżowania.

Generacja populacji początkowej polega na losowym
utworzeniu

liczby

chromosomów.

Np.

należy

wygenerować populację sześciu chromosomów o
długości dziesięciu genów. Realizacja to 60 rzutów
monetą, gdzie reszka to „0”, a orzeł to „1”.

Przykładowy wynik rzutów – populacja :

(1,1,1,0,1,1,1,1,0,1)

(1,0,0,0,1,1,0,1,0,0)
(0,0,0,1,1,0,1,1,0,1)
(0,0,1,0,0,0,1,0,0,0)
(0,1,1,0,1,0,1,1,0,1)

(0,0,1,0,1,0,0,0,0,0)

Ocena „jakości” konkretnego chromosomu polega
na obliczeniu tzw. funkcji przystosowania. Funkcja ta

jest miarą w jakim stopniu dany chromosom
rozwiązuje dany problem.

Postać funkcji przystosowania ściśle zależy od
charakteru rozwiązywanego problemu i jest jedynym

mechanizmem K – AG, poza długością chromosomu
i licznością populacji, każdorazowo zmienianym na
etapie projektowania K – AG dla rozwiązania danego
problemu.

W teorii AG zakłada się, że funkcja przystosowania

przyjmuje na swej dziedzinie zawsze wartości
nieujemne i zakłada, że rozwiązywany problem to

znalezienie maksimum tej funkcji. Jeśli pierwotna
postać funkcji przystosowania nie spełnia tych założeń

dokonuje się jej transformacji.
Np. oznaczając funkcję przystosowania przez FP biorąc

pod uwagę populację z poprzedniego przykładu,
problemem będzie znalezienie takiego chromosomu,
który posiada największą z możliwych liczbę jedynek,
wtedy :

FP(1,1,1,0,1,1,1,1,0,1)=8
FP(1,0,0,0,1,1,0,1,0,0)=4

FP(0,0,0,1,1,0,1,1,0,1)=5
FP(0,0,1,0,0,0,1,0,0,0)=2

FP(0,1,1,0,1,0,1,1,0,1)=6
FP(0,0,1,0,1,0,0,0,0,0)=2

Największą wartość funkcji przystosowania ma

pierwszy chromosom, w tej populacji najbardziej
nadaje się on do rozwiązania problemu

Selekcja chromosomów do dalszego przetwarzania

polega na wybraniu zbioru chromosomów, o tej samej
liczebności co populacja początkowa, które staną się

„rodzicami” nowo tworzonej populacji „potomków” -
czyli wybraniu zbioru przeznaczonego do reprodukcji.
Selekcja ta ma przebieg losowy jednak przeprowadzana
jest w taki sposób, aby chromosomy o największej

wartości funkcji przystosowania miały największe
szanse być wylosowane do reprodukcji.

Najprostszą metodą selekcji jest metoda ruletki
działająca w następujący sposób :

1) Sumuje się wartości funkcji przystosowania

wszystkich chromosomów;

2) Obliczona suma jest traktowana jako 100% - całe

„koło” ruletki;

3) Każdemu chromosomowi przydzielany jest kolejno

taki wycinek koła ruletki jaki wynika z następującej
proporcji :

[ ( wartość funkcji przystosowania dla danego
chromosomu ) / ( suma wartości funkcji przystosowania
wszystkich chromosomów ) ] * 100 %
Wycinek taki jest przedziałem [ a, b ], gdzie
0 <= a, b <= 100 i jest miarą prawdopodobieństwa
wylosowania danego chromosomu.

4) Losuje się liczbę p z przedziału [ 0, 100 ], która

liczba to wskazuje konkretny punkt na kole ruletki.

5) Chromosom, na którego wycinek trafił

wylosowany punkt, czyli a <= p <= b, jest
przeznaczony do reprodukcji.

6) Liczba losowań jest równa liczności populacji.

Wylosowane do reprodukcji chromosomy łączone są
losowo w pary „rodziców”, które następnie na drodze

krzyżowania i mutacji przekształcone zostaną w pary
potomków tworząc tym samym nową populację.

Mutacja chromosomu

jest mechanizmem oddziaływującym na populację
rodziców przed procesem krzyżowania lub na populację
potomków utworzoną w wyniku krzyżowania.

Mutacja przebiega w następujący sposób :
1) Ustalane jest na etapie projektowania K – AG

prawdopodobieństwo p

m

zaistnienia mutacji; zakłada

się, że jest ono bardzo małe, gdyż mutacje w świecie
żywych organizmów zachodzą statystycznie niezwykle
rzadko.

2) Dla każdego n – tego genu z kolejnego chromosomu

losowana jest liczba k z przedziału [ 0, 1 ] i jeżeli k
<= p

m

wtedy dany gen podlega mutacji.

3) Gen podlega mutacji polegającej na zmianie jego

wartości tj. z 0 na 1 lub odpowiednio z 1 na 0.

4) Decyzja,

czy

mutacja

populacji

będzie

przeprowadzona przed czy po krzyżowaniu, nie
wpływa na merytoryczny efekt mutacji.

Np.
chromosom rodzica przed mutacją

(0,0,1,0,1,

0

,1,0,0)

wylosowany punkt mutacji : n = 6
chromosom rodzica po mutacji
(0,0,1,0,1,

1

,1,0,0)

W tym przypadku mutacja poprawiła „jakość”
chromosomu, mogło się jednak stać na odwrót. Rolą
mutacji jest nie tyle zmiana jakościowa chromosomów,
co wprowadzenie nowego „materiału genetycznego” do
danej populacji, mogło się bowiem zdarzyć, że wszystkie
chromosomy rodziców posiadały gen o numerze szóstym
równy 0, wtedy korzystając tylko z mechanizmu
krzyżowania bez mutacji nie byłoby nigdy szansy na
otrzymanie chromosomu potomka posiadającego szósty

gen równy 1.

Krzyżowanie par chromosomów ma na celu wymianę
części materiału genetycznego pomiędzy chromosomami,
co może zaowocować potomkiem dziedziczącym tylko
„lepsze” cechy swoich rodziców.
Przebieg krzyżowania jest następujący :
1) Na etapie projektowania K – AG prawdopodobieństwo

krzyżowania p

k

, zakłada się, że jest ono stosunkowo

duże (niekiedy przyjmuje się nawet, że p

k

= 1) jak

nakazuje analogia do świata żywych organizmów.

2) Dla każdego chromosomu z populacji rodziców

losowana jest liczba k z przedziału [ 0, 1 ] i jeżeli k <=
p

m

wtedy dany chromosom przeznaczony jest do

krzyżowania.

3) Z grupy chromosomów przeznaczonych do

krzyżowania tworzone są losowo pary rodziców. W
przypadku, gdy liczność tej grupy jest nieparzysta
losuje się jeden dodatkowy chromosom.

4) Dla każdej pary rodziców losujemy punkt

krzyżowania, czyli numer genu n, w miejscu którego
nastąpi krzyżowanie.

5) Potomek pierwszy otrzymuje pierwsze n genów od

rodzica pierwszego, a pozostałe geny począwszy od genu
numer n + 1 od rodzica drugiego.

6) Potomek drugi otrzymuje pierwsze n genów od rodzica

drugiego, a pozostałe geny począwszy od genu numer
n + 1 od rodzica pierwszego.

Np.
Zakładamy, że wylosowane zostały do krzyżowania
wszystkie chromosomy z poprzedniej przykładowej
populacji i utworzyły poniższe pary, ponadto żaden z
chromosomów rodziców nie uległ mutacji.

RODZICE KRZYŻOWANIE POTOMKOWIE

n = 5
(

1,1,1,0,1,1,1,1,0,1

) (

1,1,1,0,1

,0,1,1,0,1

)

}

(

0,0,0,1,1,0,1,1,0,1

) (

0,0,0,1,1,

1,1,1,0,1

)

n = 3
(

1,1,1,0,1,1,1,1,0,1

) (

1,1,1

,0,1,0,1,1,0,1

)

}

(

0,1,1,0,1,0,1,1,0,1

) (

0,1,1,

0,1,1,1,1,0,1

)

n = 7
(

1,0,0,0,1,1,0

,

1,0,0

) (

1,0,0,0,1,1,0,

0,0,0

)

}

(

0,0,1,0,1,0,0,0,0,0

) (

0,0,1,0,1,0,0

,1,0,0

)

Policzmy wartość funkcji przystosowania populacji
potomków :

FP(1,1,1,0,1,0,1,1,0,1) = 7
FP(0,0,0,1,1,1,1,1,0,1) = 6

FP(1,1,1,0,1,0,1,1,0,1) = 7
FP(0,1,1,0,1,1,1,1,0,1) = 7

FP(1,0,0,0,1,1,0,0,0,0) = 3
FP (0,0,1,0,1,0,0,1,0,0) = 3

Jak widać populacja potomków charakteryzuje się o
wiele większą średnią wartością funkcji przystosowania

niż populacja rodziców, z drugiej jednak strony
„utracony” został chromosom o największej wartości
(= 8) funkcji przystosowania.

Schemat blokowy K – AG :

(etap – 0)

Generacja populacji początkowej.

(etap – „a”)

Obliczanie wartości funkcji przystosowania

chromosomów

należących do populacji początkowej.

(etap – „b”)

Selekcja metodą „ruletki” chromosomów

przeznaczonych do reprodukcji.

(etap – „c”)

Tworzenie operatorami mutacji i krzyżowania

nowej populacji potomków.

(etap – „d”)

Obliczanie wartości funkcji przystosowania

chromosomów

należących do populacji potomków.

(etap – „e”)

Populacja rodziców jest kasowana.

Populacja potomków staje się nową populacją rodziców.

(etap – „f”)

Warunek końca działania algorytmu :

Nie spełniony wtedy powrót do etapu – „b”;

Spełniony wtedy STOP.

Najlepszy chromosom z bieżącej populacji traktowany

jest jako rozwiązanie danego problemu.

ŚCISŁA DEFINICJA
ALGORYTMU
GENETYCZNEGO

Klasyczny Algorytm Genetyczny

jest probabilistycznym

algorytmem poszukiwania przestrzeni rozwiązań.

Oznaczenia :

 P – problem optymalizacyjny z funkcją celu F;
 D (P) – zbiór rozwiązań dopuszczalnych problemu P;

Chromosomem

nazywać będziemy wektor :

X = ( x

1

, ... , x

n

) є D (P)

będący rozwiązaniem dopuszczalnym problemu P;

Populacją rozwiązań dopuszczalnych

problemu P dla

iteracji t nazwiemy podzbiór :

S(t) = { X

t

1

, ... , X

t

m

} S(t) с D(P)

Funkcją przystosowania U

rozwiązania

X

t

i

є S(t)

nazywamy wartość funkcji celu dla tego rozwiązania :

U( X

t

i

) = F ( X

t

i

)

gdzie U( X

t

i

) ? 0

Λ

X

t

i

є S(t)

Operatorem mutacji M

k

nazywać będziemy

przekształcenie :

M

k

: D(P) ? D(P)

dokonujące losowej, z zadanym prawdopodobieństwem,
zmiany k – tej składowej rozwiązania X

t

i

:

M

k

( X

t

i

) = X

t

i

+1

gdzie :

X

t

i

= (x

1

, ... , x

k

, ... , x

n

) X

t

i

+1

= (x

1

, ... , x

k

, ... , x

n

)

Operatorem krzyżowania K

k

nazywać będziemy

przekształcenie :

K

k

: D(P) × D(P) ? D(P) × D(P)

dokonujące losowej, z zadanym prawdopodobieństwem,
wymiany składowych rozwiązań X

t

i

i X

t

j

względem

składowej k :

K

k

( X

t

i

, X

t

j

) = (X

t+1

i

, X

t+1

j

)

gdzie : X

t

i

= (x

1

, ... , x

n

) X

t

j

= (v

1

, ... , v

n

)

X

i

t+1

= (x

1

, ... , x

k

, v

k+1

, ... , v

n

)

X

j

t+1

= (v

1

, ... , v

k

, x

k+1

, ... , x

n

)

Schemat blokowy K – AG :

(etap – 0)

Generacja losowa populacji początkowej S(t

0

).

(etap – „a”)

Obliczanie wartości funkcji przystosowania

chromosomów

należących do populacji początkowej S(t

0

).

(etap – „b”)

Selekcja metodą „ruletki” rozwiązań z S(t)

przeznaczonych do reprodukcji.

Wybrane rozwiązania należą do S

I

(t) , pozostałe

rozwiązania są kasowane.

(etap – „c”)

Tworzenie operatorami mutacji i krzyżowania nowej

populacji S(t+1)

M

k

: S

I

(t) S(t+1) ; K

k

: S

I

(t) S(t+1)

(etap – „d”)

Obliczanie wartości funkcji przystosowania

dla rozwiązań należących do S

I

(t+1).

(etap – „e”)

Populacja S

I

(t) jest kasowana.

Populacja S(t+1) jest kopiowana w miejsce

populacji S(t)

(etap – „f”)

Warunek końca działania algorytmu :

Nie spełniony wtedy powrót do etapu – „b”;

Spełniony wtedy STOP.

Najlepsze rozwiązanie z S(t) traktowane

jest jako rozwiązanie optymalne problemu P.

PODSTAWY
MATEMATYCZNE

DEFINICJE

Schematem S

nazywamy łańcuch zawierający k

elementów zdefiniowany nad alfabetem {0,1,*}
reprezentujący wszystkie chromosomy o liczbie genów

równej k i identyczne z S na wszystkich pozycjach
określonych tzn. pozycjach zawierających „0” lub „1” w
schemacie S.
Pojawienie się symbolu „*” na pozycji n – tego genu

chromosomu oznacza, że gen na n – tej pozycji może być
dowolny – jego wartość nie określona.

Powiemy, że chromosom ch dopasowany jest do
schematu S wtedy, gdy :
1) liczba elementów schematu S równa jest liczbie

genów chromosomu ch;

2) chromosom ch i schemat S są identyczne na

wszystkich pozycjach określonych tzn. na pozycjach
zawierających „0” lub „1” w schemacie S.

Licznością schematu S

nazwiemy liczbę L(S) równą

ilości pozycji określonych w tym schemacie.

WPŁYW MUTACJI
I KRZYŻOWANIA

Wpływ mutacji

mechanizm mutacji zmieniający wartość genu z „0” na

„1” (lub vice versa) może doprowadzić do zniszczenia
schematu S – dopasowanego do chromosomu, którego
gen uległ mutacji.

Wpływ krzyżowania

mechanizm

krzyżowania

tworzący

chromosomy

potomne poprzez losową wymianę partii genów z losowo
wybranych par chromosomów rodziców może
doprowadzić do zniszczenia schematu S – dopasowanego
do jednego z chromosomów rodziców.

TWIERDZENIE O SCHEMATACH 1

Liczba wystąpień krótkich, mało licznych schematów o

przystosowaniu powyżej średniej rośnie wykładniczo w
kolejnych iteracjach algorytmu genetycznego.

TWIERDZENIE

O BLOKACH BUDUJĄCYCH 1

Algorytm genetyczny znajduje rozwiązania bliskie

wartości optymalnej poprzez zestawienie krótkich, mało
licznych o przystosowaniu dużo powyżej średniej

schematów – zwanych blokami budującymi.

OPERTORY
GENETYCZNE

KRZYŻOWANIE WIELOPUNKTOWE

Parzysta liczba punktów krzyżowania :

 chromosomy rodziców traktowane są jako koła,
 losowane są punkty na kole,
 wymiana genów następuje zgodnie z poniższym

schematem (gdzie liczba punktów przecięcia = 4),

Nieparzysta liczba punktów krzyżowania

wymiana genów następuje zgodnie z poniższym

schematem (gdzie liczba punktów przecięcia = 5) :

KRZYŻOWANIE JEDNOLITE

przebiega w następujący sposób :

 dla każdej pozycji genu pierwszego z pary

chromosomów potomków losowane jest z pewnym

ustalonym prawdopodobieństwem, który z rodziców
przekaże mu swój gen z tej pozycji,

 drugi z pary chromosomów potomków otrzymuje

pozostałe (nie wylosowane dla pierwszego) gen z
chromosomów rodziców.

OPERATORY
ZMIENIAJĄCE
PORZĄDEK

Operator inwersji

działa, tak jak operatory krzyżowania i mutacji, na

chromosom rodzica w celu utworzenia chromosomu
potomka. Jednak w odróżnieniu od nich działa on na
pojedynczym chromosomie.
Inwersja polega na losowym wybraniu fragmentu

chromosomu i odwróceniu (ustawieniu w odwrotnej
kolejności) genów w tym fragmencie.

Krzyżowanie pozycją PMX

polega na zamianie pozycji genów w chromosomach
rodziców zgodnie ze wzorcem (obszarem dopasowania)

pozycji chromosomów z pary : dla pary ( ch

1

, ch

2

)

chromosomów rodziców losuje się dwa punkty

krzyżowania,

obszary

chromosomów

pomiędzy

wylosowanymi punktami nazywane są obszarami
dopasowania, geny z chromosomu ch

1

zamieniają się

pozycją tak, aby była ona zgodna z pozycjami
wskazanymi w obszarze dopasowania chromosomu ch

2

i vice versa.

Krzyżowanie porządkiem OX

polega na zamianie porządku genów w chromosomach
rodziców zgodnie ze wzorem (obszarem dopasowania)

pozycji w chromosomie z pary : dla pary ( ch

1

, ch

2

)

chromosomów rodziców losuje się dwa punkty

krzyżowania,

obszary

chromosomów

pomiędzy

wylosowanymi punktami nazywane są obszarami
dopasowania, geny z chromosomu ch

1

zamieniają się

porządkiem tak, aby był on zgodny z porządkiem
wskazanym w obszarze dopasowania chromosomu ch

2

i vice versa.

Krzyżowanie cykliczne CX

polega na kopiowaniu do chromosomu potomka genów z

kolejnych pozycji jednego rodzica, a następnie z
drugiego.

Mutacja pozycją

polega na zamianie pozycji dwóch wylosowanych genów
w danym chromosomie.

Mutacja porządkiem

polega na zamianie kolejności występowania w
chromosomie dwóch wylosowanych genów – drugi z

genów stawiany jest przed pierwszym.

Z wyżej wymienionych operatorów szczególnie
skuteczny okazał się PMX znajdując rozwiązania

optymalne lub bliskie optymalnym.

ZASTOSOWANIA
ALGORYTMÓW
GENETYCZNYCH

ALGORYTM ROZPOZNAWANIA

WZORCÓW BINARNYCH

Algorytm

genetyczny

wzorców

binarnych

wykorzystywany jest np. przy projektowaniu
automatycznych

systemów

rozpoznawania,

klasyfikowaniu obrazów takie, jak automatyczne
rozpoznawanie występowania obiektów o znanych
charakterystykach na seriach zdjęć satelitarnych.

ALGORYTM WYKRYWANIA BRZEGU

Zadanie rozpoznawania brzegów jest jednym z
podstawowych problemów cyfrowej analizy obrazów.
Uwaga wielu grup badawczych skupiona jest na analizie
obrazów biologicznych i medycznych.
Przykładem może być analiza kształtu naczyń

krwionośnych, dzięki której można wykryć wiele chorób
serca i zagrożeń życia.

Typowy obraz naczyń krwionośnych mózgu :

Kłopotem przy analizie obrazu jest występowanie wielu
rozgałęzień. Algorytm genetyczny wykorzystany w tym

przypadku jest dwuetapowy :
wyznacza charakterystyczne punkty brzegowe oraz
łączy te punkty tworząc krzywą brzegu.

Schemat algorytmu wstępnego wyznaczania punktów
brzegu :

Po wykonaniu wielu iteracji (w tym przypadku 20)

został automatycznie wyznaczony przez algorytm
sterujący.

KONIEC

DZIĘKUJEMY