Presentation
This is the outline and text of my presentation which will be fleshed out with more information as it is worked out.
Title Page
- How representation affects the evolvability of genetic algorithms.
Introduction
- Genetic algorithms (GAs?) are a powerful solution to optimisation problems.
- They roughly mimic Darwinian evolution in order to quickly find a good solution to a problem.
- A population of solutions are tested to see which are the best, and from these new solutions are created and tested.
Introduction to GAs?: Crossover and Mutation
- Ideas taken from natural evolution.
- Crossover: combining two good solutions into a hopefully better one.
- Mutation: making a small random change to the genotype.
Introduction to GAs?: Genotype->Phenotype
- One of the most important parts of a GA.
- Genotype: the data that is being operated on by the GA with crossover and mutation.
- Phenotype: the expression of the genotype in a form to be tested for fitness.
Introduction to GAs?: Fitness
- The fitness function takes the phenotype of a potential solution and returns a number saying how good it is.
- The single most important part of a GA, as it defines its purpose. [A: more important than representation? R: I think so, without a good fitness func the GA isn't going so produce any relevant results, without a good representation you are going to impair the results you do get.]
- In biologial systems: genotype = genes, phenotype = body, fitness function = environment.
Importance of the Genotype to Phenotype mapping
- Representation scheme decides not only the resolution of the obtained solutions and the size of the search space, but also the principle of translating and understanding the primitive problem.
- A good representation leads to a quicker time to an ideal solution, and maybe a better solution.
- A bad representation may make it difficult, if not impossible, to reach a good solution.
- [A: is there a good example to use here? R: Have yet to come up with one. Suggestion welcome :) ]
Different representation types
A few different ones:
- Search for a set of values (plain numbers).
- A sequence (ordered numbers, with or without repeats).
- A set of instructions (assembly-like, execution tree) what is the proper name for a tree structure of instructions? - I don't think there is one formal name - the genetic programming book by J R Koza uses them all the time, it might be good to check there and see if there is any term he defines. A
Simple optimisation: Gray code
- An alternative to standard binary coding.
- Has 'adjacency', that is, there is an unbroken path from any point to the optimal point that is always increasing.
Gray Code
[Can use right hand side of diagram to explain the evolution path]
Larger Scale Optimisations: Orthoganality
- How is the result of a particular value on one place on the genotype affected by another place?
- What happens when it gets split up by crossover?
- Orthoganality should be maximised, but it is not always possible to have it perfect.
- How much influence does it have?
Larger Scale Optimisations: Redundancy
- What happens if the search space is larger than the solution space?
- That is, more than one genotype maps to one phenotype.
- Obviously there may be more searching to do, however...
- ...there may also be a larger number of easy paths to follow to the best solution.
Problems Working It Out
- This isn't very cut-and-dried.
- What works well for one GA may completely ruin another one
- However, there are a lot of common situations:
- Searching for a set of parameters that optimise a numeric function
- Optimising a sequence of operations (Travelling Salesman Problem)
- Building an algorithm for finding a general solution to some other problem
- If we work with these general problems, then an improvement may help for similar cases.
Literature Breakdown
- Not a lot of papers discuss trying different representations.
- Many don't even say what the representation is (making their results unreproducible).
- In general, representation is something that is worked out, ignored, and most effort goes in to tuning mutation and crossover rates.
End Result
- Ideally, a set of "If your problem can be reduced to this canonical problem, then you should do it this way".
< Resources | HomePage | Test Problems >