A. Encoding a Chromosome
The chromosome should contain information about the solution it represents.
1. Binary Encoding
One way of encoding is a binary string. The chromosome could look like this:
Chromosome 1 | 1101100100110110 |
Chromosome 2 | 1101011000011110 |
Each bit in the string can represent some characteristic of the solution or it
could represent whether or not some particular characteristic was present. Another
possibilitiy is that the chromosome could contain just 4 numbers where each number
is represented by 4 bits (the highest number therefore being 15.)
2. Permutation Encoding
Permutation encoding can be used in ordering problems, such as the travelling
salesman problem or a task ordering problem. Every chromosome is a string
of numbers, which represents number in a sequence. In the TSP each number
would represent a city to be visited.
Chromosome 1 | 1 4 7 9 6 3 5 0 2 8 |
Chromosome 2 | 9 3 2 5 8 1 6 0 4 7 |
3. Value Encoding
Direct value encoding can be used in problems where some complicated value,
such as real numbers, are used and where binary encoding would not suffice.
While value encoding is very good for some problems, it is often necessary to
develop some specific crossover and mutation techniques for these chromosomes.
Chromosome 1 | A B E D B C A E D D |
Chromosome 2 | N W W N E S S W N N |
In chromosome 1 above, A could represent a particular task, B another, etc.
For chromosome 2 N could be north, S south, and thus could be the path
through a maze.
4. Tree encoding
Tree encoding is used to actually have programs or expressions evolve.
In tree encoding every chromosome is a tree of some objects, such as
functions or commands in the programming language. LISP is often
used for this because programs in LISP can be represented in this form
and then be easily parsed as a tree.
Example of a Problem.
Finding a function from given input and output values.
Task: Find a function that will give the best output for all given
inputs.
More Later (I hope).
Reproduction
Reproduction is a process in which individual strings (chromosomes) are copied
according to their fitness. Intuitively one can think of the fitness function
as some measure of profit, utility or goodness that is to be maximized. Copying
strings according to their fitness or goodness means that strings with a higher
value have a higher probability of contributing one or more offspring in the next
generation.
This operator is an artificial version of natural selection, a Darwinian survival
of the fittest among string creatures. In natural populations fitness is deter-
mined by a creature's ability to survive predators, pestilence and other ob-
stacles to adulthood and subsequent reproduction. In the artifical setting of
a GA the objective function is the final arbiter of the string-creature's life
or death.
There are many methods for selecting the best chromosomes: roulette wheel
selection, Boltzman selection, tournament selection, rank selection, steady
state selection and others.
Roulette Wheel
Simple reproduction allocates offspring strings using a roulette wheel
with slots sized according to fitness. This is a way of choosing members
from the population of chromosomes in a way that is proportional to their
fitness. Parents are selected according to their fitness. The better the
fitness of the chromosome, the greater the chance it will be selected,
however it is not guaranteed that the fittest member goes to the next
generation.
Imagine a roulette wheel in which all chromosomes in the population
are placed according to fitness, as in the picture below. The wheel is
"spun" and the marble falls into one of the slots. The wheel is spun to
select each chromosome that is to mate.
The wheel is "spun" once for each chromosome that is chosen.
Steady State
In a steady-state genetic algorithm one member of the population is changed
at a time. To perform selection a member of the population is chosen according
to its fitness. It is copied and the copy mutated. A second member of the pop-
ulation is selected which is replaced by the mutated string. In crossover two
members of the population are chosen, a single child created which replaces a
member of the population. Any selection method can be used to select the
individual for mutation or the parents. There are a number of different
replacement strategies
- replace worst (often gives too rapid convergence)
- replace a randomly chosen member
- select replacement using the negative fitness.
The major difference between steady-state and generational GAs is that for
each P members of the population generated in the generational GA there
are 2P selections. Consequently the selection strength and genetic drift for
a steady-state GA is twice that of the generational GA. The steady-state GA,
therefore, appears twice as fast although it can lose out in the long term
because it does not explore the landscape as well as the generational GA.
Tournament
In general tournament selection n individuals are selected at random
and the fittest is selected. The most common type of tournament
selection is binary tournament selection, where just two individuals
are selected.
Elitism
The best chromosome (or a few best chromosomes) is copied to the
population in the next generation. The rest are chosen in classical
way. Elitism can very rapidly increase performance of GA, because it
prevents losing the best found solution to date. A variation is to
eliminate an equal number of the worst solutions, i.e. for each "best
chromosome" carried over a "worst chromosome" is deleted.
Rank Selection
The roulette method of selection will have problems when the fitnesses
differs greatly. For example, if the best chromosome fitness is 90% of
all the roulette wheel then the other chromosomes will have a slim
chance of being selected.
Rank selection first ranks the population and then every chromosome
receives fitness from this ranking. The worst will have fitness 1,
second worst 2 etc. and the best will have fitness N (number of
chromosomes in population).
Before:
After:
Crossover
Single Point Crossover
Randomly choose a crossover point, then for offspring 1
a) copy everything in parent 1 before the crossover point &
b) copy everything in parent2 after this point to the new
chromosome.
For offspring 2 do the reverse.
Chromosome 1 | A B C D E F G H I J |
Chromosome 2 | 0 1 2 3 4 5 6 7 8 9 |
Offspring 1 |
A B C 3 4 5 6 7 8 9 |
Offspring 2 |
0 1 2 D E F G H I J |
The crossover point above was 3.
Two Point Crossover
Same as above except this time two crossover points are randomly chosen.
Chromosome 1 | A B C D E F G H I J |
Chromosome 2 | 0 1 2 3 4 5 6 7 8 9 |
Offspring 1 |
A B 2 3 4 5 6 7 8 J |
Offspring 2 |
0 1 C D E F G H I 9 |
Here the crossover points were at 2 and 9.
Uniform Crossover
A certain number of genes are randomly selected to be "swapped"
Chromosome 1
| A B C D E F G H I J
|
Chromosome 2
| 0 1 2 3 4 5 6 7 8 9
|
Offspring 1 |
0 B C D E 5 G H I 9 |
Offspring 2 |
A 1 2 3 4 F 6 7 8 J |
Specific Crossover
A specific crossover for a specific problem
For example:
A permutation encoding where one crossover point is selected.
The gene is copied from parent 1, the second parent is scanned
and if the the number is not yet included it is added and
then the process repeats.
Arithmetic Crossover
Some arithmetic operation is performed on the two strings to create a new
string. Here it was AND.
Chromosome 1 |
1 0 1 1 1 0 1 1 1 0 1 |
Chromosome 2 |
1 1 0 0 1 0 0 0 1 1 1 |
Offspring 1 |
1 0 0 0 1 0 0 0 1 0 1 |
Mutation
Flip a bit at the rate of 1% of those bits processed.
Mutation depends on the encoding as well as the crossover.
Can easily be overdone.
Binary Encoding |
Permutation Encoding |
Chromosome 1 1 0 0 1 0 0 0 1 1 1 |
Chromosome 9 4 6 2 3 1 0 5 7 8 |
Offspring 1 0 0 0 1 0 0 0 1 1 1 |
Offspring 9 6 4 2 3 1 0 5 7 8 |
|