Evolučné algoritmy
Základné pojmy...................................................................................................................................................................................................................... 2
Prehľadávacie algoritmy ........................................................................................................................................................................................................ 2
Všeobecná schéma evolučného algoritmu............................................................................................................................................................................. 3
Selekcia .................................................................................................................................................................................................................................. 5
Vzorkovanie ........................................................................................................................................................................................................................... 6
Výber založený na očakávaných hodnotách.......................................................................................................................................................................... 7
Turnaje ................................................................................................................................................................................................................................... 8
Orezanie ................................................................................................................................................................................................................................. 9
Náhodné výbery ..................................................................................................................................................................................................................... 9
Premapovanie vhodností...................................................................................................................................................................................................... 10
Škálovacie metódy ............................................................................................................................................................................................................... 10
Zotriedenie ........................................................................................................................................................................................................................... 12
Náhrada ................................................................................................................................................................................................................................ 13
Reprezentácia ....................................................................................................................................................................................................................... 14
Genetické operátory ............................................................................................................................................................................................................. 15
Genetické operátory pre binárne reťazce............................................................................................................................................................................. 16
Genetické operátory pre celočíselné (mnohoznakové) reťazce .......................................................................................................................................... 17
Genetické operátory pre reálnu reprezentáciu ..................................................................................................................................................................... 17
Genetické operátory pre ostatné reprezentácie.................................................................................................................................................................... 20
Výpočet vhodnosti ............................................................................................................................................................................................................... 21
Klasické tvary evolučných algoritmov ................................................................................................................................................................................ 22
Teoréma schém .................................................................................................................................................................................................................... 25
Hypotéza stavebných blokov ............................................................................................................................................................................................... 28
Udržiavanie rôznorodosti..................................................................................................................................................................................................... 33
Infúzie .................................................................................................................................................................................................................................. 33
Subpopulácie........................................................................................................................................................................................................................ 34
Rovnomerné pokrytie........................................................................................................................................................................................................... 35
Niche methods...................................................................................................................................................................................................................... 35
Multikriteriálne úlohy .......................................................................................................................................................................................................... 38
Algoritmy pracujúce iba s jednou vhodnosťou ................................................................................................................................................................... 39
Agregačné metódy ............................................................................................................................................................................................................... 39
Zotriedenie vhodností .......................................................................................................................................................................................................... 40
Prispôsobujúce sa algoritmy ................................................................................................................................................................................................ 41
Nestacionárne úlohy............................................................................................................................................................................................................. 41
Metódy proti predčasnej konvergencii ................................................................................................................................................................................ 42
Metódy založené na reprezentácii s pamäťou ..................................................................................................................................................................... 42
Úlohy s ohraničeniami ......................................................................................................................................................................................................... 44
Dekódery .............................................................................................................................................................................................................................. 44
Opravné procedúry............................................................................................................................................................................................................... 44
Penalizačné funkcie ............................................................................................................................................................................................................. 44
Špeciálne operátory.............................................................................................................................................................................................................. 45
No free lunch theorem ......................................................................................................................................................................................................... 45
Nastavenie riadiacich parametrov........................................................................................................................................................................................ 47
Problém obchodného cestujúceho ....................................................................................................................................................................................... 49
Hybridizácia ......................................................................................................................................................................................................................... 55
1
Základné pojmy
evolučné algoritmy
o
patria do skupiny širokej skupiny prehľadávacích algoritmov
o
nie sú zamerané na riešenie konkrétnej úlohy, ale snažia sa riešiť problém bez toho, aby sme o ňom museli mnoho vedieť
potreba znalostí o probléme
o
ako vyzerá riešenie úlohy
ƒ
očakávame, že riešenie sa bude dať rozložiť na zložky (atribút – hodnoty)
R = ( A1 = h1
A2 = h2 L An = hn )
ƒ
o
-
-
každý atribút vlastne predstavuje jeden rozmer v priestore
•
dostaneme tak n - rozmerný priestor, pričom n je počet atribútov
ƒ
každé riešenie je teda reprezentované jedným bodom v priestore
ƒ
množina všetkých bodov v tomto priestore sa nazýva množina kandidátov na riešenie
ohodnotenie každého bodu v priestore
ƒ
musíme byť teda schopný ohodnotiť kandidáta na riešenie
ƒ
každému bodu priradzujeme vhodnosť (fitness)
•
väčšinou reálne číslo
ƒ
do priestoru teda môžeme zakresliť ďalšiu os, ktorá bude predstavovať fitness
ƒ
takto definujeme funkciu vhodnosti (fitness function)
•
vlastne mapuje karteziánsky súčin A1 × A2 × L × An na množinu reálnych čísel R
ƒ
zistením fitness každého bodu v priestore dostaneme plochu vhodnosti (fitness landscape)
každý prehľadávací algoritmus sa snaží dostať do bodu s najlepšou vhodnosťou
návrh evolučného algoritmu
o
je potrebné zvoliť správnu reprezentáciu
o
riešenie vyjadrené v pojmoch úlohy (fenotyp)
o
riešenie vyjadrené v zložkovom tvare (genotyp)
o
úloha je zadaná vo fenotype
o
úloha sa rieši v genotype
o
výsledok je fenotyp
vzťah medzi fenotypom a genotypom
o
fenotyp nemusí presne reprezentovať genotyp
ƒ
prekódovanie fenotypovej informácie na genotypovú a opačne
ƒ
toto prekódovanie nemusí byť jednoznačné ani deterministické
o
funkciu vhodnosti vyjadrujeme vo fenotype
ƒ
niekedy sa dá táto funkcia pretransformovať do genotypu
ƒ
funkcia vhodnosti v genotype a fenotype môžu byť rôzne, len globálne maximum musí ostať zachované
Prehľadávacie algoritmy
schéma prehľadávacieho algoritmu
1.
vygenerujeme počiatočnú množinu bodov
2.
otestujeme či sme nenašli riešenie
ƒ
ak áno, tak koniec
3.
vygenerovanie novej množiny bodov a návrat do bodu dva
počet bodov v množine
o
individualistický algoritmus
ƒ
používame vždy len jeden bod
o
populistický algoritmus
ƒ
používame viacero bodov súčasne
generácia nových bodov
o
exploration
ƒ
generuje sa nezávisle od aktuálnych bodov
o
exploitation
ƒ
nová množina sa odvodí od aktuálnej množiny bodov
ƒ
využitie informácie, ktorú sme nadobudli
zaradenie evolučných algoritmov
o
patria medzi exploration a exploitation
ƒ
obsahuje generátor náhodných čísel
ƒ
náhodnosť je riadená
o
sú to populačné algoritmy
o
sú založené na evolučných princípoch z prírody (biologicky motivované algoritmy)
o
slabé algoritmy
ƒ
požiadavky na vedomosti o úlohe sú slabé
ƒ
jednu metódu možno použiť na viacero úloh
výkonnosť
algoritmu
úlohy
-
o
používajú prístup zdola nahor
použitie evolučných algoritmov
o
ak neexistuje silný algoritmus
2
ideálny slabý
algoritmus
evolučné
algoritmy
silný
algoritmus
o
o
ak existuje silný algoritmus, ale je nepoužiteľný
ak existuje silný algoritmus a je použiteľný, ale postačujú nižšie požiadavky na výkon algoritmu
Všeobecná schéma evolučného algoritmu
trvanie jednej množiny bodov sa nazýva generácia
počiatočná množina bodov sa generuje v čase t = 0
štart
inicializácia
inicializácia množiny
bodov
vyhodnotenie
množiny bodov
je splnená
ukončovacia
podmienka?
áno
koniec
nie
reprodukcia
selekcia
rodičov
generovanie
potomkov
vyhodnotenie
vhodnosti potomkov
náhrada populácie
t=t+1
-
popis schémy
o
inicializácia
ƒ
inicializácia množiny bodov
{
P (0 ) = a1, a2 ,L, aµ (t )
}
µ (t ) - kardinalita množiny bodov
ƒ
•
počet jedincov v populácii sa môže časom meniť
vyhodnotenie množiny bodov
{Φ(a1 ), Φ(a2 ),L, Φ(aµ (t ) )}
o
•
dostaneme množinu vhodností
je splnená ukončovacia podmienka?
C (P (t ), P (t − 1),L, P(0))
o
ƒ
môže byť rôzna
ƒ
je teda závislá od predchádzajúcich populácií
reprodukcia
ƒ
selekcia rodičov
{
P ' (t ) = a '1 , a '2 ,L, a 'ρ (t )
}
ρ (t ) - kardinalita množiny rodičov
ƒ
generovanie potomkov
{
P ' ' (t ) = aµ (t )+1, aµ (t )+ 2 ,L, aµ (t )+ λ
3
}
λ - počet potomkov
ƒ
vyhodnotenie vhodnosti potomkov
{Φ(aµ (t )+1 ), Φ(aµ (t )+ 2 ),L, Φ(aµ (t )+λ )}
o
náhrada populácie
P (t + 1) ⊂ P(t ) ∪ P ' ' (t )
-
generácia potomkov sa robí pomocou genetických operácií
o
najznámejšie mutácia a kríženie
príklad
o
majme nekonečnú plochu
o
máme za 10 krokov pozbierať čo najviac pokladov
o
pohyb
ƒ
S – sever
ƒ
J – juh
ƒ
SV – severovýchod
ƒ
JV – juhovýchod
ƒ
SZ – severozápad
ƒ
JZ – juhozápad
▲
▲
▲
S
▲
▲
▲
▲
o
inicializačná populácia
a1 = (SZ
a2 = (SZ
a3 = (SZ
a4 = (JZ
o
▲
SZ
SV
JV
J
SV
S
SV
JV
J
S
SV
J
J
JZ
SV
S
SZ
JV
JZ
J
JZ
SZ
J
SZ
S
JZ
J
SZ
J
JV
S
JV
SZ )
SV )
S)
SV )
vyhodnotíme každého jedinca
Φ (a1 ) = 4
Φ (a2 ) = 2
Φ (a3 ) = 3
Φ (a4 ) = 3
o
vypočítame priemernú vhodnosť populácie
µ
Φ=
∑ Φi
i =1
µ
Φ=3
o
vyberieme dvoch jedincov
ƒ
napríklad a3 a a4
ƒ
použijeme kríženie pričom crosspoint bude medzi 7 a 8 génom
a ' '1 = (SZ J J SV SZ JZ S JV JV SV )
a ' '2 = (JZ SV JZ S JV SZ JZ J S S )
4
ƒ
na druhého potomka použijeme mutáciu
a' '2 = (JZ
o
SV
JZ
S
JV
SZ
JZ
J
SV
JZ )
vyhodnotíme oboch jedincov
Φ (a' '1 ) = 4
Φ (a' ' 2 ) = 1
-
priebeh celkovej vhodnosti jedincov
Φ
ideálny evolučný
algoritmus
uviaznutý v
lokálnom extréme
t
Selekcia
P(t )
-
-
-
P ' (t )
selekcia
µ
ρ
výber jedincov, ktorý budú vstupovať do reprodukcie
jedinci sa vyberajú na základe šance na reprodukciu
o
je to pravdepodobnosť toho, že sa bude jedinec reprodukovať
o
šanca je závislá na vhodnosti jedinca
ƒ
jedinec s vyššou vhodnosťou nebude mať vyššiu šancu na reprodukciu ako ten ktorý bude mať menšiu vhodnosť
ƒ
lepšiu šancu na reprodukciu majú nadpriemerný jedinci
vzorkovanie
o
z populácie vyberáme jedincov vhodných na reprodukciu
ƒ
niektorí jedinci sa vzorkujú iba raz
ƒ
niektorí jedinci sa vôbec nevzorkujú
ƒ
niektorí jedinci môžu byť ovzorkovaní viackrát
o
vzorkovanie sa uskutočňuje vždy
premapovanie vhodností
o
vhodnosť jedinca sa mapuje na inú vhodnosť
Φ (ak ) → Φ ' (ak )
o
o
o
ak jedinec prežije do ďalšej generácie, bude do nej vstupovať s pôvodnou vhodnosťou
upravuje dočasne vhodnosť pre účely vzorkovania
premapovanie vhodností sa nemusí vždy používať
selekcia
premapovanie
vhodností
vzorkovanie
-
distribučná funkcia vhodnosti
o
označuje sa s
o
predpokladajme vhodnosti f1, f 2 ,L, f n , také že platí
f1 < f 2 < L < f n
o
potom s ( f i ) vyjadruje koľko jedincov v populácii má vhodnosť fi
3
2
1
f1
fn
f2
5
-
kumulatívna distribučná funkcia vhodnosti
o
označuje sa S
S ( fi ) vyjadruje koľko jedincov má vhodnosť menšiu alebo rovnú fi
o
S ( fn ) = µ
µ
3
L
2
1
f1

 0;

S ( fi ) =  ∑ fi ;
i ≤ µ
 µ ;
-
-
fn
f2
fi < f1
f1 ≤ fi < f n
fn
distribúcia vhodnosti rodičov má inú distribúciu ako celá populácia
distribúciu vhodnosti rodičov vieme vypočítať, ak vieme akú metódu používame pre výber rodičov
o
s* ( fi ) je očakávaná distribúcia vhodnosti
o
S * ( fi ) je očakávaná kumulatívna distribúcia vhodnosti
s* ( fi )
sa nazýva miera reprodukcie
s( f i )
o
vyjadruje v akej miere sú jedinci preferovaní pri reprodukcii
o
tí, ktorí majú mieru reprodukcie väčšiu ako 1, budú viac preferovaní
pomer
Vzorkovanie
podstatou je vybrať ρ rodičov z celej populácie µ jedincov
poznáme štyri základné možnosti vzorkovania
o
prístup založený na očakávaných hodnotách
ƒ
označme si p ( fi ) pravdepodobnosť toho, že jedinec bude mať vhodnosť fi
ƒ
potom musí platiť
s* ( fi ) = p ( fi )ρ
ƒ
pravdepodobnosť p( fi ) možno vypočítať viacerými spôsobmi ale najčastejšie sa používa proporcionálna selekcia
voči vhodnosti
p ( fi ) =
Φ (ai )
µ
∑ Φ(a j )
=
Φ (ai )
µΦ
j =1
Φ (ai ) - vhodnosť jedinca ai
Φ - priemerná vhodnosť populácie
ƒ
ak µ = ρ
s* ( fi ) = ρ
ƒ
pre priemerného jedinca potom platí
s* ( fi ) =
o
o
Φ (ai ) Φ (ai )
=
µΦ
Φ
Φ (ai )
Φ
=
Φ
Φ
=1
ƒ
pre každého jedinca potom môžeme vypočítať, koľkokrát sa dostane do populácie
turnaje
ƒ
v turnajoch jedince súťažia medzi sebou a víťaz sa stáva rodičom
náhodný výber
6
o
ƒ
náhodne sa vyberá kto bude rodičom
orezanie
ƒ
populácia sa oreže a najlepší sa stávajú rodičmi
Výber založený na očakávaných hodnotách
pre každého jedinca máme pravdepodobnosť, že sa vyskytne v populácii rodičov
s* ( f i ) =
∑ EV j
j = fi
EV - očakávaná vhodnosť jedinca
-
metóda musí spĺňať tri vlastnosti
o
bias (tendencia, sklon)
ƒ
nakoľko sa skutočné vzorkovanie zhoduje s pravdepodobnosťou, že bude jedinec vybraný do populácie rodičov
o
rozptyl
ƒ
očakávame, že jedinca vyberieme EVi - krát
ƒ
ƒ
zaručuje, že nakoľko vyberieme jedinca minimálne a maximálne počet krát
minimálny rozptyl teda je EV , EV 
výkonnosť
ƒ
výpočtová náročnosť
ruletové metódy
o
metóda je založená na tom, že máme ruletu a ňou zatočíme a kde jazýček ukáže toho jedinca berieme do populácie rodičov
o
-
o
o
o
na rulete je µ políčok
veľkosť políčka predstavuje vhodnosť jedinca
ƒ
ak je vhodnosť daná pravdepodobnosťou, potom je obvod rulety 1
ƒ
ak je vhodnosť daná očakávaným výberom jedinca, potom je obvod rulety ρ
prvá ruletová metóda
ƒ
stochastické vzorkovanie s náhradou (SSwR)
ƒ
zatočíme ruletu ρ - krát a dostaneme ρ rodičov
ƒ
má nulový bias
ƒ
rozptyl je z intervalu 0, ρ
o
druhá ruletová metóda
ƒ
stochastické vzorkovanie bez náhrady (SSw/oR)
ƒ
na ruletu vynesieme očakávaný výskyt jedincov v populácii rodičov
ƒ
zatočíme ruletu a koho vyberieme, tomu očakávanú hodnotu výberu zmenšíme o 1
ƒ
bias narastá s mnohými zatočeniami
ƒ
rozptyl je z intervalu 0, EV 
o
tretia ruletová metóda
ƒ
zvyškové stochastické vzorkovanie s náhradou (RSSwR)
ƒ
ak má byť niektorý jedinec vybraný 3,4 – krát, tak 3 – krát je vybraný automaticky a zvyšok vložíme na ruletu
ƒ
bias je nulový
ƒ
pri rozptyle je zaručená iba spodná hranica EV 
o
štvrtá ruletová metóda
ƒ
zvyškové stochastické vzorkovanie bez náhrady (RSSw/oR)
ƒ
na ruletu vynesieme len zvyšky a ak nejakého jedinca vyberiem, tak jeho časť z rulety vymažem
ƒ
bias narastá s počtom zatočení
ƒ
rozptyl je z intervalu EV EV 
o
výpočtová náročnosť
ƒ
označuje sa O( parametre)
ƒ
pri ruletových metódach sa náročnosť určuje z µ a ρ
ƒ
vyhľadanie jedinca, ktorého sme vybrali má náročnosť µ
ƒ
ruletu musíme zatočiť maximálne ρ - krát
ƒ
-
teda náročnosť potom je O(µ , ρ ) = µρ , teda lineárna
ƒ
ak však budeme prehľadávať pole jedincov delením na polovice zložitosť bude O(µ , ρ ) = ρ ln µ , teda logaritmická
ƒ
náročnosť všetkých ruletových metód je približne rovnaká
zvyškové stochastické nezávislé vzorkovanie (RSIS)
o
celé časti očakávaného výskytu jedinca v populácii rodičov sa automaticky prenesú do populácie rodičov
o
ostanú nám len zvyšky
o
pre každý zvyšok vygenerujeme číslo z intervalu 0,1
o
o
ak je vygenerované číslo menšie ako zvyšok, tak jedinca zaradíme do populácie rodičov a jeho zvyšok nastavíme na 0
rozptyl je minimálny
7
-
o
bias narastá ak opakujeme prechod
o
náročnosť je lineárne závislá od µ
stochastické univerzálne vzorkovanie SUS
o
na ruletu vynášame priamo očakávané hodnoty
o
obvod rulety je ρ
o
naokolo rulety bude ρ jazýčkov s jednotkovou vzdialenosťou medzi sebou
o
bias je nulový
o
rozptyl je minimálny
o
náročnosť je lineárna s µ
o
ak vedľa seba dáme jedince s malou vhodnosťou, tak nebudú mať všetci šancu, aby boli vybraný do populácie rodičov
o
je nutné pri RSIS a SUS zamiešať očakávané hodnoty, tak aby sa nezvýšil bias
o
príklad funkcie na zamiešanie (nemá bias)
for (i = 0; i < µ ; i++) {
j = random(i, µ − 1 );
temp = pop[j];
pop[j] = pop[i];
pop[i] = temp;
}
Turnaje
-
q - árny turnaj
o
náhodne sa vyberie q jedincov, pričom každý je vybraný s rovnakou pravdepodobnosťou
o
najlepší z nich sa vyberie za rodiča
o
toto sa opakuje ρ krát
o
ak sa jedinec stal rodičom, tak ho nemažeme, teda sa môže stať rodičom viackrát
o
ak q = 2 , tak sa turnaj nazýva binárny
ƒ
najhorší jedinec nemôže vyhrať turnaj, ak nebojuje sám so sebou
ƒ
najlepší jedinec vyhrá každý turnaj
ƒ
priemerný jedinec vyhrá polovicu turnajov
o
ak q = 3 , tak sa turnaj nazýva ternárny
ƒ
najhorší jedinec nemôže vyhrať turnaj, ak nebojuje sám so sebou
ƒ
najlepší jedinec vyhrá každý turnaj
ƒ
priemerný jedinec vyhrá štvrtinu turnajov
o
čím je q vyššie, tým je tlak na selekciu vyšší
o
pri tejto metóde môže byť vhodnosť aj záporná
o
je výpočtovo málo náročná
1
o
pravdepodobnosť, že vyberieme jedinca s vhodnosťou fi do turnaja je
µ
o
pravdepodobnosť, že vyberieme ľubovoľného jedinca s vhodnosťou rovnou fi je
ƒ
s ( fi ) - distribúcia vhodnosti jedinca
s ( fi )
µ
S ( fi )
o
pravdepodobnosť, že vyberieme ľubovoľného jedinca s vhodnosťou menšou alebo rovnou fi je
o
 S ( fi ) 

