Summary Evolutionary Computing (X_400111)

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