Global Optimization Algorithms: Theory and Application

Preface......Page 3
Contents......Page 7
Part I Global Optimization......Page 19
Introduction......Page 21
Classification According to Method of Operation......Page 22
Classification According to Properties......Page 24
Single Objective Functions......Page 25
Multiple Objective Functions......Page 27
Constraint Handling......Page 33
Unifying Approaches......Page 37
Spaces, Sets, and Elements......Page 40
Fitness Landscapes and Global Optimization......Page 47
Other General Features......Page 53
Introduction......Page 56
Premature Convergence......Page 58
Ruggedness and Weak Causality......Page 61
Deceptiveness......Page 63
Neutrality and Redundancy......Page 64
Epistasis......Page 68
Noise and Robustness......Page 70
Overfitting and Oversimplification......Page 72
The No Free Lunch Theorem......Page 76
Conclusions......Page 79
Forma Analysis......Page 80
Genome Design......Page 82
Conferences, Workshops, etc.......Page 87
Journals......Page 91
Online Resources......Page 92
Books......Page 93
The Basic Principles from Nature......Page 95
The Basic Cycle of Evolutionary Algorithms......Page 96
The Basic Evolutionary Algorithm Scheme......Page 98
From the Viewpoint of Formae......Page 99
Classification of Evolutionary Algorithms......Page 100
Configuration Parameters of evolutionary algorithms......Page 104
Conferences, Workshops, etc.......Page 105
Journals......Page 108
Online Resources......Page 109
Books......Page 110
Introduction......Page 111
Pareto Ranking......Page 112
Sharing Functions......Page 114
Variety Preserving Ranking......Page 116
Tournament Fitness Assignment......Page 120
Introduction......Page 121
Truncation Selection......Page 122
Fitness Proportionate Selection......Page 124
Tournament Selection......Page 127
Ordered Selection......Page 131
VEGA Selection......Page 133
Clearing and Simple Convergence Prevention (SCP)......Page 134
Reproduction......Page 137
NCGA Reproduction......Page 138
VEGA......Page 139
Introduction......Page 141
Areas Of Application......Page 142
Conferences, Workshops, etc.......Page 143
Books......Page 144
Genomes in Genetic Algorithms......Page 145
Mutation: Unary Reproduction......Page 147
Crossover: Binary Reproduction......Page 148
Crossover: Binary Reproduction......Page 149
Schemata and Masks......Page 150
Holland's Schema Theorem......Page 151
The Building Block Hypothesis......Page 152
Representation......Page 153
Overspecification and Underspecification......Page 154
Genotype-Phenotype Mappings and Artificial Embryogeny......Page 155
History......Page 157
Conferences, Workshops, etc.......Page 160
Online Resources......Page 161
Creation: Nullary Reproduction......Page 162
Mutation: Unary Reproduction......Page 163
Recombination: Binary Reproduction......Page 164
Editing: Unary Reproduction......Page 165
Wrapping: Unary Reproduction......Page 166
Automatically Defined Functions......Page 167
Automatically Defined Macros......Page 168
Node Selection......Page 169
Cramer's Genetic Programming......Page 171
Gene Expression Programming......Page 172
Edge Encoding......Page 174
Introduction......Page 176
Trivial Approach......Page 177
Strongly Typed Genetic Programming......Page 178
Gads 1......Page 179
Grammatical Evolution......Page 181
Gads 2......Page 185
Christiansen Grammar Evolution......Page 186
Tree-Adjoining Grammar-guided Genetic Programming......Page 187
Introduction......Page 191
Advantages and Disadvantages......Page 192
Automatic Induction of Machine Code by Genetic Programming......Page 193
Brameier and Banzhaf: LGP with Implicit Intron removal......Page 194
Graph-based Approaches......Page 195
Parallel Distributed Genetic Programming......Page 196
Cartesian Genetic Programming......Page 199
Forms of Epistasis in Genetic Programming......Page 202
Algorithmic Chemistry......Page 205
Soft Assignment......Page 206
Rule-based Genetic Programming......Page 207
Artificial Life and Artificial Chemistry......Page 213
Push, PushGP, and Pushpop......Page 214
Fraglets......Page 216
Correctness of the Evolved Algorithms......Page 219
All-Or-Nothing?......Page 223
Non-Functional Features of Algorithms......Page 224
Areas Of Application......Page 227
(+)-ES......Page 228
Introduction......Page 229
General Information......Page 230
Areas Of Application......Page 231
Books......Page 232
Conferences, Workshops, etc.......Page 233
A Small Example......Page 234
Conditions......Page 236
Classifiers......Page 238
Learning Classifier Systems......Page 239
The Bucket Brigade Algorithm......Page 240
Families of Learning Classifier Systems......Page 242
Introduction......Page 245
Journals......Page 246
River Formation Dynamics......Page 247
Introduction......Page 249
Areas Of Application......Page 250
Books......Page 251
Introduction......Page 253
Multi-Objective Hill Climbing......Page 254
Problems in Hill Climbing......Page 255
GRASP......Page 256
Raindrop Method......Page 257
Introduction......Page 259
Areas Of Application......Page 260
Introduction......Page 263
Temperature Scheduling......Page 265
Multi-Objective Simulated Annealing......Page 266
The Bak-Sneppens model of Evolution......Page 269
Extremal Optimization and Generalized Extremal Optimization......Page 270
Areas Of Application......Page 271
Introduction......Page 273
Multi-Objective Tabu Search......Page 274
Memetic Algorithms......Page 277
Baldwin Effect......Page 278
Areas Of Application......Page 280
Books......Page 281
Areas Of Application......Page 283
The Downhill Simplex Algorithm......Page 284
Hybridizing with the Downhill Simplex......Page 286
Introduction......Page 289
Breadth-First Search......Page 291
Depth-First Search......Page 292
Depth-limited Search......Page 293
Random Walks......Page 294
Greedy Search......Page 295
A search......Page 296
Adaptive Walks......Page 297
Analysis......Page 299
Client-Server......Page 301
Island Model......Page 302
Cellular Genetic Algorithms......Page 305
Updating the Optimal Set......Page 307
Obtaining Optimal Elements......Page 308
Pruning via Clustering......Page 309
Adaptive Grid Archiving......Page 310
Part II Applications......Page 313
The Optimization Problem......Page 315
The Optimization Algorithm Applied......Page 316
Other Run Parameters......Page 317
Measures......Page 319
Simple Evaluation Measures......Page 320
Sophisticated Estimates......Page 323
Confidence Intervals or Statistical Tests......Page 324
Factorial Experiments......Page 325
Single-Objective Optimization......Page 327
Dynamic Fitness Landscapes......Page 328
Kauffman's NK Fitness Landscapes......Page 329
The p-Spin Model......Page 332
The ND Family of Fitness Landscapes......Page 333
The Royal Road......Page 334
OneMax and BinInt......Page 337
Long Path Problems......Page 338
Tunable Model for Problematic Phenomena......Page 341
Artificial Ant......Page 354
The Greatest Common Divisor......Page 357
Introduction......Page 373
The 2007 Contest – Using Classifier Systems......Page 374
Introduction......Page 383
The 2006/2007 Semantic Challenge......Page 385
Genetic Programming: Genome for Symbolic Regression......Page 397
Sample Data, Quality, and Estimation Theory......Page 398
An Example and the Phenomenon of Overfitting......Page 399
Introduction......Page 401
Synthesizing Protocols......Page 403
Paper List......Page 404
Conclusions......Page 411
Introduction......Page 413
Evolving Proactive Aggregation Protocols......Page 414
Part III Sigoa – Implementation in Java......Page 437
Introduction......Page 439
Separation of Specification and Implementation......Page 440
Architecture......Page 441
Subsystems......Page 442
The Phenotype......Page 445
The Simulation......Page 446
The Objective Functions......Page 449
The Evolution Process......Page 451
Part IV Background......Page 453
Relations between Sets......Page 455
Operations on Sets......Page 456
Tuples......Page 458
Lists......Page 459
Binary Relations......Page 461
Functions......Page 462
Order Relations......Page 463
Equivalence Relations......Page 464
Books......Page 465
Probability......Page 466
Probabily as defined by Bernoulli (1713)......Page 467
The Limiting Frequency Theory of von Mises......Page 468
Conditional Probability......Page 469
Cumulative Distribution Function......Page 470
Probability Mass Function......Page 471
Count, Min, Max and Range......Page 472
Expected Value and Arithmetic Mean......Page 473
Variance and Standard Deviation......Page 474
Moments......Page 475
Median, Quantiles, and Mode......Page 476
The Law of Large Numbers......Page 478
Discrete Uniform Distribution......Page 479
Poisson Distribution......Page 480
Binomial Distribution B(n, p)......Page 483
Some Continuous Distributions......Page 484
Continuous Uniform Distribution......Page 485
Normal Distribution N(,2)......Page 486
Exponential Distribution exp()......Page 489
Chi-square Distribution......Page 490
Student's t-Distribution......Page 494
Example – Throwing a Dice......Page 497
Introduction......Page 499
Likelihood and Maximum Likelihood Estimators......Page 500
Confidence Intervals......Page 503
Density Estimation......Page 506
Statistical Tests......Page 508
Non-Parametric Tests......Page 509
Generating Pseudorandom Numbers......Page 526
Converting Random Numbers to other Distributions......Page 528
Riemann Zeta Function......Page 532
Clustering......Page 535
Distance Measures for Real-Valued Vectors......Page 537
Distance Measures Between Clusters......Page 539
k-means Clustering......Page 540
Linkage Clustering......Page 541
Leader Clustering......Page 543
Algorithms and Programs......Page 547
Properties of Algorithms......Page 549
Complexity of Algorithms......Page 550
Randomized Algorithms......Page 552
Distributed Systems and Distributed Algorithms......Page 553
Network Topologies......Page 554
Some Architectures of Distributes Systems......Page 556
Grammars and Languages......Page 561
Generative Grammars......Page 562
Derivation Trees......Page 563
Backus-Naur Form......Page 564
Attribute Grammars......Page 565
Extended Attribute Grammars......Page 567
Adaptive Grammars......Page 568
Tree-Adjoining Grammars......Page 569
S-expressions......Page 571
Appendices......Page 573
Applicability and Definitions......Page 575
Copying in Quantity......Page 576
Modifications......Page 577
Collections of Documents......Page 578
Future Revisions of this License......Page 579
Preamble......Page 581
Terms and Conditions for Copying, Distribution and Modification......Page 582
How to Apply These Terms to Your New Libraries......Page 586
Credits and Contributors......Page 589
Citation Suggestion......Page 591
A......Page 593
B......Page 601
C......Page 621
D......Page 634
E......Page 646
F......Page 648
G......Page 658
H......Page 668
I......Page 677
J......Page 681
K......Page 685
L......Page 698
M......Page 707
N......Page 721
O......Page 726
P......Page 729
R......Page 737
S......Page 746
T......Page 764
U......Page 771
V......Page 772
W......Page 776
X......Page 787
Y......Page 788
Z......Page 791
Index......Page 795
List of Figures......Page 811
List of Tables......Page 815
List of Algorithms......Page 817
List of Listings......Page 819