pravdepodobnosť, že ľubovoľný jedinec s vhodnosťou menšou alebo rovnou fi vyhrá turnaj je 
 µ 
µ
q
 S ( fi ) 
 = S * ( fi )
očakávaný počet jedincov , ktorí sa stanú rodičmi v s vhodnosťou menšou alebo rovnou f i potom je ρ 
 µ 
očakávaný počet jedincov, ktorí sa stanú rodičmi a budú mať vhodnosť rovnú fi je
q
o
o
  S ( f ) q  S ( f ) q 
i 
i −1  
s * ( f i ) = S * ( f i ) − S * ( f i −1 ) = ρ  
−
  µ   µ  


o
skutočný počet jedincov, ktorí sa stanú rodičmi s vhodnosťou f i je
s ( fi ) = S ( fi ) − S ( fi −1 )
o
potom miera reprodukcie je
s* ( fi )
=
s( f i )
o
  S ( f ) q  S ( f ) q 
i 
i −1  
−
  µ   µ  


S ( f i ) − S ( f i −1 )
ρ  
pravdepodobnosť výberu jedinca v vhodnosťou fi je
8
 S( f ) q  S( f ) q 
i
i −1
 − 
 

  µ 
 µ  

S ( f i ) − S ( f i −1 )
ρ  
p( f i ) =
o
o
EV
ρ
=
ρ
=
q
q
1  S ( f i ) − S ( f i −1 )
q  S( f )− S( f
µ 
i
i −1 )




z toho vyplýva, že turnajovú metóda môžeme simulovať pomocou metódy založenej na očakávanej hodnote
ak každý jedinec má rôznu vhodnosť
S ( f i ) − S ( f i −1 ) = 1
p( f i ) =
1
µq
[S ( f )
i
q
− S ( f i −1 )q
]
Orezanie
jedince v populácii sa zoradia podľa vhodnosti
definuje sa číslo T ∈ (0,1)
-
ponechá sa Tµ najlepších jedincov
o
horšie jedince sa nemajú šancu stať rodičmi
o
z lepších jedincov sa vyberajú rodičia
ƒ
deterministicky
T sa volí tak, aby bolo vo vzťahu s ρ , tak aby sa každý jedinec z lepšej časti vybral do populácie
•
s celočíselným násobkom
ƒ
stochastický výber
•
náhodne sa vyberú jedince
•
všetky jedince majú rovnakú šancu stať sa rodičmi


0;
S ( fi ) ≤ (1 − T )µ

 S ( fi ) − (1 − T )µ
p (ai ) = 
; S ( fi −1 ) < (1 − T )µ < S ( fi )
Tµ

s ( fi )

;
inak

Tµ

•
•
s ( fi )
Tµ
orezanie je teda možné simulovať pomocou metódy založenej na očakávanej hodnote výberu
•
-
pre jedince, ktoré sa vyskytli v horšej časti je pravdepodobnosť výberu 0
S ( fi ) − (1 − T )µ
pre jedince, ktoré sú na hranici je pravdepodobnosť výberu
Tµ
pre jedince v lepšej časti je pravdepodobnosť výberu
Náhodné výbery
najčastejšie používaný náhodný výber je čistý náhodný výber
o
je ako orezanie pri T = 1
môžeme však jedince zoradiť podľa vhodnosti
o
náhodne vygenerujeme index jedinca
o
nemusíme však index generovať priamo, ale cez prevodovú funkciu a tak riadiť selekčný tlak
fn µ
fn µ
f1 1
f1 1
χ
0
rovnomerne preferujeme jedincov
o
fn µ
f1 1
0
χ
preferujeme slabších jedincov
0
χ
preferujeme lepších jedincov
prevodová funkcia
 µ 
2
j=
 c − c − 4(c − 1)χ
 2(c − 1) 



χ - náhodné číslo z intervalu 0,1
o
o
o
považujme χ za kumulatívnu distributívnu funkciu
predpokladajme, že χ = p(x )(i ≤ x ) = F (x ) je pravdepodobnosť, že generovaný index je menší alebo rovný x
potom
9
 µ 

2
j=
 c − c − 4(c − 1)F (x ) 
2
c
−
1
(
)



o
keďže x je horné ohraničenie indexu j , potom môžeme písať
x=
o
µ 

2
 c − c − 4(c − 1)F (x ) 
2(c − 1) 

vyjadríme F (x )
c 2 − 4(c − 1)F (x ) = c −
2 x(c − 1)
µ

2 x(c − 1) 

4(c − 1)F (x ) = c 2 −  c −
µ


F (x ) =
1  c 2 µ 2 − (cµ − 2 x(c − 1))2 

4(c − 1) 
µ2

F (x ) =
µcx − x 2 (c − 1)
µ2
F (x ) =
o
2
x
x(c − 1) 

c −
µ 
µ 
zderivujeme výraz podľa x
dF (x ) 1 
2x
(c − 1)
=  c −
dx
µ
µ

o
uvažujme, že
c = ι+
ι− = 2 −ι+
dF (x ) 1  +
x
= ι − ι + − ι − 
dx
µ
µ
(
o
)
dostali sme klesajúcu funkciu
Premapovanie vhodností
pokiaľ pracujeme so surovou vhodnosťou môže vzniknúť niekoľko problémov
o
1. problém
ƒ
rozdiel medzi jedincami sa nezmení, ale pomer áno
keď máme jedinca a1 s vhodnosťou 1 a a2 s vhodnosťou 2
•
keď máme jedinca a1 s vhodnosťou 11 a a2 s vhodnosťou 12
•
o
2. problém
ƒ
môže prevládnuť jediný superjedinec, ktorý však môže byť v lokálnom minime
o
3. problém
ƒ
ak sú vhodnosti veľké a všetci jedinci sú dobrí, potom rozdiely medzi nimi sú malé a nie je zaručený selekčný tlak
o
4. ak je vhodnosť záporná, nie je možné použiť niektoré metódy na vzorkovanie
delia sa do dvoch základných kategórií
o
škálovanie (scaling)
o
zotriedenie (ranking)
pri premapovaní vhodností sa vlastne snažíme o
( )
( )
Φ (a1 ), Φ (a2 ),L, Φ aµ → Φ ' (a1 ), Φ ' (a2 ),L, Φ ' aµ
-
u metód premapovania, ktoré budeme preberať, platí monotónnosť
( )
( )
Φ (ai ) < Φ a j ⇒ Φ ' (ai ) < Φ ' a j
-
o
musia zachovávať utriedené poradie jedincov podľa vhodnosti pred aj po premapovaní vhodností
premapovanie vhodností má zmysel iba pri metódach založených na očakávaných hodnotách
ak by sme použili nemonotónnu funkciu premapovania, tak by malo premapovanie zmysel aj pri ostatných metódach selekcie
Škálovacie metódy
jedná sa o zmenu mierky
každú vhodnosť chceme vtesnať do nejakého intervalu (chceme ju teda kontrolovať)
windowing
o
najjednoduchšia metóda
o
používa sa ak relatívne rozdiely medzi vhodnosťami jedincov sú malé
o
najhorší jedinec bude mať nulovú vhodnosť
10
vhodnosť všetkých ostatných sa vypočíta odčítaním vhodnosti najhoršieho jedinca
bojuje proti stagnácii riešenia
po aplikovaní tejto metódy bude mať každý jedinec kladnú vhodnosť
najhorší jedinec sa nemusí hľadať len v aktuálnej generácii, ale v posledných niekoľkých generáciách
ƒ
je veľká pravdepodobnosť toho, že v predchádzajúcich generáciách sa vyskytoval horší jedinec ako je najhorší
v aktuálnej generácii
sigma škálovanie
o
založené na podobnom princípe ako windowing
o
zavádza sa distribúcia vhodnosti populácie
o
neodpočítava sa vhodnosť najhoršieho jedinca, ale sa odčítava niekoľko smerodajných odchýlok σ
o
o
o
o
-
f − sσ
σ - smerodajná odchýlka
f - priemerná vhodnosť populácie
s - počet odčítaných smerodajných odchýlok
99%
σ
o
σ
σ
σ
σ
potom teda platí
(
Φ' = Φ − f − sσ
o
σ
)
priemerná vhodnosť jedinca potom je
Φ = sσ
o
jedinec lepší o 1 σ bude vybratý
(s + 1)ρ
µs
o
ak počet potomkov bude toľko koľko rodičov
s +1
s
-
o
väčšinou sa volí s = 2
o
potláčajú sa superjedinci
o
môže vzniknúť jedinec so zápornou vhodnosťou
lineárne škálovanie
o
určíme si vhodnosť si najlepšieho jedinca
o
o
určíme si, aby priemerný jedinec mal vhodnosť 1
vytvoríme si lineárnu funkciu, ktorá bude funkciu vhodnosti transformovať
s
1
pr
Φ' = 1 +
max
s −1
(Φ − pr )
max − pr
max - maximálna hodnota vhodnosti
pr - priemerná hodnota vhodnosti
o
o
o
o
o
bojuje proti superjedincom
priemerný jedinec bude mať vhodnosť 1
najlepší bude mať očakávanú vhodnosť s
s sa postaví menej ako 2. často sa postaví 1,5
môžu vzniknúť záporný jedinci
ƒ
ak sa tomu chceme vyhnúť postavíme s nasledovne
11
s = 1+
max − pr
pr − min
min - minimálna hodnota vhodnosti
Zotriedenie
podstatou je to, že sa jedinci zotriedia podľa vhodnosti
musíme rozhodnúť o poradí jedincov, ak majú rovnakú vhodnosť
vhodnosti nahradíme za nové vhodnosti
výhoda je, že zabúdame staré vhodnosti a môžeme nastaviť vhodnosti tak ako potrebujeme
lineárne zotriedenie
o
všetky ohodnotenia sú kladné
o
aj najhorší jedinec bude mať nejakú vhodnosť
o
najhorší jedinec bude mať vhodnosť ι −
o
o
najlepší jedinec bude mať vhodnosť ι +
potom vhodnosť i - teho jedinca je
(
)

i −1 
Φ ' (ai ) = ι − + ι + − ι −

µ
−1

o
o
rieši všetky problémy, ktoré môžu nastať pri vzorkovaní
vhodnosti jedincov sa postavia tak aby priemerný jedinec mal vhodnosť 1
ι+ +ι−
2
o
pravdepodobnosť selekcie i - teho jedinca je
pi =
o
=1
(
1
) i −1 
−
+
−
ι + ι − ι

µ
µ − 1
každá vhodnosť sa po zotriedení vyskytuje presne raz
s ( fi ) = 1
o
očakávanú pravdepodobnosť výskytu si odvodíme z očakávanej kumulatívnej distribúcie vhodnosti
S * ( fi ) =
S ( fi )
∑ ρp j
1
p j - pravdepodobnosť selekcie j - teho jedinca
S ( fi )
(
)
ρ  − + − i −1 

ι + ι − ι
µ
µ − 1

1
S ( fi )
S ( fi )
ρ
ρ + − i −1
ι −ι
S * ( fi ) = ∑ ι − + ∑
µ
µ
µ −1
1
1
+
− S ( fi )
ρ
ρ ι −ι
S * ( fi ) = ι − S ( fi ) +
∑i −1
µ
µ µ −1 1
S * ( fi ) =
∑
(
ƒ
platí vzťah
k
(k + 1)k
i =1
2
∑i =
S * ( fi ) =
o
)
ρ −
ρ ι + − ι − S ( fi )(S ( fi ) − 1)
ι S ( fi ) +
µ
µ µ −1
2
potom očakávanú pravdepodobnosť výskytu je
s* ( fi ) = S * ( fi ) − S * ( fi −1 )
ρ
ρ ι + − ι − S ( fi )(S ( fi ) − 1)   ρ −
ρ ι + − ι − S ( fi −1 )(S ( fi −1 ) − 1) 
ι S ( fi −1 ) +
−
s* ( f i ) =  ι − S ( f i ) +
µ
 µ

µ
µ
1
2
µ
µ −1
2
−

 

