Evolutionary Computing
Chapter 0 Evolutionary problem solving
- Fitness (evolution) chances for survival and reproduction
- Quality (problem solving) chance for seeding new solutions
- Evolvable objects (phenotypes) > genetic code (genotypes) > reproduction > fitness >
selection
Chapter 1 Problems to be solved
Problems
1. Black box model (input, model, output one is unknown)
Optimization
- Model and desired output is known
- Task is to find inputs
Modelling
- Input and desired output is known
- Task is to find model
Simulation
- Input and model are known
- task is to find output
2. Search problems: collection of all objects of interest including the desired solution
Search problems = define search spaces
Problem-solvers = move through search spaces (to find a solution)
3. Optimisation vs constraint satisfaction
Objective function = a way of assigning a value to a possible solution that
reflects its quality on scale
Constraint = binary evaluation telling whether a given requirement holds or not
4. NP problems
Problem type depending on the problem only
Hardness/complexity classified:
1. Class P solved in polynomial time
2. Class NP
- Not necessarily solved in polynomial time
- Any solution can be verified within
polynomial time by some algorithm (P subset of NP)
3. Class NP-Complete
- Some NP (other NP can be reduced by algorithm running in
polynomial time)
, 4. Class NP-hard
- As hard as any problem in NP-complete
- Solution cannot necessarily be verified within polynomial time
Chapter 2 The origins
Darwin Evolution
Definition: population consists of a diverse set of individuals
1. Survival of the fittest
All environments have finite resources
Individuals that compete for the resources most effectively have increased
chance of reproduction
2. Diversity drives change Phenotypic traits
Physical and behavioural differences that affect response to environment
Unique to each individual, partly as a result of random changes
Lead to higher chances of reproduction
Can be inherited
3. Summary:
Combinations of traits that are better adapted tend to increase representation
in population
- Individuals are “units of selection”
Variations occur through random changes yielding constant source of diversity,
coupled with selection means that:
- Population is the “unit of evolution”
D. Dennet ‘If you have variation, heredity, and selection, then you must get evolution’
Adaptive landscape metaphor
- Population with n traits as existing in a n+1-dimensional space (landscape) with heigh
corresponding to fitness
- Each individual (phenotype) represents a single point on the landscape
- Population is therefore a “cloud” of points, moving on the landscape over time as it
evolves (adaptation)
- Genetic drift:
Random variations in feature distribution
(+ or -) arising from sampling error
Can cause the population “melt down” hills, thus crossing valleys and leaving
local optima
Genetics, genes and the genome
- Genotype (DNA inside) determines phenotype (outside)
- The mapping genes phenotypic traits are very complex
Pleiotropy: one gene may affect many traits
Polygeny: many genes may affect one trait
- Ontogenesis = process of differential behaviours during development (after
fertilization)
,Chapter 3 What is an Evolutionary Algorithm?
Common model of evolutionary processes
1. Population of individuals
2. Individuals have fitness
3. Reproduction/variation operators
Mutation
Recombination (a.k.a. crossover)
4. Selection towards higher fitness
‘Survival of the fittest’
‘Mating of the fittest’
5. Fitness of population increases over time
Two pillars of evolution / competing forces
1. Push towards novelty
Increase population diversity by variation:
- Mutation
- Recombination
Variation operators act on individual level
2. Push towards quality
Decrease population diversity by selection:
- Of parents
- Of survivors
Selection operators act on population level
General scheme of EAs vs. pseudo-code
Main EA Components
1. Representation:
Role: provides code for candidate solutions that can be manipulated by variation
operators
Phenotype
- Object in original problem context, the outside
- Encoding (repres.): phenotype to genotype (not necessarily one to one)
Genotype
- Code to denote that object, the inside
- Decoding (inverse repres.): genotype to phenotype (must be one to one)
Loci = fixed positions of genes in chromosomes
Allele = value of gene
, 2. Evaluation / fitness function
Role:
- Fitness function: represents the task to solve, the requirements to adapt
to
- Enables selection
- Provides basis for comparison
Quality function of objective function
Assigns a single real-valued fitness to each phenotype which performs basis for
selection
- So the more discrimination (different values) the better
Usually talk about fitness being maximized (some can be posed as minimisation
problems, but conversion is trivial)
3. Population
Role: holds the candidate solution of the problem as individuals (genotypes)
Population is:
- a multiset of individuals
- the basic unit of evolution (populations is evolving, not the individuals)
Selection operators act on population level
Variation operators act on individual level
Diversity of population refers to number of different fitness values or
phenotypes or genotypes present
4. Selection
Role:
- Identifies individuals to become parents / to survive
- Pushes population towards higher fitness
Parent selection: usually probabilistic / stochastic
- Can help escape from local optima
- High quality solutions more likely to be selected than low quality solutions
- Even the worst in current population usually has non-zero probability of
being selected
Survivor selection (a.k.a. replacement) often deterministic
- Fitness based: rank parents + offspring and take best
- Age based: make as many offspring as parents and delete all parents
Sometimes a combination of stochastic and deterministic:
- Elitism: the best n individuals always survive (deterministic rule)
5. Variation operators
Role: generate new candidate solutions
Usually divided into two types according to their arity (number of inputs)
- arity 1: mutation operators
- arity > 1: recombination operators
- arity = 2: typically called crossover
- arity > 2: multi-parent reproduction, is possible, not used often
Most EAs use both recombination and mutation
Variation operators must match the given representation
Chapter 0 Evolutionary problem solving
- Fitness (evolution) chances for survival and reproduction
- Quality (problem solving) chance for seeding new solutions
- Evolvable objects (phenotypes) > genetic code (genotypes) > reproduction > fitness >
selection
Chapter 1 Problems to be solved
Problems
1. Black box model (input, model, output one is unknown)
Optimization
- Model and desired output is known
- Task is to find inputs
Modelling
- Input and desired output is known
- Task is to find model
Simulation
- Input and model are known
- task is to find output
2. Search problems: collection of all objects of interest including the desired solution
Search problems = define search spaces
Problem-solvers = move through search spaces (to find a solution)
3. Optimisation vs constraint satisfaction
Objective function = a way of assigning a value to a possible solution that
reflects its quality on scale
Constraint = binary evaluation telling whether a given requirement holds or not
4. NP problems
Problem type depending on the problem only
Hardness/complexity classified:
1. Class P solved in polynomial time
2. Class NP
- Not necessarily solved in polynomial time
- Any solution can be verified within
polynomial time by some algorithm (P subset of NP)
3. Class NP-Complete
- Some NP (other NP can be reduced by algorithm running in
polynomial time)
, 4. Class NP-hard
- As hard as any problem in NP-complete
- Solution cannot necessarily be verified within polynomial time
Chapter 2 The origins
Darwin Evolution
Definition: population consists of a diverse set of individuals
1. Survival of the fittest
All environments have finite resources
Individuals that compete for the resources most effectively have increased
chance of reproduction
2. Diversity drives change Phenotypic traits
Physical and behavioural differences that affect response to environment
Unique to each individual, partly as a result of random changes
Lead to higher chances of reproduction
Can be inherited
3. Summary:
Combinations of traits that are better adapted tend to increase representation
in population
- Individuals are “units of selection”
Variations occur through random changes yielding constant source of diversity,
coupled with selection means that:
- Population is the “unit of evolution”
D. Dennet ‘If you have variation, heredity, and selection, then you must get evolution’
Adaptive landscape metaphor
- Population with n traits as existing in a n+1-dimensional space (landscape) with heigh
corresponding to fitness
- Each individual (phenotype) represents a single point on the landscape
- Population is therefore a “cloud” of points, moving on the landscape over time as it
evolves (adaptation)
- Genetic drift:
Random variations in feature distribution
(+ or -) arising from sampling error
Can cause the population “melt down” hills, thus crossing valleys and leaving
local optima
Genetics, genes and the genome
- Genotype (DNA inside) determines phenotype (outside)
- The mapping genes phenotypic traits are very complex
Pleiotropy: one gene may affect many traits
Polygeny: many genes may affect one trait
- Ontogenesis = process of differential behaviours during development (after
fertilization)
,Chapter 3 What is an Evolutionary Algorithm?
Common model of evolutionary processes
1. Population of individuals
2. Individuals have fitness
3. Reproduction/variation operators
Mutation
Recombination (a.k.a. crossover)
4. Selection towards higher fitness
‘Survival of the fittest’
‘Mating of the fittest’
5. Fitness of population increases over time
Two pillars of evolution / competing forces
1. Push towards novelty
Increase population diversity by variation:
- Mutation
- Recombination
Variation operators act on individual level
2. Push towards quality
Decrease population diversity by selection:
- Of parents
- Of survivors
Selection operators act on population level
General scheme of EAs vs. pseudo-code
Main EA Components
1. Representation:
Role: provides code for candidate solutions that can be manipulated by variation
operators
Phenotype
- Object in original problem context, the outside
- Encoding (repres.): phenotype to genotype (not necessarily one to one)
Genotype
- Code to denote that object, the inside
- Decoding (inverse repres.): genotype to phenotype (must be one to one)
Loci = fixed positions of genes in chromosomes
Allele = value of gene
, 2. Evaluation / fitness function
Role:
- Fitness function: represents the task to solve, the requirements to adapt
to
- Enables selection
- Provides basis for comparison
Quality function of objective function
Assigns a single real-valued fitness to each phenotype which performs basis for
selection
- So the more discrimination (different values) the better
Usually talk about fitness being maximized (some can be posed as minimisation
problems, but conversion is trivial)
3. Population
Role: holds the candidate solution of the problem as individuals (genotypes)
Population is:
- a multiset of individuals
- the basic unit of evolution (populations is evolving, not the individuals)
Selection operators act on population level
Variation operators act on individual level
Diversity of population refers to number of different fitness values or
phenotypes or genotypes present
4. Selection
Role:
- Identifies individuals to become parents / to survive
- Pushes population towards higher fitness
Parent selection: usually probabilistic / stochastic
- Can help escape from local optima
- High quality solutions more likely to be selected than low quality solutions
- Even the worst in current population usually has non-zero probability of
being selected
Survivor selection (a.k.a. replacement) often deterministic
- Fitness based: rank parents + offspring and take best
- Age based: make as many offspring as parents and delete all parents
Sometimes a combination of stochastic and deterministic:
- Elitism: the best n individuals always survive (deterministic rule)
5. Variation operators
Role: generate new candidate solutions
Usually divided into two types according to their arity (number of inputs)
- arity 1: mutation operators
- arity > 1: recombination operators
- arity = 2: typically called crossover
- arity > 2: multi-parent reproduction, is possible, not used often
Most EAs use both recombination and mutation
Variation operators must match the given representation
