Podstawy algorytmów
ewolucyjnych
Dariusz Badura
Ewolucyjne projektowanie
2. Evaluate Circuit
3. Select Breeding Pairs
Fitness
1 0 1 0 1 1 0 1 0 1
30
1 0 1 0 0 1 0 1 0 0
28
1 1 1 1 0 1 0 0 1 1
18
1 0 0 1 0 1 0 1 1 0
14
0 0 1 1 0 1 1 0 1 1
14
1. Create New Population
0 0 1 1 0 1 1 0 1 1
1 0 1 0 0 1 0 0 1 1
Iterate until
1 1 1 1 0 1 0 1 0 0
stopping conditions 4. Cross Over
are met
1 0 0 1 0 1 0 1 1 0
1 0 1 0 1 1 0 1 0 1
1 0 1 0 1 1 0 1 0 1
1 1 1 1 0 1 0 0 1 1
6. Insert Into New Population 5. Mutate
1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1
1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 1
Ewolucyjne przeszukiwanie
... oznaczać będzie poszukiwanie rozwiązania problemu 
zadania poprzez wprowadzenie losowego generowania
rozwiązań z wykorzystaniem operatorów genetycznych.
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.
W celu porównania skuteczności ewolucyjnego i losowego
przeszukiwania należałoby porównać czas poszukiwania
satysfakcjonujÄ…cego rozwiÄ…zania obiema metodami.
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
ocena
Kodowanie
osobników
rozwiÄ…zania
funkcja
Problem
oceniajÄ…ca
mutacja
selekcja
genetyczne
operatory
poszukiwanie
genetyczne
wiedza
operacje replikacja
genetyczne
RozwiÄ…zanie
Algorytm ewolucyjny
RozwiÄ…-
czy spełniony
Inicjacja Ocena
zanie
war. term. ?
populacji populacji
Selekcja
osobników
Operacje
genetyczne
Tworzenie
nowej
populacji
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
Nind  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:
2*(SP -ð 1)*(Pos -ð 1)
Fitness(Pos) =ð 2 -ð SP +ð
Nind -ð 1
Wartość SP (presji selekcji) mieści się w zakresie [1.0, 2.0].
Ranking nieliniowy
Dopuszcza większe wartości presji selekcji, przy funkcji
dostosowania określonej wzorem:
( Pos -ð1)
X
Fitness(Pos) =ð Nind *
Nind
i -ð1
X
åð
i=ð1
X jest pierwiastkiem wielomianu:
Nind -ð1 Nind -ð2
0 =ð (SP -ð Nind )* X +ð SP * X +ð Kð+ð SP * X +ð SP
lub w innej postaci:
Nind
X -ð 1
Nind -ð1
0 =ð SP * -ð Nind * X
X -ð 1
Ranking nieliniowy pozwala kształtować wartości presji selekcji
(SP) w zakresie [1.0, Nind - 2.0].
Funkcja dostosowania
liniowego i nieliniowego rankingu
wartość dostosowania (param.: presja selekcji)
Wartość oceny
ranking liniowy bez rank. ranking nieliniowy
2,0 1,1 1,0 3,0 2,0
1
2,0 1,10 1.0 3,00 2,00
3
1,8 1,08 1.0 2,21 1,69
4
1,6 1,06 1.0 1,62 1,43
7
1,4 1,04 1.0 1,16 1,21
8
1,2 1,02 1.0 0,88 1,03
9
1,0 1,00 1.0 0,65 0,87
10
0,8 0,98 1.0 0,48 0,74
15
0,6 0,96 1.0 0,35 0,62
20
0,4 0,94 1.0 0,26 0,53
30
0,2 0,92 1.0 0,19 0,45
95
0,0 0,90 1.0 0,14 0,38
Funkcja dostosowania
liniowego i nieliniowego rankingu
2,5
2,0
1,5
Serie1
Serie2
1,0
0,5
0,0
1 2 3 4 5 6 7 8 9 10 11
Funkcja dostosowania
liniowego i nieliniowego rankingu
Ranking nieliniowy
3,50
3,00
2,50
2,00
Serie1
1,50
Serie2
1,00
0,50
0,00
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 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
f. dostosowania
Właściwości selekcji
rankingowej
Intensywność selekcji:
1
SelIntRank(SP) =ð (SP -ð 1)*
pð
Utrata różnorodności:
SP -ð 1
LossDivRank(SP) =ð
4
Wariancja selekcji:
(SP -ð 1)2
SelVarRank(SP) =ð 1 -ð =ð 1 -ð (SelIntRank(SP))2
pð
Właściwości selekcji rankingowej
Selekcja koła ruletki
Number of
1 2 3 4 5 6 7 8 9 10 11
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
0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.02 0.0
probability
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
wskaz
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
Zależność pomiędzy
truncation 10 20 40 50 80
1%
pomiędzy poziomem threshold % % % % %
odcięcia a
Selection
2.66 1.76 1.2 0.97 0.8 0.34
intensity
intensywnością
selekcji
2
fc
-
1
2
SelIntTrunc(Trunc) =ð
* e
Trunc * 2*pð
Utrata różnorodności:
LossDivTrunc(Trunc) = 1-Trunc.
Wariancja selekcji:
SelVarTrunc(Trunc) = 1-SelIntTrunc(Trunc)·(SelIntTrunc(Trunc)-fc).
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 - Nind.
Tournament size 1 2 3 5 10 30
selection intensity 0 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 + að (rodzic 2  rodzic 1),
gdzie að 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 að 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 að :
Nowe osobniki  potomne :
próbka 1 0.5 1.1 -0.1
potomek 1 67.5 1.9 2.1
próbka 2 0.1 0.8 0.5
potomek 2 23.1 8.2 19.5
Rekombinacja liniowa
Współczynnik að 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
0 1 1 1 0 0 1 1 0 1 0
mutacjÄ…
po mutacji 0 1 1 0 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:
" Pt - populacja bazowa
" Ot - populacja potomna
" Tt - 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.
" dð(H)  rozpiÄ™tość schematu H = OdlegÅ‚ość miÄ™dzy skrajnymi
pozycjami ustalonymi (nie-gwiazdkowymi) w schemacie H
Algorytm genetyczny- schemat
begin
t := 0
inicjalizacja P0
ocena P0
while (not warunek stopu) do
begin
Tt := reprodukcja Pt
Ot := krzyżowanie i mutacja Tt
ocena Ot
Pt+1 := Ot
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ą.
chromosom:
0 1 0 0 0 1 0 1 1 0
gen
Operacje genetyczne:
" Mutacja jest operatorem wykonywanym dla
każdego genu osobno (z prawdo-
podobieństwem pm wartość genu zmienia się
na przeciwnÄ…).
osobnik rodzicielski:
0 1 0 0 0 1 0 1 1 0
osobnik potomny:
0 1 1 0 0 0 0 1 1 0
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.
osobniki rodzicielskie: osobniki potomne:
0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0
1 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 0
miejsce rozcinania
Reprodukcja
" Populacja Tt jest tworzona przy użyciu reprodukcji
proporcjonalnej (ruletkowej).
" Prawdopodobieństwo skopiowania (reprodukcji) osobnika
X ze zbioru Pt do zbioru Tt wynosi:
Fð(ðX )ð
pr(ðX )ð=ð
åðFð(ðY)ð
YÎðPt
gdzie: X , Y  osobniki, Fð  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 Xt oraz tymczasowy Yt
" Gen w chromosomie jest liczbÄ… rzeczywistÄ….
Strategia ewolucyjna (1+1) -
schemat
begin
t := 0
inicjacja Xt
ocena Xt
while (not warunek stopu) do
begin
Yt := mutacja Xt
ocena Yt
if (Fð(Yt) > Fð(Xt)) than Xt+1 := Yt
else Xt+1 := Xt
t:=t+1
end
end
Strategia ewolucyjna (1+1) - mutacja
Chromosom Yt jest generowany przez dodanie losowej
modyfikacji do każdego genu chromosomu Xt :
Yit =ð Xit +ðsðxðN(ð0,1)ð,i
gdzie: sð - zasiÄ™g mutacji
xð - wartość zmiennej losowej o rozkÅ‚adzie normalnym
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 (sðóð:= ci sð).
" Gdy dokÅ‚adnie 1/5 mutacji koÅ„czy siÄ™ sukcesem, wartość sð nie wymaga
modyfikacji.
" W przeciwnym przypadku należy zawÄ™zić zasiÄ™g mutacji (sðóð:= cd sð).
" Wartości parametrów modyfikujących:
cd = 0.82, ci = 1/0.82.
Strategia (1+1) ma niewielką odporność na minima lokalne, w związku z tym
powstały nowe schematy:
 strategia (1+lð)
 strategia (mð + lð)
 strategia (mð, lð)
