Evolutionary Algorithms - Introduction and representation Flashcards
General scheme of EAs
EA scheme is pseudo-code
Common model of evolutionary processes
- 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)
In EA, there are two competing forces
Increasing population diversity by genetic operator (mutation, recombination) push towards novelty.
Decreasing population diversity by selection (of parents and survivors) push towards quality.
EA terms
Main EA components: Evaluation (fitness) function
- 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
Main EA components: Population
- 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
Main EA components: Selection mechanism
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)
Different types of EAs
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
Variation operators
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
Main EA components: Mutation
- 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
Main EA components: Recombination
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
Mutation rate (binary representation)
Alter each gene independently with a probability pm (the mutation rate)
Positional Bias
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
Binary Representation: Crossover or mutation?
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.
Permutation Representations: Mutation
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)
Permutation Representations: Crossover operators
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
