Thomas Weise Global Optimization Algorithms - Theory and Application 2Ed

Preface......Page 3
Contents......Page 7
Part I Global Optimization......Page 17
Introduction......Page 19
Classification According to Method of Operation......Page 20
Classification According to Properties......Page 22
Single Objective Functions......Page 23
Multiple Objective Functions......Page 25
Weighted Sum......Page 27
Pareto Optimization......Page 29
The Method of Inequalities......Page 32
External Decision Maker......Page 34
Prevalence Optimization......Page 35
Spaces, Sets, and Elements......Page 37
Fitness Landscapes and Global Optimization......Page 45
Other General Features......Page 50
Premature Convergence and Multimodality......Page 53
Ruggedness and Weak Causality......Page 56
Neutrality and Redundancy......Page 59
Epistasis......Page 63
Overfitting and Oversimplification......Page 64
Robustness and Noise......Page 67
Dynamically Changing Fitness Landscape......Page 69
No Free Lunch Theorem......Page 70
Formae and Search Space/Operator Design......Page 71
Forma Analysis......Page 72
Genome Design......Page 74
Areas Of Application......Page 76
Conferences, Workshops, etc.......Page 77
Journals......Page 80
Books......Page 81
The Basic Principles from Nature......Page 83
Classification of Evolutionary Algorithms......Page 88
Areas Of Application......Page 92
Conferences, Workshops, etc.......Page 93
Online Resources......Page 96
Books......Page 97
Introduction......Page 98
Pareto Ranking......Page 99
Sharing Functions......Page 101
Variety Preserving Ranking......Page 103
Introduction......Page 108
Truncation Selection......Page 110
Fitness Proportionate Selection......Page 111
Tournament Selection......Page 116
Ordered Selection......Page 119
VEGA Selection......Page 121
Simple Convergence Prevention......Page 122
Reproduction......Page 124
NCGA Reproduction......Page 125
VEGA......Page 126
Introduction......Page 129
Areas Of Application......Page 130
Conferences, Workshops, etc.......Page 131
Books......Page 132
Genomes in Genetic Algorithms......Page 133
Mutation......Page 134
Crossover......Page 135
Crossover......Page 136
Schema Theorem......Page 137
Wildcards......Page 138
Criticism of the Schema Theorem......Page 139
The Building Block Hypothesis......Page 140
History......Page 141
Areas Of Application......Page 143
Conferences, Workshops, etc.......Page 144
Online Resources......Page 145
Creation......Page 146
Recombination......Page 147
Editing......Page 149
Wrapping......Page 150
Automatically Defined Functions......Page 151
Automatically Defined Macros......Page 152
Node Selection......Page 153
Cramer's Genetic Programming......Page 155
Gene Expression Programming......Page 156
Edge Encoding......Page 158
Trivial Approach......Page 161
Strongly Typed Genetic Programming......Page 162
Gads 1......Page 163
Grammatical Evolution......Page 165
Gads 2......Page 169
Christiansen Grammar Evolution......Page 170
Tree-Adjoining Grammar-guided Genetic Programming......Page 172
Linear Genetic Programming......Page 175
Parallel Algorithm Discovery and Orchestration......Page 177
Parallel Distributed Genetic Programming......Page 178
Genetic Network Programming......Page 180
Cartesian Genetic Programming......Page 181
Introduction......Page 183
Algorithmic Chemistry......Page 185
Rule-based Genetic Programming......Page 187
Soft Assignment......Page 193
Push, PushGP, and Pushpop......Page 194
Fraglets......Page 197
Restricting Problems......Page 200
Why No Exhaustive Testing?......Page 201
Non-Functional Features of Algorithms......Page 202
Areas Of Application......Page 205
(+)-ES......Page 206
Introduction......Page 207
General Information......Page 208
Areas Of Application......Page 209
Books......Page 210
Conferences, Workshops, etc.......Page 211
Messages......Page 212
Conditions......Page 214
Classifiers......Page 216
Non-Learning Classifier Systems......Page 217
The Bucket Brigade Algorithm......Page 218
Families of Learning Classifier Systems......Page 220
Introduction......Page 223
Multi-Objective Hill Climbing......Page 224
Problems in Hill Climbing......Page 225
Hill Climbing with Random Restarts......Page 226
Introduction......Page 227
Areas Of Application......Page 228
Introduction......Page 231
Temperature Scheduling......Page 233
Multi-Objective Simulated Annealing......Page 234
Areas Of Application......Page 237
The Downhill Simplex Algorithm......Page 238
Hybridizing with the Downhill Simplex......Page 240
Introduction......Page 243
Multi-Objective Tabu Search......Page 244
Introduction......Page 247
Online Resources......Page 248
Introduction......Page 251
Areas Of Application......Page 252
Books......Page 253
Memetic Algorithms......Page 255
Online Resources......Page 256
Books......Page 257
Introduction......Page 259
Breadth-First Search......Page 261
Depth-First Search......Page 262
Iterative Deepening Depth-First Search......Page 263
Random Walks......Page 264
Greedy Search......Page 265
Adaptive Walks......Page 266
Analysis......Page 269
Client-Server......Page 271
Island Model......Page 272
Cellular Genetic Algorithms......Page 275
Updating the Optimal Set......Page 277
Obtaining Optimal Elements......Page 278
Pruning the Optimal Set......Page 279
Adaptive Grid Archiving......Page 280
Part II Applications......Page 283
The Optimization Problem......Page 285
The Optimization Algorithm Applied......Page 286
Other Run Parameters......Page 287
Measures......Page 288
Simple Evaluation Measures......Page 289
Sophisticated Estimates......Page 291
Single-Objective Optimization......Page 293
Dynamic Fitness Landscapes......Page 294
Kauffman's NK Fitness Landscapes......Page 295
The p-Spin Model......Page 298
The Royal Road......Page 299
OneMax and BinInt......Page 303
Tunable Model for Problematic Phenomena......Page 304
Artificial Ant......Page 317
The Greatest Common Divisor......Page 319
Introduction......Page 331
The 2007 Contest -- Using Classifier Systems......Page 332
Introduction......Page 341
The 2006/2007 Semantic Challenge......Page 343
Genetic Programming: Genome for Symbolic Regression......Page 355
Sample Data, Quality, and Estimation Theory......Page 356
An Example and the Phenomenon of Overfitting......Page 357
Limits of Symbolic Regression......Page 359
Global Optimization of Distributed Systems......Page 361
Optimizing Network Topology and Dimensioning......Page 362
Optimizing Routing......Page 366
Synthesizing Protocols......Page 373
Optimizing Network Security......Page 377
Optimizing Parameters and Configurations......Page 378
Introduction......Page 379
Evolving Proactive Aggregation Protocols......Page 380
Part III Sigoa -- Implementation in Java......Page 403
Introduction......Page 405
Separation of Specification and Implementation......Page 406
Architecture......Page 407
Subsystems......Page 409
The Phenotype......Page 411
The Simulation......Page 412
The Objective Functions......Page 415
The Evolution Process......Page 417
Part IV Background......Page 419
Relations between Sets......Page 421
Operations on Sets......Page 422
Tuples......Page 424
Lists......Page 425
Binary Relations......Page 427
Functions......Page 428
Order Relations......Page 429
Equivalence Relations......Page 430
Probability......Page 431
Probabily as defined by Bernoulli (1713)......Page 432
The Axioms of Kolmogorov......Page 433
Conditional Probability......Page 434
Cumulative Distribution Function......Page 435
Probability Density Function......Page 436
Count, Min, Max and Range......Page 437
Variance and Standard Deviation......Page 438
Moments......Page 440
Median, Quantiles, and Mode......Page 441
Some Discrete Distributions......Page 443
Discrete Uniform Distribution......Page 444
Poisson Distribution......Page 445
Binomial Distribution B(n, p)......Page 448
Some Continuous Distributions......Page 449
Continuous Uniform Distribution......Page 450
Normal Distribution N(,2)......Page 451
Exponential Distribution exp()......Page 454
Chi-square Distribution......Page 455
Student's t-Distribution......Page 459
Example -- Throwing a Dice......Page 462
Estimation Theory......Page 464
Likelihood and Maximum Likelihood Estimators......Page 465
Confidence Intervals......Page 468
Density Estimation......Page 471
Generating Random Numbers......Page 473
Generating Pseudorandom Numbers......Page 474
Random Functions......Page 475
Converting Random Numbers to other Distributions......Page 476
Gamma Function......Page 480
Clustering......Page 481
Distance Measures for Real-Valued Vectors......Page 483
Cluster Error......Page 485
nth Nearest Neighbor Clustering......Page 486
Linkage Clustering......Page 487
Leader Clustering......Page 489
Algorithms and Programs......Page 493
Properties of Algorithms......Page 495
Complexity of Algorithms......Page 496
Randomized Algorithms......Page 498
Distributed Systems and Distributed Algorithms......Page 499
Network Topologies......Page 500
Some Architectures of Distributes Systems......Page 502
Modeling Distributed Systems......Page 507
Grammars and Languages......Page 515
Generative Grammars......Page 516
Derivation Trees......Page 517
Backus-Naur Form......Page 518
Attribute Grammars......Page 519
Extended Attribute Grammars......Page 521
Adaptive Grammars......Page 522
Christiansen Grammars......Page 523
Tree-Adjoining Grammars......Page 524
S-expressions......Page 526
Part V Appendices......Page 527
Abbreviations and Symbols......Page 529
Applicability and Definitions......Page 541
Verbatim Copying......Page 542
Modifications......Page 543
Translation......Page 545
Future Revisions of this License......Page 546
Preamble......Page 547
Terms and Conditions for Copying, Distribution and Modification......Page 548
No Warranty......Page 552
How to Apply These Terms to Your New Libraries......Page 553
Credits and Contributors......Page 555
Citation Suggestion......Page 557
References......Page 559
Index......Page 731
List of Figures......Page 747
List of Tables......Page 753
List of Algorithms......Page 755
List of Listings......Page 757