Global Optimization Algorithms - Theory and Application

Preface......Page 3
Contents......Page 7
Part I Global Optimization......Page 21
Introduction......Page 23
Taxonomy According to Method of Operation......Page 24
Classification According to Properties......Page 27
Local and Global Optima......Page 28
Restrictions of the Search Space......Page 29
Multi-objective Optimization......Page 32
Weighted Sum......Page 33
Pareto Optimization......Page 34
The Method of Inequalities......Page 37
External Decision Maker......Page 38
Prevalence Optimization......Page 40
Premature Convergence and Multi-Modality......Page 41
Deceptive Fitness Landscapes......Page 45
Neutral Fitness Landscapes......Page 46
Overfitting......Page 47
Modeling and Simulating......Page 48
Termination Criterion......Page 51
Minimization......Page 52
Obtaining Optimal Elements......Page 53
Pruning the Optimal Set......Page 55
Conferences, Workshops, etc.......Page 61
Journals......Page 63
Books......Page 64
The Basic Principles from Nature......Page 67
Classification of Evolutionary Algorithms......Page 73
Populations in Evolutionary Algorithms......Page 74
Forma Analysis......Page 76
Conferences, Workshops, etc.......Page 80
Journals......Page 83
Books......Page 84
Fitness Assignment......Page 85
Prevalence-Count Fitness Assignment......Page 86
Rank-Based Fitness Assignment......Page 87
Sharing Functions......Page 89
Niche Size Fitness Assignment......Page 91
NSGA Fitness Assignment......Page 92
NSGA2 Fitness Assignment......Page 93
RPSGAe Fitness Assignment......Page 95
SPEA2 Fitness Assignment......Page 96
Selection......Page 98
Random Selection......Page 100
Tournament Selection......Page 101
Crowded Tournament Selection......Page 103
Roulette Wheel Selection......Page 104
Linear and Polynomial Ranking Selection......Page 105
VEGA Selection......Page 106
MIDEA Selection......Page 107
NPGA Selection......Page 110
CNSGA Selection......Page 112
PESA-II Selection......Page 114
Reproduction......Page 119
NCGA Reproduction......Page 121
MIDEA......Page 123
NPGA2......Page 124
NSGA......Page 125
CNSGA......Page 126
PAES......Page 127
PESA......Page 128
SFGA and PSFGA......Page 129
SPEA......Page 130
SPEA2......Page 131
NCGA......Page 134
Introduction......Page 137
Areas Of Application......Page 139
Conferences, Workshops, etc.......Page 140
Genomes......Page 141
Fixed-Length String Chromosomes......Page 144
Variable-Length String Chromosomes......Page 146
Genotype-Phenotype Mapping......Page 147
Artificial Embryogeny......Page 148
Schemata and Masks......Page 149
Holland's Schema Theorem......Page 150
Criticism of the Schema Theorem......Page 151
The Building Block Hypothesis......Page 152
Principles for Individual Representations......Page 153
Locality and Causality......Page 154
Redundancy......Page 155
Implications of the Forma Analysis......Page 156
Introduction......Page 159
Areas Of Application......Page 162
Conferences, Workshops, etc.......Page 163
Books......Page 164
Creation......Page 165
Mutation......Page 166
Crossover......Page 167
Editing......Page 168
Wrapping......Page 169
Lifting......Page 170
Automatically Defined Functions......Page 171
Node Selection......Page 172
Cramer's Genetic Programming......Page 174
Gene Expression Programming......Page 176
Grammars in Genetic Programming......Page 179
Strongly Typed Genetic Programming......Page 180
Gads 1......Page 182
Grammatical Evolution......Page 185
Gads 2......Page 189
Christiansen Grammar Evolution......Page 191
Tree-Adjoining Grammar-Guided Genetic Programming......Page 193
Linear Genetic Programming......Page 197
Parallel Distributed Genetic Programming......Page 199
Cartesian Genetic Programming......Page 202
Problems of String-to-Tree GPMs......Page 205
Rule-based Genetic Programming......Page 207
Genotype and Phenotype......Page 209
Program Execution and Dimensions of Independence......Page 210
Complex Statements......Page 211
Push, PushGP, and Pushpop......Page 213
Restricting Problems......Page 216
Why No Exhaustive Testing?......Page 218
Non-Functional Features of Algorithms......Page 219
Areas Of Application......Page 223
Populations in Evolutionary Strategy......Page 224
(','(,))-ES......Page 225
General Information......Page 226
Areas Of Application......Page 229
Books......Page 230
Areas Of Application......Page 231
The Basic Idea of Learning Classifier Systems......Page 232
Messages......Page 233
Conditions......Page 235
Actions......Page 236
Classifiers......Page 237
Learning Classifier Systems......Page 238
The Bucket Brigade Algorithm......Page 239
Families of Learning Classifier Systems......Page 242
Introduction......Page 243
Problems in Hill Climbing......Page 244
Hill Climbing with Random Restarts......Page 245
Introduction......Page 247
Areas Of Application......Page 249
Introduction......Page 251
Temperature Scheduling......Page 253
Multi-Objective Simulated Annealing......Page 254
Introduction......Page 257
Multi-Objective Tabu Search......Page 258
Introduction......Page 261
Journals......Page 262
Online Resources......Page 263
Introduction......Page 265
Online Resources......Page 267
Conferences, Workshops, etc.......Page 268
Memetic Algorithms......Page 269
Introduction......Page 271
Breadth-First Search......Page 273
Depth-First Search......Page 274
Iterative deepening depth-first search......Page 275
Random Walks......Page 276
Informed Search......Page 278
Greedy Search......Page 279
Adaptive Walks......Page 280
Analysis......Page 283
Client-Server......Page 286
Island Model......Page 287
Mixed Distribution......Page 290
Cellular GA......Page 291
Part II Applications......Page 293
Single-Objective Optimization......Page 295
Dynamic Fitness Landscapes......Page 296
Kauffman's NK Fitness Landscapes......Page 298
Intermediate K......Page 299
The Royal Road......Page 300
Variable-Length Representation......Page 301
Epistatic Road......Page 302
Royal Trees......Page 303
Artificial Ant......Page 304
Solutions......Page 305
Problem Definition......Page 307
Rule-based Genetic Programming......Page 311
Introduction......Page 319
The 2007 Contest -- Using Classifier Systems......Page 320
Introduction......Page 332
The 2006/2007 Semantic Challenge......Page 333
Symbolic Regression......Page 349
Genetic Programming: Genome for Symbolic Regression......Page 350
Sample Data, Quality, and Estimation Theory......Page 351
An Example and the Phenomenon of Overfitting......Page 352
Limits of Symbolic Regression......Page 355
Aggregation Protocols......Page 357
The Solution Approach: Genetic Programming......Page 362
Network Model and Simulation......Page 363
Node Model and Simulation......Page 365
Evaluation and Objective Values......Page 367
Input Data......Page 369
Phenotypic Representations of Aggregation Protocols......Page 373
Results from Experiments......Page 376
Part III Sigoa -- Implementation in Java......Page 385
Introduction......Page 387
Separation of Concerns......Page 389
Architecture......Page 390
Subsystems......Page 392
The 2007 DATA-MINING-CUP......Page 395
The Genotype and the Embryogeny......Page 396
The Simulation......Page 398
The Objective Functions......Page 400
The Evolution Process......Page 402
Specification......Page 407
Reference Implementation......Page 408
Specification......Page 411
Reference Implementation......Page 413
Specification......Page 415
Reference Implementation......Page 416
Random Number Generators......Page 419
Statistic Data Representation......Page 421
Statistic Data Representation......Page 422
Specification......Page 425
The Simulations......Page 426
Simulation Provider and Simulation Manager......Page 427
Simulation Provider and Simulation Manager......Page 428
Simulation Inheritance......Page 430
The Activity Model......Page 433
The Job System Interface......Page 435
The Interface to the Optimization Tasks......Page 436
Using a Job System......Page 439
The Activity Model......Page 440
The Job System Base Classes......Page 441
Job System Implementations......Page 442
The Pipeline System......Page 447
Specification......Page 448
Basic Classes......Page 449
Some Basic Pipes......Page 452
Pipes for Persistent Output......Page 454
Specification......Page 457
Clustering Algorithms......Page 459
Distance Measures......Page 461
Basic Interfaces......Page 465
Reproduction......Page 470
Objective Functions......Page 472
Computing an Objective Value......Page 473
Embryogeny......Page 476
Fitness Assignment and Selection......Page 478
The Optimizer......Page 479
Predefined Algorithm Interfaces......Page 480
Basic Classes......Page 481
Reproduction......Page 487
Objective Functions......Page 490
The Evaluator......Page 493
Embryogeny......Page 494
Fitness Assignment......Page 495
Selection......Page 497
The Optimizer......Page 498
Predefined Algorithms......Page 501
Implementing Evolutionary Algorithms......Page 502
Genotypes......Page 507
The Evaluation Scheme for Functions of Real Vectors......Page 508
Reproduction Operators for Real Vectors......Page 509
Encoding and Decoding Data in Bit String Genomes......Page 511
Reproducing Bit Strings......Page 513
The Selector......Page 517
Part IV Background......Page 519
Set Membership......Page 521
Special Sets......Page 522
Operations on Sets......Page 523
Tuples and Lists......Page 525
Binary Relations......Page 528
Order relations......Page 529
Functions......Page 530
Probability......Page 533
Probabily as defined by Bernoulli (1713)......Page 534
The Axioms of Kolmogorov......Page 535
Conditional Probability......Page 536
Cumulative Distribution Function......Page 537
Properties of Distributions and Statistics......Page 539
Count, Min, Max and Range......Page 540
Expected Value and Arithmetic Mean......Page 541
Variance and Standard Deviation......Page 542
Moments......Page 543
Median, Quantiles, and Mode......Page 544
Entropy......Page 546
Discrete Uniform Distribution......Page 547
Poisson Distribution......Page 550
Binomial Distribution B(n, p)......Page 552
Continuous Uniform Distribution......Page 555
Normal Distribution N(,2)......Page 557
Exponential Distribution exp()......Page 560
Chi-square Distribution......Page 562
Student's t-Distribution......Page 565
Example - Throwing a Dice......Page 568
Estimation Theory......Page 569
Likelihood and Maximum Likelihood Estimators......Page 572
Confidence Intervals......Page 576
Generating Random Numbers......Page 579
Generating Pseudorandom Numbers......Page 580
Converting Random Numbers to other Distributions......Page 581
Definitions of Random Functions......Page 585
The kth Nearest Neighbor Method......Page 587
Crowding Distance......Page 588
Gamma Function......Page 590
Clustering......Page 591
Distance Measures for Real-Valued Vectors......Page 594
Distance Measures Between Clusters......Page 596
Cluster Error......Page 597
nth Nearest Neighbor Clustering......Page 598
Linkage Clustering......Page 599
Leader Clustering......Page 601
What are Algorithms?......Page 605
Properties of Algorithms......Page 608
Complexity of Algorithms......Page 609
Randomized Algorithms......Page 611
Distributed Systems and Distributed Algorithms......Page 612
Network Topologies......Page 613
Some Architectures of Distributes Systems......Page 616
Modeling Distributed Systems......Page 623
Syntax and Formal Languages......Page 634
Derivation Trees......Page 636
Backus-Naur Form......Page 637
Extended Backus-Naur Form......Page 638
Attribute Grammar......Page 639
Extended Attribute Grammars......Page 641
Adaptable Grammar......Page 643
Christiansen Grammars......Page 644
Tree-Adjoining Grammar......Page 645
S-Expressions......Page 647
Part V Appendices......Page 651
Applicability and Definitions......Page 653
Copying in Quantity......Page 655
Modifications......Page 656
Collections of Documents......Page 658
Termination......Page 659
Future Revisions of this License......Page 660
Preamble......Page 661
Terms and Conditions for Copying, Distribution and Modification......Page 663
How to Apply These Terms to Your New Libraries......Page 669
Credits and Contributors......Page 671
Citation Suggestion......Page 673
References......Page 675
Index......Page 827
List of Figures......Page 847
List of Tables......Page 855
List of Algorithms......Page 857
List of Listings......Page 861