s* ( f i ) =
ρ −
ρ ι+ −ι−
(S ( fi )(S ( fi ) − 1) − S ( fi −1 )(S ( fi −1 ) − 1))
ι (S ( fi ) − S ( fi −1 )) +
µ
2µ µ − 1
s* ( f i ) =
ρ −
ρ ι+ −ι−
ι (S ( fi ) − S ( fi −1 )) +
S ( fi )2 − S ( fi ) − S ( fi −1 )2 + S ( fi −1 )
µ
2µ µ − 1
(
12
)
(
ρ −
ρ ι+ −ι−
ι s ( fi ) +
S ( fi )2 − s( fi ) − S ( fi −1 )2
µ
2µ µ − 1
s* ( f i ) =
ρ
ρ ι+ −ι−
s* ( fi ) = s ( fi ) ι − −
µ
2µ µ − 1

ι+ −ι−
2
)
= 1−ι−
(
ρ  − 1 − ι −  ρ 1 − ι −
ι −
+
S ( fi )2 − S ( fi −1 )2
µ 
µ − 1  µ µ − 1
s* ( f i ) = s ( f i )
ρ  ι − µ − 1  ρ 1 − ι −
+
S ( fi )2 − S ( fi −1 )2
µ  µ − 1  µ µ − 1
(
)
)
zvolíme si
ι− =
1
µ
(
ρ
S ( fi )2 − S ( fi −1 )2
µ2
s* ( f i ) =
)
pravdepodobnosť selekcie i - teho jedinca je
1
µ2
-
(
 ρ ι+ −ι−
+
S ( fi )2 − S ( fi −1 )2
 2µ µ − 1

s* ( f i ) = s ( f i )
•
o
)
(S ( f ) − S ( f ) )
i
2
i −1
2
o
zisťujeme, že binárny turnaj a lineárne zotriedenie vykonáva to isté
exponenciálne zotriedenie
o
definujeme si parameter c ∈ (0,1)
o
najlepší jedinec bude mať vhodnosť 1
o
druhý najlepší jedinec bude mať vhodnosť c
o
o
tretí najlepší jedinec bude mať vhodnosť c 2
vhodnosť i - teho jedinca je
Φ ' (ai ) = c µ −1
o
o
ak je c = 1 potom je to konštantné zotriedenie a teda náhodný výber
pravdepodobnosť selekcie jedinca pri exponenciálnom zotriedení je
c µ −i
µ
∑ cµ − j
j =1
ƒ
platí vzťah
N
∑c j =
j =0
o
c N +1 − 1
c −1
potom môžeme pravdepodobnosť selekcie jedinca vyjadriť
c µ −i
µ −1
∑ ck
=
(c − 1)c µ −i
cµ − 1
k =0
Náhrada
-
sme v generácii v čase t a máme pôvodných jedincov P(t ) = a1, a2 ,L, aµ (t ) a potomkov P ' ' (t ) = aµ (t )+1, aµ (t )+ 2 ,L, aµ (t )+ λ (t )
chceme vytvoriť P (t + 1) = a1, a2 ,L, aµ (t +1)
nová generácia môže byť rovnako veľká ako stará, ale nie je to podmienka
možnosti, ktoré pri náhrade môžu vzniknúť
o
ak P (t + 1) bude vytváraná z P' ' (t )
ƒ
generačná náhrada
ƒ
iba potomkovia generujú novú populáciu
ƒ
nazývajú sa aj čiarkové náhrady
ƒ
existujú dva prístupy
vygenerujeme len toľko potomkov, koľko potrebujeme
•
13
λ (t ) = µ (t + 1)
•
ak máme viac potomkov ako potrebujeme, tak z nich musíme vyberať, ktorí prežijú do nasledujúcej
generácie
λ (t ) > µ (t + 1)
o
o
v tomto prípade nemusíme robiť selekciu rodičov
ak P (t + 1) bude vytváraná z P (t ) aj P ' ' (t )
ƒ
rodičia aj potomkovia generujú novú populáciu
ƒ
nazývajú sa aj plus stratégie
ƒ
existujú dva prístupy
•
zosypeme P (t ) a P' ' (t ) do jednej množiny a zabudneme, ktorí jedinci odkiaľ pochádzajú
•
naďalej uvažujeme o obidvoch. Percento zo starej populácie sa bude nahrádzať z P ' ' (t )
o
G - parameter, koľko jedincov vymením
G - generačná medzera
o
(1 − G )P + P' '
o
stead – state algoritmus
ƒ
snaží sa generačnú medzeru zmenšovať
ƒ
najčastejšie položí G = 2
ak P (t + 1) bude generovaná len z P (t )
ƒ
neprípustné z hľadiska evolučných algoritmov
selekčné metódy sa môžu použiť aj v náhrade
možnosti stretov generácií
o
generácie sa nestretnú
ƒ
celá populácia rodičov je nahradená za vygenerovaných potomkov
o
generácie sa prekrývajú
ƒ
jedinec môže teoreticky prežiť od prvej generácie po poslednú
elitizmus
o
strata alebo uchovanie elity do novej generácie
o
zabezpečuje, že elita je deterministicky presunutá do novej generácie
o
ak v novej generácii už jedinec z elity je, potom ho tam opäť nezaraďujeme
o
sledovanie vývoja najlepšieho jedinca
o
-
-
Φ
najlepší jedinec
priemerný jedinec
t
Reprezentácia
aj pri selekcii aj pri náhrade sme neuvažovali reprezentáciu jedinca
pri návrhu genetického algoritmu si musíme postaviť dve základné otázky
o
ako bude reprezentovaná vhodnosť jedinca
o
ako bude reprezentovaný samotný jedinec
dve základné reprezentácie jedinca
o
reprezentácia s pevnou dĺžkou
ƒ
jedinec je presne daný
ƒ
ak máme pevnú dĺžku prehľadávaného priestoru
o
reprezentácia s pohyblivou dĺžkou
ƒ
pracujeme s väčšími celkami naraz
ƒ
s takýmito algoritmami sa stretávame menej
ƒ
je dobré obmedziť maximálnu dĺžku reprezentácie jedinca
delenie jedincov z hľadiska reprezentácie
o
binárna reprezentácia
ƒ
pochádza z genetických algoritmov
ƒ
je to lineárna reprezentácia
o
celočíselná reprezentácia
ƒ
pochádza z evolučných stratégií
ƒ
je to lineárna reprezentácia
o
reálna reprezentácia
ƒ
pochádza z evolučných stratégií
ƒ
je to lineárna reprezentácia
o
poradie
14
-
-
ƒ
pochádza z evolučných stratégií
ƒ
je to lineárna reprezentácia
o
iné (štruktúry)
ƒ
môže mať ľubovoľný tvar
ƒ
najviac používané
•
stromy
matice
•
delenie reprezentácií
o
binárne reťazce
ƒ
na každej pozícii v reťazci je hodnota 1 alebo 0 (áno alebo nie)
ƒ
je najrozšírenejší z hľadiska historických dôvodov
•
binárne reťazce boli rozšírené vďaka genetickým algoritmom a tento smer teraz prevažuje
ƒ
je to najjednoduchšia reprezentácia
ƒ
sú popísané najjednoduchšou teóriou
o
celočíselné (mnohoznakové reťazce)
ƒ
na každej pozícii v reťazci môže byť nejaký prvok z nejakej množiny
ƒ
môžu ale nemusia to byť číselné reprezentácie
ƒ
medzi prvkami nemusí byť žiaden vzťah
o
reálna reprezentácia
ƒ
na každej pozícii v reťazci je reálne číslo
ƒ
bola preferovaná evolučnými stratégiami
mali za základ reálnu reprezentáciu problému
•
o
poradie
ƒ
máme množinu objektov, ktorú treba zoradiť
z tejto množiny sa prvok vyskytuje raz a práve raz
•
ƒ
vytvárame permutácie objektov
o
štruktúry
ƒ
nie je vyhranená štruktúra
ƒ
sú to všetky ostatné reprezentácie
ƒ
matice
ak je priestor prehľadávania pevne daný
•
ƒ
stromy
•
reprezentácia prehľadávaného priestoru je premenlivá
preferované genetickým programovaním
•
voľba reprezentácie sťažuje, alebo zjednodušuje riešenie úlohy
nedá sa povedať návod, kedy ktorú stratégiu použiť
úloha sa mapuje na reprezentáciu
o
aké má byť riešenie (fenotyp) mapujeme na reprezentáciu jedinca (genotyp)
extremálne voľby reprezentácie
o
ak chceme voliť jednu reprezentáciu na všetky problémy je najvhodnejšie voliť binárnu reprezentáciu
ƒ
existuje dôkaz, že sú to najefektívnejšie reťazce
ƒ
prax ukazuje, že to nemusí byť pravda
o
môžeme použiť takú reprezentáciu, aby reprezentácia v genotype reprezentovala fenotypické vlastnosti aj za cenu vlastnej
reprezentácie jedincov
Genetické operátory
slúžia na vygenerovanie nových bodov v priestore
z genetického materiálu populácie rodičov vytvoríme novú populáciu
sú rôzne v závislosti od formy reprezentácie jedinca
sú tri typy genetických operátorov a sú závislé od toho koľko rodičov sa používa na vytvorenie jedinca
o
asexuálny operátor – jeden rodič
o
sexuálny operátor – dvaja rodičia
o
panmitický operátor – viacero rodičov
v praxi sa s panmitickým operátorom málo stretávame
asexuálny operátor vždy mení genetický materiál
o
existuje niečo, čo sa nevyskytuje v rodičovi
sexuálny operátor
o
nemusí meniť genetický materiál, lebo kombinuje materiál
ƒ
každú časť potomka je možné nájsť v niektorom z rodičov
o
môže aj meniť genetický materiál
ƒ
potomok môže obsahovať niečo, čo sa nenachádza ani v jednom z rodičov
panmitický operátor
o
platia podobné pravidlá ako pri sexuálnom operátore
väčšinou sa používa aj kombinácia genetických materiálov aj zmena v genetickom materiály
je teda možné použiť iba čisto sexuálny operátor
sexuálny operátor sa nazýva kríženie
asexuálny operátor sa nazýva mutácia
základná schéma vygenerovania potomkov
R1
P1
mutácia
P‘1
P2
mutácia
P’2
kríženie
R2
o
o
možno vymeniť mutáciu a kríženie alebo časť rodičov iba mutovať a časť krížiť
operátor sa aplikuje na nejaký vstup
15
ƒ
často operátor aplikujeme s nejakou pravdepodobnosťou
•
pravdepodobnosť kríženia pk
•
pravdepodobnosť mutácie pm
•
rodičia prežijú do ďalšej generácie s pravdepodobnosťou 1 − pk
•
-
generovanie čísla, podľa ktorého rozhodneme či sa daný operátor použije musí byť generovaný
s rovnomernou hustotou rozdelenia
je možné vytvárať vlastné operátory
Genetické operátory pre binárne reťazce
kríženie
o
krížením môžeme dostať jedného jedinca alebo častejšie dvoch jedincov
o
jednobodové kríženie
ƒ
vygeneruje sa deliaca čiara a jedince sa rozdelia na hlavu a telo
ƒ
telá alebo hlavy sa navzájom vymenia
Î
ak má jedinec dĺžku l , potom je l − 1 možností na vygenerovanie deliacej čiary
pozícia rozdelenia sa generuje s rovnomernou hustotou rozloženia
•
dvojbodové kríženie
ƒ
vygenerujú sa dve rôzne pozície
ƒ
vymenia sa stredy genetických materiálov
ƒ
o
Î
o
n – bodové kríženie
ƒ
generuje sa n deliacich bodov
ƒ
striedajú sa výbery úsekov z jedného a druhého rodiča
Î
ƒ
možnosť reprezentácie jedinca do kruhu a potom je možné generovať l deliacich bodov
Î
o
uniformné kríženie
ƒ
používa sa maska, ktorá kríženie riadi
ƒ
maska je binárny reťazec a pre každý operátor sa generuje vždy nová
ƒ
jedinci sú vytváraný nasledovne
prvý jedinec
•
o
ak v maske je 0, tak zoberiem bit z prvého jedinca
o
ak v maske je 1, tak zoberiem bit z druhého jedinca
druhý jedinec
•
o
ak v maske je 0, tak zoberiem bit z druhého jedinca
o
ak v maske je 1, tak zoberiem bit z prvého jedinca
16
0 1 0 1 1 0 0 0 1 0
ƒ
Î
vo všeobecnosti, ak by sme chceli podobný efekt dosiahnuť n – bodovým krížením, museli by sme
l
generovať deliacich bodov
2
•
pravdepodobnosť výskytu 0 v maske si označme p0
•
pravdepodobnosť výskytu 1 v maske si označme p1
p0 = 1 − p1
•
•
-
mutácia
o
l
2
ak p0 = 0,2 , tak vygenerujeme súvislejšie úseky a klesá počet deliacich bodov
ak p0 = p1 = 0,5 , potom deliacich bodov by sme museli mať
postupne sa prechádza každá pozícia v reťazci a hodnota na danej pozícii buď ostane, alebo sa preklopí na opačnú
0 1 0 1 1 0 0 0 1 0
-
Î
1 1 0 0 0 0 0 0 0 0
o
pravdepodobnosť mutácie označme pm
o
pravdepodobnosť že sa preklopí niektorý bit označme p p
o
potom pravdepodobnosť zmeny niektorého bitu môže byť pm . p p s tým, že mutácia bude prebiehať vždy
panmitické operátory
o
skenovací operátor
ƒ
zisťujeme aké bity sú v rodičoch na danej pozícii
ƒ
dostaneme distribúciu hodnôt
ƒ
deterministický prístup
založený na počte hlasov
•
•
ktorá hodnota sa najčastejšie vyskytuje v rodičoch na danej pozícii, bude aj v potomkovi
0 1 0 1 1 0 0 0 1 0
1 0 0 0 1 1 1 0 0 1
Î
0 1 0 1 1 0 1 0 1 0
0 1 0 1 1 0 1 1 1 0
•
takto vieme vygenerovať len jedného potomka
je rozšírenie uniformného kríženie
stochastický prístup
•
založený na pravdepodobnosti výskytu danej hodnoty
•
vygenerujeme si pravdepodobnosti pre každú hodnotu podľa distribúcie hodnôt
•
podľa toho akú hodnotu vygenerujeme tak vyberieme ktorá hodnota pôjde do potomka
takto vieme vygenerovať viacero jedincov
•
diagonálny operátor
ƒ
koľko máme rodičov na toľko úsekov ich rozdelíme
ƒ
potomkov zostavujeme diagonálne
ƒ
ƒ
o
Î
ƒ
rozšírenie n – bodového kríženia
Genetické operátory pre celočíselné (mnohoznakové) reťazce
zmena oproti binárnym reťazcom je malá
o
kríženie a panmitické operátory zostávajú rovnaké
mutácia
o
musíme mať pravdepodobnosť mutácie pm
o
musíme mať pravdepodobnosť či sa bude daná pozícia mutovať p p
o
musíme mať pravdepodobnosť na akú hodnotu znaku sa daná pozícia zmení p z
ƒ
novú hodnotu je možné získať z distribúcie jednotlivých hodnôt
Genetické operátory pre reálnu reprezentáciu
kríženie
17
o
o
o
je to reťazec pozícií, teda je možné použiť všetky operátory z binárnej reprezentácie
existuje ďalšia sada operátorov
ak mením nejakú pozíciu, na nej sa môže vyskytovať hodnota z intervalu a, b
o
keďže existuje usporiadanie na množine reálnych čísel, môžeme dostať hodnoty, ktoré neboli v žiadnom rodičovi
o
nech p1i hovorí aká je hodnota na pozícii i u prvého rodiča
o
nech pi2 hovorí aká je hodnota na pozícii i u druhého rodiča
o
o
kríženie môže byť matematická operácia
typické intervaly, ktoré sa používajú
ƒ
vygenerované číslo môže byť z jedného z týchto intervalov
ax
p1i
a
o
bx
pi2
b
lineárne kríženie
ƒ
pre vygenerovanie potomkov môžeme použiť nasledovné vzťahy
0,5 p1i + 0,5 pi2
1,5 p1i − 0,5 pi2
− 1,5 p1i + 0,5 pi2
M
ƒ
prvý vzťah vygeneruje jedinca z intervalu p1i , pi2
ƒ
ďalšie vzťahy vygenerujú jedincov z intervalu a x , bx
ƒ
o
majme takúto zásobu vzťahov
•
môžeme náhodne vygenerovať číslo a podľa toho rozhodneme ktorý vzťah pre ktorú pozíciu použijeme
•
môžeme generovať všetky pozície jedným vzťahom
o
jedinec je rovnorodejší
ƒ
môžeme vygenerovať viacero jedincov
každú pozíciu musíme generovať iným vzťahom (náhodný výber vzťahu)
•
•
keďže vzťahy sú symetrické a prvý sa väčšinou používa vygenerujeme nepárny počet jedincov (3)
o
najhoršieho vyradíme
o
vyradíme na základe pravdepodobnosti že prežije podľa vhodnosti
prostredné kríženie
ƒ
hodnota nového jedinca na pozícii i bude na základe hodnôt rodičov na i - tej pozícii p1i a pi2 nasledovná
p 'i = χp1i + (1 − χ ) pi2
χ ∈ 0,1
o
ƒ
väčšinou sa χ vygeneruje rovnaké pre každú pozíciu, ale nie je to podmienka
ƒ
nová hodnota p'i je z intervalu a x , bx
ƒ
ƒ
fuzzy connective base
hodnota na pozícii môže byť
FCB
a + (b − a )T (s1 , s 2 )
a + (b − a )G (s1 , s 2 )
a + (b − a )C (s1 , s 2 )
a + (b − a )P(s1 , s 2 )
s1 = p1i normalizovaná na interval 0;1
s2 = pi2 normalizovaná na interval 0;1
•
normalizácia hodnôt
s1 =
p1i − a
b−a
s2 =
ƒ
funkcie T , G, C , P vracajú hodnoty z intervalu 0;1
ƒ
výsledná hodnota je z intervalu a x ; bx
ƒ
funkcia T je taká, že výsledok je z intervalu a; p1i
18
pi2 − a
b−a
ƒ
funkcia G je taká, že výsledok je z intervalu pi2 ; , b
ƒ
funkcia C je taká, že výsledok je z intervalu pi1; pi2
ƒ
funkcia P je taká, že výsledok je z intervalu a x ; bx
ƒ
ƒ
tieto funkcie si vytvoríme
často sa však používa algebraická skupina týchto funkcií
T = xy
G = x + y − xy
P = x λ y1− λ
C = x λ + y1− λ
ƒ
ƒ
-
mutácia
o
často sa T položí t – norme a G t – conorme
vygenerujeme však štyroch potomkov
•
na každú pozíciu použijeme funkciu T , G, C , P
•
polovičku potomkov musíme odstrániť
uniformná mutácia
ƒ
používame pravdepodobnosť, či nastane mutácia pm
ƒ
o
ak mutácia na nejakom bite nastáva, tak nové vygenerované číslo bude z rovnomerného rozloženia hodnôt
pravdepodobnosti
extremálna mutácia
ƒ
ak sa má daný bit mutovať, tak ho zmutujeme na extrémnu hodnotu a alebo b
ƒ
o
používa sa, ak kríženie nastavuje bity z intervalu pi1; pi2
neuniformná mutácia
ƒ
vychádza z myšlienky, že na začiatku hľadania nevieme kam postupovať v priestore, a tak by mutácia mala vytvárať
veľké zmeny v genetickom materiále
ƒ
na konci, keď prehľadávame malý subpriestor, mutácia by mala vytvárať už len malé zmeny v genetickom materiále
p 'i = pi + ∆ (t , b − pi )
P 'i = pi + ∆(t , pi − a )
ƒ
ƒ
od aktuálnej hodnoty niečo odčítam alebo pričítam
•
ktorý vzťah použijeme sa vygeneruje s rovnomernou pravdepodobnosťou
∆ je funkcia, ktorá nevyskočí z intervalu pi ; b , alebo a; pi
β

 t  
1−  

T
 
∆ (t , y ) = y1 − r 




y - maximálna hodnota
r - číslo z intervalu 0;1 vygenerované s rovnomerným rozložením pravdepodobnosti
t - aktuálna generácia
T - maximálny počet generácií
β - umožňuje riadiť rýchlosť mutácie
•
•
ak r = 0 , potom je to extremálna mutácia
na začiatku ∆(t , y ) vracia číslo z 0; y
•
ku koncu ∆ (t , y ) vracia číslo blízke 0
čím je generácia vyššia tým sa menej mutuje
Mühlenbeinova mutácia
ƒ
princíp väčších a menších zmien v rámci jednej generácie
ƒ
o
p 'i = pi ± (b − a )γ
15
γ = ∑ ai 2−i
i =0
ƒ
ƒ
či použijeme + alebo – vo vzorci náhodne generujeme s rovnakou pravdepodobnosťou
majme lineárnu reprezentáciu čísla
0 1
15
ai - hodnota bitu v reprezentácii čísla
19
•
desatinná čiarka je za nultým bitom
•
maximálne číslo potom môže byť
•
215
keďže náhodne generujeme ai , teda náhodne generujeme aj γ
o
•
o
216 − 1
pravdepodobnosť generovania 0 je 0,35
o
pravdepodobnosť generovania 1 je x10−20
menšie čísla sa generujú viac
o
väčšie zmeny sa nevyskytujú tak často ako malé
normálna mutácia
ƒ
pomocou Gaussovho rozloženia pravdepodobnosti
0
p 'i = pi + N (0,σ )
ƒ
ƒ
s najväčšou pravdepodobnosťou generujeme 0
často sa používa normované ľubovoľné rozdelenie
p 'i = pi + σN (0,1)
ƒ
tvary sú podobné, ale nie rovnaké
•
v prvom prípade musíme priamo ovplyvňovať generátor čísel v druhom nie
Genetické operátory pre ostatné reprezentácie
genetické operátory pre maticovú reprezentáciu
o
každý jedinec je zadaný obdĺžnikovou maticou
o
príklad kríženia
ƒ
náhodne sa vygeneruje ľavý horný a pravý dolný roh okna
ƒ
prvky v okne sa navzájom vymenia
o
príklad mutácie
ƒ
vygenerovanie okna v jedincovi
ƒ
náhodná výmena prvkov v okne
genetické operátory pre stromovú reprezentáciu
o
vznikli pre potreby genetického programovania na vyjadrenie programov
o
často sa používa na reprezentáciu LISP
o
príklad stromových reprezentácií
-
/
x
x
/
x
-
x
-
+
x
*
x
x
vyjadruje
x
*
x
x
x
x − x3
vyjadruje 2 x − x
20
−x
x
príklad kríženia
ƒ
vymenenie častí stromových štruktúr
ƒ
jednobodové kríženie
o
/
+
x
x
x
x
/
*
x
x
-
*
x
x
vyjadruje
x
vyjadruje x + x3 − x
x
x
−x
x
x−x
príklad mutácie
ƒ
náhodné pregenerovanie vetvy stromu
genetické operátory pre binárnu reprezentáciu s premenlivou dĺžkou
o
príklad kríženia
ƒ
keďže sú reprezentácie rôznej dĺžky, vygenerujú sa body pre oboch jedincov osobitne
o
-
Î
ƒ
ƒ
-
vždy bude šanca, že sa zmení dĺžka reťazcov a teda aj reprezentácií jedincov
je teda nutné, aby sme naprogramovali procedúru, ktorá bude brať do úvahy rôzne dĺžky reprezentácií
volá sa pri výpočte vhodnosti jedinca
•
•
ak je jedinec dlhší
o
zobrať potrebný počet bitov zľava
o
zobrať iba najčastejšie sa vyskytujúce hodnoty
o
výber prvkov pomocou náhodného výberu
ak je jedinec kratší
•
o
chýbajúca genetická informácia sa doplní z typického jedinca
ƒ
logický jedinec môže byť riešenie, ktoré nie je optimálne, ale je dobré
o
chýbajúca genetická informácia sa doplní z viacerých typických jedincov
ƒ
porovnanie kratšieho jedinca s typickými jedincami
ƒ
doplnenie genetickým materiálom z toho, s ktorým sa najlepšie zhoduje
vlastné genetické operátory
o
môžeme si navrhnúť aj vlastné genetické operátory
o
táto možnosť sa používa vtedy, ak klasické genetické operátory nepostačujú
Výpočet vhodnosti
pri výpočte vhodnosti je nutné pretransformovať genotyp na fenotyp a tak vypočítavať fitness
o
nie je to nutné ak je prepis genotypu na fenotyp ten istý
účelová funkcia reprezentuje prepis genotypu na fenotyp
o
mierkovanie
o
normovanie
o
transformácia maximalizácie na minimalizáciu
ƒ
1. možnosť
K − UF
K - dostatočná konštanta
UF - účelová funkcia
ƒ
2. možnosť
1
UF + ε
ε - kladná konštanta, aby sme v menovateli nedostali 0
UF - musí byť v tomto prípade nezáporná
21
-
predpokladajme problém
o
máme krabice a veci, ktoré chceme do nich nabaliť
o
chceme, aby sme veci pobalili do čo najmenšieho počtu krabíc
o
predpokladajme účelovú funkciu, ktorá vyjadruje minimalizáciu a teda počet krabíc potrebných na pobalenie vecí
ƒ
problém však je, že účelová funkcia bude vyzerať nasledovne
počet krabíc
rozloženie vecí
v krabiciach
ƒ
ƒ
o
teda tvar účelovej funkcie je veľmi dôležitý
je nutné túto funkciu aproximovať funkciou, ktorá by mala globálny extrém v rovnakom bode a aby bol tvar funkcie
čo najlepší
•
aby mala sklon
aby bola čo najhladšia
•
môžeme však za účelovú funkciu brať naplnenie krabíc
 Fi 
 
