Summary Evolutionary Computing – Berend Markhorst
Table of content
Chapter 1 – Problems to be solved .................................................................................................................. 3
Chapter 2 – Evolutionary Computing: The Origins ........................................................................................... 4
Chapter 3 – What is an evolutionary algorithm? ............................................................................................. 5
Chapter 4 – Representation, mutation, and recombination ............................................................................. 8
Binary representation ......................................................................................................................................... 8
Integer representation ........................................................................................................................................ 9
Real-valued representation ................................................................................................................................ 9
Tree representation .......................................................................................................................................... 11
Chapter 5 – Fitness, Selection and Population Management ......................................................................... 11
Chapter 6 – Popular Evolutionary Algorithm Variants ................................................................................... 13
Genetic Algorithms ........................................................................................................................................... 13
Evolution Strategies .......................................................................................................................................... 14
Evolutionary Programming ............................................................................................................................... 14
Genetic Programming....................................................................................................................................... 14
Learning Classifier Systems ............................................................................................................................... 15
Differential evolution ........................................................................................................................................ 15
Particle Swarm Optimisation ............................................................................................................................ 16
Estimation of Distribution Algorithms .............................................................................................................. 16
Chapter 7 – Parameters and Parameter Tuning ............................................................................................. 16
Chapter 8 – Parameter Control ..................................................................................................................... 18
Changing parameters ....................................................................................................................................... 18
Changing the penalty coefficients .................................................................................................................... 18
Classification of control techniques .................................................................................................................. 19
Chapter 9 – Working with Evolutionary Algorithms ....................................................................................... 20
Performance measures ..................................................................................................................................... 20
Chapter 10 – Hybridization with Other Techniques: Memetic Algorithms...................................................... 22
Local search ...................................................................................................................................................... 22
MA’s structure .................................................................................................................................................. 23
Adaptive MAs ................................................................................................................................................... 24
Design issues for MAs ....................................................................................................................................... 24
Chapter 12 – Multiobjective Evolutionary Algorithms ................................................................................... 24
EA Approaches to MOPs ................................................................................................................................... 25
1
,Summary Evolutionary Computing – Berend Markhorst
Chapter 13 – Constraint Handling ................................................................................................................. 25
Approaches to handling constraints ................................................................................................................. 25
Chapter 17 – Evolutionary robotics ............................................................................................................... 26
2
, Summary Evolutionary Computing – Berend Markhorst
Chapter 1 – Problems to be solved
The field of evolutionary computing is primarily concerned with problem solvers.
The classification of problems in this section is based on a black box model of computer
systems. When input is provided, the system processes that input through some
computational model, whose details are not specified in general. In essence there are three
components: input, model and output.
Optimization, e.g. travelling salesman problem. For a given instance of this problem, we
have a formula (the model) that for each given
sequence of cities (the inputs) will compute the
length of the tour (the output).
Modelling, e.g. voice control system for smart
homes. The set of all phrases pronounced by the
user (inputs) must be correctly mapped onto the
set of all control commands in the repertoire of
the smart home. It is important to note that
modelling problems can be transformed into
optimization problems.
Simulation, e.g. performing what-if analyses.
An assumption behind the black box view is that a computational model is directional: it
computes from the inputs towards the outputs and it cannot be simply inverted. This implies
that solving a simulation problem is different from solving an optimization or a modelling
problem.
The process of problem solving can be viewed as a search through a potentially huge set of
possibilities to find the desired solution. Search space: collection of all objects of interest
including the solution we are seeking.
Problems à define search spaces. Problem
solvers à methods that tell us how to move
through search spaces.
Objective function à way of assigning a value
to a possible solution that reflects its quality
on a scale. Constraint à represents a binary
evaluation telling us whether a given
requirement holds or not.
The nature of a problem is less obvious than it
may seem; you can model something as a FOP, CSP or COP.
There are two kinds of optimization problems: numerical and combinatorial. Then there’s
problem size (which is grounded in the dimensionality of the problem at hand) and running-
time (usually the worst-case scenario). Problem reduction: we can transform one problem
into another via a suitable mapping.
Class P: there exists an algorithm that
can solve it in polynomial time. Class NP:
it can be solved by some algorithm and
any solution can be verified within
polynomial time. Note that P is a subset
of NP. Class NP-complete: if it belongs to
the class NP and any other problem in NP
can be reduced to this problem by an
3
Table of content
Chapter 1 – Problems to be solved .................................................................................................................. 3
Chapter 2 – Evolutionary Computing: The Origins ........................................................................................... 4
Chapter 3 – What is an evolutionary algorithm? ............................................................................................. 5
Chapter 4 – Representation, mutation, and recombination ............................................................................. 8
Binary representation ......................................................................................................................................... 8
Integer representation ........................................................................................................................................ 9
Real-valued representation ................................................................................................................................ 9
Tree representation .......................................................................................................................................... 11
Chapter 5 – Fitness, Selection and Population Management ......................................................................... 11
Chapter 6 – Popular Evolutionary Algorithm Variants ................................................................................... 13
Genetic Algorithms ........................................................................................................................................... 13
Evolution Strategies .......................................................................................................................................... 14
Evolutionary Programming ............................................................................................................................... 14
Genetic Programming....................................................................................................................................... 14
Learning Classifier Systems ............................................................................................................................... 15
Differential evolution ........................................................................................................................................ 15
Particle Swarm Optimisation ............................................................................................................................ 16
Estimation of Distribution Algorithms .............................................................................................................. 16
Chapter 7 – Parameters and Parameter Tuning ............................................................................................. 16
Chapter 8 – Parameter Control ..................................................................................................................... 18
Changing parameters ....................................................................................................................................... 18
Changing the penalty coefficients .................................................................................................................... 18
Classification of control techniques .................................................................................................................. 19
Chapter 9 – Working with Evolutionary Algorithms ....................................................................................... 20
Performance measures ..................................................................................................................................... 20
Chapter 10 – Hybridization with Other Techniques: Memetic Algorithms...................................................... 22
Local search ...................................................................................................................................................... 22
MA’s structure .................................................................................................................................................. 23
Adaptive MAs ................................................................................................................................................... 24
Design issues for MAs ....................................................................................................................................... 24
Chapter 12 – Multiobjective Evolutionary Algorithms ................................................................................... 24
EA Approaches to MOPs ................................................................................................................................... 25
1
,Summary Evolutionary Computing – Berend Markhorst
Chapter 13 – Constraint Handling ................................................................................................................. 25
Approaches to handling constraints ................................................................................................................. 25
Chapter 17 – Evolutionary robotics ............................................................................................................... 26
2
, Summary Evolutionary Computing – Berend Markhorst
Chapter 1 – Problems to be solved
The field of evolutionary computing is primarily concerned with problem solvers.
The classification of problems in this section is based on a black box model of computer
systems. When input is provided, the system processes that input through some
computational model, whose details are not specified in general. In essence there are three
components: input, model and output.
Optimization, e.g. travelling salesman problem. For a given instance of this problem, we
have a formula (the model) that for each given
sequence of cities (the inputs) will compute the
length of the tour (the output).
Modelling, e.g. voice control system for smart
homes. The set of all phrases pronounced by the
user (inputs) must be correctly mapped onto the
set of all control commands in the repertoire of
the smart home. It is important to note that
modelling problems can be transformed into
optimization problems.
Simulation, e.g. performing what-if analyses.
An assumption behind the black box view is that a computational model is directional: it
computes from the inputs towards the outputs and it cannot be simply inverted. This implies
that solving a simulation problem is different from solving an optimization or a modelling
problem.
The process of problem solving can be viewed as a search through a potentially huge set of
possibilities to find the desired solution. Search space: collection of all objects of interest
including the solution we are seeking.
Problems à define search spaces. Problem
solvers à methods that tell us how to move
through search spaces.
Objective function à way of assigning a value
to a possible solution that reflects its quality
on a scale. Constraint à represents a binary
evaluation telling us whether a given
requirement holds or not.
The nature of a problem is less obvious than it
may seem; you can model something as a FOP, CSP or COP.
There are two kinds of optimization problems: numerical and combinatorial. Then there’s
problem size (which is grounded in the dimensionality of the problem at hand) and running-
time (usually the worst-case scenario). Problem reduction: we can transform one problem
into another via a suitable mapping.
Class P: there exists an algorithm that
can solve it in polynomial time. Class NP:
it can be solved by some algorithm and
any solution can be verified within
polynomial time. Note that P is a subset
of NP. Class NP-complete: if it belongs to
the class NP and any other problem in NP
can be reduced to this problem by an
3
