Introduction to Evolutionary Algorithms

Description

Cover Page Other titles published in this series Title Page ISBN 184996128X Preface Contents Part I Evolutionary Algorithms Chapter 1 - Introduction 1.1 What Are Evolutionary Algorithms Used For? 1.2 What Are Evolutionary Algorithms? Suggestions for Further Reading References Chapter 2 - Simple Evolutionary Algorithms 2.1 Introductory Remarks 2.2 Simple Genetic Algorithm 2.2.1 An Optimization Problem 2.2.2 Representation and Evaluation 2.2.3 Initialization 2.2.4 Selection 2.2.5 Variation Operators 2.2.6 Simple Genetic Algorithm Infrastructure 2.3 Evolution Strategy and Evolutionary Programming 2.3.1 Evolution Strategy 2.3.2 Evolutionary Programming 2.4 Direction-based Search 2.4.1 Deterministic Direction-based Search 2.4.1.1 Simplex Search 2.4.2 Random Direction-based Search 2.4.2.1 Scatter Search 2.4.2.2 Differential Evolution 2.5 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Chapter 3 - Advanced Evolutionary Algorithms 3.1 Problems We Face 3.2 Encoding and Operators 3.2.1 Binary Code and Related Operators 3.2.2 Real Code and Related Operators 3.2.2.1 Real Code Crossover Without Preference 3.2.2.2 Real Code Crossover with Preference 3.2.2.3 Real Code MutationWithout Explicit Direction 3.2.2.4 Directional Mutation 3.2.3 Other Topics on Code and Operators 3.3 Selection Methods 3.3.1 Dilemmas for Selection Methods 3.3.2 Proportional Selection 3.3.3 Fitness Scaling and Transferral 3.3.4 Ranking 3.3.5 Tournament Selection 3.4 Replacement and Stop Criteria 3.4.1 Replacement 3.4.2 Stop Criteria 3.5 Parameter Control 3.5.1 Strategy Parameter Setting 3.5.2 Examples of Variation Operator Control 3.5.2.1 Conditional Variation Operators 3.5.2.2 Adaptive Control on the Intensity of Assortative Mating 3.5.2.3 Fuzzy Logic Controller for Pc and Pm 3.5.2.4 Adaptive Control on Mutation Types 3.5.2.5 Evolutionary Gradient Search 3.5.2.6 Covariance Matrix Adaptation 3.5.2.7 Self-adaptive Crossover Probability Control in Differential Evolution 3.5.3 Examples of popsize Control 3.5.3.1 Saw-tooth-type Deterministic Control on popsize 3.5.3.2 Adaptive Control on popsize Using an Age Concept 3.5.3.3 Population Competition-based Adaptive Control on popsize 3.6 Performance Evaluation of Evolutionary Algorithms 3.6.1 General Discussion on Performance Evaluation 3.6.1.1 No Free Lunch Theorem for Optimization 3.6.1.2 Considerations on Benchmark Problems 3.6.2 Performance Evaluation and Comparison 3.6.2.1 Performance Indices of Numerical Optimization 3.6.2.2 Performance Description and Comparison of Evolutionary Algorithms 3.7 Brief Introduction to Other Topics 3.7.1 Coevolution 3.7.2 Memetic Algorithms 3.7.3 Hyper-heuristics 3.7.4 Handling Uncertain Environments 3.8 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Part II Dealing with Complicated Problems Chapter 4 - Constrained Optimization 4.1 Introduction 4.1.1 Constrained Optimization 4.1.2 Constrained Optimization Evolutionary Algorithms 4.2 Feasibility Maintenance 4.2.1 Genetic Algorithm for Numerical Optimization of Constrained Problems 4.2.2 Homomorphous Mappings 4.3 Penalty Function 4.3.1 Static Penalty Function 4.3.2 Dynamic Penalty Function 4.3.3 Adaptive Penalty Function 4.3.3.1 Adaptive Segregational Constraint Handling Evolutionary Algorithm 4.3.4 Self-adaptive Penalty Function 4.4 Separation of Constraint Violation and Objective Value 4.4.1 Constrained Optimization Evolutionary Algorithms Based on Rank 4.4.1.1 Stochastic Ranking 4.4.1.2 Dynamic Stochastic Ranking in Multimember Differential Evolution 4.4.1.3 Constrained Optimization Evolutionary Algorithm Based on Multiple Ranks 4.4.2 Simple Multimembered Evolution Strategy 4.4.3 α Constrained Method 4.5 Performance Evaluation of Constrained Optimization Evolutionary Algorithms 4.5.1 Benchmark Problems 4.5.2 Performance Indices 4.6 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Chapter 5 - Multimodal Optimization 5.1 Problems We Face 5.1.1 Multimodal Problems 5.1.2 Niche, Species, and Speciation 5.2 Sequential Niche 5.3 Fitness Sharing 5.3.1 Standard Fitness Sharing 5.3.2 Clearing Procedure 5.3.3 Clustering for Speciation 5.3.4 Dynamic Niche Sharing 5.3.5 Coevolutionary Shared Niching 5.4 Crowding 5.4.1 Deterministic Crowding 5.4.2 Restricted Tournament Selection 5.4.3 Species Conserving Genetic Algorithm 5.5 Performance Indices for Multimodal Optimization 5.6 Application Example 5.7 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Chapter 6 - Multiobjective Optimization 6.1 Introduction 6.1.1 Problems We Face 6.1.2 Terminologies 6.1.3 Why Are Evolutionary Algorithms Good at Multiobjective Optimization Problems? 6.2 Preference-based Approaches 6.2.1 Weight Sum Method 6.2.1.1 Fixed Weight Sum Method 6.2.1.2 Random Weight Sum Method 6.2.1.3 Adaptive Weight Sum Method 6.2.2 Compromise Method 6.2.3 Goal Programming Method 6.3 Vector-evaluated Genetic Algorithm 6.4 Considerations for Designing Multiobjective Evolutionary Algorithms 6.4.1 Quality 6.4.1.1 Quality Measure Approaches Considering Global Information 6.4.1.2 Quality Measure Approaches Considering Local Information 6.4.2 Distribution 6.4.2.1 Distribution Measure Approaches Using Individual Numbers 6.4.2.2 Distribution Measure Approaches Using Distance 6.5 Classical Multiobjective Evolutionary Algorithms 6.5.1 Nondominated Sorting Genetic Algorithm II 6.5.2 Strength Pareto Evolutionary Algorithm 2 and Pareto Envelope-based Selection Algorithm 6.5.2.1 Strength Pareto Evolutionary Algorithm 2 6.5.2.2 Pareto Envelope-Based Selection Algorithm 6.5.3 Pareto Archived Evolution Strategy 6.5.4 Micro-GA for Multiobjective Optimization 6.6 Cutting Edges of Multiobjective Evolutionary Algorithms 6.6.1 Expanding Single-objective Evolutionary Algorithms into Multiobjective Optimization Problems 6.6.1.1 Embedding Differential Evolution into NSGA-II 6.6.1.2 Multiobjective Scatter Search 6.6.1.3 Cooperative Coevolutionary Multiobjective Optimization 6.6.2 Archive Maintenance 6.6.2.1 Adaptive Archive Maintenance Based on Hyperbox 6.6.2.2 Archive Maintenance Based on ε -Dominance 6.6.3 Rebirth from the Ashes 6.6.3.1 Rebirth of VEGA 6.6.3.2 Rebirth of Weight Sum Method 6.7 Performance Evaluation of Multiobjective Evolutionary Algorithms 6.7.1 Benchmark Problems 6.7.2 Performance Indices 6.7.2.1 Cardinality-based Performance Indices 6.7.2.2 Volume-based Performance Indices 6.7.2.3 Distance-based Performance Indices 6.7.2.4 Attainment Surface-based Performance Indices 6.7.2.5 Distribution Performance Indices 6.7.2.6 Spread Performance Indices 6.7.2.7 Distribution and Spread Performance Indices 6.8 Objectives vs. Constraints 6.8.1 Handling Constraints in Multiobjective Optimization Problems 6.8.2 Multiobjective Evolutionary Algorithms for Constraint Handling 6.8.2.1 Transforming Constrained Problems into (1+k)-objective Problems 6.8.2.2 Transforming Constrained Problems into Two-objective Problems 6.9 Application Example 6.10 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Chapter 7 - Combinatorial Optimization 7.1 Introduction 7.1.1 Combinatorial Optimization 7.1.2 NP-complete and NP-hard Problems 7.1.3 Evolutionary Algorithms for Combinatorial Optimization 7.2 Knapsack Problem 7.2.1 Problem Description 7.2.2 Evolutionary Algorithms for Knapsack Problem 7.3 Traveling Salesman Problem 7.3.1 Problem Description 7.3.2 Heuristic Methods for Traveling Salesman Problem 7.3.2.1 Construction Methods 7.3.2.2 Local Search Methods 7.3.3 Evolutionary Algorithm Code Schemes for Traveling Salesman Problem 7.3.3.1 Edge Code 7.3.3.2 Binary Code 7.3.3.3 Random Key Code 7.3.3.4 Path Code 7.3.3.5 Adjacent Code 7.3.3.6 Ordinal Code 7.3.3.7 Matrix Code 7.3.4 Variation Operators for Permutation Code 7.3.4.1 Mutation Operators 7.3.4.2 Crossover Operators 7.4 Job-shop Scheduling Problem 7.4.1 Problem Description 7.4.2 Heuristic Methods for Job-shop Scheduling 7.4.2.1 Construction Methods 7.4.2.2 Local Search Method 7.4.3 Evolutionary Algorithm Code Schemes for Job-shop Scheduling 7.4.3.1 Direct Approaches 7.4.3.2 Indirect Approaches 7.5 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Part III Brief Introduction to Other Evolutionary Algorithms Chapter 8 - Swarm Intelligence 8.1 Introduction 8.2 Ant Colony Optimization 8.2.1 Rationale Behind Ant Colony Optimization 8.2.2 Discrete Ant Colony Optimization 8.2.2.1 Ant System for Traveling Salesman Problem 8.2.2.2 Ant Colony System for Traveling Salesman Problem 8.2.2.3 Ant System for Job-shop Scheduling Problem 8.2.3 Continuous Ant Colony Optimization 8.3 Particle Swarm Optimization 8.3.1 Organic Particle Swarm Optimization 8.3.2 Neighbor Structure and Related Extensions 8.3.2.1 Constriction Particle Swarm 8.3.2.2 Fully Informed Particle Swarm 8.3.2.3 Bare Bones Particle Swarm 8.3.3 Extensions from Organic Particle Swarm Optimization 8.4 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Chapter 9 - Artificial Immune Systems 9.1 Introduction 9.2 Artificial Immune System Based on Clonal Selection 9.2.1 Clonal Selection 9.2.2 Clonal Selection Algorithm 9.2.3 Artificial Immune System for Multiobjective Optimization Problems 9.3 Artificial Immune System Based on Immune Network 9.3.1 Immune Network Theory 9.3.2 Continuous Immune Network 9.3.3 Discrete Immune Network 9.4 Artificial Immune System Based on Negative Selection 9.4.1 File Protection by Negative Selection 9.4.2 Intrusion Detection by Negative Selection 9.5 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Chapter 10 - Genetic Programming 10.1 Introduction to Genetic Programming 10.1.1 The Difference Between Genetic Programming and Genetic Algorithms 10.1.2 Genetic Programming for Curve Fitting 10.1.2.1 Syntax Tree Code 10.1.2.2 Initialization 10.1.2.3 Evaluation 10.1.2.4 Variation Operators 10.2 Other Code Methods for Genetic Programming 10.2.1 Gene Expression Programming 10.2.2 Grammatical Evolution for Solving Differential Equations 10.3 Example of Genetic Programming for Knowledge Discovery 10.4 Summary Suggestions for Further Reading Exercises and Potential Research Projects References Appendix A - Benchmark Problems Benchmark Problems for Chap. 2 and Chap. 3 Benchmark Problems for Chap. 4 Benchmark Problems for Chap. 5 Benchmark Problems for Chap. 6 Benchmark Problems for Chap. 7 References Index Symbols A B C D E F G H I J K L M N O P R S T U V W Z