c
∑  N
i =1
k
N
Fi - naplnenie krabice
c - kapacita krabice
k - konštanta, ktorá je väčšia ako 1 a tým preferuje plnšie krabice
N - počet krabíc
ƒ
keby sme položili k = 1
N
∑ Fi
1
i =1
c
-
N
ƒ
dostali by sme pôvodnú plochú účelovú funkciu
je teda nutné mať znalosti o úlohe, aby sme mohli navrhnúť správnu účelovú funkciu
Klasické tvary evolučných algoritmov
pod klasickým tvarom evolučného algoritmu rozumieme, že odborník povie že je to určitý typ algoritmu
o
musíme poznať základné tvary algoritmov, ktoré sa najčastejšie používajú, aby sme mohli určiť tvar evolučného algoritmu
evolučné stratégie
o
reprezentácia
ƒ
vektor reálnych čísel
x1
o
xl
x2
genetické operátory
ƒ
na začiatku sa používala iba mutácia
ƒ
neskôr sa pridalo aj kríženie
ƒ
stále sa na mutáciu dáva najväčší dôraz
ƒ
používa sa normálna mutácia
x'i = xi + σ i N i (0;1)
•
•
x1
•
•
každá pozícia má nezávislý generátor náhodných čísel
často sa nastavuje aj σ i náhodne, teda máme reprezentáciu jedinca
x2
σ1
xl
σ2
σl
vytvorili sme tzv. samoadaptívny systém
je nutné mutovať aj druhú časť
σ 'i = σ i e(τN (0;1)+τN i (0;1))
N (0;1) - rovnaké pre všetky pozície
N i (0;1) - vlastný generátor pre každú pozíciu
22
ƒ
o
o
mutácia prebieha na normálnom rozdelení
v prvej časti výmena podľa jednobodového kríženia
v druhej časti sa vypočítava pomocou matematických operácií
selekcia
ƒ
na začiatku vstupoval každý jedinec do selekcie s rovnakou pravdepodobnosťou vybratia
ƒ
tento prístup sa často používa aj teraz
populačná náhrada
ƒ
čiarková stratégia (µ , λ )
ƒ
o
•
kríženie
•
•
ƒ
ostatné
ƒ
ƒ
•
•
iba z λ nových jedincov sa vyberajú potomkovia
veľmi často je λ > µ
•
vyberie sa iba µ najlepších jedincov
plus stratégia (µ + λ )
•
rodičia a potomkovia sa zlúčia do jednej množiny
•
z výslednej množiny vyberáme potomkov
často sa volí λ = 6 µ
pomocou mutácie sa dostaneme s rovnakou pravdepodobnosťou ďaleko všetkými smermi
pokus o usmernenie mutácie
•
výpočet kovariancie v druhej časti jedinca (kde mutujeme σ i )
extrém
extrém
aktuálne
riešenie
aktuálne
riešenie
normálna mutácia
usmernená mutácia
inicializácia
ƒ
nie je vyhradená
ƒ
na začiatku máme nejakú dobrú kombináciu parametrov
ƒ
ďalšie jedince vygenerujeme tak, že náhodne zmeníme hodnoty jedinca
o
ukončovacia podmienka
ƒ
nie je vyhradené
ƒ
výpočet vhodnosti v predchádzajúcich iteráciách a ak je zmena od aktuálnej iterácie malá, algoritmus končí
evolučné programovanie
o
na začiatku bola reprezentovaná konečnými automatmi
o
neskôr sa začalo pracovať s číslami
o
reprezentácia
ƒ
vektor reálnych čísel s dĺžkou l
ƒ
vhodnosť jedinca nezávisí len od účelovej funkcie, tá sa transformuje a k pretransformovanej hodnote sa vygeneruje
náhodná alternácia
o
-
Φ (UF (x1 , x 2 , L , xl ), χ )
o
ƒ
jedinci s rovnakým genetickým materiálom môžu byť rôzne vyhodnotený
genetické operátory
ƒ
používa sa iba výhradne mutácia
ƒ
používa sa normálna mutácia v tvare
x'i = xi + β i Φ (ai ) + γ i .N (0;1)
•
rozloženie pravdepodobnosti potom je
σ = βi Φ (ai ) + γ i
•
vidíme, že je závislé od vhodnosti jedinca
jedinec s malou vhodnosťou
jedinec s veľkou vhodnosťou
23
o
o
•
dobrý jedinec je častejšie vyberaný ako horší
ƒ
každý jedinec je mutovaný
selekcia
ƒ
v selekcii nie je selekčný tlak
populačná náhrada
ƒ
selekčný tlak je v náhrade
ƒ
vhodnosť sa neurčuje z účelovej funkcie priamo
ƒ
z populácie vyberieme q náhodne jedincov
ƒ
porovnajú sa vhodnosti daného jedinca a q vybratých
ƒ
koľkokrát bude daný jedinec víťazom, takú bude mať vhodnosť
ƒ
vhodnosť teda bude z intervalu 0; q
inicializácia
ƒ
vychádzame z prehľadávaného priestoru
ƒ
každý rozmer priestoru je z určitého intervalu
ƒ
v priestore sa podľa rozmerov priestoru vytvorí rovnomerná mriežka a ňou sa vyberú jedinci
o
ukončovacia podmienka
ƒ
napríklad počet generácií
genetické algoritmy
o
reprezentácia
ƒ
typicky používame reprezentáciu binárnym reťazcom
ƒ
reálne číslo sa kóduje na binárnom reťazci
nech reálne čísla sú zakódované na l bitoch
•
o
-
0
•
l −1
1
číslo je potom vyjadrené
l −1
∑ ai 2l −1−i
i =0
•
maximálne zakódované číslo je 2l − 1
•
chceme však reprezentovať číslo z intervalu a; b
xr = a +
b−a
x
2l − 1
x - zakódované prirodzené číslo
a, b - hranice intervalu, na ktorý chceme dané číslo transformovať
b−a
2l − 1
•
o
o
o
o
o
- nazýva sa inkrement
presnosť kódovania reálneho čísla
o
ak vieme s akou presnosťou chceme číslo kódovať, potom sa musí inkrement do tejto hodnoty
zmestiť
o
z toho vieme určiť počet bitov potrebných na zakódovanie
genetické operátory
ƒ
používa sa mutácia aj kríženie
ƒ
kríženie je dôležitejšie
ƒ
najčastejšie sa používa jednobodové kríženie
selekcia
ƒ
selekčný tlak sa kladie už sem
ƒ
väčšinou sa používa ruleta
populačná náhrada
ƒ
pri formovaní novej generácie sa nepoužíva selekčný tlak
inicializácia
ƒ
náhodné generovanie jedincov
ukončovacia podmienka
ƒ
ak populácia skonverguje
ƒ
musíme mať číslo, ktoré túto konvergenciu vyjadruje, tzv. mieru konvergencie
1
lµ
•

µ
µ

i =1

∑ max ∑ (1 − aij ); ∑ aij 
l
j =1
 i =1
µ
∑ aij je výpočet počtu jednotiek na j - tej pozícii vo všetkých jedincoch
i =1
24
•
µ
∑ (1 − aij ) je výpočet počtu núl na j - tej pozícii vo všetkých jedincoch
i =1
•
ƒ
µ
 µ

µ
max ∑ 1 − aij ; ∑ aij  vyjadruje či sa nuly alebo jednotky viac vyskytujú a je z intervalu
;µ
 i =1

2
i =1


(
)
µ
o
ak sa hodnota blíži k
o
ak sa hodnota blíži k µ , populácia už skonvergovala
2
, populácia ešte neskonvergovala
i vyjadruje jedinca
•
•
j vyjadruje pozíciu bitu
ak bude miera konvergencie väčšia ako určitý prah, potom môžeme algoritmus ukončiť
Teoréma schém
vysvetľuje teorému ako genetický algoritmus pracuje
existujú rôzne pokusy na vysvetlenie
majme jedinca ai = (0 1 1 1 0 0 1 0 1)
-
-
jedinec v prehľadávanom priestore reprezentuje bod
predpokladajme, že abeceda na tvorbu jedincov je 0,1,*
o
znak * reprezentuje absenciu danej hodnoty (je jedno či tam bude 0 alebo 1)
môžeme potom vygenerovať jedinca ai = (0 1 * * * * * * *)
extrémne schémy
o
ani jedna *
ƒ
jeden bod z priestoru
o
všetky *
ƒ
celý prehľadávaný priestor
bod patrí do podpriestoru, ak na všetkých určených bitoch je rovnaký s podpriestorom alebo má na tom mieste podpriestor znak *
o
bod vzorkuje danú schému
-
prehľadávaný priestor obsahuje 2l bodov
-
v prehľadávanom priestore možno vytvoriť 3l schém
-
bod je súčasťou 2l schém
-
populácia môže pokrývať 2l ; µ 2l schém
-
-
stupeň schémy znamená počet nehviezdičkovaných (významových) pozícií, ktoré má daná schéma a označuje sa O(H )
definičná dĺžka schémy
o
rozdiel indexov najľavejšej a najpravejšej nehviezdičkovanej pozície
o
definičná dĺžka sa nedá vyjadriť pre schému, ktorá reprezentuje celý priestor (má samé hviezdičky)
číslo m(H , t ) reprezentuje počet bodov, ktoré sú reprezentované v generácii t schémou H
ak budeme uvažovať genetický algoritmus bez genetických operátorov, potom platí
m(H , t + 1) = m(H , t )
Φ (H )
Φ
Φ (H ) - vhodnosť schémy H
Φ - priemerná vhodnosť populácie
o
o
tento vzorec vyjadruje priemernú vhodnosť jedinca, ktorý danú schému vzorkuje
ak by sme mali nejakú vhodnosť nadpriemernú
m(H , t + 1) = m(H , t )
o
Φ + cΦ
Φ
= m(H , t )(1 + c )
ak by sme mali vypočítať m(H , t + 1) z t − 1 - ho kroku, tak
m(H , t + 1) = m(H , t − 1)(1 + c )2
o
ak by sme mali vypočítať m(H , t + 1) z 0 - tého kroku, tak
m(H , t + 1) = m(H ,0 )(1 + c )t +1
počet bodov, ktoré vzorkujú schému sa mení exponenciálne
ƒ
ak je to podpriemerná schéma, tak počet bodov ktoré vzorkujú schému exponenciálne klesá
ƒ
ak je to nadpriemerná schéma, tak počet bodov ktoré vzorkujú schému exponenciálne narastá
ak budeme uvažovať aj kríženie (jednobodové kríženie)
o
-
0 1 * * * * * * *
Î
0 * * * * 1 * * *
0 1 * * * 1 * * *
0 * * * * * * * *
25
o
o
čím je definičná dĺžka schémy väčšia, tým je väčšia pravdepodobnosť, že sa rozbije
pravdepodobnosť rozbitia schémy teda je
pr =
δ
l −1
δ - definičná dĺžka schémy
o
pravdepodobnosť, že sa schéma zachová je
ps = 1 −
o
ak sa kríženie deje len s určitou pravdepodobnosťou pk , tak
ps ≥ 1 −
o
δ
l −1
δ
l −1
pk
ƒ
je to dolný odhad pravdepodobnosti prežitia schémy
potom teda pri krížení musí platiť
m(H , t + 1) ≥ m(H , t )
-
δ 
Φ (H ) 

1 − pk
t −1 
Φ 
o
vzorec vyjadruje, že nadpriemerne kompaktné schémy sa exponenciálne rozširujú v populácii
o
počet bodov, ktoré vzorkujú danú schému pri selekčnom tlaku je znižovaný genetickým operátorom kríženia
ak budeme uvažovať aj mutáciu
o
mutovať môžu iba významové pozície aby sa schéma zachovala
o
ak pm je pravdepodobnosť mutácie jedného bitu, potom pravdepodobnosť, že mutácia na danom bite neprebehne je 1 − pm
o
pravdepodobnosť prežitia schémy potom je
(1 − pm )O(H )
ƒ
ƒ
pravdepodobnosť prežitia schémy je väčšia, lebo pri mutácii inej schémy nám môže vzniknúť daná schéma
ak platí, že pm je malá hodnota (nastavuje sa väčšinou 1 – 2%), potom
.
(1 − pm )O (H ) =1 − pm O(H )
o
potom teda ak do vzorca pre výpočet počtu vzorkovacích bodov v nasledujúcom kroku pridáme aj mutácia, platí
m(H , t + 1) ≥ m(H , t )
o
Φ (H ) 
δ

− pmO(H )
1 − pk
l −1
Φ 

tento vzorec hovorí, že evolučné algoritmy fungujú tak, že krátke, kompaktné a nadpriemerné schémy sa v populácii
exponenciálne rozširujú
ƒ
nadpriemerné schémy zabezpečuje
Φ (H )
Φ
ƒ
krátke schémy
•
mutácia ich nerozbíja
pmO (H )
ƒ
kompaktné schémy
•
kríženie ich nerozbíja
pk
-
o
De Jong
o
o
o
δ
l −1
tento vzorec zahŕňa selekciu, jednobodové kríženie a mutáciu
jednobodové kríženie sa málo používa
urobil rozšírenie na n - bodové kríženie a uniformné kríženie
rozšírenie pre n - bodové kríženie a dva nevýznamové body
26
p2e (n, L, L1 ) =
n
 
 2 
2i
n  L   L − L1 


 L 
i =0  
∑  2i  L1 
n − 2i
p2e - pravdepodobnosť prežitia schémy druhého stupňa (má iba 2 nevýznamové pozície)
n - znamená n možností na vybratie deliaceho bodu
L - počet všetkých možných deliacich bodov
L1 - počet možných deliacich bodov medzi nevýznamovými pozíciami
n
 2  - aby sme ďalej mohli pracovať s maximálnym párnym číslom 2i
 
2i - aby sme pracovali s párnymi číslami, lebo medzi nevýznamovými pozíciami musíme vygenerovať
párny počet deliacich bodov, aby sa schéma zachovala
n
  - počet možných vybratí párneho počtu bodov z n
 2i 
2i
 L1 
  - pravdepodobnosť toho, že do stredu padne párny počet deliacich bodov
 L
n − 2i - zvyšok po odčítaní párneho počtu bodov 2i
n − 2i
 L − L1 


 L 
pozíciami
n
 
2
∑
- pravdepodobnosť toho, že ostatné body padnú mimo oblasť vymedzenú nevýznamovými
- suma všetkých pravdepodobností cez všetky možné počty párnych čísel
i =0
ƒ
ƒ
vzorec hovorí, že schémy sa zachovávajú, ak medzi nevýznamové body padne práve párny počet deliacich bodov
grafy pravdepodobnosti prežitia schémy pre niekoľko typov n - bodových krížení
p
1
jednobodové kríženie
dvojbodové kríženie
trojbodové kríženie
štvorbodové kríženie
0,5
0
L −1
1
•
o
nad krivkou
o
disrupčný potenciál operátora
o
schopnosť operátora zrušiť danú schému
ƒ
preferujú sa také operátory, ktoré majú najmenší disrupčný potenciál
•
najmenší disrupčný potenciál má dvojbodové kríženie
rozšírenie pre n - bodové kríženie a tri nevýznamové body
nevýznamový bod
úseky v ktorých musia byť párne počty deliacich bodov
o
ƒ
vzorec sa do seba rekurzívne vnára
rozšírenie pre uniformné kríženie
ƒ
na významových pozíciách musí mať maska všade 1 alebo všade 0
ƒ
pravdepodobnosť výskytu samých núl v maske na významových pozíciách je
( p0 )O(H )
ƒ
pravdepodobnosť výskytu samých jedničiek na významových pozíciách je
( p1 )O(H ) = (1 − p0 )O(H )
ƒ
celková pravdepodobnosť prežitia schémy potom je
p = ( p0 )O (H ) + (1 − p0 )O (H )
ƒ
chceme, zistiť kedy bude nadobúdať pravdepodobnosť prežitia extrém
dp
= O(H )( p0 )O (H )−1 − O(H )(1 − p0 )O (H )−1
p0
27
0 = O(H )( p0 )O (H )−1 − O(H )(1 − p0 )O (H )−1
O(H )( p0 )O (H )−1 = O(H )(1 − p0 )O (H )−1
( p0 )O(H )−1 = (1 − p0 )O(H )−1
p0 = 1 − p0
p0 = 0,5
-
ƒ
najväčší disrupčný tlak bude, ak pravdepodobnosť vybratia 0 bude 0,5
ƒ
v ostatných prípadoch bude disrupčný tlak menší
dôsledok teorémy schém
o
predpokladajme, že v populácii sú všetky schémy
o
chceme vedieť, koľko schém má pravdepodobnosť prežitia väčšiu alebo rovnú ε
ƒ
teda nás zaujímajú schémy, ktoré majú definičnú dĺžku menšiu alebo rovnú lS
ƒ
majme jedinca o dĺžke l a zaujímajú nás tie schémy, ktoré majú aspoň jeden významový bit
lS
L
ƒ
L
počet schém v lS je
2l S −1
ƒ
lS sa môže v jedincovi pohybovať
2l S −1 (l − lS + 1)
ƒ
ak je v populácii µ jedincov, potom
µ 2lS −1 (l − lS + 1)
lS
ƒ
predpokladajme, že µ = 2 2 , potom vzťah môžeme upravovať nasledovne
µ 2lS 2−1 (l − lS + 1)
µ2
2

lS
2
lS
2−1 (l − lS + 1)

2
µ  2 2  2−1 (l − lS + 1)




