| |
| |
| |
| Introduction | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| The Main Evolutionary Computing Metaphor | |
| |
| |
| |
| Brief History | |
| |
| |
| |
| The Inspiration from Biology | |
| |
| |
| |
| Darwinian Evolution | |
| |
| |
| |
| Genetics | |
| |
| |
| |
| Evolutionary Computing: Why? | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| What is an Evolutionary Algorithm? | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| What is an Evolutionary Algorithm? | |
| |
| |
| |
| Components of Evolutionary Algorithms | |
| |
| |
| |
| Representation (Definition of Individuals) | |
| |
| |
| |
| Evaluation Function (Fitness Function) | |
| |
| |
| |
| Population | |
| |
| |
| |
| Parent Selection Mechanism | |
| |
| |
| |
| Variation Operators | |
| |
| |
| |
| Survivor Selection Mechanism (Replacement) | |
| |
| |
| |
| Initialisation | |
| |
| |
| |
| Termination Condition | |
| |
| |
| |
| Example Applications | |
| |
| |
| |
| The Eight-Queens Problem | |
| |
| |
| |
| The Knapsack Problem | |
| |
| |
| |
| Working of an Evolutionary Algorithm | |
| |
| |
| |
| Evolutionary Computing and Global Optimisation | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Genetic Algorithms | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Introductory Example | |
| |
| |
| |
| Representation of Individuals | |
| |
| |
| |
| Binary Representations | |
| |
| |
| |
| Integer Representations | |
| |
| |
| |
| Real-Valued or Floating-Point Representation | |
| |
| |
| |
| Permutation Representations | |
| |
| |
| |
| Mutation | |
| |
| |
| |
| Mutation for Binary Representations | |
| |
| |
| |
| Mutation Operators for Integer Representations | |
| |
| |
| |
| Mutation Operators for Floating-Point Representations | |
| |
| |
| |
| Mutation Operators for Permutation Representations | |
| |
| |
| |
| Recombination | |
| |
| |
| |
| Recombination Operators for Binary Representations | |
| |
| |
| |
| Recombination Operators for Integer Representations | |
| |
| |
| |
| Recombination Operators for Floating-Point Representations | |
| |
| |
| |
| Recombination Operators for Permutation Representations | |
| |
| |
| |
| Multiparent Recombination | |
| |
| |
| |
| Population Models | |
| |
| |
| |
| Parent Selection | |
| |
| |
| |
| Fitness Proportional Selection | |
| |
| |
| |
| Ranking Selection | |
| |
| |
| |
| Implementing Selection Probabilities | |
| |
| |
| |
| Tournament Selection | |
| |
| |
| |
| Survivor Selection | |
| |
| |
| |
| Age-Based Replacement | |
| |
| |
| |
| Fitness-Based Replacement | |
| |
| |
| |
| Example Application: Solving a Job Shop Scheduling Problem | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Evolution Strategies | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Introductory Example | |
| |
| |
| |
| Representation | |
| |
| |
| |
| Mutation | |
| |
| |
| |
| Uncorrelated Mutation with One Step Size | |
| |
| |
| |
| Uncorrelated Mutation with n Step Sizes | |
| |
| |
| |
| Correlated Mutations | |
| |
| |
| |
| Recombination | |
| |
| |
| |
| Parent Selection | |
| |
| |
| |
| Survivor Selection | |
| |
| |
| |
| Self-Adaptation | |
| |
| |
| |
| Example Applications | |
| |
| |
| |
| The Ackley Function | |
| |
| |
| |
| Subjective Evolution of Colour Mixes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Evolutionary Programming | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Introductory Example | |
| |
| |
| |
| Representation | |
| |
| |
| |
| Mutation | |
| |
| |
| |
| Recombination | |
| |
| |
| |
| Parent Selection | |
| |
| |
| |
| Survivor Selection | |
| |
| |
| |
| Example Application | |
| |
| |
| |
| The Ackley Function | |
| |
| |
| |
| Evolving Checkers Players | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Genetic Programming | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Introductory Example | |
| |
| |
| |
| Representation | |
| |
| |
| |
| Mutation | |
| |
| |
| |
| Recombination | |
| |
| |
| |
| Parent Selection | |
| |
| |
| |
| Survivor Selection | |
| |
| |
| |
| Initialisation | |
| |
| |
| |
| Bloat in Genetic Programming | |
| |
| |
| |
| Problems Involving ""Physical"" Environments | |
| |
| |
| |
| Example Application: Symbolic Regression | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Learning Classifier Systems | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Introductory Example | |
| |
| |
| |
| General Background | |
| |
| |
| |
| ZCS: A ""Zeroth-Level"" Classifier System | |
| |
| |
| |
| XCS | |
| |
| |
| |
| Motivation | |
| |
| |
| |
| Description | |
| |
| |
| |
| Extensions | |
| |
| |
| |
| Example Applications | |
| |
| |
| |
| Modelling Financial Market Traders | |
| |
| |
| |
| A Multistep Problem | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Parameter Control in Evolutionary Algorithms | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Examples of Changing Parameters | |
| |
| |
| |
| Changing the Mutation Step Size | |
| |
| |
| |
| Changing the Penalty Coefficients | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Classification of Control Techniques | |
| |
| |
| |
| What is Changed? | |
| |
| |
| |
| How are Changes Made? | |
| |
| |
| |
| What Evidence Informs the Change? | |
| |
| |
| |
| What is the Scope of the Change? | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Examples of Varying EA Parameters | |
| |
| |
| |
| Representation | |
| |
| |
| |
| Evaluation function | |
| |
| |
| |
| Mutation | |
| |
| |
| |
| Crossover | |
| |
| |
| |
| Selection | |
| |
| |
| |
| Population | |
| |
| |
| |
| Varying Several Parameters Simultaneously | |
| |
| |
| |
| Discussion | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Multimodal Problems and Spatial Distribution | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Introduction: Multimodal Problems and the Need for Diversity | |
| |
| |
| |
| Multimodal Problems | |
| |
| |
| |
| Genetic Drift | |
| |
| |
| |
| Biological Motivations and Algorithmic Approaches | |
| |
| |
| |
| Algorithmic Versus Genetic Versus Solution Space | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Implicit Measures | |
| |
| |
| |
| Multiple Populations in Tandem: Island Model EAs | |
| |
| |
| |
| Spatial Distribution Within One Population: Diffusion Model EAs | |
| |
| |
| |
| Automatic Speciation Using Mating Restrictions | |
| |
| |
| |
| Explicit Diversity Maintenance | |
| |
| |
| |
| Fitness Sharing | |
| |
| |
| |
| Crowding | |
| |
| |
| |
| Multiobjective Evolutionary Algorithms | |
| |
| |
| |
| Multiobjective Optimisation Problems | |
| |
| |
| |
| Dominance and Pareto Optimality | |
| |
| |
| |
| EA Approaches to Multiobjective Optimisation | |
| |
| |
| |
| Example Application: Distributed Coevolution of Job Shop Schedules | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Hybridisation with Other Techniques: Memetic Algorithms | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Motivation for Hybridising EAs | |
| |
| |
| |
| A Brief Introduction to Local Search | |
| |
| |
| |
| Lamarckianism and the Baldwin Effect | |
| |
| |
| |
| Structure of a Memetic Algorithm | |
| |
| |
| |
| Heuristic or Intelligent Initialisation | |
| |
| |
| |
| Hybridisation Within Variation Operators: Intelligent Crossover and Mutation | |
| |
| |
| |
| Local Search Acting on the Output from Variation Operators | |
| |
| |
| |
| Hybridisation During Genotype to Phenotype Mapping | |
| |
| |
| |
| Design Issues for Memetic Algorithms | |
| |
| |
| |
| Preservation of Diversity | |
| |
| |
| |
| Choice of Operators | |
| |
| |
| |
| Use of Knowledge | |
| |
| |
| |
| Example Application: Multistage Memetic Timetabling | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Theory | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Competing Hyperplanes in Binary Spaces: the Schema Theorem | |
| |
| |
| |
| What is a Schema? | |
| |
| |
| |
| Holland's Formulation for the SGA | |
| |
| |
| |
| Schema-Based Analysis of Variation Operators | |
| |
| |
| |
| Walsh Analysis and Deception | |
| |
| |
| |
| Criticisms and Recent Extensions of the Schema Theorem | |
| |
| |
| |
| Gene Linkage: Identifying and Recombining Building Blocks | |
| |
| |
| |
| Dynamical Systems | |
| |
| |
| |
| Markov Chain Analysis | |
| |
| |
| |
| Statistical Mechanics Approaches | |
| |
| |
| |
| Reductionist Approaches | |
| |
| |
| |
| Analysing EAs in Continuous Search Spaces | |
| |
| |
| |
| No Free Lunch Theorems | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Constraint Handling | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Constrained Problems | |
| |
| |
| |
| Free Optimisation Problems | |
| |
| |
| |
| Constraint Satisfaction Problems | |
| |
| |
| |
| Constrained Optimisation Problems | |
| |
| |
| |
| Two Main Types of Constraint Handling | |
| |
| |
| |
| Ways to Handle Constraints in EAs | |
| |
| |
| |
| Penalty Functions | |
| |
| |
| |
| Repair Functions | |
| |
| |
| |
| Restricting Search to the Feasible Region | |
| |
| |
| |
| Decoder Functions | |
| |
| |
| |
| Application Example: Graph Three-Colouring | |
| |
| |
| |
| Indirect Approach | |
| |
| |
| |
| Mixed Mapping - Direct Approach | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Special Forms of Evolution | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| Coevolution | |
| |
| |
| |
| Cooperative coevolution | |
| |
| |
| |
| Competitive coevolution | |
| |
| |
| |
| Example Application: Coevolutionary Constraint lSatisfaction | |
| |
| |
| |
| Interactive Evolution | |
| |
| |
| |
| Optimisation, Design, Exploration | |
| |
| |
| |
| Interactive Evolutionary Design and Art | |
| |
| |
| |
| Example Application: The Mondriaan Evolver | |
| |
| |
| |
| Nonstationary Function Optimisation | |
| |
| |
| |
| Algorithmic Approaches | |
| |
| |
| |
| Selection and Replacement Policies | |
| |
| |
| |
| Example Application: Time-Varying Knapsack Problem | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Working with Evolutionary Algorithms | |
| |
| |
| |
| Aims of this Chapter | |
| |
| |
| |
| What Do You Want an EA to Do? | |
| |
| |
| |
| Performance Measures | |
| |
| |
| |
| Different Performance Measures | |
| |
| |
| |
| Peak versus Average Performance | |
| |
| |
| |
| Test Problems for Experimental Comparisons | |
| |
| |
| |
| Using Predefined Problem Instances | |
| |
| |
| |
| Using Problem Instance Generators | |
| |
| |
| |
| Using Real-World Problems | |
| |
| |
| |
| Example Applications | |
| |
| |
| |
| Bad Practice | |
| |
| |
| |
| Better Practice | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Recommended Reading for this Chapter | |
| |
| |
| |
| Summary | |
| |
| |
| |
| What Is in This Book? | |
| |
| |
| |
| What Is Not in This Book? | |
| |
| |
| |
| Gray Coding | |
| |
| |
| |
| Test Functions | |
| |
| |
| |
| Unimodal Functions | |
| |
| |
| |
| OneMax | |
| |
| |
| |
| The Sphere Model | |
| |
| |
| |
| Royal Road Function | |
| |
| |
| |
| Multimodal Functions | |
| |
| |
| |
| Ackley Function | |
| |
| |
| |
| Schwefel's function | |
| |
| |
| |
| Generalized Rastrigin's function | |
| |
| |
| |
| Deb's Deceptive 4-Bit Function | |
| |
| |
| |
| Randomised Test Function Generators | |
| |
| |
| |
| Kauffman's NK Landscapes | |
| |
| |
| |
| NKC Landscapes | |
| |
| |
| |
| Random L-SAT | |
| |
| |
| References | |
| |
| |
| Index | |