Preface
Acknowledgments
Contents
Acronyms
Part I Introduction and Fundamentals
1 Introduction
1.1 Optimization and Machine Learning
1.2 Optimization Problems
1.2.1 Mathematical Formulation
1.2.2 Continuous Optimization Versus Discrete Optimization
1.3 Optimization Algorithms
1.3.1 Deterministic Algorithms and Probabilistic Algorithms
1.3.2 Intelligent Optimization Techniques
References
2 Fundamentals
2.1 Fitness Landscapes
2.1.1 Solution Space
2.1.2 Objective Space
2.1.3 Neighbourhood
2.1.4 Global Optimum
2.1.5 Local Optimum
2.2 Properties of Fitness Landscape
2.2.1 Modality
2.2.2 Ruggedness
2.2.3 Deceptiveness
2.2.4 Neutrality
2.2.5 Separability
2.2.6 Scalability
2.2.7 Domino Convergence
2.2.8 Property Control, Analysis, and Visualization
2.3 Computational Complexity
2.3.1 Complexity Measures
2.3.1.1 Time Complexity
2.3.1.2 Space Complexity
2.3.1.3 Ways of Measures
2.3.1.4 Time Versus Space
2.3.2 P Versus NP Problem
References
3 Canonical Optimization Algorithms
3.1 Numerical Optimization Algorithms
3.1.1 Line Search
3.1.2 Steepest Descent Method
3.1.3 Newton Method
3.1.4 Conjugate Gradient Method
3.2 State Space Search
3.2.1 State Space
3.2.1.1 The Shortest Path Problem
3.2.1.2 The Travelling Salesman Problem
3.2.2 Uninformed Search
3.2.2.1 Breadth-First Search
3.2.2.2 Depth-First Search
3.2.2.3 Depth-Limited Search
3.2.3 Informed Search
3.2.3.1 Greedy Search
3.2.3.2 A* Search
3.2.3.3 Monte-Carlo Tree Search
3.3 Single-Solution-Based Random Search
3.3.1 Hill Climbing
3.3.2 Simulated Annealing
3.3.3 Iterated Local Search
3.3.4 Variable Neighborhood Search
References
Part II Evolutionary Computation Algorithms
4 Basics of Evolutionary Computation Algorithms
4.1 Introduction
4.1.1 Biological Evolution
4.1.2 Origin of Evolutionary Algorithms
4.1.3 Basic Evolutionary Processes
4.1.4 Developments
4.1.5 Related Resources
4.2 Solution Representation
4.2.1 Binary Representation
4.2.2 Integer Representation
4.2.3 Real-Valued Representation
4.2.4 Tree Representation
4.2.5 The Effect of Representation
4.3 Selection
4.3.1 Parents Selection
4.3.2 Survivor Selection
4.3.3 Selection Pressure
4.4 Reproduction
4.4.1 Mutation
4.4.2 Recombination
References
5 Popular Evolutionary Computation Algorithms
5.1 Genetic Algorithm
5.1.1 Basic Principle and Framework
5.1.2 Applications of Genetic Algorithms
5.2 Evolutionary Programming
5.2.1 The Emergence of Evolutionary Programming
5.2.2 The Classical Evolutionary Programming
5.2.2.1 Representation
5.2.2.2 Mutation
5.2.2.3 Selection
5.2.3 Framework and Parameter Settings
5.2.4 Recent Advances in Evolutionary Programming
5.3 Genetic Programming
5.3.1 Introduction
5.3.2 Genotype-Phenotype Mapping
5.3.2.1 Integer String Approach
5.3.2.2 Gene Expression Programming
5.3.3 Other Genome Structures
5.3.3.1 Linear GP
5.3.3.2 Graph-Based GP
5.3.4 Open Issues
5.3.4.1 Epistasis in GP
5.3.4.2 Correctness
5.3.4.3 All-or-Nothing
5.3.4.4 Non-functional Features of Algorithms
5.4 Particle Swarm Optimization
5.4.1 The Rise of Particle Swarm Optimization
5.4.2 Original Particle Swarm Optimization
5.4.3 Standard Particle Swarm Optimization
5.4.3.1 Initialization
5.4.3.2 Population Topology
5.4.3.3 Confinement
5.4.3.4 Velocity Updating
5.4.4 Recent Advances in Particle Swarm Optimization
5.4.4.1 Communication Topology
5.4.4.2 PSO with Diversity Maintenance
5.4.4.3 Adaptive PSO
5.4.4.4 Hybrid PSO
5.5 Differential Evolution
5.5.1 Introduction of Differential Evolution
5.5.1.1 Mutation
5.5.1.2 Crossover
5.5.1.3 Selection
5.5.2 Framework and Parameter Settings
5.5.3 Some Advances in Differential Evolution
5.5.3.1 Parameter Adaptation
5.5.3.2 Adaptation of Mutation Operators
5.5.3.3 New Mutation Operators
5.6 Evolution Strategy
5.6.1 Basic Evolution Strategy Paradigm
5.6.1.1 Parent Selection
5.6.1.2 Mutation
5.6.1.3 Mutation Step Size Control
5.6.1.4 Recombination
5.6.1.5 Survivor Selection
5.6.1.6 Canonical Self-Adaptation Evolution Strategy
5.6.2 Covariance Matrix Adaptation Evolution Strategy
5.6.2.1 Reproduction with Covariance Matrix
5.6.2.2 Covariance Matrix Adaptation
5.6.2.3 Complete Process of CMA-ES
5.6.2.4 Niching CMA-ES
5.7 Estimation of Distribution Algorithm
5.7.1 Standard Procedures
5.7.2 Discrete Versions
5.7.2.1 Univariate Factorizations
5.7.2.2 Bivariate Factorizations
5.7.2.3 Multivariate Factorizations
5.7.3 Continuous Versions
5.8 Ant Colony Optimization
5.8.1 Biological Inspiration
5.8.2 ACO Framework
5.8.2.1 Initialization
5.8.2.2 Solution Construction
5.8.2.3 Local Search
5.8.2.4 Pheromone Update
5.8.3 ACO Variants
5.8.3.1 Set of Update Solutions
5.8.3.2 Pheromone Update
5.8.4 Recent Advances
5.8.4.1 Dynamic Optimization
5.8.4.2 Multi-objective Optimization
5.8.4.3 Multimodal Optimization
5.8.4.4 Parallel ACO Implementations
References
Part III Optimization Techniques
6 Parameter Control and Policy Control
6.1 Parameter Control
6.1.1 Unary Parameter Control
6.1.1.1 Population Size Control
6.1.1.2 Operator Parameter Control
6.1.1.3 Problem-Related Parameter Control
6.1.2 Multi-parameter Control
6.1.3 Discussions
6.2 Policy Control
6.2.1 Operator Selection Control
6.2.2 Hyper-heuristics
6.2.3 Discussions
References
7 Exploitation Versus Exploration
7.1 Introduction
7.2 Exploitation and Exploration Methods
7.2.1 Iterative Methods
7.2.2 Single-Solution Meta-heuristics
7.2.3 Population-Based Meta-heuristics
7.3 Enhancing Exploration and Exploitation
7.3.1 Exploration Enhancement Methods
7.3.2 Exploitation Enhancement Methods
7.4 Balancing Exploration and Exploitation
7.4.1 Explicit Differentiation Methods
7.4.2 Population Diversity-Driven Methods
7.4.3 Non-overlapping Multi-population Methods
7.4.4 Space Partitioning-Based Methods
7.5 Discussions
References
8 Multimodal Optimization
8.1 Introduction
8.2 Niching Methods for Traditional EAs
8.2.1 Fitness Sharing
8.2.2 Restricted Tournament Selection
8.2.3 Clearing
8.2.4 Crowding
8.3 Niching Methods of Emerging EAs
8.3.1 DE with Neighbor Mutation
8.3.2 PSO with Restricted Communication Topology
8.4 Other Evolutionary Niching Methods
8.4.1 Multi-population
8.4.2 Multi-objective Selection
8.5 Challenges
References
Part IV Advanced Topics and Applications
9 Multi-objective Optimization
9.1 Introduction
9.1.1 Basic Concepts
9.1.2 Properties of PF
9.2 Multi-objective Evolutionary Algorithms
9.2.1 Domination-Based Algorithms
9.2.2 Indicator-Based Algorithms
9.2.3 Decomposition-Based Algorithms
9.3 Performance Evaluation
9.3.1 C Indicator
9.3.2 Generational Distance
9.3.3 Maximum Spread
9.3.4 Spacing
9.3.5 Inverted Generational Distance
9.3.6 Hypervolume
9.4 Visualization in the Objective Space
9.4.1 Visualization Using Original Values
9.4.1.1 Scatterplot Matrix
9.4.1.2 Parallel Coordinate
9.4.1.3 Heat Maps
9.4.2 Visualization Using Transformed Values
9.4.2.1 Radial Coordinate Visualization
9.4.2.2 Level Diagrams
9.4.2.3 Hyper-radial Visualization
9.4.3 Visualizing the Distribution Relation of Solution
9.4.3.1 Distance and Distribution Charts
9.4.3.2 Hyper-space Diagonal Counting
9.5 Challenges
9.5.1 Many-objective Test Problems
9.5.2 Many-Objective Optimization Algorithms
9.5.3 Performance Evaluation Methods
9.5.4 Visualization of Many-Objective Optimization
References
10 Constrained Optimization
10.1 Introduction
10.2 Constraint-Handling Techniques
10.2.1 Penalty Function
10.2.1.1 Static Penalty Function
10.2.1.2 Dynamic Penalty Function
10.2.1.3 Adaptive Penalty Function
10.2.2 Separation of Objectives and Constraints
10.2.2.1 Feasibility Rule
10.2.2.2 -Constraint Methods
10.2.2.3 Stochastic Ranking
10.2.2.4 Multi-objective Methods
10.2.3 Ensemble Methods
10.3 Challenges and Future Directions
References
11 Dynamic Optimization
11.1 Introduction
11.1.1 Basics of Changes
11.1.2 Characteristics of Changes
11.2 Dynamism Handling Methods
11.2.1 Difficulties
11.2.2 Dynamism Handling Strategies
11.3 Benchmark Problems and Metrics for Dynamic Single-Objective Optimization
11.3.1 Classical Problem Generators
11.3.2 Performance Measures
11.4 Benchmark Problems and Metrics for Dynamic Multi-objective Optimization
11.4.1 Classical Benchmark Problems
11.4.2 Performance Measures
11.5 Dynamic Constrained Optimization
11.6 Challenges
References
12 Robust Optimization
12.1 Introduction
12.2 Robust Optimization Algorithms
12.2.1 Uncertainties in Decision Variables
12.2.1.1 Definition
12.2.1.2 Measures
12.2.2 Uncertainties in Objective Function
12.2.3 Uncertainties in Environments
12.2.3.1 Min-Max Optimization Problem
12.2.3.2 Coevolution for Min-Max Optimization Problem
12.2.3.3 Limitation and Improvements
12.2.4 Uncertainties Over Time
12.3 Discussions
References
13 Large-Scale Global Optimization
13.1 Large-Scale Global Optimization Problems
13.2 Coevolution Methods
13.2.1 Cooperative Coevolution
13.2.2 Static Grouping
13.2.3 Dynamic Grouping
13.2.3.1 Random Dynamic Grouping
13.2.3.2 Learning-Based Dynamic Grouping
13.3 Non-decomposition-Based Methods
13.3.1 PSO-Based Algorithms
13.3.2 EDA-Based Algorithms
13.3.3 DE-Based Algorithms
13.4 Learning-Based Algorithms
13.5 Discussions
References
14 Expensive Optimization
14.1 Introduction
14.1.1 Expensive Optimization Problems
14.1.2 Surrogate-Assisted Evolutionary Algorithms
14.2 Surrogate Models
14.2.1 Response Surface Methods
14.2.2 Gaussian Processes
14.2.3 Artificial Neural Networks
14.2.4 Radial Basis Function Networks
14.2.5 Support Vector Machines
14.2.6 Model Ensembles
14.3 Model Management
14.3.1 Model Management in Offline SAEAs
14.3.2 Model Management in Online SAEAs
14.3.3 Infill Sampling Criterion
14.4 Discussions
References
15 Real-World Applications
15.1 Antenna Design
15.1.1 Antenna Basics
15.1.1.1 Frequency
15.1.1.2 Frequency Bands
15.1.1.3 Impedance
15.1.1.4 Radiation Pattern
15.1.1.5 Directivity
15.1.1.6 Efficiency
15.1.1.7 Gain
15.1.1.8 Beamwidths and Sidelobes
15.1.1.9 Voltage Standing Wave Ratio
15.1.1.10 Polarization
15.1.2 Antenna Design Problems
15.1.3 Case Studies
15.1.3.1 S-band Omnidirectional Antenna
15.1.3.2 Circularly Polarized Antenna
15.2 Vehicle Routing
15.2.1 Basics of the Vehicle Routing Problem
15.2.1.1 Depot
15.2.1.2 Customers
15.2.1.3 Vehicles
15.2.2 Variants of the Vehicle Routing Problem
15.2.2.1 Capacitated VRPs
15.2.2.2 VRPs with Time Windows
15.2.2.3 VRPs with Simultaneous Delivery and Pickup
15.2.2.4 VRPs with Uncertainties
15.2.3 Multi-objective VRP with Real-Time Traffic Conditions
15.2.4 Algorithm Framework and Results
15.2.4.1 Solution Initialization
15.2.4.2 Adaptive Local Search Strategy
15.2.4.3 Online Optimization
15.2.4.4 Experimental Results
15.3 Contamination Source Identification in Water Distribution Systems
15.3.1 Contamination Source Identification Problem
15.3.1.1 Water Distribution System
15.3.1.2 Simulation-Optimization Model
15.3.2 Adaptive Multi-population Algorithm
15.3.2.1 Generation of Multiple Populations
15.3.2.2 Cooperative Coevolutionary Search
15.3.2.3 Population Management
15.3.3 Experimental Results
15.3.3.1 Experimental Setup
15.3.3.2 Results and Discussions
References
A Mathematical Background
A.1 Mathematical Analysis
A.1.1 Set
A.1.1.1 Properties
A.1.1.2 Operations
A.1.1.3 Properties of Set Operations
A.1.1.4 Display Methods
A.1.2 Function
A.1.2.1 Common Functions
A.1.2.2 Sequences
A.1.2.3 The Limit of Function
A.1.2.4 The Continuity of Function
A.1.2.5 Derivative and Differentiation
A.1.2.6 Absolute Minimum and Maximum
A.2 Mathematical Algebra
A.2.1 Vector
A.2.1.1 Vector Space
A.2.1.2 Dimension
A.2.1.3 Systems of Linear Equations
A.2.2 Matrix
A.2.2.1 Operations
A.2.2.2 Matrix of Linear System
A.3 Probability and Stochastics Processes
A.3.1 Probability
A.3.1.1 Markov Chains
B Open Framework of Evolutionary Computation
B.1 Features of OFEC
B.1.1 Comprehensiveness
B.1.2 Easy of Use
B.1.3 Scalability
B.2 Procedures of using OFEC
B.2.1 Running OFEC
B.2.2 Adding a Problem
B.2.2.1 Adding an Algorithm
B.3 Components of OFEC
B.3.1 Problem Component
B.3.2 Algorithm Component
B.4 Implemented Algorithms and Problems
References
Index