µ (µ )2 2−1(l − lS + 1)
µ 3C
ak používame populáciu s µ jedincami, pracujeme naraz s µ 3 podpriestormi
vo všeobecnosti teda vzorkujeme tretiu mocninu priestoru
•
•
tomuto javu sa hovorí implicitný paralelizmus
teoréma schém poukazuje na to ako pracujú evolučné algoritmy
o
evolučné algoritmy teda pracujú vždy s podpriestormi
ƒ
-
Hypotéza stavebných blokov
stavebná teoréma schém
vychádza z teorémy schém
algoritmus na začiatku pracuje s krátkymi schémami, ktoré sa ovzorkujú
horšie schémy sa zrušia a lepšie postupujú ďalej, z ktorých sa stavajú dlhšie schémy – bloky
toto vzorkovanie prebieha aj na blokoch a z dobrých sa stavajú väčšie bloky
príklad
o
majme funkciu, ktorej chceme nájsť globálne maximum a jedinca kódujme na 4 bitoch
28
Φ
0000
o
1111
schémy 0*** a 1*** vzorkujú nasledovné oblasti
Φ
0***
1***
0000
o
1111
ƒ
lepšia je schéma 1***
schémy *0** a *1** vzorkujú nasledovné oblasti
Φ
*0**
0000
o
*1**
*0**
*1**
1111
ƒ
lepšia je schéma *1**
vznikne nám teda schéma 11**
Φ
11**
1111
0000
-
-
ƒ
budeme teda prehľadávať iba menší priestor
tento prístup funguje, len ak medzi pozíciami nie sú žiadne závislosti
závislosť jednotlivých génov sa nazýva epistáza
delenie epistáz
o
žiadna
ƒ
medzi pozíciami nie sú žiadne väzby
ƒ
zmena na niektorej pozícii vyvoláva odpovedajúcu zmenu vo vhodnosti
o
slabá
ƒ
zmena na niektorej pozícii vyvoláva odpovedajúcu zmenu alebo žiadnu zmenu vo vhodnosti
o
silná
ƒ
zmena na niektorej pozícii vyvoláva vo vhodnosti odpovedajúcu alebo opačnú zmenu
príklad
o
predpokladajme že jedinec 00101101 má maximálnu vhodnosť
o
majme iného jedinca, ktorému zmeníme jeden bit na odpovedajúci v prvom jedincovi
29
0 0 1 0 1 1 0 1
0
1
ƒ
-
žiadna epistáza
•
vhodnosť sa zvýši
•
ak má funkcia vhodnosti iba jedno maximum
ƒ
slabá epistáza
•
vhodnosť sa zvýši alebo zostane zachovaná
•
ak má funkcia vhodnosti rovné plochy
ƒ
silná epistáza
•
vhodnosť sa zvýši, alebo aj zníži
•
ak má funkcia vhodnosti aspoň dve maximá (jedno globálne a jedno lokálne)
dominanciou evolučných algoritmov sú silné epistázy
o
majú s ňou však tiež problémy
klamlivé úlohy
o
sú také, keď schémy ktoré nie sú súčasťou hľadaného riešenia majú vyššiu vhodnosť, ako schémy ktoré sú súčasťou riešenia
o
stavebné bloky, ktoré potrebujeme na skonštruovanie výsledného jedinca sa vylúčia
o
ak klamlivosť platí pre všetky pozície v jedincovi, potom je to plne klamlivá úloha
o
ak klamlivosť platí len pre niektoré pozície v jedincovi, potom je to klamlivá úloha
o
príklad
ƒ
predpokladajme dvojbitového jedinca
ƒ
predpokladajme, že globálne maximum dosiahne jedinec s bitovou kombináciou 11
ƒ
potom platí
Φ (11) > Φ (00 )
Φ (11) > Φ (01)
Φ (11) > Φ (10)
ƒ
potom pri klamlivej úlohe platí
Φ (1 *) < Φ (0 *) ∨ Φ (*1) < Φ (*0 )
ƒ
oba platiť naraz nemôžu
•
klamlivé úlohy potom vyzerajú nasledovne
?
01
01
00
00
11
11
10
klamlivá schéma
o
o
10
úplne klamlivá schéma
majme reprezentáciu jedinca na troch bitoch x1, x2, x3
vhodnosť jedinca sa bude vypočítavať podľa vzorca
Φ = 13 − 14 x1 − 6 x2 − 2 x3 − 8 x1x2 − 12 x1x3 − 20 x2 x3 + 64 x1x2 x3
30
o
x1
x2
x3
Φ
0
0
0
13
0
0
1
11
0
1
0
7
0
1
1
-15
1
0
0
-1
1
0
1
-15
1
1
0
-15
1
1
1
15
1
*
*
-4
0
*
*
4
*
1
*
-2
*
0
*
2
*
*
1
-1
*
*
0
1
ƒ
takto by úloha skonvergovala k jedincovi 000 a nie 111 kde je globálne maximum
premapujme genotyp podľa vzorca
 x'1 %2  1 0 0  x1 

 
 
 x' 2 %2 = 1 1 0  x 2 
 x'3 %2  0 1 1  x3 
% - zvyšok po delení
ƒ
o
vhodnosti jednotlivých jedincov sa nezmenia, ale zmenia sa vhodnosti schém
x1
x2
x3
Φ
x'1
x'2
x'3
0
0
0
13
0
0
0
0
0
1
11
0
0
1
0
1
0
7
0
1
1
0
1
1
-15
0
1
0
1
0
0
-1
1
1
0
1
0
1
-15
1
1
1
1
1
0
-15
1
0
1
1
1
1
15
1
0
0
1
*
*
-4
0
*
*
4
4
*
1
*
-2
-6
*
0
*
2
6
*
*
1
-1
-3
*
*
0
1
3
-4
ƒ
zmenili sme úlohu z úplne klamlivej na iba klamlivú
ƒ
algoritmus skonverguje k riešeniu 000, namiesto 100, ktoré má najvyššiu vhodnosť po premapovaní
premapujme genotyp podľa vzorca
 x' '1 %2  1 1 0  x1 

 
 
 x' '2 %2 = 1 0 1  x2 
 x' '3 %2  1 1 1  x3 
ƒ
tabuľka po transformovaní bude vyzerať nasledovne
x1
x2
x3
Φ
x''1
x''2
x''3
0
0
0
13
0
0
0
0
0
1
11
0
1
1
0
1
0
7
1
0
1
0
1
1
-15
1
1
0
1
0
0
-1
1
1
1
1
0
1
-15
1
0
0
1
1
0
-15
0
1
0
1
1
1
15
0
0
1
1
*
*
-4
0
*
*
4
6
*
1
*
-2
-5
*
0
*
2
5
*
*
1
-1
8
*
*
0
1
-8
31
-6
o
o
ƒ
z úplne klamlivej úlohy sme vytvorili úlohu, ktorá bude konvergovať k správnemu riešeniu
genotyp a fenotyp
ƒ
kríženie a mutácia sa vykonávajú v genotype
ƒ
vhodnosť sa počíta vo fenotype
ƒ
je teda nutné prepočítavať genotyp na fenotyp
Grayove kódy
ƒ
pomocou Grayových kódov môžeme zmeniť úplne klamlivú úlohu iba na klamlivú úlohu
X g = M .X
X g - genetický kód po úprave
X - genetický kód pred úpravou
M - transformačná grayova matica
•
transformačná matica M je štvorcová a počíta sa rekurzívne
M1 = [1]
1 0 0 0 L 0


1

0

M i +1 = 

Mi
0

M



0

ƒ
spätná transformácia
X = N .X g
•
transformačná matica N je štvorcová a počíta sa rekurzívne
N1 = [1]
1 0 0 0 L 0


1

1

Ni +1 = 

Ni
1

M



1

ƒ
primárne použitie Grayových kódov
•
klasická reprezentácia binárneho kódu
0
1
2
3
4
5
M
•
(0
(0
(0
(0
(1
(1
0
0
1
1
0
0
M
0)
1)
0)
1)
0)
1)
o
pri mutácii sa môže napríklad číslo 1 zmeniť na 0, 3, alebo 5 s rovnakou pravdepodobnosťou
o
mutácia teda môže veľmi meniť genetický kód
o
najväčšia zmena môže, ktorá môže nastať, je až polovička maximálneho kódovaného čísla
na odstránenie tohto problému sa používa Grayov kód
0
1
2
3
4
5
M
o
(0
(0
(0
(0
(1
(1
0
0
1
1
1
1
M
0)
1)
1)
0)
0)
1)
pravdepodobnosť nastatia mutácie na susedov je rovnaká na obe strany
32
Udržiavanie rôznorodosti
nadpriemerné schémy sa v populácii rozširujú a podpriemerné vylučujú
o
znižuje sa rozsah genetického materiálu
o
môže vypadnúť určitá schéma
o
v ideálnom prípade zostáva v populácii genetický materiál iba z riešenia
o
v druhom prípade ostáva v populácii genetický materiál z riešenia ale aj z iných riešení
o
v najhoršom prípade vypadne genetický materiál z populácie skôr ako sa podarilo nájsť riešenie
o
uviaznutie v lokálnom extréme – predčasná konvergencia
o
kríženie len mieša genetický materiál v populácii
o
mutácia zavádza do populácie aj nový genetický materiál
tri faktory predčasnej konvergencie
o
selekčný tlak
ƒ
čím je väčší, tým viac genetického materiálu z populácie vypadáva
ƒ
zníženie selekčného tlaku
•
iný selekčný operátor
•
zmena koeficientov selekcie – zmena prahu
o
selekčný šum
ƒ
populácia má tendenciu sa zmenšovať iba do určitého priestoru
ƒ
čím je väčší, tým nám môže populácia skôr skonvergovať a teda aj predčasne
o
genetické operátory
ƒ
pôsobia proti konvergencii
ƒ
rozbíjajú schémy a tým rozširujú genetický materiál
ƒ
znížiť selekčný tlak možno teda aj disrupčným potenciálom genetických operátorov
prístupy v boji proti predčasnej konvergencii
o
ponechanie populácie
o
veľkosť populácie
o
protimetódy
o
infúzia
o
subpopulácie
o
rovnomerné pokrývanie
ponechanie populácie
o
ponechanie populácie jej prirodzenému vývinu
o
mutácia môže kód zmeniť tak, že nájdeme globálne maximum
o
prakticky nebojuje proti predčasnej konvergencii
veľkosť populácie
o
najjednoduchší prístup
o
zväčšenie populácie
o
genetický materiál pomalšie vypadne
o
konvergencia trvá dlhšie
protimetódy
o
ak vieme čo zapríčiňuje predčasnú konvergenciu
o
vyberieme také genetické operátory, ktoré bojujú práve proti predčasnej konvergencii
infúzia
o
nový genetický materiál sa umelo pumpuje do populácie
subpopulácie
o
v populácie budeme udržiavať subpopulácie
o
každá subpopulácia bude konvergovať na iné miesto
o
pokiaľ existuje v populácii subpopulácia, potom existuje aj genetický materiál, ktorým je tvorená
rovnomerné pokrytie
o
snaha odtláčať body od seba a tak bojovať proti predčasnej konvergencii
o
pôsobenie protisily
Infúzie
-
-
skupiny metód, kde umelo do populácie dopĺňame genetický materiál
v ideálnom prípade dopĺňame všetko čo vypadlo
o
avšak kontrola celej populácie je zdĺhavá
dopĺňanie náhodného genetického materiálu
o
rýchla a jednoduchá metóda
eliminácia duplikácií
o
cieli na to, že sledujeme čo v populácii chýba
o
spúšťa sa vtedy, keď vkladáme potomka do populácii
o
sledujeme či vkladaný potomok nie je podobný tomu čo v populácii už je
o
ak nájdeme nejaký genetický materiál podobný, potom daného potomka zmutujem, v opačnom prípade ho do populácie
zaradíme
o
opäť sa jedinec kontroluje
o
toto sa opakuje maximálne n - krát
ƒ
väčšinou sa n = 3
o
táto metóda sa nedá použiť, ak všetci potomkovia nahrádzajú všetkých rodičov
o
používa sa, len ak nová populácia je tvorená starou, a len niektoré jedince sú vymenené
reinicializácia
o
populáciu rozdelíme na dve časti
ƒ
prežívajúcu časť
0 ≤ Pr < µ
ƒ
reinicializujúca sa časť
1 ≤ Re ≤ µ
o
rozdelenie sa vykonáva pomocou selekčnej metódy
o
možnosti reinicializácie
ƒ
náhodná
•
náhodne vygenerujeme novú populáciu
ƒ
hypermutácia
33
o
o
o
o
o
•
zmutovanie jedincov v reinicializačnej časti
•
mutácia sa deje s vysokou pravdepodobnosťou
ƒ
hypermutácia so vzorom
•
zoberú sa niektoré jedince z prežívajúcej časti a tie sa hypermutujú
ak bude vykonávaná často, musíme reinicializovať iba malú časť populácie
ak bude vykonávaná menej často, môžeme reinicializovať väčšiu časť
delenie reinicializácií
ƒ
reinicializácia po etapách
ƒ
reinicializácia po udalostiach
•
ak populácia skonverguje – ak sa genetický materiál príliš ochudobní
•
podľa výkonu genetického algoritmu – ak sa výkon už veľmi nezvyšuje
pri reinicializácii nepotrebujeme mutáciu
nepotrebujeme veľké populácie, lebo hypermutácia ich vytvorí
ƒ
tým aj znižujeme výpočtovú náročnosť
Subpopulácie
problém je to, ako dosiahnuť, aby v populácii vznikali subpopulácie
delenie metód
o
založené na párení
ƒ
vychádza z biologickej motivácii
ƒ
delenie na druhy
ƒ
jedince sa pária len v rámci jedného druhu
ƒ
párenie jedincov z iných druhov je výnimočné
o
založené na súťaži
ƒ
každý druh okupuje istý priestor
ƒ
každý druh obýva svoj vlastný priestor
ƒ
jedince súťažia len v rámci jedného druhu
ƒ
druhy si navzájom nekonkurujú
ƒ
každý druh má svoje vlastné zdroje o ktoré súťaží
metódy založené na párení
o
metóda vzdialenosti
ƒ
počíta sa vzdialenosť medzi dvomi jedincami ako rozdiel v genetickom materiály
ƒ
rozdielnosť genetického materiálu musí byť pod určitou hranicou
o
metóda príznakov
ƒ
jedinec má príznak, ktorý identifikuje druh
príznak
o
genetický materiál
ƒ
ak kódujeme príznak na r bitoch, potom možno zakódovať 2r bitov
ƒ
len jedince rovnakého druhu sa môžu páriť
ƒ
nevýhodou je, že musíme odhadnúť správny počet druhov
metódy založené na stochastickom princípe
ƒ
kombinácia vzdialenostných a príznakových metód
ƒ
príznak je reálne číslo z intervalu 0;1
ƒ
ƒ
ƒ
ak je príznak blízky 0, potom sa druhý rodič preferuje podobný prvému
ak je príznak rovný 1, potom sa druhý rodič preferuje podobný doplnku prvého rodiča
v ostatných prípadoch
pravdepodobnosť
párenia
1
P21
P12
R2 R1 p1
minimálny
genetický
rozdiel
p2
maximálny
genetický
rozdiel
P12 - pravdepodobnosť, že sa druhý rodič spári s prvým
P21 - pravdepodobnosť, že sa prvý rodič spári s druhým
p1 - prvý príznak
p2 - druhý príznak
•
skutočná pravdepodobnosť párenia potom bude
P12 .P21
o
metóda tresholdu
ƒ
vyberá iba prvého rodiča pomocou selekčnej metódy
ƒ
druhého rodiča vyberáme náhodne
ƒ
ak je rozdiel medzi rodičmi menší ako prah, potom sa párenie koná
ƒ
v opačnom prípade sa vyberá ďalší rodič
34
ƒ
-
toto sa opakuje maximálne n - krát
•
často n = 3
metódy založené na súťaži
o
pracujú pri náhrade populácie
o
preselekcia
ƒ
potomkovia nahradia svojich rodičov
o
krauding
ƒ
pri zaraďovaní jedinca do populácie vygenerujem CF jedincov
ƒ
vypočítame vzdialenosť od každého jedinca z CF
ƒ
jedinec nahradí najpodobnejšieho
ƒ
CF - crauding factor
ƒ
selekcia skupiny
•
náhodná
•
náhodné z horšej časti populácie
•
na základe selekčnej schémy
Rovnomerné pokrytie
metóda zdieľania
o
vychádza z biologického princípu
o
jedinci súťažia o zdroje v určitom prostredí
o
prostredie má limitované prostriedky
o
ak je prostriedkov dostatok, jedinci sa exponenciálne množia
ƒ
dochádza k predčasnej konvergencii
o
ak je prostriedkov málo, tak sa jedince snažia migrovať
o
dve metódy pre určovanie prostriedkov
ƒ
všetci jedinci dostávajú menej prostriedkov
ƒ
niektorí jedinci vyhynú
o
zdroje sú odvodené od fitness
ƒ
ak kapacita prostriedkov klesne, tak sa fitness všetkým zníži
ƒ
noví jedinci sa snažia hľadať iné priestory
ƒ
menšia vhodnosť jedincov zapríčiňuje ďalšie hľadanie maxima
ƒ
prepočítava sa vhodnosť jedinca
Φ ' (ai ) =
Φ (ai )
µ
∑ sh(d (ai , a j ))
j =1
Φ (ai ) - pôvodná vhodnosť
Φ ' (ai ) - upravená vhodnosť
( )
sh(d (ai , a j )) - shearingová funkcia
ak ai = a j potom sh(d (ai , a j )) = 1
ak d (ai , a j ) > r , tak sh(d (ai , a j )) = 0 a jedinec zdroje neodoberá
ak d (ai , a j ) < r , tak sh(d (ai , a j )) > 0 a jedinec zdroje odoberá
d ai , a j -vzdialenosť medzi jedincami
r - polomer, v ktorom skúmame ubúdanie zdrojov
•
•
čím viac jedincov bude v polomere, tým viac sa im bude vhodnosť zmenšovať
príklad shearingovej funkcie
(
 d ai , a j
sh d ai , a j = 1 − 
r

((
))
) α
(
1
r
d
cez parameter α môžeme riadiť rýchlosť klesania funkcie
o
často sa volí α = 1
problémom je zvolenie parametru r
•
ƒ
Niche methods
riešenie multimodálnych úloh
o
chceme nájsť niekoľko najlepších riešení
používa sa, ak sa napríklad nedajú vybrať všetky príznaky pre funkciu príslušnosti
výstup sa ešte ďalej spracováva, alebo sa ponúkne ako výsledok a užívateľ si z nich vyberie
delenie
o
paralelné metódy
ƒ
rozdeľujú populáciu na menšie
35
)
d ai , a j ≤ r


-
ƒ
každá populácia hľadá iné riešenie
ƒ
rozdelenie jedincov do subpopulácií, aby pokryli viaceré riešenia a tým bojujeme proti konvergencii
ƒ
s počtom požadovaných riešení musíme zväčšovať adekvátne populáciu
o
sériové metódy
ƒ
opakovane spúšťame genetický algoritmus
ƒ
hľadáme iné riešenia
sériové metódy
o
ak hľadáme dva extrémy, tak v ideálnom prípade potrebujeme dve spustenia algoritmu
o
avšak celkový počet spustení by mal byť
cps = p.R
p - počet riešení, ktoré hľadáme
R - faktor redundancie
o
ak je rovnaká pravdepodobnosť, toho že jedinci pôjdu do jedného z extrémov, potom
R=
p
1
∑m
m =1
o
priemerne teda potrebujeme pre dva extrémy celkový počet spustení
R = 1+
1 3
=
2 2
cps = p.R = 2.
3
=3
2
táto metóda sa dá použiť iba vtedy, ak je rovnaká pravdepodobnosť, že jedinci pôjdu do jedného z vrcholov, čo väčšinou nie je
splnené
paralelné metódy
o
základom paralelných metód je snaha, aby populácia nekonvergovala, teda ide o udržiavanie rôznorodosti populácie
o
nie všetky metódy potláčajúce rôznorodosť sú vhodné
o
varianta craudingu
ƒ
klasický crauding, kde jedinec nahrádza najbližšieho jedinca nefunguje dostatočne
ƒ
deterministický crauding
•
snaží sa z craudingu odstrániť jeho výpočtovú náročnosť
•
nemá snahu kontrolovať všetkých jedincov, ale len populáciu rodičov
•
tvoria sa turnaje medzi potomkami a rodičmi
o
lepší jedinec sa zaradí do populácie
•
možné kombinácie medzi rodičmi a potomkami pre dvoch rodičov, z ktorých vznikajú dvaja potomkovia
o
-
ƒ
o
P2 → R1
P2 → R2
•
pre každú kombináciu vypočítavame podobnosť a turnaj sa vykonáva pre najpodobnejších jedincov
multi niche crauding
•
vychádza tiež zo základnej craudingovej schémy
•
z populácie nevyberieme len jednu skupinu, ale niekoľko skupín
•
porovnávame jedincov v rámci jednotlivých skupín s potomkami
o
dostaneme najpodobnejších jedincov v rámci jednotlivých skupín
•
potomok nahradí najhoršieho z najpodobnejších
shearing
ƒ
používa sa v nezmenenej podobe
ƒ
kapacita určitého prostredia sa znižuje počtom jedincov, ktorí sa v tom prostredí nachádzajú a tým sa znižuje
vhodnosť
ƒ
ƒ
ƒ
ƒ
-
P1 → R1
P1 → R2
( )
výpočtová náročnosť len na premapovanie vhodností je O n 2
•
vypočítavame vzdialenosť jedinca od všetkých ostatných
•
tento výpočet musíme urobiť pre každého jedinca
ak by bola rovnaká pravdepodobnosť, že sa dostaneme do niektorého extrému, potom počet potrebných jedincov
v populácii musí byť Zp
ak by nebola rovnaká pravdepodobnosť, že sa dostaneme do niektorého extrému, potom počet potrebných jedincov
v populácii musí byť ZpR
•
R - faktor redundancie, ktorý je založený na pomeroch obsahov jednotlivých extrémov
•
to však predpokladá znalosti o danej úlohe
možnosti riešenia vysokej výpočtovej náročnosti
•
vyberieme len vzorku populácie a shearing použijeme len na túto vzorku
•
pozhlukujeme jedincov zhlukovacím algoritmom a shearing budeme vykonávať iba na jednotlivých
zhlukoch
sériové metódy
o
sekvenčné hľadanie viacerých riešení
o
využívame informáciu o polohe riešenia
o
po nájdení riešenia sa snažíme problém upraviť tak, aby sa tam dané riešenie už nevyskytovalo
o
jedná sa o odstraňovanie extrémov, ktoré je založené na sekvencii depresných funkcií
ƒ
ak hľadáme nulté riešenie, premapujeme vhodnosť nasledovne
36
M 0 ( x ) = Φ (x )
•
teda vhodnosť zostáva rovnaká
•
nájdeme riešenie s1
ak hľadáme ďalšie riešenia postupujeme nasledovne
ƒ
M1 (x ) = M 0 (x )G (x, s1 )
nájdeme riešenie s2
M 2 (x ) = M1 (x )G (x, s2 )
nájdeme riešenie s3
atď.
funkcia G (x, si ) musí odstraňovať niektoré riešenie
ƒ
1
d (x, si )
r
ƒ
funkcia G (x, si ) vytvára modifikáciu iba v okolí r od nájdeného riešenia si
ƒ
takáto funkcia nám zabezpečí, že čím budeme bližšie k extrému, tým je jeho potlačenie väčšie
d >r
 1;

