Parallel Problem Solving from Nature, PPSN XI: 11th International Conference, Krakov, Poland, September 11-15, 2010, Proceedings, Part I (Lecture Notes in Computer Science (6238))

This book constitutes the refereed proceedings of the 11th International Conference on Parallel Problem Solving from Nature - PPSN XI, held in Kraków, Poland, in September 2010. The 131 revised full papers were carefully reviewed and selected from 232 submissions. The conference covers a wide range of topics, from evolutionary computation to swarm intelligence, from bio-inspired computing to real world applications. Machine learning and mathematical games supported by evolutionary algorithms as well as memetic, agent-oriented systems are also represented. Cover ......Page 1 Preface......Page 6 Organization......Page 8 Table of Contents – Part I......Page 12 Table of Contents – Part II......Page 18 Introduction......Page 23 Problem and Algorithms......Page 25 Improvement Times......Page 26 Expected Optimization Time......Page 27 The Optimal Fixed Mutation Rate......Page 28 The Optimal Adaptive Mutation Rate......Page 29 Conclusions......Page 31 References......Page 32 Introduction......Page 33 Mirrored Sampling and Sequential Selection......Page 34 Convergence Rates on the Sphere and Lower Bounds......Page 36 Application to the CMA-ES Algorithm......Page 39 References......Page 42 Introduction......Page 44 Related Work and Associated Issues......Page 45 Overview of Experiments......Page 47 Footprints in SMT Instance Space......Page 48 Footprints in VRP Instance Space......Page 51 Summary and Conclusion......Page 52 References......Page 53 Introduction......Page 54 The (1+1) Evolutionary Algorithm for Optimizing Functions Defined over Bitstrings......Page 55 Drift Analysis......Page 56 Drift Analysis for Linear Functions......Page 57 Construction of the Drift Function......Page 58 Splitting into Blocks......Page 59 Feasible Drift......Page 60 The Case Analysis......Page 61 Conclusion......Page 62 References......Page 63 Introduction......Page 64 Our Work......Page 65 Preliminaries......Page 66 A Difficult to Optimize Monotone Function......Page 68 Proof of the Lower Bound......Page 70 Conclusions......Page 72 References......Page 73 Introduction......Page 74 Mathematical Formulation of the Isotropic (μ/μw, λ) Evolution Strategy Minimizing Spherical Functions......Page 76 Optimal Step-Size Adaptation Rule When Minimizing Spherical Functions......Page 77 Log-Linear Behavior of the Scale-Invariant (μ/μw, λ)-ES Minimizing Spherical Functions......Page 80 Numerical Experiments......Page 81 Conclusion......Page 82 References......Page 83 Introduction......Page 85 Comparing Two Solutions with Uniform Noise......Page 86 Relating Distance to Overlap......Page 88 Two Sampling Schemes......Page 89 A Simple Demonstration for the (1+1)-ES......Page 91 Conclusions and Outlook......Page 93 References......Page 94 Introduction......Page 95 Individual Ranking......Page 96 Suggested Problem Properties......Page 97 Function-Set Analysis......Page 98 Conclusions and Outlook......Page 103 References......Page 104 Introduction......Page 105 Generalization of One-Point Crossover......Page 106 Euclidean and Manhattan Spaces......Page 108 Permutations......Page 109 Genetic Programming Trees......Page 110 Variable-Length Sequences......Page 113 Conclusions......Page 114 References......Page 115 Introduction......Page 116 Using a Landscape Generator to Actively Study the Relationship between Problems and Algorithms......Page 117 Constructing Linear Ridges in Randomized Landscapes......Page 118 Comparing EMNA and UMDAc in Terms of Landscape Dependency Structure......Page 119 Experimental Results on Ridge Landscapes......Page 120 Conclusions......Page 124 References......Page 125 Introduction......Page 126 Definitions and Algorithms......Page 127 Analysis of the Local Optima Networks......Page 129 Network Features and Connectivity......Page 130 Basins of Attraction Features......Page 132 Discussion......Page 134 References......Page 135 Introduction......Page 136 Differential Mutation Distribution......Page 137 Multivector Differential Mutation......Page 138 Discussion......Page 139 Experimental Study......Page 141 References......Page 145 Previous Work......Page 146 Preliminaries......Page 147 Lower Bounds with Fitness-Levels......Page 148 A Lower Bound for LeadingOnes......Page 150 A Lower Bound for OneMax......Page 152 Generalization to All Functions with Unique Optimum......Page 154 References......Page 155 State of the Art Concerning Binary Encodings......Page 156 Requirements for a ``Good'' Binary Encoding......Page 157 Constructing a New Coding......Page 159 Analytical Results......Page 160 Experimental Comparison of the Encoding Schemes......Page 161 References......Page 164 Introduction......Page 166 Preliminaries......Page 167 Markov Chain Switching Theorem......Page 168 The Evolutionary Algorithm......Page 170 Analysis......Page 171 Conclusion......Page 174 References......Page 175 Introduction......Page 176 Evolution Gradient......Page 177 Natural Evolution Gradient......Page 178 Inverse of the Fisher Information Matrix......Page 179 Explicit Form of the Natural Evolution Gradient......Page 180 Parameter Update Rules......Page 181 CMA-ES as a Variant of NESs......Page 182 References......Page 184 Introduction......Page 186 Previous Work......Page 187 A Fine-Grained View of Locality......Page 188 Binary Decision Diagram Phenotypes......Page 189 Experiments and Results......Page 191 Conclusions......Page 193 References......Page 194 Introduction......Page 196 The (1+1) Evolutionary Algorithm......Page 197 A Simple Drift Theorem with Tail Bounds......Page 198 Linear Functions......Page 200 Minimum Spanning Trees and Minimum Weight Bases in Matroids......Page 201 Eulerian Cycles......Page 202 Conclusion......Page 203 References......Page 204 Introduction......Page 206 Algorithms......Page 208 Crossover with Repair......Page 209 Feasible Parent Selection......Page 213 References......Page 214 Introduction......Page 216 Credit Assignment......Page 217 Strategy Selection......Page 218 Comparison-Based Adaptive Strategy Selection: Fitness-Based AUC Bandit......Page 219 Experimental Setting......Page 220 Comparative Results......Page 222 Conclusion and Perspectives......Page 224 References......Page 225 Introduction......Page 226 Problem and Algorithms......Page 227 Local Optima and Lower Bounds......Page 228 FPT of Edge Exchanges......Page 231 References......Page 234 Introduction......Page 236 Archive Based EA for Finding Robust Solutions......Page 237 A Novel Archive Based Approach......Page 238 Experiments......Page 240 Experimental Results......Page 242 Notes on the Archive Quality......Page 243 Conclusion and Outlook......Page 244 References......Page 245 Introduction......Page 246 Preliminaries and Previous Work......Page 247 Experimental Reproduction of the Theoretical Results......Page 250 Comparison of Topologies and Migration Intervals......Page 252 Statistical Validation......Page 253 References......Page 255 Introduction......Page 256 Preliminaries......Page 257 Proving Upper Bounds for Parallel EAs......Page 259 Parallel EAs with Ring Structures......Page 260 Parallel EAs with Two-Dimensional Grids and Tori......Page 262 Parallel EAs with Complete Topologies......Page 263 References......Page 265 Introduction......Page 266 Negative Drift Theorem for Populations......Page 267 Applications to Evolutionary Algorithms......Page 272 References......Page 275 Complexity Bounds for Evolutionary Algorithms......Page 276 Automatic Speculative Parallelization......Page 277 Real World Algorithms Don't All Reach the Optimal Speed-Up......Page 279 Self-adaptation (SA)......Page 280 Experimental Speed-Up......Page 281 The log(λ) Correction for EMNA......Page 282 The log(λ) Correction for CMA-ES......Page 283 Conclusion......Page 284 References......Page 285 Introduction......Page 286 Linkage Tree......Page 287 Hierarchical Clustering Using Mutual Information......Page 288 Related Work......Page 289 Deceptive Trap functions......Page 290 Nearest Neighbor NK-Landscape with Tunable Overlap......Page 292 Conclusion......Page 294 References......Page 295 Introduction......Page 296 Exact Model of the GA in Stationary Environments......Page 297 Dynamic Optimization Problems......Page 298 The XOR DOP Generator......Page 299 Experimental Study......Page 301 Conclusion and Future Work......Page 304 References......Page 305 Introduction......Page 306 The Role of Degeneracy in Evolution......Page 308 Computational Study and Experimental Setup......Page 309 Evolvability in Dynamic Environments......Page 311 Discussion and Conclusions......Page 313 References......Page 314 Introduction......Page 316 Data-Mining-Adjusted Statistical Hypothesis Tests......Page 318 Trading Methodology......Page 320 Adapting the Data-Mining Bias Tests to a Population of Rules......Page 321 Results......Page 322 Conclusion......Page 324 References......Page 325 Introduction......Page 326 Related Work......Page 327 Object Monitor......Page 328 Feature Extractor......Page 329 Classifier......Page 331 Results and Discussions......Page 332 Timing Analysis......Page 333 References......Page 334 Introduction: Motivation and Music Classification as Optimization Problem......Page 336 Genre Classification......Page 337 Categories and Feature Sets......Page 338 Evolutionary Strategy with Local Operators (ES-LO)......Page 339 Evolutionary Strategy with Success Rule Adaptation (ES-SRA)......Page 340 Experimental Assessment of Search Strategies......Page 341 References......Page 344 Introduction......Page 346 Representation......Page 347 Initialization......Page 348 Genetic Operators......Page 349 Fitness Function......Page 350 Experimental Validation......Page 351 References......Page 354 Introduction......Page 356 Related Work......Page 357 Curiosity and Discovery Instincts......Page 359 Experimental Validation......Page 361 Discussion and Perspectives......Page 364 References......Page 365 Introduction......Page 366 Evolution of Artificial Neural Network Designs......Page 367 The Neuro-genetic Approach......Page 368 Crossover Operator......Page 369 Experiments and Results......Page 372 References......Page 374 Introduction......Page 376 Reinforcement Learning and Scalable Go......Page 377 Indirect Encodings and HyperNEAT......Page 378 Approach: HyperNEAT in Go......Page 379 Substrate Extrapolation......Page 380 Experiment......Page 381 Results......Page 382 Discussion and Future Work......Page 383 References......Page 384 Introduction......Page 386 Approximate Ranking......Page 387 Rank-Based Surrogate Model with Rank-SVMs......Page 388 From CMA-ES to Rank-SVM Kernel......Page 389 Overview of ACM-ES......Page 390 Results and Discussion......Page 392 Conclusion and Perspectives......Page 394 References......Page 395 Introduction......Page 396 Evolutionary Clustering......Page 397 Coevolutionary Approach......Page 398 Empirical Analysis......Page 399 Evaluation Data Sets......Page 400 Results......Page 402 Conclusions......Page 404 References......Page 405 Introduction......Page 406 Uncountably Many-Objective Feature Selection......Page 407 Dominance and Crowding......Page 408 Implementation......Page 409 Experimentation......Page 411 Results......Page 412 Discussion......Page 414 References......Page 415 Genome-Wide Association Studies, Complex Disease, and Epistasis......Page 416 Grammatical Evolution Neural Networks (GENN) and Domain Knowledge......Page 417 Genetic Data Simulation with genomeSIMLA......Page 418 Domain Knowledge......Page 419 GENN and Incorporation of Domain Knowledge......Page 420 Results......Page 421 Discussion......Page 422 References......Page 423 Introduction......Page 426 Learning Classifier Systems......Page 428 System Evaluations......Page 429 Parameter Sweep......Page 430 Pittsburgh LCS Evaluations......Page 431 Discussion and Conclusions......Page 433 References......Page 435 Introduction......Page 436 Standard PET Reconstruction Algorithms......Page 437 Varying Population Size Scheme in a Cooperative Co-evolution Algorithm......Page 438 Threshold Selection......Page 439 Dual Mutation......Page 440 Experimental Setup......Page 441 Mitosis......Page 442 Initialisation of Flies on LORs......Page 443 References......Page 444 Introduction......Page 446 K2 Algorithm and K2-Based Search and Score......Page 447 Experiments......Page 448 Results and Discussion......Page 450 References......Page 454 Introduction......Page 456 Credit Default Swap Background......Page 457 CDS Pricing Challenge......Page 458 CGP Model Modification......Page 460 Experimental Datasets, Settings and Objectives......Page 461 Results......Page 462 Conclusions......Page 464 References......Page 465 Introduction and Related Work......Page 467 Ring-Based (Meta-)Cooperative Model......Page 468 The ToSP......Page 469 Computational Results......Page 471 Conclusions......Page 474 References......Page 475 Introduction......Page 477 Spatial Distribution......Page 478 Game Basic Strategies......Page 479 Games and Results......Page 481 IPD-Possessor Game......Page 482 IPD-Possessor-Trader Game......Page 484 Conclusions......Page 485 References......Page 486 Introduction......Page 487 Related Work......Page 488 Overview......Page 489 Decoding Heuristics......Page 491 Experimental Results......Page 492 Feasibility and Optimality......Page 493 Effects of Number of Heuristics in a Set......Page 494 References......Page 495 Motivation......Page 497 EMAS Architecture and Behavior......Page 498 EMAS Dynamics......Page 501 Sample Actions and Asymptotic Behavior......Page 503 References......Page 505 Introduction......Page 507 The Multi-start Pareto Local Search Algorithm (PLS)......Page 508 Iterated Pareto Local Search (IPLS)......Page 509 Iterated PLS for Multi-objective QAPs......Page 510 Experimental Results......Page 511 References......Page 516 Introduction......Page 518 Preliminaries......Page 519 Hyper-Heuristics for Sports Scheduling......Page 521 Experimental Results......Page 523 Conclusion......Page 525 References......Page 526 Introduction......Page 528 Markov Clustering Algorithm......Page 530 Interpretation of MCL Clustering as Dependency Models......Page 531 Dependency Structure Building and Sampling......Page 532 The Markov Clustering EDA......Page 533 Numerical Results......Page 534 Conclusions and Future Work......Page 535 References......Page 536 Introduction......Page 538 Our Multiobjective Memetic Algorithm......Page 540 Variants of Our Multiobjective Memetic Algorithm......Page 541 Computational Experiments......Page 542 Conclusions......Page 546 References......Page 547 Introduction......Page 548 Game-Theoretical Model......Page 549 The Secure and Task Abortion Aware Game......Page 550 Genetic-Based Metaheuristics for Solving the Game......Page 553 Experimental Analysis......Page 554 References......Page 557 Introduction......Page 558 Problem Definition and Notations......Page 559 Selective Routes Exchange Crossover......Page 560 Generation of the Initial Population......Page 563 Analysis of Performance......Page 564 Comparisons with Other Algorithms......Page 565 References......Page 566 Introduction......Page 568 Meta Heuristic......Page 569 Ant Based Hyper Heuristic with Space Reduction......Page 570 Experimental Results: A Case Study of the p-Median Problem......Page 573 References......Page 576 Introduction......Page 578 Main Scheme and Initial Population......Page 579 Combination Operators......Page 580 Computational Results......Page 582 Analysis......Page 583 Population Entropy and Distance......Page 584 Tradeoff between Intensification and Diversification......Page 585 Conclusions......Page 586 References......Page 587 Introduction......Page 588 Generalized Partition Crossover......Page 589 GPX with Local Search......Page 591 The Algorithms: Descriptions and Comparisons......Page 592 Comparisons: The Hybrid GA with GPX versus Chained-LK......Page 593 The Power of a Population......Page 595 Where Are the Global Edges?......Page 596 References......Page 597 Introduction......Page 598 Previous Related Work......Page 599 The Multi-objective Meta-model Assisted Memetic Algorithm......Page 600 Discussion of Results......Page 604 References......Page 606 Introduction......Page 608 Preliminaries......Page 609 General Results on Optimal μ-Distributions in 3-Objective Problems......Page 611 Geometrical Properties of the Hypervolume Contributions of Single Solutions in 3-Objective Problems......Page 612 Fronts for Which It Is Impossible to Obtain the Extreme Points......Page 614 Conclusions......Page 616 References......Page 617 Introduction......Page 619 Single-Objective Optimization with the (1+1)-EA......Page 620 Multi-objective Optimization with the SMS-EMOA......Page 621 (1+1)-SMS-EMOA on 2-Objective Problems......Page 622 (1+1)-SMS-EMOA beyond Two Objectives......Page 625 Sub-linear Convergence Rates......Page 626 Conclusions......Page 627 References......Page 628 Introduction......Page 629 Preliminaries......Page 631 Multiplicative Approximation......Page 632 Additive Approximation......Page 634 References......Page 637 Introduction......Page 639 Evolutionary Multiobjective Optimization (EMOA)......Page 640 Selection Schemes......Page 641 Evolutionary Algorithms with Heuristic......Page 642 The EMOA Selection Operator......Page 644 The EMOA Heuristic......Page 645 Asymptotic Features......Page 646 References......Page 647 Introduction......Page 649 Natural Evolution Strategies......Page 650 An Elitist Variant for the NES Family......Page 652 Multi-objective NES......Page 654 Experimental Evaluation of MO-NES......Page 655 Conclusion......Page 657 References......Page 658 Introduction......Page 659 Notations......Page 660 An Example......Page 661 Framework of MEACO......Page 662 IntervalOpt......Page 664 Experimental Results......Page 665 References......Page 667 Introduction......Page 669 Average Ranking......Page 670 Grid Setting......Page 671 Layering Selection......Page 672 Experimental Setup and Results......Page 674 Comparative Experiment......Page 675 Conclusions......Page 677 References......Page 678 Introduction......Page 679 General Idea of the Partitioning Framework......Page 680 A New Partition Strategy......Page 681 Partitioning Using Conflict Information......Page 682 DTLZ5($I,M$): Conflict Known $a Priori$......Page 683 Effect of the Size of the Subspaces......Page 685 Knapsack Problem: Unknown Conflict $a Priori$......Page 686 Conclusions and Future Work......Page 687 References......Page 688 Introduction......Page 689 Problem and Algorithm......Page 690 Analysis......Page 692 References......Page 698 Introduction......Page 699 General Concepts of Path Relinking......Page 700 Initial, Initiating and Guiding Solutions......Page 701 Path Generation and Selection......Page 702 Performance Varying the Number of Objectives and Selection......Page 703 Performance Varying the Levels of Epistastic Interactions......Page 706 References......Page 708 Introduction......Page 709 Equitable Efficiency......Page 710 Problem Formulation......Page 712 Classical and Evolutionary Solution Approaches......Page 713 Simulation Results......Page 714 References......Page 718 The RHS Algorithm as a Markov Chain......Page 719 The Transition Matrix of a Genetic Algorithm......Page 721 Stopping Criteria for a Genetic Algorithm......Page 722 References......Page 728 Motivation......Page 729 Background and Notation......Page 730 Measuring Diversity–Approaches in Biology and in EAs......Page 731 Optimizing Diversity – A Novel Set-Based Algorithm......Page 733 Experimental Results......Page 735 Conclusions......Page 737 References......Page 738 Introduction......Page 740 Single-Objective Optimization Based on EI......Page 741 Multi-objective Optimization Based on EI......Page 742 Analysis and Evaluation......Page 743 Conclusions and Outlook......Page 748 References......Page 749 Introduction......Page 750 Preliminaries......Page 751 DE vs. SBX on CEC 2007 Problems......Page 752 DE vs. SBX on Aerodynamic Problems......Page 756 References......Page 758 Author Index ......Page 761