Foundations of Genetic Algorithms: 9th International Workshop, FOGA 2007, Mexico City, Mexico, January 8-11, 2007, Revised Selected Papers (Lecture Notes in Computer Science, 4436)

Readers will find here a fascinating text that is the thoroughly refereed post-proceedings of the 9th Workshop on the Foundations of Genetic Algorithms, FOGA 2007, held in Mexico City in January 2007. The 11 revised full papers presented were carefully reviewed and selected during two rounds of reviewing and improvement from 22 submissions. The papers address all current topics in the field of theoretical evolutionary computation and also depict the continuing growth in interactions with other fields such as mathematics, physics, and biology Title Page Preface Organization Table of Contents Inbreeding Properties of Geometric Crossover and Non-geometric Recombinations Introduction Geometric Framework Geometric Preliminaries Geometric Crossover Definition Notable Geometric Crossovers Geometric Crossover Landscape Interpretations of the Definition of Geometric Crossover Functional Interpretation Abstract Interpretation Existential Interpretation Geometric Crossover Classes Inbreeding Properties of Geometric Crossover Relation with Forma Analysis Non-geometric Crossovers Possibility of a General Theory of Evolutionary Algorithms Conclusions and Future Work Just What Are Building Blocks? Introduction A Short History of “Building Blocks” What Do Exact Models Tell Us? The Landscapes The Metrics What’s the Point? Results Benchmarks Dependency on Landscape Modularity Finite Population Effects Conclusions Sufficient Conditions for Coarse-Graining Evolutionary Dynamics Introduction The Promise of Coarse-Graining Some Previous Coarse-Graining Results Structure of This Paper Mathematical Preliminaries Formalization of a Class of Coarse-Grainings Global Coarsenablity of Variation Limitwise Semi-coarsenablity of Selection Limitwise Coarsenablity of Evolution Sufficient Conditions for Coarse-Graining IPGA Dynamics Conclusion References Appendix On the Brittleness of Evolutionary Algorithms Introduction Definitions and Notation Design and Analysis of a Pessimistic Fitness Model for Linear Functions Analysis of PO-EA Conclusions Mutative Self-adaptation on the Sharp and Parabolic Ridge Introduction Modeling the Evolutionary Dynamics: The Evolution Equations Preliminaries Self-adaptation on the Sharp and Parabolic Ridge The System in $\zeta^*$ and $R$ The Parabolic Ridge The Sharp Ridge Conclusion and Outlook References The Density Function of an Offspring The Progress Rates The Self-adaptation Response The First Order Self-adaptation Response Deriving the Derivatives Genericity of the Fixed Point Set for the Infinite Population Genetic Algorithm Introduction The Infinite Population Genetic Algorithm Transversality: Background and Terminology Proof of Main Results Conclusions Neighborhood Graphs and Symmetric Genetic Operators Introduction Notation Neighborhood Structures Neighborhood Operators Transitive Automorphism Groups Implementation Binary Crossover Mutation Conclusion Decomposition of Fitness Functions in Random Heuristic Search Introduction Algorithmic-Decomposition of the Fitness Function Greedy Criteria for Performance Distance and Performance Number of Ties and Entropy Approximation of the Performance Function A First Order Approximation A Predictive Measure of Problem Difficulty Indication for the Expected Entropy Empirical Evaluation Exhaustive Analysis Estimation of Problem Hardness Conclusions On the Effects of Bit-Wise Neutrality on Fitness Distance Correlation, Phenotypic Mutation Rates and Problem Hardness Introduction Previous Work Bitwise Neutrality Fitness Distance Correlation Definition Test Problems $fdc$ in the Absence of Neutrality $fdc$ in the Presence of Bitwise Neutrality $fdc$ for OneMax with Bitwise Neutrality $fdc$ Under Parity $fdc$ Under Truth Table $fdc$ Under Majority Phenotypic Mutation Rates Results and Analysis Conclusions Continuous Optimisation Theory Made Easy? Finite-Element Models of Evolutionary Strategies, Genetic Algorithms and Particle Swarm Optimizers Introduction Discretisation FEM Approximation of Exact Markov Chain Exact Markov Model of Approximate Optimiser Evolutionary Strategy Model Particle Swarm Optimisation Model Background Model of “bare bones” PSO Real-Valued Genetic Algorithm Model Success Probability and Expected Run Time of Continuous Optimisers Experimental Results Evolutionary Strategies Bare-Bones PSO Real-Valued GA Two-Dimensional Problems: Sphere and Rastrigin Conclusions Saddles and Barrier in Landscapes of Generalized Search Operators Introduction Search Operators and Generalized Topology Mutation and Move Sets Recombination Spaces Closure Functions Continuity Connectedness Topological Connectedness Productive Connectedness Path-Connectedness Basins and Barriers Discussion Author Index This book constitutes the thoroughly refereed post-proceedings of the 9th Workshop on the Foundations of Genetic Algorithms, FOGA 2007, held in Mexico City, Mexico in January 2007. The 11 revised full papers presented were carefully reviewed and selected during two rounds of reviewing and improvement from 22 submissions. The papers address all current topics in the field of theoretical evolutionary computation including evolution strategies, evolutionary programming, and genetic programming, and also depict the continuing growth in interactions with other fields such as mathematics, physics, and biology