Strategia (mð + lð)
Każdy osobnik składa się z dwóch chromosomów:
1. wektor X wartości zmiennych niezależnych
2. wektor sð zawierajÄ…cy wartoÅ›ci odchyleÅ„
standardowych wykorzystywanych podczas
mutacji
Strategia (mð + lð)  operacje
genetyczne
Mutacja
" Podczas mutacji najpierw modyfikowane sÄ… elementy
wektora sð, 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 sð
chromosomów macierzystych.
Strategia (mð + lð)  schemat
begin
t := 0
inicjacja Pt
ocena Pt
while (not warunek stopu) do
begin
Tt := reprodukcja Pt
Ot := krzyżowanie i mutacja Tt
ocena Ot
Pt+1 := mð najlepszych osobników z Pt Èð Ot
t:=t+1
end
end
Strategia (mð ,lð )
" ... zachowuje mechanizm ewolucyjny i strukturÄ™ kodowania
osobników strategii (mð +lð ) , z wyjÄ…tkiem etapu tworzenia nowej
populacji bazowej Pt+1.
" W przeciwieÅ„stwie do strategii (mð +lð ) , nowa populacja bazowa Pt+1
tworzona jest wyłącznie z doboru najlepiej przystosowanych
osobników populacji tymczasowej Ot (bez udziału poprzedniej
populacji bazowej Pt).
" Zmiana mechanizmu tworzenia kolejnej populacji bazowej Pt eliminuje
problem osobliwości dominującego osobnika, występującego w
strategii (mð +lð ) . 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
Topologia pełnej sieci
Migration
Schemat migracji osobników pomiędzy
subpopulacjami
Topologia migracji pierścieniowej
Topologia migracji pierścieniowej
Topologia migracji sÄ…siedztwa
Topologia migracji sÄ…siedztwa
Migracja osobników
Worker / Farmer genetic algorithm
Algorytm dyfuzyjno  genetyczny
Programowanie
genetyczne
Programowanie genetyczne
" genetycznych
" różnica pomiędzy GP GA  reprezentacja rozwiązania.
Programowanie genetyczne Algorytmy genetyczne
Tworzenie rozwiązań jako Tworzenie rozwiązań jako
programy lub schematy w łańcuchy liczb
językach programowania
Postacie osobników
" Osobnik jako sekwencja rozkazów
(instrukcji);
" Osobnik jako graf  drzewo (strukturalny
program, wyrażenie arytmetyczne /
algebraiczne)
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).
4. Najlepszy utworzony w dowolnej populacji program, najlepsze
z możliwych rozwiązań, traktowane jest jako rezultat
programowania genetycznego [Koza 1992]
Operacja krzyżowania różnych
osobników
Osobniki rodzicielskie
Osobniki potomne
Operacja krzyżowania osobników
identycznych
Osobniki rodzicielskie
Osobniki potomne
Operacja mutacji
Osobnik z
ródłowy
Osobniki zmutowane
Projektowanie układów cyfrowych z
wykorzystaniem programowania genetycznego
Pytanie: Jak realizować układ z rozpływem
sygnałów (fan-out)