Geneticke´ algoritmy Jirˇ´ı Vomlel Laboratorˇ inteligentnı´ch syste´mu˚ Vysoka´ sˇkola ekonomicka´ Praha Tato prezentace je k dispozici na: http://www.utia.cas.cz/vomlel/
Motivace z Darwinovy teorie evoluce Prˇ´ırodnı´ evoluce je u´speˇsˇna´ a robustnı´ metoda adaptace v biologicky´ch syste´mech. • deˇti deˇdı´ vlastnosti rodicˇu˚ • lepsˇ´ı jedinci le´pe prˇezˇ´ıvajı´ a majı´ tudı´zˇ vı´ce potomku˚ Evoluce v prˇ´ırodeˇ vyzˇaduje cˇas - ovsˇem pomocı´ pocˇı´tacˇu˚ mu˚zˇeme vytvorˇit a ohodnotit tisı´ce umeˇly´ch individuı´ beˇhem zlomku vterˇiny.
2
Korespondence s Darwinovou teoriı´ evoluce v prˇ´ırodeˇ
v geneticky´ch algoritmech
jedinec
rˇeteˇzec symbolu˚, naprˇ. h = (1001)
prˇ´ırodnı´ vy´beˇr
vy´beˇr podle hodnotı´cı´ funkce f (h)
krˇ´ızˇenı´
kombinace dvou rˇeteˇzcu˚ naprˇ. (000 | 1) + (101 | 0) → (0000) + (1011)
mutace
na´hodna´ za´meˇna 0 a 1 v rˇeteˇzci naprˇ. (0010) → (1010)
3
Prˇ´ıklad prˇevzaty´ z http://cs.felk.cvut.cz/~xobitko/ga/
Je da´na funkce f : X 7→ R a cı´lem geneticke´ho algoritmu je najı´t x ∈ X v neˇmzˇ funkce naby´va´ globa´lnı´ho minima.
4
pocˇa´tecˇnı´ generace
5
elita´rˇstvı´ - nejlepsˇ´ı jedinci prˇecha´zejı´ prˇ´ımo do nove´ generace
6
dva jedinci jsou vybra´ni pro krˇ´ızˇenı´
7
vznikli novı´ potomci, kterˇ´ı jsou prˇesny´mi klony rodicˇu˚
8
docha´zı´ k mutaci geneticke´ informace potomku˚
9
potomci jsou prˇida´ni do nove´ populace
10
opeˇt dva jedinci jsou vybra´ni pro krˇ´ızˇenı´
11
docha´zı´ ke krˇ´ızˇenı´
12
docha´zı´ k mutaci
13
potomci jsou opeˇt prˇida´ni do nove´ populace
14
a po cˇase je uvedeny´m postupem vytvorˇena nova´ generace
15
nova´ generace nahrazuje starou
16
po neˇkolika dalsˇ´ıch generacı´ch
17
za´veˇrecˇna´ generace
18
Geneticky´ algoritmus - pojmy h
jedinec (hypote´za)
f
hodnotı´cı´ funkce (angl. fitness) jedincu˚ - f (h) obvykle uda´va´ kvalitu jedince h , t.j. chceme f maximalizovat.
t
prahova´ maxima´lnı´ hodnota pro hodnotı´cı´ funkci
p
velikost populace
Pc
pravdeˇpodobnost krˇ´ızˇenı´
Pm
pravdeˇpodobnost mutace
19
Geneticky´ algoritmus • Inicialize: H je na´hodna´ pocˇa´tecˇnı´ populace • Ohodnocenı´: pro kazˇde´ h ∈ H, spocˇti f (h) • Pokud maxh f (h) < t opakuj – Pravdeˇpodobnostnı´ vy´beˇr (1 − Pc ) · p jedincu˚ z H do H 0 . – Krˇ´ızˇenı´: p Pravdeˇpodobnostnı´ vy´beˇr Pc · 2 dvojic jedincu˚ z H. Pro kazˇdou dvojici vytvorˇ dva potomky krˇ´ızˇenı´m. Prˇidej potomky do H 0 . – Mutace: Invertuj na´hodneˇ vybrane´ bity u jedincu˚ z H 0 s pravdeˇpodobnostı´ Pm . – Aktualizace: H ← H 0 – Ohodnocenı´: pro kazˇde´ h ∈ H, spocˇti f (h) • Navrat’ jedince h ∈ H naby´vajı´cı´ho nejvysˇsˇ´ı hodnoty f (h) 20
Metody na´hodne´ho vy´beˇru • Proporciona´lneˇ k hodnotı´cı´ funkci, t.j. P(hi ) =
f (hi ) . p ∑ j=1 f (h j )
Existuje nebezpecˇı´ sekupenı´ vsˇech jedincu˚ blı´zko sebe. • Pomocı´ turnaje. – Vyber na´hodneˇ dva jedince h1 , h2 . Kazˇdy´ jedinec ma´ stejnou pravdeˇpodobnost vy´beˇru. – S pravdeˇpodobnostı´ Pt vyber jedince s vysˇsˇ´ı hodnotou f , jinak vyber jedince s nizˇsˇ´ı hodnotou f . • Podle porˇadı´. – Serˇad’ jedince podle jejich hodnotı´cı´ funkce (sestupneˇ). – Pravdeˇpodobnost vy´beˇru jedince je inverzneˇ proporciona´lnı´ vzhledem k jeho porˇadı´.
21
Reprezentace jedincu˚ Volba vhodne´ reprezentace: ˇ eteˇzec by meˇl neˇjaky´m zpu˚sobem odra´zˇet vlastnosti objektu, • R ktery´ reprezentuje. • Je zˇa´doucı´, aby vsˇichni jedinci reprezentovali prˇ´ıpustna´ rˇesˇenı´ proble´mu, nebot’ vyrˇazova´nı´ neprˇ´ıpustny´ch rˇesˇenı´ mu˚zˇe vy´razneˇ zpomalit algoritmus. Jedinec mu˚zˇe by´t naprˇ´ıklad reprezentova´n • rˇeteˇzcem nul a jednicˇek - bina´rnı´ reprezentace nebo • rˇeteˇzcem cˇı´sel - cˇı´selna´ reprezentace nebo • rˇeteˇzcem pı´smen abecedy - znakova´ reprezentace • stromem neˇjaky´ch objektu˚ (naprˇ. funkcı´ nebo prˇ´ıkazu˚ programovacı´ho jazyka) - geneticke´ programova´nı´ 22
Bina´rnı´ reprezentace (+) snadna´ implementace geneticky´ch opera´toru˚ (−) pro mnoho proble´mu˚ nenı´ vsˇak prˇirozena´ Prˇ´ıklady Hleda´nı´ minima funkce: f : N 7→ R, kde N je mnozˇina cely´ch cˇı´sel od 0 do 255. Pro cela´ cˇı´sla pouzˇijeme bina´rnı´ rˇeteˇzce de´lky 8. Naprˇ. 23 = (00010111) Proble´m batohu (Knapsack problem): • V mı´stnosti jsou veˇci ru˚zne´ velikosti a ru˚zne´ ceny. • Zlodeˇj chce do batohu urcˇite´ omezene´ kapacity zabalit veˇci tak, aby maximalizoval celkovou hodnotu veˇcı´ v batohu. Kazˇdy´ bit v reprezentaci rˇ´ıka´, zda-li odpovı´dajı´cı´ veˇc je nebo nenı´ v batohu. 23
Zpu˚soby krˇ´ızˇenı´ Initial strings
Crossover Mask
Offspring
Single-point crossover: 11101001000
11111000000
00001010101
11101010101 00001001000
Two-point crossover: 11101001000
00111110000
00001010101
11001011000 00101000101
Uniform crossover: 11101001000
Point mutation:
10011010011
10001000100
00001010101
01101011001
11101001000
11101011000
24
Proble´m obchodnı´ho cestujı´cı´ho (TSP) • Obchodnı´ cestujı´cı´ dostane seznam meˇst, ktera´ ma´ navsˇtı´vit. • Jsou mu zna´my vzda´lenosti mezi jednotlivy´mi meˇsty. Obchodnı´ cestujı´cı´ ma´ navsˇtı´vit vsˇechna meˇsta (pra´veˇ jednou) a vra´tit se do vy´chozı´ho bodu. • Cı´lem je minimalizovat celkovu vzda´lenost, kterou urazı´.
25
TSP - ko´dova´nı´ a krˇ´ızˇenı´ Ko´dova´nı´ • Kazˇde´mu meˇstu je prˇirˇazeno cele´ cˇı´slo. • Meˇsta se v rˇeteˇzci vyskytujı´ v porˇadı´ jake´m jsou navsˇtı´vena. • Naprˇ. (9340125768) Hladove´ krˇ´ızˇenı´ (angl. Greedy crossover) • Vyber prvnı´ meˇsto jednoho rodicˇe. • Porovnej druha´ meˇsta u obou rodicˇu˚ a vyber to, ktere´ je blı´zˇe k prvnı´mu vybrane´mu. • Jestlizˇe meˇsto je jizˇ v rˇeteˇzci, vyber meˇsto od druhe´ho rodicˇe. • Jestlizˇe i toto meˇsto je jizˇ v rˇeteˇzci vyber na´hodneˇ neˇjake´ meˇsto, ktere´ v rˇeteˇzci jesˇteˇ nenı´. • Obdobneˇ pokracˇuj pro trˇetı´, cˇtvrte´, ... meˇsto. 26
TSP - mutace Hladove´ prˇehozenı´ (angl. Greedy swap) • Vyber na´hodneˇ dveˇ meˇsta a prohod’ je v rˇeteˇzci. • Pokud je noveˇ vytvorˇena´ cesta kratsˇ´ı, prˇijmi mutaci, jinak zachovej pu˚vodnı´ cestu. • Naprˇ. (0123456) → (0321456). Mutace 2opt
Demo: TSPApp.exe 200 meˇst v kruhu - porovna´nı´ p = 10 a p = 100, heuristics (2opt mutace) 0 a 5. 27
Cvicˇenı´ - proble´m osmi dam na sˇachovnici Prˇ´ıklad rˇesˇenı´:
´ kolem je umı´stit osm dam na sˇachovU nici 8 × 8, tak aby zˇa´dna´ da´ma neohrozˇovala zˇa´dnou jinou. Cvicˇenı´: Navrhneˇte geneticky´ algoritmus pro rˇesˇenı´ proble´mu osmi dam. To znamena´ navrhnout: • vhodnou reprezentaci rˇesˇenı´ proble´mu pomocı´ rˇeteˇzce, • hodnotı´cı´ funkci, • opera´tor krˇ´ızˇenı´, a • opera´tor mutace. 28
Geneticke´ programova´nı´ - prˇ´ıklad Aproximujı´cı´ funkce Cı´lem je nalezenı´ funkce, ktera´ by nejle´pe aproximovala dane´ trojice hodnot (x1 , y1 , z1 ), (x2 , y2 , z2 ), . . . , (xn , yn , zn ). T.j. pro dana´ prvnı´ dveˇ cˇı´sla z trojice xi , yi by vra´tila vy´stup zi0 co nejblı´zˇe trˇetı´mu cˇı´slu trojice zi . p Jedinci jsou funkce ve stromu. Naprˇ. funkce sin(x) + x2 + y + sin +
x
y
^ x
29
2
Geneticke´ programova´nı´ - prˇ´ıklad krˇ´ızˇenı´ +
+
^
sin
sin
2
x
+
+
x ^
y
x
y
2
x
+
+
^
sin
x
sin
2
^ x
+
x 2
+
x
30
y
y
Sche´mata Sche´ma = rˇeteˇzec obsahujı´cı´ 0, 1, * (“cokoliv”) • Prˇ´ıklad sche´matu: 10∗∗0∗ • Jedinci odpovı´dajı´cı´ vy´sˇe uvedene´mu sche´matu: 100000, 100001, 100100, 100101, 101000, 101001, 101100, 101101. Charakteristika populace: p
...
pocˇet jedincu˚ v populaci
mt (s)
...
pocˇet jedincu˚ odpovı´dajı´cı´ch sche´matu s v cˇase t
f (h) f¯t
...
hodnota (fitness) jedince (hypote´zy) h
...
pru˚meˇrna´ hodnota populace v cˇase t
Ht (s)
...
mnozˇina jedincu˚ odpovı´dajı´cı´ch sche´matu s v cˇase t 31
Veˇta o sche´matech (pro vy´beˇr) f¯t (s)
... =
pru˚meˇrna´ hodnota jedincu˚ z mnozˇiny Ht (s) 1 m t (s)
· ∑h∈Ht (s) f (h)
E[mt+1 (s)]
...
ocˇeka´vany´ pocˇet jedincu˚ sche´matu s v cˇase t + 1
P(h)
...
pravdeˇpodobnost vy´beˇru jedince h df
P(h)
=
P(h ∈ Ht+1 (s))
=
odpovı´dajı´cı´ch
f (h) = p ∑i=1 f (hi )
∑
h0 ∈H
t (s)
f (h) p · f¯t f (h0 ) f¯t (s) · mt (s) = ¯ p · ft p · f¯t
E[mt+1 (s)] = p · P(h ∈ Ht+1 (s)) =
32
f¯t (s) · mt (s) ¯ ft
Veˇta o sche´matech (jednobodove´ krˇ´ızˇenı´ a mutace) Pc
...
pravdeˇpodobnost aplikace opera´toru krˇ´ızˇenı´
`
...
de´lka rˇeteˇzce, ktery´ reprezentuje jedince
d(s)
...
vzda´lenost mezi definovany´mi prvky sche´matu s nejvı´ce vlevo a nejvı´ce vpravo. Naprˇ. u s = (∗ ∗ ∗0 ∗ 1 ∗ 110 ∗ ∗) je vzda´lenost |9 − 3| = 6.
o(s) 1 − Pc ·
d(s) `
(1 − Pm )o(s)
...
pocˇet definovany´ch prvku˚ ve sche´matu s
...
dolnı´ odhad pravdeˇpodobnosti, zˇe krˇ´ızˇenı´ nenarusˇ´ı sche´ma
...
pravdeˇpodobnost, zˇe mutace nenarusˇ´ı sche´ma
E[mt+1 (s)] ≥
¯ f t (s) d(s) o(s) · m (s) · 1 − P · · (1 − P ) t c m ¯ ` ft 33
Vlastnosti geneticky´ch algoritmu˚ (+) Dajı´ se pouzˇ´ıt pro rˇesˇenı´ proble´mu˚ jinak teˇzˇko rˇesˇitelny´ch (naprˇ´ıklad, kdyzˇ interakce mezi jednotlivy´mi cˇa´stmi jsou teˇzˇko popsatelne´). (+) Veˇtsˇinou neuva´znou v loka´lnı´m maximu. (+) Vzˇdy poskytnou neˇjake´ rˇesˇenı´. (+) Jsou snadno implementovatelne´ a paralerizovatelne´. (−) Nema´me zˇa´dnou za´ruku, zˇe nalezene´ rˇesˇenı´ je optima´lnı´. (−) Neˇkdy mohou by´t velmi pomale´ (obzva´sˇt’ pokud nejsou dobrˇe navrzˇeny reprezentace jedincu˚ a opera´tory krˇ´ızˇenı´ a mutace). (−) Vyzˇadujı´ vhodne´ nastavenı´ veˇtsˇ´ıho mnozˇstvı´ parametru˚ algoritmu (naprˇ. PC , PM , p). 34
Strucˇna´ historie geneticky´ch algoritmu˚ • 1960: Ingo Rechenberg prˇedstavuje mysˇlenku evolucˇnı´ch vy´pocˇtu˚ ve sve´ pra´ci ”Evolution strategies” • 1975: John Holland poprve´ popisuje geneticky´ algoritmus a vyda´va´ svoji knihu ”Adaptation in Natural and Artificial Systems” • 1992: John Koza pouzˇil geneticky´ algoritmus pro vy´voj programu˚, ktere´ majı´ plnit urcˇite´ zadane´ u´lohy. Svoji metodu nazval geneticke´ programova´nı´.
35
Prˇ´ıklady aplikacı´ geneticky´ch algoritmu˚ dle encyklopedie wordIQ.com • Optimalizace na´kla´da´nı´ kontejneru˚. • Ucˇenı´ chova´nı´ robotu˚. • Optimalizace infrastruktury pro mobilnı´ komunikaci. • Optimalizace struktury molekul. • Na´vrh usporˇa´da´nı´ vy´robnı´ch hal. • Ru˚zne´ pla´novacı´ proble´my (naprˇ. kdyzˇ jednotlive´ u´lohy jsou navza´jem za´visle´). • Predikce akciovy´ch trhu˚.
36
