OBSAH 1
Pøedmluva
19
2
Evoluèní algoritmy: nástin
25
2.1
Centrální dogma evoluèních výpoèetních technik .............. 26
2.2
Chcete vìdìt víc? .................................................................... 29
3
Historická fakta trochu jinak
3.1
Pár zajímavých faktù ............................................................... 32
3.2
Chcete vìdìt víc? .................................................................... 34
4
Úvod do problematiky optimalizaèních algoritmù
31
35
4.1
Optimalizaèní a heuristické algoritmy ................................... 36
4.2
Souèasný stav ......................................................................... 37
4.2.1
Nástin principù èinnosti vybraných algoritmù ............................................ 41
4.3
No Free Lunch Teorém ........................................................... 44
4.4
Perspektivy a alternativy ........................................................ 45
4.5
Chcete vìdìt víc? .................................................................... 46
5
Ve nelze spoèítat
5.1
Prohledávaný prostor a jeho sloitost .................................. 48
5.2
Fyzikální limity výpoèetních technologií .............................. 54
5.3
Chcete vìdìt víc? .................................................................... 58
6
Optimalizace a úèelová funkce
6.1
Vybrané pojmy z optimalizace ............................................... 60
A
Obsah, pøedmluva a seznam symbolù
47
59
3
6.2
Úèelová funkce ........................................................................ 63
6.3
Geometrie úèelové funkce ..................................................... 63
6.4
Tvorba úèelové funkce ........................................................... 66
6.5
Chcete vìdìt víc? .................................................................... 68
7
Víceúèelová optimalizace a Paretova mnoina
7.1
Paretova mnoina ................................................................... 70
7.2
Ukázkové pøíklady ................................................................... 76
7.3
Nastavitelné víceúèelové optimalizaèní problémy ............... 84
7.4
Chcete vìdìt víc? .................................................................... 88
8
Vybrané základní pojmy z evoluèních algoritmù
89
8.1
Oblasti pouitelnosti evoluèních algoritmù .......................... 90
8.2
Spoleèné rysy .......................................................................... 92
8.3
Populace .................................................................................. 92
8.4
Jedinci, jejich struktura a reprezentace ................................ 96
8.5
Grayùv kód .............................................................................. 96
8.6
Chcete vìdìt víc? .................................................................... 99
9
Omezení a oetøení krizových stavù
9.1
Formulace problému ............................................................. 102
9.2
Omezení kladená na argumenty úèelové funkce ............... 103
9.3
Penalizace funkcí .................................................................. 104
9.4
Práce s celoèíselnými a diskrétními hodnotami ................ 105
9.5
Chcete vìdìt víc? .................................................................. 108
10
Evoluce a sloitost
10.1
10.1.1
4
69
101
109
Èasová sloitost algoritmù .................................................. 110
Aritmetika èasových sloitostí ................................................................. 112
Zelinka, Oplatková, eda, Omera, Vèelaø: Evoluèní výpoèetní techniky
A
10.2
10.2.1 10.2.2 10.2.3
10.3
10.3.1 10.3.2 10.3.3
10.4
Datové struktury a sloitost algoritmù ................................ 115
Prüferovo èíslo ........................................................................................ 115 Binární halda ........................................................................................... 117 Voroného diagram a Delaunayho triangulace ......................................... 126
Exaktní metody ...................................................................... 130
Dynamické programování ....................................................................... 131 Metoda vìtví a mezí ................................................................................ 137 Backtracking (prohledávání s návratem) ................................................. 140
P a NP tøídy problémù ........................................................... 142
10.4.1
Pøíklady NP-úplných problémù ................................................................ 145
10.5
Aproximativní a heuristické metody ................................... 149
10.6
Pøíklady aproximativních algoritmù .................................... 150
10.7
Chcete vìdìt víc? .................................................................. 156
11
Vybrané optimalizaèní a evoluèní techniky 157
11.1
Prohledávání do íøky (breadthfirst search) ..................... 158
11.2
Prohledávání do hloubky (depth-first search) .................... 159
11.3
Best-first search .................................................................... 159
11.4
Greedy algoritmus ................................................................ 159
11.5
Metoda lokálního hledání ..................................................... 160
11.6
Slepý algoritmus ................................................................... 162
11.7
Horolezecký algoritmus ........................................................ 163
11.8
Simulované íhání ................................................................. 166
11.8.1
Verze simulovaného íhání ..................................................................... 170
11.9
Tabu Search ........................................................................... 171
11.10
11.10.1 11.10.2 11.10.3 11.10.4 11.10.5 11.10.6 11.10.7 11.10.8 11.10.9 11.10.10 11.10.11
A
Genetické algoritmy .............................................................. 173
Terminologie GA ...................................................................................... 173 Vhodnost ................................................................................................. 174 Výbìr rodièù ............................................................................................ 175 Poøadová selekce (Rank selection) ......................................................... 175 Elitismus .................................................................................................. 176 Reprodukce ............................................................................................. 176 Køíení ..................................................................................................... 176 Mutace .................................................................................................... 177 Parametry køíení a mutace .................................................................... 178 Kódování ................................................................................................. 178 Schémata ................................................................................................ 179
Obsah, pøedmluva a seznam symbolù
5
11.10.12 Verze genetických algoritmù ................................................................... 180 11.10.12.1 Hybridní genetický algoritmus ......................................................................................... 180 11.10.12.2 Messy genetický algoritmus ............................................................................................ 181
11.11
Farmáøský model .................................................................................... 183 Migraèní model ........................................................................................ 183 Difusní model .......................................................................................... 185 Pøíklady pouití PGA ............................................................................... 186
11.11.4.1 11.11.4.2 11.11.4.3 11.11.4.4
Vliv poètu migrantù v kadé epoe ................................................................................. 186 Vliv rùzného poètu generací mezi jednotlivými migracemi ............................................. 187 Vliv strategie výbìru migrantù ......................................................................................... 187 Vliv poètu podpopulací .................................................................................................... 187
11.11.5
Souhrnné shrnutí vlastností PGA ............................................................ 187
11.11.5.1 11.11.5.2 11.11.5.3 11.11.5.4 11.11.5.5 11.11.5.6
Adaptace sloitých systémù ............................................................................................ 188 Biologické koøeny evoluèních algoritmù. ......................................................................... 189 Samoorganizace a adaptace sloitých systémù ............................................................. 195 Varianty genetických algoritmù ....................................................................................... 198 Paralelní evoluce s hierarchickým uspoøádáním ............................................................ 199 Nárùst uspoøádanosti systémù ....................................................................................... 201
11.12
11.12.1 11.12.2 11.12.3 11.12.4
11.13
Evoluèní strategie ................................................................. 203
Dvouèlenné ES: (1 + 1) ES ................................................................... 203 Víceèlenné ES: (µ + l) ES a (µ, l) ES ................................................ 204 Rekombinaèní ES: (µ/r + l) ES ............................................................. 205 Adaptivní ES ........................................................................................... 206
Rojení èástic (Particle swarm) ............................................. 208
11.13.1 11.13.2 11.13.3 11.13.4
Princip ..................................................................................................... 208 Algoritmus ............................................................................................... 210 Nastavitelné parametry PSO ................................................................... 211 Dalí verze PSO algoritmu ...................................................................... 212
11.14
Rozptýlené hledání (Scatter Search) ................................... 214
11.15
Optimalizace mravenèí kolonií (Ant Colony Optimization) 215
11.16
11.16.1 11.16.2 11.16.3
11.17
11.17.1 11.17.2 11.17.3 11.17.4 11.17.5 11.17.6
6
Paralelní genetické algoritmy .............................................. 182
11.11.1 11.11.2 11.11.3 11.11.4
Umìlý imunitní systém (Artificial Imunne System) ............ 218
Rozpoznávání vzorcù .............................................................................. 218 Hypermutace ........................................................................................... 218 Negativní výbìr ....................................................................................... 219
SOMA: SamoOrganizující se Migraèní Algoritmus ............ 220
Parametry a terminologie ........................................................................ 221 Populace ................................................................................................. 223 Mutace .................................................................................................... 223 Køíení ..................................................................................................... 224 Princip algoritmu SOMA .......................................................................... 225 Strategie SOMA algoritmu ....................................................................... 230
Zelinka, Oplatková, eda, Omera, Vèelaø: Evoluèní výpoèetní techniky
A
11.17.7 11.17.8 11.17.9
Závislost SOMA na øídicích a ukonèovacích parametrech ...................... 232 Zaøazení algoritmu SOMA ....................................................................... 233 SOMA a jiné optimalizaèní algoritmy ....................................................... 233
11.18
Diferenciální evoluce ............................................................ 235
11.18.1 11.18.2 11.18.3 11.18.4 11.18.5 11.18.6 11.18.7 11.18.8 11.18.9
Historie .................................................................................................... 235 Parametry a terminologie ........................................................................ 236 Populace ................................................................................................. 237 Mutace .................................................................................................... 237 Køíení ..................................................................................................... 238 Princip èinnosti diferenciální evoluce ...................................................... 238 Varianty diferenciální evoluce .................................................................. 242 Závislost diferenciální evoluce na øídicích parametrech .......................... 243 Stagnace ................................................................................................. 244
11.19
Chcete vìdìt víc? .................................................................. 245
12
EVT a evoluce symbolických struktur
12.1
Základní pojmy ...................................................................... 248
12.2
247
Evoluèní hardware ................................................................ 250
12.2.1 12.2.2 12.2.3 12.2.4 12.2.5 12.2.6
Thompsonùv experiment ......................................................................... 250 Evoluce v extrémním prostøedí ................................................................ 251 Adaptivní hardware ................................................................................. 252 Akcelerátory evoluèního návrhu v FPGA ................................................ 252 Evoluce kvantových chování ................................................................... 252 Evoluce antény v rámci Space Technology 5 Project (ST5), NASA ........ 253
12.3
Genetické programování ...................................................... 254
12.4
Gramatická evoluce .............................................................. 257
12.5
12.5.1 12.5.2 12.5.3 12.5.4 12.5.5 12.5.6 12.5.7 12.5.8 12.5.9 12.5.10 12.5.11 12.5.12
A
Paralelní gramatická evoluce ............................................... 261
Pouitá gramatika ................................................................................... 261 Implementace funkce s aritou n .............................................................. 263 Generování závorek ve funkcích ............................................................. 263 Paralelní gramatická evoluce .................................................................. 263 Gramatická evoluce ................................................................................ 263 Zpracování gramatiky .............................................................................. 264 Pøekládání genotypu na fenotyp .............................................................. 266 Køíení ..................................................................................................... 266 Mutace .................................................................................................... 267 Populaèní model ..................................................................................... 267 Samièí populace ...................................................................................... 267 Samèí populace ...................................................................................... 267
Obsah, pøedmluva a seznam symbolù
7
12.5.13 12.5.14
12.6
Analytické programování ..................................................... 271
12.6.1 12.6.2 12.6.3 12.6.4 12.6.5 12.6.6 12.6.7
Analytické programování princip .......................................................... 271 Data a zobrazení ..................................................................................... 275 Køíení, mutace a dalí evoluèní operace ............................................... 277 Posílené hledání ..................................................................................... 277 Bezpeènostní procedury .......................................................................... 278 Podobnosti a rozdíly s existujícími metodami ......................................... 278 Vybrané øeené problémy ....................................................................... 279
12.7
Chcete vìdìt víc? .................................................................. 280
13
Testovací funkce
13.1
13.1.1 13.1.2
281
Galerie testovacích funkcí .................................................... 282
13.1.9 13.1.10 13.1.11 13.1.12 13.1.13 13.1.14 13.1.15 13.1.16 13.1.17 13.1.18 13.1.19 13.1.20
První de Jongova funkce (1st De Jong) .................................................. 285 Druhá de Jongova funkce Rosenbrockovo sedlo (Rosenbrocks saddle) ............................................................................. 286 Tøetí de Jongova funkce (3rd De Jong) ................................................... 287 Ètvrtá de Jongova funkce (4th De Jong) ................................................. 288 Rastriginova funkce (Rastrigins function) ............................................... 289 Schwefelova funkce (Schwefels function) .............................................. 290 Griewangkova funkce (Griewangks function) ......................................... 291 Sinová obálková sinusoidální funkce (sine envelope sine wave function) ......................................................... 292 Roztaená sinusoidální V funkce (stretched V sine wave function) ........ 293 Ackleyho funkce I (Ackleys function I) .................................................... 294 Ackleyho funkce II (Ackleys function II) .................................................. 295 Plato vajec (egg holder) .......................................................................... 296 Ranova funkce (Ranas function) ............................................................ 297 Patologická funkce (pathological function) .............................................. 298 Michalewiczova funkce (Michalewiczs function) ..................................... 299 Mastersova funkce (Masterss cosine wave function) ............................. 300 Problém dìlení èaje ................................................................................ 301 Shekelova funkce (Shekels foxhole) ...................................................... 303 Pseudo-Dirakova funkce ......................................................................... 305 Fraktální funkce ....................................................................................... 306
13.2
Permutaèní testovací problémy ........................................... 309
13.3
Chcete vìdìt víc? .................................................................. 310
13.1.3 13.1.4 13.1.5 13.1.6 13.1.7 13.1.8
8
Master populace ...................................................................................... 268 Úèelová funkce (fitness) .......................................................................... 268
Zelinka, Oplatková, eda, Omera, Vèelaø: Evoluèní výpoèetní techniky
A
14
Ukázkové studie
14.1
Testování evoluèních algoritmù........................................... 313
14.2
311
Problémy rozvrhování výroby .............................................. 316
14.2.1
Problém rozvrhování proudové výroby .................................................... 317
14.3
Problém rozvrhování zakázkové výroby ............................. 325
14.3.1 14.3.2 14.3.3 14.3.4
Reprezentace zaloená na úlohách ........................................................ 327 Reprezentace zaloená na operacích ..................................................... 328 Reprezentace disjunktivním grafem ........................................................ 329 Metoda CPM ........................................................................................... 330
14.4
Problém pokrytí ..................................................................... 333
14.5
Problém batohu ..................................................................... 336
14.6
Steinerovy problémy ............................................................. 337
14.7
Plánování trasy robotu ......................................................... 345
14.7.1
Silnièní mapy ........................................................................................... 350
14.8
Evoluce a rozvrhování proudové výroby ............................ 355
14.8.1 14.8.2 14.8.3 14.8.4 14.8.5
14.9
Proudová výroba a definice úèelové funkce ............................................ 356 Pouité algoritmy a testovací problémy ................................................... 356 Test FSS I ................................................................................................ 357 Test FSS II ............................................................................................... 358 Závìr ....................................................................................................... 358
Øízení deterministického chaosu ........................................ 359
14.9.1 14.9.2 14.9.3 14.9.4
Popis problému ....................................................................................... 359 Úèelová funkce ........................................................................................ 360 Optimalizaèní algoritmus ......................................................................... 361 Experimentální výsledky logistická rovnice .......................................... 362
14.9.4.1 14.9.4.2 14.9.4.3 14.9.4.4
Øízení chaosu logistická rovnice, stabilizace p1 UPO ............................................... 363 Øízení chaosu logistická rovnice, stabilizace p2 UPO ............................................... 365 Øízení chaosu logistická rovnice, stabilizace p4 UPO ............................................... 367 Srovnání s klasickou øídicí technikou OGY ..................................................................... 369
14.9.5
Experimentální výsledky Henonova mapa ........................................... 370
14.9.5.1 14.9.5.2 14.9.5.3 14.9.5.4
Øízení chaosu Henonova mapa, stabilizace p1 UPO ................................................ 370 Øízení chaosu Henonova mapa, stabilizace p2 UPO ................................................ 372 Øízení chaosu Henonova mapa, stabilizace p4 UPO ................................................ 374 Srovnání s klasickou øídicí technikou OGY .................................................................. 376
14.9.6
Závìr ....................................................................................................... 377
14.10
14.10.1 14.10.2 14.10.3 14.10.4
A
Øízení plazmového reaktoru ................................................ 378
Plazma øízená radiovou frekvencí ........................................................... 378 Langmuirova sonda ................................................................................. 379 Aktivní kompenzace v RF plazmatu ........................................................ 379 Hardwarové vybavení a zapojení ............................................................ 380
Obsah, pøedmluva a seznam symbolù
9
14.10.5 14.10.6 14.10.7
Nastavení experimentu ........................................................................... 381 Návrh experimentu a øídicích parametrù ................................................. 382 Závìr ....................................................................................................... 382
14.11
Aerodynamická optimalizace geometrie køídla .................. 387
14.11.1 14.11.2 14.11.3 14.11.4 14.11.5
Optimalizovaný model køídla ................................................................... 387 Výsledky optimalizace ............................................................................. 389 SportStar ................................................................................................. 390 VUT-100 Cobra ....................................................................................... 391 Závìr ....................................................................................................... 395
14.12
Optimalizace umístìní smìrovacích stanic v bezdrátových sítích ....................................................................................... 395
14.12.1 14.12.2 14.12.3 14.12.4 14.12.5
14.13
14.13.1 14.13.2 14.13.3
14.14
14.14.1 14.14.2 14.14.3 14.14.4
14.15
10
Optimalizovaný model ............................................................................. 396 Vliv pøenosových uzlù ............................................................................. 398 Umístìní routovacích uzlù pøírùstkovou metodou ................................... 398 Umístìní smìrovacích uzlù za pouití algoritmu SOMA ......................... 398 Závìr ....................................................................................................... 405
Aproximace funkcí ................................................................ 405
Sextic a Quintic problém ......................................................................... 406 Problém 3Sine a 4Sine ........................................................................... 409 Závìr ....................................................................................................... 412
Syntéza øídicích pøíkazù robotu ........................................... 414
Definice problému ................................................................................... 415 Øeení ..................................................................................................... 417 Pouité evoluèní algoritmy ...................................................................... 422 Závìr ....................................................................................................... 425
Evoluèní syntéza deterministického chaosu ...................... 428
14.15.1 14.15.2 14.15.3 14.15.4 14.15.5 14.15.6
Souèasný stav a motivace ....................................................................... 428 Nejjednoduí model deterministického chaosu logistická rovnice ...... 429 Výbìr základního chaotického systému .................................................. 430 Úèelová funkce ........................................................................................ 432 Experimentální výsledky ......................................................................... 432 Závìr ....................................................................................................... 437
14.16
Syntéza logických funkcí a elektronických obvodù .......... 444
14.16.1
Syntéza boolovské paritní funkce ............................................................ 444
14.16.1.1 14.16.1.2 14.16.1.3
Úèelová funkce ................................................................................................................ 445 Pouité algoritmy ............................................................................................................. 445 Výsledky .......................................................................................................................... 445
14.16.2
Návrh elektronických obvodù .................................................................. 453
14.16.2.1 14.16.2.2 14.16.2.3 14.16.2.4
Pouité algoritmy a úèelová funkce ................................................................................. 453 Svìtelná signalizace ........................................................................................................ 453 Tepelná regulace ............................................................................................................. 455 Øízení vlakových výhybek ............................................................................................... 456
Zelinka, Oplatková, eda, Omera, Vèelaø: Evoluèní výpoèetní techniky
A
14.16.3
14.17
14.17.1 14.17.2
Závìr ....................................................................................................... 458
Syntéza neuronových sítí ..................................................... 458
Vybraný algoritmus, jeho nastavení a úèelová funkce ............................. 459 Øeení lineálnì separabilního problému ................................................. 460
14.17.2.1
Syntetizované sítì pro lineárnì separabilní problém ..................................................... 460
14.17.3
Øeení problému XOR ............................................................................ 464
14.17.3.1
Syntetizované sítì pro nelineárnì separabilní problém .................................................. 464
14.17.4 14.17.5
Stromová struktura .................................................................................. 468 Závìr ...................................................................................................... 470
14.18
Syntéza evoluèních algoritmù metaevoluce .................... 471
14.18.1
První pokusy ........................................................................................... 471
14.18.1.1 14.18.1.2 14.18.1.3
Mnoina obecných funkcí ................................................................................................ 472 Úèelová funkce ................................................................................................................ 472 Výsledky prvních pokusù ................................................................................................. 473
14.18.2 14.18.3 14.18.4
Vícedimenzionální problémy s více operátory ......................................... 475 Úèelová funkce ........................................................................................ 477 Závìr ....................................................................................................... 504
14.19
Vybrané pøíklady P a NP problémù ...................................... 504
14.20
Chcete vìdìt víc? .................................................................. 509
Závìr
511
Pouitá literatura ................................................................................. 514 Rejstøík ................................................................................................ 531 Kontakty na prodejny technické literatury ....................................... 535 Pár slov o nakladatelství .................................................................... 536
A
Obsah, pøedmluva a seznam symbolù
11
