Evolutionary Algorithms - Introduction and representation

Question 1

General scheme of EAs

Answer 1

Question 2

EA scheme is pseudo-code

Answer 2

Question 3

Common model of evolutionary processes

Answer 3

• Population of individuals
• Individuals have a fitness
• Variation operators: corssover, mutation
• Selection towards higher fitness
  
  • “survival of the fittest” and
  • “mating of the fittest”

Optimization according to some fitness-criterion (optimization on a fitness landscape)

Question 4

In EA, there are two competing forces

Answer 4

Increasing population diversity by genetic operator (mutation, recombination) push towards novelty.

Decreasing population diversity by selection (of parents and survivors) push towards quality.

Question 5

EA terms

Answer 5

Question 6

Main EA components: Evaluation (fitness) function

Answer 6

• Role:
  
  • Represents the task to solve, the requirements to adapt to (can be seen as “the environment”)
  • Enables selection (provides basis for comparison)
  • e.g., some phenotypic traits are advantageous, desirable, e.g. big ears cool better, these traits are rewarded by more offspring that will expectedly carry the same trait
• A.k.a.quality function or objective function
• Assigns a single real-valued fitness to each phenotype which forms the basis for selection
• •Typically we talk about fitness being maximised
  
  • Some problems may be best posed as minimisation problems, but conversion is trivial

Question 8

Main EA components: Population

Answer 8

• Role: holds the candidate solutions of the problem as individuals (genotypes)
• Formally, a population is a multiset of individuals, i.e. repetitions are possible
• Population is the basic unit of evolution, i.e., the population is evolving, not the individuals
• Selection operators act on population level
• Variation operators act on individual level

Question 9

Main EA components: Selection mechanism

Answer 9

Role:

• Identifies individuals – to become parents – to survive
• Pushes population towards higher fitness
• Usually probabilistic
  
  • high quality solutions more likely to be selected than low quality
  • but not guaranteed
  • even worst in current population usually has non-zero probability of being selected
• This stochastic nature can aid escape from local optima
• Survivor selection a.k.a. replacement
• Most EAs use fixed population size so need a way of going from (parents + offspring) to next generation
• Often deterministic (while parent selection is usually stochastic)
  
  • Fitness based: e.g., 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)

Question 10

Different types of EAs

Answer 10

Historically different flavours of EAs have been associated with different data types to represent solutions

• Binary strings : Genetic Algorithms (GA)
• Real-valued vectors : Evolution Strategies (ES)
• Finite state Machines: Evolutionary Programming (EP)
• LISP trees: Genetic Programming (GP)

These differences are largely irrelevant, best strategy:

• choose representation to suit problem
• choose variation operators to suit representation

Selection operators only use fitness and so are independent of representation

Question 11

Variation operators

Answer 11

Role: to generate new candidate solutions.

Usually divided into two types according to their arity (number of inputs to the variation operator):

• Arity 1 : mutation operators
• Arity >1 : recombination operators
• Arity = 2 typically called crossover
• Arity > 2 is formally possible, seldom used in EC

There has been much debate about relative importance of recombination and mutation

• Nowadays most EAs use both
• Variation operators must match the given representation

Question 12

Main EA components: Mutation

Answer 12

• Role: causes small, random variance
• Acts on one genotype and delivers another
• Element of randomness is essential and differentiates it from other unary heuristic operators
• Importance ascribed depends on representation and historical dialect:
  
  • Binary GAs – background operator responsible for preserving and introducing diversity
  • EP for FSM’s / continuous variables – the only search operator
  • GP – hardly used
• May guarantee connectedness of search space and hence convergence proofs

Question 13

Main EA components: Recombination

Answer 13

Main EA components: Recombination

• Role: merges information from parents into offspring
• Choice of what information to merge is stochastic
• Most offspring may be worse, or the same as the parents
• Hope is that some are better by combining elements of genotypes that lead to good traits
• Principle has been used for millennia by breeders of plants and livestock

Question 14

Mutation rate (binary representation)

Answer 14

Alter each gene independently with a probability p_m (the mutation rate)

Question 15

Positional Bias

Answer 15

Performance with 1-point crossover depends on the order that variables occur in the representation

• More likely to keep together genes that are near each other
• Can never keep together genes from opposite ends of string
• This is known as Positional Bias
• Can be exploited if we know about the structure of our problem, but this is not usually the case

Question 16

Binary Representation: Crossover or mutation?

Answer 16

It depends on the problem, but in general, it is good to have both. Both have a different role. Mutation-only-EA is possible, x-over-only-EA would not work.

Question 17

Permutation Representations: Mutation

Answer 17

Normal mutation operators lead to inadmissible solutions

• e.g. bit-wise mutation: let gene i have value j
• changing to some other value k would mean that k occurred twice and j no longer occurred

Therefore must change at least two values

Mutation parameter now reflects the probability that some operator is applied once to the whole string, rather than individually in each position

Examples:

• Swap mutation (pick two alleles at random and swap their positions)
• Insert mutation (Pick two at random, move the second to follow the first, shifting the rest along to accommodate)
• Scramble mutation (pick a subset of genes at random, and randomly rearrange the alleles in thos positions)
• Inversion mutation (pick to at random and invert the substring between them)

Question 19

Permutation Representations: Crossover operators

Answer 19

Normal” crossover operators will often lead to inadmissible solutions

Many specialised operators have been devised which focus on combining order or adjacency information from the two parents:

• Order 1 crossover (Choose an arbitrary part from the first parent. Copy this part to the first child. Copy the numbers that are not in the first part, to the first child (starting right from cut point). Analogous for the second child.)
• Partially Mapped Crossover (PMX)
• Cycle crossover
• Edge Recombination