α
G (x, si ) =  d 
 r  ; d ≤ r
 
nastavenie parametra r
ƒ
parameter r nám udáva, v akom okolí od extrému sa bude funkcia meniť
ƒ
funkcia okolo extrému sa mení nasledovne
o
Φ
problém pred nájdením riešenia
problém po nájdením riešenia
s1
r
ƒ
ƒ
r
vznikajú nám ďalšie lokálne virtuálne extrémy, ktoré je možné riešiť nasledovne
•
zavedenie prahu a testovanie, či má riešenie väčšiu vhodnosť ako prah
o
možno použiť len vtedy, ak poznáme informácie o úlohe
•
ak je jedinec v okolí r , tak ho považujeme za virtuálny extrém
•
nájdenie vhodnosti na pôvodnej funkcii a horolezeckým princípom sa dostaneme do extrému. Ak sme už
raz taký extrém objavili, tak ho opäť neakceptujeme
•
kombináciou metód
ak položíme r veľmi malé dostaneme dva vysoké virtuálne extrémy
Φ
problém pred nájdením riešenia
problém po nájdením riešenia
r
ƒ
s1
r
ak položíme r veľmi veľké, tak môžeme iný extrém znížiť a dokonca aj posunúť
•
preto r volíme radšej malé
37
Φ
problém pred nájdením riešenia
problém po nájdením riešenia
s1
ƒ
r
ak sú riešenia rovnomerne rozdelené, potom sa r nastavuje podľa vzorca
r=
•
k
2k P
polomer r by v žiadnom prípade nemal prekročiť túto hranicu
Multikriteriálne úlohy
riešenie úloh, kde máme viac kritérií
podľa každého kritéria môžeme určiť vhodnosť
vhodnosť jedinca teda bude reprezentovaná nasledovne
Φ (a1 ) = (Φ1 (a1 ), Φ 2 (a1 ),L, Φ m (a1 ))
-
-
pre prácu s takouto reprezentáciu vhodnosti jedinca je nutné upraviť genetický algoritmus
o
použitie iba jednej vhodnosti v evolučnom algoritme
o
použitie všetkých vhodností v evolučnom algoritme
ƒ
agregácie vhodností
ƒ
triedenie vhodností
ƒ
zmena algoritmu
množiny Pareto
o
zaoberá sa pojmom dominancie
o
predpokladajme dva vektory
u = (u1, u2 ,L, um )
v = (v1, v2 ,L, vm )
ƒ
predpokladajme, že platí
∀i; ui ≤ vi
∃i; ui < vi
ƒ
o
príklad
ƒ
ƒ
potom vektor v dominuje vektoru u
•
vektor v nie je v žiadnom ohľade horší a minimálne v jednom ohľade je lepší ako vektor u
problém minimalizácie
majme dve funkcie
Φ1 = x 2
Φ 2 = (x − 2 )2
Φ
0
ƒ
2
ak prekreslíme graf do priestoru vhodností bude vyzerať nasledovne
38
Φ2
C
D
4 F
A
B
E
4
Φ1
•
•
•
•
•
•
•
o
o
každý jedinec sa nachádza na čiare
B dominuje nad A
D dominuje nad C
E dominuje nad B a A
F dominuje nad D a C
medzi E a F neexistujú body, ktoré by boli dominantné nad niektorými inými
množiny bodov medzi E a F tvoria Pareto množiny
o
niekedy sa nazýva ja Pareto front
je množina nedominantných riešení
každý bod z Pareta je kandidátom na riešenie
Algoritmy pracujúce iba s jednou vhodnosťou
algoritmus VEGA
o
vectore evaluated genetic algorithm
o
pracuje iba s jednou vhodnosťou
P'
P
Î
o
Î
selekcia rodičov
ƒ
rodičia sa vytvárajú m - krát, pričom m je počet vhodností
ƒ
napĺňa sa teda m úsekov
ƒ
o
o
o
o
P' '
do každého úseku sa vyberá
ρ
rodičov
m
ƒ
rodičia v prvom úseku sa vyberajú podľa prvej vhodnosti
ƒ
rodičia v druhom úseku sa vyberajú podľa druhej vhodnosti
rodičov náhodne premiešame, aby sme zabudli, ktorý z ktorej časti pochádza ktorý rodič
následne vygenerujeme potomkov
algoritmus je dobre použiteľný, ak Pareto front je konkávny
algoritmus nie je vhodné použiť, ak Pareto front je konvexný
Φ2
Φ2
Φ1
konkávny Pareto
front
ƒ
ƒ
Φ1
konvexný Pareto
front
na konkávnom fronte, majú aj stredne dobré riešenia vhodnosť vyššiu, a teda sa môžu dostať do populácie rodičov
na konvexnom fronte majú stredne dobré riešenia vhodnosť nižšiu, a teda sa menej dostávajú do populácie rodičov
Agregačné metódy
celková vhodnosť bude reprezentovaná jednou vhodnosťou vypočítanou z jednotlivých čiastkových vhodností
súčet vhodností
m
Φ (ai ) = ∑ Φ j (ai )
j =1
-
o
nie je veľmi vhodné
váhovaný súčet vhodností
m
Φ (ai ) = ∑ w j Φ j (ai )
j =1
39
o
o
priamo v takejto nie je možné použiť
nevieme povedať čo w j znamená
o
ƒ
môže znamenať preferenciu určitej zložky vhodnosti
ƒ
môže znamenať aj normovanie
pred použitím je potrebné najskôr jednotlivé vhodnosti normalizovať
Φ' =
Φ − min
max − min
ƒ
o
o
o
o
získať minimálnu a maximálnu vhodnosť je niekedy problém
•
v takom prípade sa minimum a maximum odhaduje
o
min bude minimum z jedinca
o
min bude minimum z niektorej zložky vhodností
min sa bude počítať z každého jedinca a z každej zložky
o
po váhovaní jednotlivé váhy znamenajú uprednostnenie
nastavenie váh je však ďalší problém
nekladie však vysoké nároky na algoritmus
nedá sa použiť vtedy, ak sú neporovnateľné kritériá (farba – spotreba)
Zotriedenie vhodností
klasické premapovanie vhodností
o
princíp je podobný ako u premapovania vhodností
o
vhodnosť jedinca je závislá aj od vhodnosti ostatných jedincov
o
usporiadame jedincov najskôr podľa Φ1
potom usporiadame jedincov podľa Φ 2
dostaneme jedincov, ktorí majú rôzne poradie podľa rôznych vhodností
ƒ
vypočítame priemerné poradie pre každého jedinca
o
jedincov usporiadame podľa priemerného poradia
o
podľa tohto poradia jedincom lineárne premapujeme vhodnosť od 0 po 1
o
nemusíme robiť normalizáciu
premapovanie na základe Paretových množín
o
prvý spôsob
ƒ
každému jedincovi priradíme vhodnosť, ktorá bude reflektovať Paretov front
ƒ
jedinec najbližší Paretovmu frontu bude mať najvyššiu vhodnosť
ƒ
jedinec najviac vzdialený od Paretovho frontu bude mať najnižšiu vhodnosť
ƒ
jedincov budeme ohodnocovať nasledovne
o
o
-
Φ = 1 + pdj
pdj - počet dominantných jedincov na danom fronte
Φ2
1+0
1+1
1+0
1+0
1+4
1+2
Φ1
o
druhý spôsob
ƒ
nájdeme Paretov front a všetkým prvkom na ňom priradíme vhodnosť 1
ƒ
na jedincov na predchádzajúcom fronte zabudneme a vytvoríme ďalší front, ktorému priradíme vhodnosť 2
ƒ
atď.
Φ2
1
2
1
1
3
2
Φ1
ƒ
ƒ
úloha sa nám pretransformuje na minimalizačnú
táto metóda však rýchle konverguje, preto musíme použiť niektorú z metód proti konvergencii
•
shearing
40
•
rôznosť jedincov sa nemôže počítať z genetického materiálu, ale z premapovaných vhodností
d (a1, a2 ) =
•
vzdialenosť jedincov však možno počítať aj všeobecnejším vzorcom
d (a1, a2 ) = k
•
k>2
(Φ1(a1 ) − Φ1(a2 ))2 + (Φ 2 (a1 ) − Φ 2 (a2 ))2 + L + (Φ m (a1 ) − Φ m (a2 ))2
m
∑ (Φi (a1 ) − Φi (a2 ))k
k =1
pre rôzne k sa vhodnosť premapováva nasledovne
k=2
•
k=1
k<1
keďže Paretov front nikdy nemôže byť kolmý na osi, a ak je k < 2 , tak je zmenšená penalizácia
vhodnosti v smere Paretovho frontu a tým preferujeme jedincov na fronte, čo práve potrebujeme
Prispôsobujúce sa algoritmy
manipuluje sa priamo s kódom genetického algoritmu
kód sa prispôsobí tak, aby vedel pracovať aj s viacerými vhodnosťami naraz
program teda musí vedieť pracovať s vektorom vhodností
turnaj
o
prvá možnosť
ƒ
náhodne vyberieme dvoch jedincov a porovnáme ich podľa dominancie
ƒ
veľká nevýhoda je v tom, že vybraný jedinci sa nemusia dať porovnať
o
druhá možnosť
ƒ
náhodne vyberieme dvoch jedincov
ƒ
náhodne si vyberieme vzorku jedincov z populácie
zistíme koľkým jedincom je dominantný prvý vybraný jedinec
•
zistíme koľkým jedincom je dominantný druhý vybraný jedinec
•
ƒ
ten, ktorý dominuje viacerým jedincom bude mať vyššiu vhodnosť a v turnaji vyhrá
náhrada
o
jedinci, ktorí sú kandidáti na novú populáciu, sú rozdelení na dve časti
ƒ
jedince, ktoré tvoria Paretov front – ich počet je N pf
ƒ
o
o
ƒ
ƒ
o
ostatné jedince – ich počet je N o
prioritné jedince sa nachádzajú a Paretovom fronte
ak N pf < µ
všetci jedinci z Paretovho frontu pôjdu do novej populácie
počet doplníme náhodne z ostatných jedincov
ak N pf > µ
ƒ
ƒ
predpokladajme, že máme k hodnotiacich kritérií (vhodností)
celkový počet voľných miest novej populácie rozdelíme na k + 1 častí nasledovne
•
každá časť môže byť obsadená
µ
k +ε
jedincami
ƒ
ƒ
ƒ
posledná časť bude zvyšok
•
všetkých jedincov z Paretovho frontu utriedime podľa prvej vhodnosti a do prvej časti vyberieme najlepších
všetkých jedincov z Paretovho frontu utriedime podľa druhej vhodnosti a do druhej časti vyberieme najlepších
atď.
ƒ
z populácie vyberáme vždy
ƒ
ƒ
µ
jedincov
k +ε
ostáva nám zaplniť ešte zvyšok
z množiny jedincov z Paretovho frontu odstránime všetkých vybraných jedincov
•
z ostávajúcich jedincov náhodne doplníme počet na potrebnú hranicu
•
žiadny jedinec sa nevyskytuje v novej populácii dvakrát, pretože všetci ležia na Paretovom fronte, ktorý takú
situáciu popiera
Nestacionárne úlohy
podstatou týchto úloh je, že máme iba jednu vhodnosť, avšak tá sa v čase mení
poloha hľadaného riešenia sa teda posúva
niekedy je možné tento problém odstrániť tak, že sa opakovane spustí evolučný algoritmus, ak nastal posun extrému
je však možná aj reprezentácia, že evolučný algoritmus stále beží v pozadí a ak je potrebné (pri zmene extrému) nastaví hodnoty na
odpovedajúce
typy zmien
o
pomalá zmena – postupný posun extrému v čase
o
skoková zmena – skok extrému na iné miesto v priestore
o
periodická zmena – zmeny sa vykonávajú v cykloch medzi dvomi alebo viacerými hodnotami
požiadavky na algoritmus
41
-
o
musí detekovať zmenu extrému
o
musí sa vedieť prestaviť a hľadať nové riešenie
metódy na riešenie nestacionárnych úloh
o
metódy proti predčasnej konvergencii
o
metódy založené na reprezentácii s pamäťou
ƒ
špeciálne metódy
ƒ
zavádzajú redundantnosť do algoritmu
ƒ
máme uchovaný aj redundantný genetický materiál, ktorý nám umožní konvergenciu populácie
Metódy proti predčasnej konvergencii
často sa používa infúzia genetického materiálu
shearing sa nedá použiť, pretože často nevieme povedať, či sú jedinci v extréme
Cobb
o
nechával populáciu skonvergovať
o
ak detekoval zmenu extrému, tak všetko nanovo reinicializoval a spustil algoritmus nanovo
o
dá sa použiť, avšak iba na pomalé zmeny, pretože nájdenie riešenia trvá určitý čas
o
vhodné pri skokových zmenách
o
nedokáže ošetriť prípad, ak sú jedinci skonvergovaní a v priestore vznikne nový extrém, ktorý sa stane globálnym
Grefenstette
o
genetický algoritmus beží stále a v každom jeho cykle sa určitá časť populácie reinicializuje
o
nemusí sa detekovať zmena extrému, pretože algoritmus bude stále konvergovať do extrému, aj keď sa jeho poloha zmení
o
veľkosť časti populácie, ktorú reinicializujeme je závislá od typu úlohy
ƒ
doporučuje sa do 30% populácie
Metódy založené na reprezentácii s pamäťou
multiploidné reprezentácie
o
inšpirované z biológie
ƒ
použitie viac chromozómov v jednom jedincovi
ƒ
človek má dva chromozómy
ƒ
salamandra má tri chromozómy
ƒ
zemiak má až štyri chromozómy
o
pod pamäťou sa potom rozumie, že ak dôjde k zmene extrému, zaúčinkuje iný chromozóm a jedinec teda bude môcť mať
dobrú vhodnosť a tým máme kandidáta na riešenie
o
dobré využitie v úlohách s periodickými zmenami
o
problém nastáva pri reprezentácii vo fenotype a je nutné definovať schémy na prepis z genotypu na fenotyp
ƒ
dominantné schémy
definuje sa dominancia
•
vo fenotype sa prejaví iba dominantná časť, ostatné časti sa neprejavia
•
ƒ
aditívne schémy
skombinovanie chromozómov do výsledného genotypu a jeho prepis na fenotyp
•
o
dominantné schémy
ƒ
Bagly
je nutné vyjadriť, čo v ktorom géne je dominantné
•
každý chromozóm je definovaný nasledovne
•
H – hodnota v prvom chromozóme
D – dominancia v prvom chromozóme
H, D
H’ – hodnota v druhom chromozóme
D‘ – dominancia v druhom chromozóme
H‘, D‘
ƒ
•
•
•
•
•
Holstein
•
•
•
ƒ
•
Brindle
ak D > D' tak vo výsledku sa prejaví H
ak D < D' tak vo výsledku sa prejaví H '
ak D = D' tak sa vykonáva porovnávanie na predchádzajúcom bite
výhoda je tá, že nemáme pevne danú dominanciu
nevýhoda je tá, že prehľadávaný priestor je zložitejší
pracoval s binárnymi reťazcami
povedal, že 1 bude dominantnejšia ako 0
0
1
0
0
1
1
1
1
o
nepríjemné však je to, že je veľký nepomer 1 a 0
použitie aj recesívnej 10
0
10
1
0
0
0
1
10
0
1
1
1
1
1
1
o
nepomer 0 a 1 stále existuje, avšak už nie je taký veľký
výhoda je, že zavedením pevného kódovania reprezentácia nie je zložitejšia ako u klasických jedincov
42
•
•
•
o
chromozómy v jedincovi rozdelil na významové a dominantné chromozómy
dominantný chromozóm nám povie, ktorý gén z ktorého jedinca prevládne
ak budeme používať kombináciu dvoch chromozómov na kódovanie jedinca, tak v dominantnom
chromozóme bude na géne
o
0 – ak bude dominantný gén z prvého chromozómu
o
1 – ak bude dominantný gén z druhého chromozómu
H0
významový chromozóm
H1
významový chromozóm
D
dominantný chromozóm
aditívne schémy
ƒ
cieľom bolo zlepšiť Holsteinovu reprezentáciu schémy
chcú, aby sa zbytočne nezväčšoval prehľadávací priestor
•
chcú odstrániť nepomer medzi 0 a 1
•
chcú dosiahnuť rovnaký počet 1 a 0
•
ƒ
hodnoty v chromozómoch sa priamo navonok neprejavujú, sú iba pomocné
ƒ
výslednú hodnotu dostaneme sčítaním hodnôt cez všetky chromozómy pre jednotlivé gény
•
výsledok bude od minimálnej hodnoty ┴ po maximálnu hodnotu ┬
•
tento výsledok sa nazýva intenzita prejavu
ƒ
schémy s jedným prahom
1
0
ƒ
┬
┴
ak je súčet menší ako prah, tak bude vo výsledku 0
•
ak bude súčet väčší alebo rovný ako prah, tak bude vo výsledku 1
•
schémy s dvomi prahmi
1
0
ƒ
AA
4
┬
┴
ak je súčet menší ako prvý prah, tak bude vo výsledku 0
•
ak je súčet väčší ako druhý prah, tak bude vo výsledku 1
•
ak je súčet medzi prahmi, tak vo výsledku bude náhodne vygenerovaná 0 alebo 1
•
genetická pamäť
predpokladajme hodnoty v chromozómoch A, B, C a D, pričom A sa počíta za 2, B za 3, C za 7 a D za 9
•
predpokladajme dva chromozómy
•
môžu nám vzniknúť kombinácie s týmito ohodnoteniami
•
AB
5
BB
6
•
•
•
•
AC
9
•
•
•
•
AD
11
BD
12
CC
14
CD
16
DD
18
môžeme postaviť prah T = 10,5
potom 5 kombinácií vedie na 0
potom 5 kombinácií vedie na 1
zoberieme dvoch jedincov s rovnakým génom AC
o
vo fenotype obaja majú 0
o
ich skrížením môžu vzniknúť jedinci s prejavom vo fenotype
AA
0
•
BC
10
AC
0
AC
0
CC
1
1
potomkoch
4
u jedincov AA, AB a BB neexistuje genetická pamäť – potomkovia sa prejavia vždy ako 0
u jedincov CC, CD a DD neexistuje genetická pamäť – potomkovia sa prejavia vždy ako 1
u jedincov AC, BC, AD a BD je genetická pamäť
genetická konvergencia
o
jedinec geneticky skonvergoval vtedy, ak nemá genetickú pamäť
o
je teda nutný boj proti genetickej konvergencii
ƒ
nútená mutácia
ak sa v jedincovi vyskytne kombinácia, ktorá nemá genetickú pamäť,
•
tak sa tento gén mutuje bližšie k prahu
existuje teda genetická pamäť, ktorá sa môže vyskytnúť až v
43
-
•
napríklad AA sa mutuje na AC
mutuje sa tak, aby prejav vo fenotype zostal nezmenený
•
keby sme použili iba hodnoty A, B a C s hodnotami 0, 1 a 2, dostali by sme schému s dvomi prahmi
•
(schému s pásmom neurčitosti)
redundantná haploidná reprezentácia
o
v jedincovi je len jeden chromozóm
o
výsledok je kódovaný v genotype na určitom celku génov
o
jednu vlastnosť teda reprezentuje viac génov
ƒ
napríklad
A C
o
o
o
každý gén môže nadobúdať viac hodnôt
krížením dvoch potomkov s génom AC môžeme dostať len potomka s génom AC
nútená permutácia
ƒ
zoberie hodnoty v rámci časti, ktorá je zodpovedná za jednu vlastnosť a náhodne ich premieša
Úlohy s ohraničeniami
úlohy, kde nie každý bod priestoru je riešením
z úlohy teda vyplývajú niektoré ohraničenia
o
prípustné riešenia sa označujú F (fisible)
o
neprípustné riešenia sa označujú U (unfisible)
je potrebné nájsť najlepší bod z priestoru riešení
v oblasti neprípustných riešení nemusíme vedieť vypočítať vhodnosť
typy ohraničení
o
tvrdé ohraničenia – ak sa prekročia, riešenia sú nevhodné
o
mäkké ohraničenia – ak sa prekročia, riešenia sú menej vhodné
ak bude plocha, kde sa vyskytujú prípustné riešenia, väčšia ako tá, kde sa vyskytujú neprípustné, potom je možné použiť aj klasický
genetický algoritmus, ktorý nám môže skonvergovať do riešenia v rámci ohraničení
metódy na riešenie úloh s ohraničeniami
o
penalizačné funkcie
o
dekodéry
o
opravné procedúry
o
špeciálne operátory
Dekódery
dekódery sa používajú na transformáciu medzi genotypovou a fenotypovou informáciou
princípom je tak dekódovať, tak aby každé riešenie bolo vo fenotype prijateľné
genotyp
fenotyp
Î
Í
F
U
genotyp
nevýhody
o
o
o
o
Î
Í
F
U
F
dekódovanie cez dekóder
neexistuje univerzálny dekóder
dekódovanie trvá určitý čas
nie vždy je možné dekóder navrhnúť
všetky body z genotypu sú dekódované na menšiu oblasť vo fenotype
ƒ
jednému bodu z genotypu prislúcha jeden bod vo fenotype
ƒ
jednému bodu vo fenotype môže prislúchať viac bodov z genotypu
Opravné procedúry
sú podobné ako dekódery
majme bod X z genotypu, ktorý nie je prípustný
X sa opraví na X ' , ktoré je prípustné a ktoré bude mať vhodnosť Φ( X ')
-
-
F
U
klasické dekódovanie
-
fenotyp
nerovnomernosť pokrytia, lebo na Φ( X ') môže byť mapovaných viac bodov
rozdelenie opravných procedúr
o
špecifická procedúra
ƒ
vytvorenie vlastnej procedúry na opravu kódu, alebo tvorbu jedincov
o
greedy prístup
ƒ
systematicky prehľadávame všetky zmeny súradníc vo všetkých smeroch, kým nenájdeme riešenie
o
náhodné menenie
ƒ
náhodná mutácia
dva spôsoby použitia opravných procedúr
o
nahradenie vhodnosti zlého bodu vhodnosťou dobrého
ƒ
mapovanie viacerých bodov na rovnakú vhodnosť
o
nahradenie genetického materiálu zlého bodu za dobrý
ƒ
pri týchto prístupoch nám populácia konverguje do určitej oblasti
Penalizačné funkcie
sú zvyčajne využívané, pretože predstavujú všeobecný prístup k úlohám s ohraničeniami
osobitne uvažujeme vhodnosť a osobitne penalizáciu
44
o
o
o
-
nech ai je i - ty jedinec z populácie
nech Φ (ai ) je jeho vhodnosť
nech P (ai ) je jeho penalizácia
typy penalizácií
o
binárna penalizácia
P (ai ) nadobúda buď hodnotu 0 alebo 1
ƒ
o
jedna hodnota hovorí, že jedinec spĺňa ohraničenia
•
druhá hodnota hovorí, že jedinec nespĺňa ohraničenia
•
ƒ
nie vždy je vhodné takúto penalizáciu zaviesť
numerická penalizácia
ƒ
predstavuje počet nesplnených ohraničení
ƒ
môže byť aj váhovaná
P (ai ) =
o
∑ w j Pj
j =1
o - počet ohraničení
w j - váha j - teho ohraničenia
Pj - je 1 ak je ohraničenie porušené, v opačnom prípade je 0
miera nesplnenia ohraničení
ƒ
uvažuje sa do akej miery je dané ohraničenie nesplnené
ƒ
nie vždy sa dá použiť
ƒ
dá sa použiť iba pri numerických ohraničeniach
ƒ
miery nesplnení jednotlivých ohraničení sčitujeme
ƒ
váhovanie už v tomto prípade nemá zmysel
algoritmus však nevie priamo pracovať s ohraničeniami, preto je nutné využiť niektoré postupy
o
multikriteriálne úlohy
ƒ
jedno kritérium je vhodnosť jedinca – snažíme sa maximalizovať
ƒ
druhé kritérium je jeho penalizácia – snažíme sa minimalizovať
o
spojenie vhodnosti a penalizácie dohromady
o
-
Φ ' (a i ) = Φ (a i ) + αP (a i )
ƒ
nastavenie parametra α
•
dá sa nastavovať experimentálne
jeden extrém
•
o
slabá penalizácia
o
snažiť sa nastaviť α tak, aby bolo minimálne, ale aby nám riešenie neskonvergovalo mimo
ohraničenia
druhý extrém
•
o
silná (smrtiaca) penalizácia
o
nastavenie α tak, aby každé neprípustné riešenie bolo horšie ako najhoršie z prípustných
riešení
o
väčšinou sa dá aplikovať
o
nevýhoda je v tom, že ak rozdiel medzi vhodnosťou neprípustného riešenia a nejakého
prípustného riešenia je veľká, môže dôjsť k predčasnej konvergencii
Špeciálne operátory
snaha o upravenie algoritmu tak, aby prehľadávanie priestoru nevyšlo z prípustných riešení
nutná inicializácia z prípustných riešení
o
nie vždy je to možné
aby mohol tento prístup fungovať, musí sa dať oblasť riešenia popísať maticovou nerovnicou
Ax ≤ d
o
teda
a11x1 + a12 x2 + L + a1n xn ≤ d1
a21x1 + a22 x2 + L + a2 n xn ≤ d 2
M
am1x1 + am 2 x2 + L + amn xn ≤ d m
-
o
to znamená, že oblasť ohraničení musí byť konvexná
ak je táto podmienka splnená a použijeme kríženie prostredné kríženie ( λr1 + (1 − λ )r2 ), tak potomok bude tiež z prípustnej oblasti
ak je táto podmienka splnená, môžeme nájsť hranice pre ohraničenie pre každú os a mutácia bude môcť prebehnúť iba v tejto obalsti
existujú úlohy, kde sa vyžaduje iba splnenie ohraničení a na vhodnosti jedinca nezáleží
No free lunch theorem
týka sa optimalizačných úloh
o
predpokladajme, že máme funkciu f : X → Y
45
-
o
hľadáme také x ∈ X , aby y ∈ Y bolo čo najlepšie
táto teoréma platí pre prehľadávacie algoritmy
majme priestor ktorý prehľadávame
každý bod z tohto priestoru potrebujeme vyhodnocovať
predpokladajme, že algoritmus vykonal m vyhodnotení
predpokladajme, že algoritmus nebude zabúdať body, ktoré už prehľadal
po m vyhodnoteniach môžeme zostaviť hystogram
početnosť
y
-
-
ak zafixujeme algoritmus (t. z. že náhodný generátor bude generovať tie isté náhodné čísla, všetky parametre budú stále rovnaké), tak
pravdepodobnosť vygenerovania konkrétneho hystogramu je závislá
o
od algoritmu, ktorý použijem - označme a
o
od počtu prehľadávaní - označme m
o
od problému, ktorý riešime - označme f
túto pravdepodobnosť si označme p(h | f , m, a )
z matematického hľadiska platí
∑ p(h | f , m, a1 ) = ∑ p(h | f , m, a2 )
f
f
f - problém ktorý riešime, teda plocha vhodnosti
-
chceme zistiť aká je pravdepodobnosť vygenerovania hystogramu v závislosti iba od a a m
o
ak
nevieme
vypočítať
pravdepodobnosť
javu p(x ) ,
ale
máme
kompletný
štatistický
súbor
n
javov e1, e2 ,L, en (platí ∑ p (ei ) = 1 ), tak platí nasledujúci vzťah
i =1
n
p(x ) = ∑ p(x | ei ). p(ei )
i =1
o
ƒ
závislá pravdepodobnosť
v našom prípade sú súborom všetky možné plochy vhodností f
p(h | m, a ) = ∑ p (h | f , m, a ). p( f | m, a )
f
o
plocha vhodnosti však nezávisí od m alebo a
p( f | m, a ) =
o
1
=k
n
teda vzorec môžeme prepísať
p(h | m, a ) = k ∑ p (h | f , m, a )
f
o
podľa lunch free theorem bude však ∑ p(h | f , m, a ) nezávislá na a
f
p(h | m ) = ∑ p(h | f , m, a )
f
o
z toho potom vyplýva
p (h | m, a ) = kp(h | m )
o
o
o
ak nevieme nič o úlohe, tak pravdepodobnosť nezávisí na konkrétnom algoritme
ak o funkcii vhodnosti nevieme nič povedať, tak vo všeobecnosti nevieme povedať, ktorý algoritmus je lepší a ktorý horší
teda medzi dvomi algoritmami môže byť
ƒ
symetrický vzťah
•
jeden je lepší na jednu polovičku úloh
druhý je lepší na druhú polovičku úloh
•
ƒ
nesymetrický vzťah
46
-
•
jeden je vhodnejší na väčšiu časť úloh
druhý je však oveľa vhodnejší ako prvý na menšiu časť úloh
•
o
to však znamená, že evolučné algoritmy musia byť na určitých problémoch horšie ako náhodné prehľadávanie
o
ak máme konkrétnu funkciu vhodnosti a chceme aby bol evolučný algoritmus lepší, tak o nej musíme vedieť niečo povedať
o
ak riešime úlohu cez funkciu vhodnosti o ktorej nič nevieme, tak evolučný algoritmus nemusí dobre riešiť úlohu
zabezpečenie zlepšenia evolučného algoritmu
o
ideálne je poznať funkciu vhodnosti
ƒ
to však nie je vždy možné
o
do algoritmu sa zabudovávajú doménové znalosti o úlohe
o
algoritmus je potom silnejší a výkonnejší
o
ak nevieme povedať ani o doméne nič, tak do algoritmu zabudujeme znalosti aspoň o danej triede úloh
Nastavenie riadiacich parametrov
zaoberá sa výberom mutácie, kríženia, pravdepodobností a pod.
ak máme problém P , ktorý chceme vyriešiť, tak musíme vykonať tieto základné kroky
o
reprezentácia jedinca
ƒ
zistiť čo je riešením úlohy
ƒ
zvoliť reprezentáciu riešenia, teda jedinca
ƒ
od reprezentácie závisí priestor prehľadávania – snažíme sa, aby bol čo najmenší
ƒ
priestor riešení by mal byť vyvážený
o
vhodnosť
ƒ
ako sa bude vypočítavať vhodnosť, teda výpočet vhodnosti v numerickom tvare
ƒ
od nej závisí plocha vhodnosti, kde požadujeme aby mala dobrý tvar
o
štruktúra
ƒ
zvoliť, ktoré bloky budú v evolučnom algoritme použité
ƒ
výber či bude použitá mutácia, kríženie a pod.
o
výber blokov
ƒ
zvolenie konkrétnych blokov
ƒ
teda zvolenie napríklad konkrétneho typu selekcie, alebo mutácie
o
nastavenie riadiacich parametrov
ƒ
vykonať nastavenie parametrov pre každý blok
spôsoby nastavovania riadiacich parametrov
o
použitie vyskúšaných hodnôt
ƒ
často sa volí pravdepodobnosť kríženie z intervalu 0,5;1
o
ƒ
pravdepodobnosť mutácie sa volí malá
ƒ
veľkosť populácie možno tiež takto nastaviť podľa často používaných veľkostí
použitie vzorcov
ƒ
použitie empirických vzorcov na nastavenie parametrov
ƒ
napríklad pravdepodobnosť mutácie
pm ≈
1
l
l - dĺžka jedinca
o
takto sa najčastejšie mutuje iba jeden bit v jedincovi
•
pokus – omyl
ƒ
nastavenie parametrov a spustenie algoritmu
ƒ
na základe toho ako algoritmus danú úlohu riešil zmením parametre
ƒ
pri tomto type je však nutná skúsenosť
ƒ
miery na zisťovanie ako algoritmus riešil danú úlohu
•
vhodnosť populácie
o
priemer vhodností všetkých jedincov v populácii
o
vhodnosť najlepších jedincov
o
vhodnosť najhorších jedincov
•
on – line vhodnosť
o
priemer vhodností všetkých jedincov, ktorý boli za behu algoritmu generovaný
•
off – line vhodnosť
o
priemerná vhodnosť iba najlepších jedincov zo všetkých generácií
•
progres
o
predpokladajme že chceme vhodnosť minimalizovať a minimálnu vhodnosť poznáme
p=
Φ0 − Φ
Φ 0 − Φ min
Φ 0 - vhodnosť v nultej generácii
Φ min - minimálna vhodnosť, ktorá môže vzniknúť
Φ - aktuálna vhodnosť jedinca
o
o
o
na začiatku je p = 0
pri nájdení riešenia je p = 1
metaevolúcia
ƒ
parametre budeme hľadať pomocou ďalšieho evolučného algoritmu
47
evolučný
algoritmus 2
evolučný
algoritmus 1
parametre
problém
o
ƒ
aby sme vedeli určiť vhodnosť v evolučnom algoritme 2, musíme poznať vhodnosť v evolučnom algoritme 1
dynamické parametre
ƒ
parametre evolučného algoritmu sa budú počas behu meniť
ƒ
priame nastavenie parametrov
pomocou vzorcov, ktoré si zadefinujeme
•
príklad
•
o
dynamická zmena veľkosti populácie
o
zavedieme si vek jedinca
o
založené na tom, že ak je jedinec dlhšie v populácii, tak sa môže viackrát reprodukovať
o
selekcia sa vypúšťa
o
náhrada
µ'= µ + λ − v
µ ' - počet jedincov v ďalšej generácii
µ - počet jedincov v aktuálnej generácii
λ - počet potomkov
v - počet jedincov, ktoré prekročili vek
o
o
o
vekom sa selekčný tlak reguluje a tým sa mení veľkosť populácie
ƒ
nadpriemerným jedincom sa dáva dlhší vek
ƒ
podpriemerným jedincom sa dáva kratší vek
je potrebné si stanoviť
ƒ
minimálny vek - Min
ƒ
maximálny vek - Max
keď vznikne jedinec bude mu priradený vek


Max − Min Φ(a )
vek = min Min +
, Max 


2
Φ


Φ (a ) - vhodnosť jedinca
Φ - priemerná vhodnosť populácie
ƒ
nepriame nastavenie parametrov
•
napríklad neuniformná mutácia
β

 t 

1− T 


∆ (t , y ) = y1 − r


o
o





ƒ
aj dynamické parametre možno nastaviť metaevolúciou
adaptívna zmena parametrov
ƒ
parametre môže nastavovať expertný systém
ƒ
musíme vygenerovať pravidlá pre zmeny parametrov
ƒ
napríklad
•
AK populácia konverguje, POTOM zvýš pravdepodobnosť mutácie
AK priemerná vhodnosť populácie sa nemení, POTOM zmenši pravdepodobnosť mutácie
•
samoadaptivita
ƒ
algoritmus si sám adaptuje aj parametre
ƒ
parametre, ktoré chceme nastaviť budú uložené v jedincovi
reprezentácia riešenia reprezentácia
parametrov
ƒ
ƒ
ƒ
zväčšíme však priestor prehľadávania
úlohou nebude len nájsť najlepšie riešenie, ale aj najlepšie parametre
napríklad normálna mutácia
p'i = pi + σ i N (0,1)
•
každé σ i je reprezentované v časti jedinca pre reprezentáciu parametrov
48
Problém obchodného cestujúceho
tento problém je vzor sekvenčných úloh
pri sekvenčných úlohách je nutné vyjadriť poradie
je daná množina miest ( n - počet miest)
snažíme sa nájsť takú cestu, aby sme prešli všetky mestá, pričom každé navštívime iba raz
o
typicky je to kruhová cesta, ale nemusí byť
snažíme sa optimalizovať danú cestu vzhľadom na jej dĺžku
o
vzdialenosť medzi mestami A a B nemusí byť rovnaká ako medzi B a A
riešením je poradie miest
je to úloha s ohraničeniami
o
nie každý jedinec je validný
o
validných riešení je oveľa menej ako nevalidných
snažíme sa pracovať iba s validnými jedincami
o
takto budeme pracovať iba na validnom priestore riešení
o
validný jedinec je ten, ktorý prejde všetky mestá, pritom každé iba raz
o
validných riešení je n!
-
o
počet všetkých riešení je n n
o
riešením je teda permutácia prvkov
vhodnosť
o
súčet váh ciest
o
snaha o minimalizáciu
reprezentácia
o
musíme reprezentovať permutácie
o
musíme voliť také genetické operátory, aby nám budovali iba validné riešenia
o
reprezentácia pomocou reálnych čísel
ƒ
genotyp je reprezentovaný n reálnymi číslami
ƒ
poradie miest je potom dané podľa pozície výskytu od najmenšieho po najväčšie reálne číslo v genetickom kóde
ƒ
príklad
•
genotyp jedinca je
[2,34
•
−1,09 1,91 0,87 −0,12 0,99 2,13 1,23 0,55]
poradie miest je
(2
5 9 4 6 8 3 7 1)
ƒ
ƒ
o
môžeme použiť ľubovoľný operátor na reálnej reprezentácii jedincov
ak by sa nám vyskytli dve rovnaké reálne čísla v genotype (málo pravdepodobné, vzhľadom na to, že reálnych čísel
je v nejakom intervale nekonečne veľa), tak z nich vyberieme náhodne jedno z nich
reprezentácia susednosti
ƒ
jedinec je reprezentovaný ako zoznam n miest, pričom mesto j sa nachádza na pozícii i vtedy, ak vedie cesta
z i do j
ƒ
príklad
majme cestu
•
(1
•
ƒ
4 8 3 9 7 1 5 6]
potom napríklad schéma [* * 5 * * *] reprezentuje, že obsahuje všetky cesty vedúce z 3 do 5
nevýhoda
•
vznik parciálnej cesty, t.j. takej, že sa vrátime skôr do východzieho mesta, ako prejdeme všetky mestá
príklad
•
[2
(1
ƒ
(1))
v genotype je reprezentovaná ako
[2
ƒ
ƒ
2 4 3 8 5 9 6 7
•
mutácia
•
•
kríženie
•
•
4 8 1 9 3 5 7 6]
2 4 1)
nie všetky permutácie sú riešenia
pri klasickej mutácii nemusí vzniknúť permutácia, a teda validný jedinec
ak zmeníme nejakú pozíciu, tak zmenu musíme doplniť aj na tej pozícii, ktorá obsahuje číslo na ktoré
som mutáciou zmutoval danú pozíciu
o
vykonávame len výmenu pozícií
klasické kríženie sa nedá použiť, lebo by nám nevznikali permutácie a teda ani validný jedinci
kríženie alternáciou hrán
o
striedavo vyberám prechody medzi mestami najskôr z prvého a potom z druhého jedinca až
do doby, keď zaradenie vybranej hrany by vytvorilo parciálnu cestu, alebo by bolo zaradené
číslo i na i - tu pozíciu
o
zostávajúce prechody prestávame vyberať z rodičov, ale náhodne ich dogenerujeme
o
príklad
49
ƒ
majme rodičov
[2
[7
ƒ
3 8 7 9 4 1 5 6]
5 1 6 9 2 8 4 3]
z nich vygenerujeme potomka
[2
(1
2 5 8 7 6 4 3 9
(1))
ƒ
posledné dve hodnoty sú generované náhodne tak, aby nevznikol parciálny jedinec
môžeme vygenerovať aj druhého jedinca, keď budeme začínať z druhého jedinca
o
o
5 9 3 8 4 6 7 1]
reprezentácia poradia
ƒ
cesta je reprezentovaná ako zoznam n miest, pričom pozícia nereprezentuje dané mesto (číslo mesta), ale bude
existovať referenčný zoznam miest a jedince budú obsahovať odkazy do tohto referenčného zoznamu
ƒ
príklad
predpokladajme referenčný zoznam
•
{9
•
8 7 6 5 4 3 2 1}
predpokladajme jedinca, ktorý reprezentuje cestu
(1
•
potom kódujeme podľa poradia v referenčnom zozname, pričom prvky zo zoznamu vymažeme
kódovaná cesta
()
(1)
(1 2)
(1 2 4)
(1 2 4 3)
(1 2 4 3 8)
(1 2 4 3 8 5)
(1 2 4 3 8 5 9)
(1 2 4 3 8 5 9 6)
(1 2 4 3 8 5 9 6 7 )
•
referenčný zoznam
kódovaný jedinec
{9 8 7 6 5 4 3 2 1} [ ]
{9 8 7 6 5 4 3 2}
[9]
{9 8 7 6 5 4 3}
[9 8]
{9 8 7 6 5 3}
[9 8 6]
{9 8 7 6 5}
[9 8 6 6]
{9 7 6 5}
[9 8 6 6 2]
{9 7 6}
[9 8 6 6 2 4]
{7 6}
[9 8 6 6 2 4 1]
{7}
[9 8 6 6 2 4 1 2]
{}
[9 8 6 6 2 4 1 2 1]
jedinec teda bude zakódovaný nasledovne
[9
ƒ
(1))
2 4 3 8 5 9 6 7
8 6 6 2 4 1 2 1]
na prvej pozícii môže byť číslo z intervalu 1; n , na druhej 1; n − 1 , atď., až na predposlednej 1;2 a na
poslednej 1;1
o
ƒ
ľubovoľný jedinec potom reprezentuje cestu
ƒ
je to klasický príklad na dekóder
ƒ
možno použiť bežne genetické operátory
ƒ
pri mutácii sa každá pozícia mutuje z iného rozsahu
reprezentácia cesty
ƒ
cesta je v genotype priamo vymenovaná
ƒ
pri manipulovaní s jedincom musíme vytvárať permutácie
ƒ
schéma jedinca je však menej hodnotná, lebo nám menej vyjadruje ako pri reprezentácii susednosti
ƒ
musíme použiť špeciálne operátory
ƒ
každá permutácia je prípustná (nemáme predčasné skončenia cesty)
ƒ
kríženie PMX
•
cieľom je zachovať čo najväčší počet pozícií miest z rodičov do potomkov
vygenerujú sa dva deliace body
•
do potomka jednu časť zoberieme z jedného rodiča a druhú z druhého
•
o
z druhého rodiča vyberieme len tie pozície, ktoré môžeme aby sme dostali validného jedinca
a pozície, ktoré nemôžeme zobrať doplníme na základe podobnosti rodičov
príklad
•
2
3
8
7
9
4
1
5
6
7
5
1
6
9
2
8
4
3
6
5
8
7
9
4
1
2
3
50
ƒ
ƒ
kríženie OX
podobné ako PMX
•
vygenerujú sa dva deliace body
•
•
prvá časť sa prenesie z prvého rodiča
z druhého rodiča sa vyškrtnú všetky použité mestá a doplní sa genetický materiál potomka v poradí
•
v akom zostali nevyškrtnuté mestá v druhom rodičovi
•
príklad
2
3
8
7
9
4
1
5
6
7
5
1
6
9
2
8
4
3
4
3
7
5
1
6
9
2
8
6
2
8
7
9
4
1
3
5
kríženie ER
rekombinácia hrán
•
snaží sa kombinovať hrany medzi sebou
•
vytvorí si tabuľku, kde sa zistia, ktoré hrany sú v rodičoch s ktorými uzlami spojené
•
potom z rodiča vyberieme prvý prvok a ostatné vyberáme z tabuľky
•
o
ak máme v tabuľke viac možností vybratia, vyberieme tú, ktorá má menej susedov
v zozname
o
ak by chýbal prechod, tak ho náhodne vygenerujeme
•
príklad
o
majme rodičov
o
2
3
8
7
9
4
1
5
6
7
5
1
6
9
2
8
4
3
z nich vygenerujeme tabuľku
R1
o
4 5 5 6 4 5 6
2:
6 3 9 8 3 6 8 9
3:
2 8 4 7 2 4 7 8
4:
9 1 8 3 1 3 8 9
5:
1 6 7 1 1 6 7
6:
5 2 1 9 1 2 5 9
7:
8 9 3 5 3 5 8 9
8:
3 7 2 4 2 3 4 7
9:
7 4 6 2 2 4 6 7
vyberieme mesto 2 z prvého rodiča a tabuľka sa nám zmení nasledovne
R1
o
R2
1:
R2
1:
4 5 5 6 4 5 6
2:
6 3 9 8 3 6 8 9
3:
2 8 4 7
4:
9 1 8 3 1 3 8 9
5:
1 6 7 1 1 6 7
6:
5 2 1 9 1
7:
8 9 3 5 3 5 8 9
8:
3 7 2 4
3 4 7
9:
7 4 6 2
4 6 7
4 7 8
5 9
keďže mestá 3, 6, 8 a 9 majú rovnaký počet hrán, vyberieme z nich náhodne mesto 6
51
R1
o
4 5 5 6 4 5
2:
6 3 9 8 3
3:
2 8 4 7
4:
9 1 8 3 1 3 8 9
5:
1 6 7 1 1
7
6:
5 2 1 9 1
5 9
7:
8 9 3 5 3 5 8 9
8:
3 7 2 4
3 4 7
9:
7 4 6 2
4
R2
4 5 5 6 4 5
2:
6 3 9 8 3
3:
2 8 4 7
4:
9 1 8 3 1 3 8
5:
1 6 7 1 1
7
6:
5 2 1 9 1
5
7:
8 9 3 5 3 5 8
8:
3 7 2 4
3 4 7
9:
7 4 6 2
4
8
4 7 8
7
keďže mestá 4 a 7 majú rovnaký počet hrán, vyberieme z nich náhodne mesto 4
R2
1:
4 5 5 6
2:
6 3 9 8 3
8
3:
2 8 4 7
7 8
4:
9 1 8 3 1 3 8
5:
1 6 7 1 1
7
6:
5 2 1 9 1
5
7:
8 9 3 5 3 5 8
8:
3 7 2 4
9:
7 4 6 2
5
3
7
7
keďže z miest 1, 3 a 8 má najmenej hrán mesto 1, vyberieme ho
R1
o
7
1:
R1
o
8 9
4 7 8
keďže mestá 1, 5 a 9 majú rovnaký počet hrán, vyberieme z nich náhodne mesto 9
R1
o
R2
1:
R2
1:
4 5 5 6
2:
6 3 9 8 3
5
3:
2 8 4 7
4:
9 1 8 3
3 8
5:
1 6 7 1
7
6:
5 2 1 9
5
7:
8 9 3 5 3 5 8
8:
3 7 2 4
9:
7 4 6 2
8
7 8
3
7
7
z mesta 1 je už len prechod na mesto 5, tak ho vyberieme
52
R1
4 5 5 6
2:
6 3 9 8 3
3:
2 8 4 7
4:
9 1 8 3
3 8
5:
1 6 7 1
7
6:
5 2 1 9
7:
8 9 3 5 3
8:
3 7 2 4
9:
7 4 6 2
8
7 8
8
3
7
7
z mesta 5 je už len prechod na mesto 7, tak ho vyberieme
o
R1
R2
1:
4 5 5 6
2:
6 3 9 8 3
3:
2 8 4 7
4:
9 1 8 3
5:
1 6 7 1
6:
5 2 1 9
7:
8 9 3 5 3
8:
3 7 2 4
9:
7 4 6 2
8
8
3 8
8
3
keďže mestá 3 a 8 majú rovnaký počet hrán, vyberieme z nich náhodne mesto 3
o
R1
R2
1:
4 5 5 6
2:
6 3 9 8
3:
2 8 4 7
4:
9 1 8 3
5:
1 6 7 1
6:
5 2 1 9
7:
8 9 3 5
8:
3 7 2 4
9:
7 4 6 2
8
8
8
8
z mesta 3 je už len prechod na mesto 8, tak ho vyberieme
o
R1
R2
1:
4 5 5 6
2:
6 3 9 8
3:
2 8 4 7
4:
9 1 8 3
5:
1 6 7 1
6:
5 2 1 9
7:
8 9 3 5
8:
3 7 2 4
9:
7 4 6 2
vygenerovali sme potomka
o
2
o
R2
1:
6
9
4
1
5
7
3
8
maticová reprezentácia
ƒ
budeme používať incidenčnú maticu s prvkami mij
•
ƒ
mij = 1 ak mesto i sa nachádza pred mestom j (nemusí sa nachádzať bezprostredne)
predpokladajme cestu
(2
ƒ
3 8 7 9 4 1 5 6)
potom matica bude vyzerať nasledovne
53
1 2 3 4 5 6 7 8 9
1 0 0 0 0 1 1 0 0 0
2 1 0 1 1 1 1 1 1 1
3 1 0 0 1 1 1 1 1 1
4 1 0 0 0 1 1 0 0 0
5 0 0 0 0 0 1 0 0 0
6 0 0 0 0 0 0 0 0 0
7 1 0 0 1 1 1 0 0 1
8 1 0 0 1 1 1 1 0 1
9 1 0 0 1 1 1 0 0 0
ƒ
vlastnosti incidenčnej matice
•
na diagonále sú nuly
m(m − 1)
počet jednotiek je
•
2
je tranzitívna, teda platí: mij = 1 ∧ m jk = 1 ⇒ mik = 1
•
•
definuje úplné usporiadanie
o
ƒ
kríženie
•
ak by bolo jednotiek menej ako
predpokladajme, že krížime rodičov
[2
[1
•
m(m − 1)
, tak by definovala parciálne usporiadanie
2
3 8 7 9 4 1 5 6]
2 3 4 5 6 7 8 9]
ich incidenčné matice sú nasledovné
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 0 0 0 0 1 1 0 0 0
1 0 1 1 1 1 1 1 1 1
2 1 0 1 1 1 1 1 1 1
2 0 0 1 1 1 1 1 1 1
3 1 0 0 1 1 1 1 1 1
3 0 0 0 1 1 1 1 1 1
4 1 0 0 0 1 1 0 0 0
4 0 0 0 0 1 1 1 1 1
5 0 0 0 0 0 1 0 0 0
5 0 0 0 0 0 1 1 1 1
6 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 1 1 1
7 1 0 0 1 1 1 0 0 1
7 0 0 0 0 0 0 0 1 1
8 1 0 0 1 1 1 1 0 1
8 0 0 0 0 0 0 0 0 1
9 1 0 0 1 1 1 0 0 0
9 0 0 0 0 0 0 0 0 0
•
vytvoríme prienik týchto matíc
1 2 3 4 5 6 7 8 9
1 0 0 0 0 1 1 0 0 0
2 0 0 1 1 1 1 1 1 1
3 0 0 0 1 1 1 1 1 1
4 0 0 0 0 1 1 0 0 0
5 0 0 0 0 0 1 0 0 0
6 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 1
8 0 0 0 0 0 0 0 0 1
9 0 0 0 0 0 0 0 0 0
mesto
1
2
3
4
5
6
7
8
9
•
predchádzajúce mesto
2
2, 3
1, 2, 3, 4
1, 2, 3, 4, 5
2, 3
2, 3
2, 3, 7, 8
ak máme len čiastočné usporiadanie, tak ho dogenerujeme na úplné a vznikne nám jedinec
54
[1
2 3 4 5 6 8 7 9]
alebo
[1
2 3 8 7 9 4 5 6]
Hybridizácia
spájanie evolučných algoritmov s inými algoritmami
použijeme spojenie evolučného algoritmu s lokálnym prehľadávaním
lokálne prehľadávanie
o
v okolí nejakého bodu nájdeme najlepšie riešenie
delenie hybridizácie
o
paralelná hybridizácia
o
sériová hybridizácia
sériová hybridizácia
o
vývojový diagram
Nájdené
riešenie?
áno
Koniec
nie
Evolučný
algoritmus
Lokálne
prehľadávanie
t=t+1
o
o
o
o
vždy používa iba jeden bod na rozdiel od evolučného algoritmu, ktorý používa populáciu bodov
môžeme na každý bod nasadiť lokálne prehľadávanie, alebo iba na niektoré, vybrané nejakou selekčnou metódou
ƒ
evolučný algoritmus môže vytvoriť populáciu rodičov, z nich vytvoriť potomkov a následne vykonať populačnú
náhradu, a tých jedincov ešte môžeme zlepšiť pomocou lokálneho prehľadávania
ƒ
evolučný algoritmus môže vytvoriť populáciu rodičov, z nich vytvoriť potomkov, tých môžeme zlepšiť pomocou
lokálneho prehľadávania a na takýchto jedincoch vykonať populačnú náhradu
tieto prístupy sú analógiou učenia sa počas života
majme plochu vhodnosti a predpokladajme, že sa snažíme nájsť jej minimum
ƒ
ƒ
ƒ
ƒ
o
o
plochu vhodnosti meníme práve pomocou lokálneho prehľadávania
červenou je znázornená plocha vhodnosti iba evolučného algoritmu
modrou je znázornená plocha vhodnosti aj s použitím lokálneho prehľadávania
zeleným je znázornená plocha vhodnosti, ak by sme lokálne prehľadávanie zastavili, až keď by dospelo k lokálnemu
minimu
pri použití lokálneho prehľadávania sa mení vhodnosť jedincovi
ƒ
ak s vhodnosťou meníme aj genetický materiál – Lamackova evolúcia
ƒ
ak iba meníme vhodnosť jedinca, nie genetický materiál – Baldwinova evolúcia (Baldwinov efekt)
predpokladajme jedinca, ktorý má 4 bity s binárnym kódovaním
55
1001
(10)
1101
(2)
1000
(12)
0000
(28)
1011
(6)
0010
(24)
0001
(26)
0011
(22)
0100
(20)
0110
(16)
1111
(30)
potom podľa schémy teorém
0***
*0**
**0*
***0
o
0111
(14)
1110
(0)
1010
(8)
ƒ
0101
(18)
1100
(4)
>
>
=
<
1***
*1**
**1*
***1
a teda algoritmus bude konvergovať k jedincovi 0001 alebo 0011
•
použime jeden krok Baldwinovej evolúcie
1001
(26)
1101
(30)
1000
(28)
0000
(28)
1011
(30)
0010
(28)
0001
(28)
0011
(26)
0100
(28)
0110
(24)
1111
(30)
podľa schémy teorém
0***
*0**
**0*
***0
o
0111
(30)
1110
(30)
1010
(24)
ƒ
0101
(26)
1100
(20)
=
=
<
<
1***
*1**
**1*
***1
a teda algoritmus bude konvergovať k jedincovi 0011 alebo 0111 alebo 1011 alebo 1111
•
použime jeden krok Lamackovej evolúcie
ƒ
bod v mriežke existuje, ak bod ostáva, lebo má maximálny fitness z okolia, alebo do neho prídem z iného bodu
0000
(28)
0001
(26)
0100
(20)
0010
(24)
ƒ
1111
(30)
podľa schémy teorém
0***
*0**
>
>
1***
*1**
56
**0*
***0
-
>
>
**1*
***1
•
a teda algoritmus bude konvergovať k jedincovi 0000
o
Lamarckova evolúcia zvyšuje selekčný tlak ale až tak, že môže vzniknúť predčasná konvergencia
paralelná hybridizácia
o
vývojový diagram
Nájdené
riešenie?
áno
Koniec
nie
Evolučný
algoritmus
wEA
Lokálne
prehľadávanie
wLS
t=t+1
o
o
o
o
o
o
v lokálnom prehľadávaní každého jedinca musím zlepšiť, aby som dostal rovnaký počet jedincov na výstupe evolučného
algoritmu aj lokálneho prehľadávania
ƒ
evolučný algoritmus bude mať na výstupe populáciu
ƒ
lokálne prehľadávanie bude mať na výstupe populáciu
v jednom kroku môže pracovať iba jeden algoritmus
to, ktorý bude v danom kroku pracovať budeme rozhodovať na základe váh wEA a wLS
ƒ
ƒ
ten, ktorý bude mať väčšiu váhu, ten v aktuálnom kroku pobeží
wEA - váha evolučného algoritmu
ƒ
wLS - váha lokálneho prehľadávania
na začiatku sa obe váhy postavia náhodné
váha sa bude meniť od vhodnosti nájdených riešení
ƒ
odmenou ( R ) môže byť nakoľko sa zmenila priemerná vhodnosť populácie
váhu v kroku t + 1 vypočítame
w(t + 1) = (1 − c )w(t ) + cR
c - konštanta
R - odmena
o
cez c vážime, aký bol daný algoritmus dobrý v predchádzajúcich krokoch a v kroku aktuálnom
ƒ
ak by bolo c = 1 , tak by algoritmus reagoval iba na posledný krok
ƒ
ak by bolo c = 0 , tak by stále bežal iba ten algoritmus, ktorý by mal na začiatku priradenú vyššiu náhodnú váhu
57
Download

Evolučné algoritmy