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