The initial population, encodings, and fitnesses are given in Table 20.1. Note that chromosomes x = 2 and x = 10 have equal fitness values, hence their relative ranking is an arbitrary choice.
The genetic algorithm we use has a simple form of selection and reproduction. The top performing chromosome is reproduced and preserved for use in the next iteration of the algorithm. It replaces the lowest performing chromosome, which is removed from the population altogether. Hence we remove x = 31 from selection.
The next step is to perform crossover between the chromosomes. We randomly pair the top four ranked chromosomes and determine whether they are subject to crossover by a non-deterministic probability. In this example, we have chosen a crossover probability of 0.5, easily modeled by a coin toss. The random pairings selected are ranked chromosomes (1,4) and (2,3). Each pair of chromosomes will undergo a single random point crossover to produce two new chromosomes.
As described earlier, the single random point crossover operation selects a random point to perform the crossover. In this iteration, both pairs undergo crossover (Figure 20.8).
The resulting chromosomes from the crossover operation are as follows:
(1)00|010 po 00100 = 4
(4)10|100 no 10010 = 18
(2)0|1010 po 00000 = 0
(3)0|0000 no 01010 = 10
Crossover point
Figure 20.8: Crossover
Note that in the case of the second crossover, because the first bit is identical in both strings the resulting chromosomes are the same as the parents. This is effectively equivalent to no crossover operation occurring. After one itera-
299
20 Genetic Algorithms
tion we can see the population has converged somewhat toward the optimal answer. We now repeat the evaluation process with our new population (Table 20.2).
x |
Bit String |
|
f(x) |
Ranking |
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
00100 |
|
–4 |
1 |
|
|
|
|
|
|
|
2 |
00010 |
|
–16 |
2 |
|
|
|
|
|
|
|
10 |
01010 |
|
–16 |
3 |
|
|
|
|
|
|
|
0 |
00000 |
|
–36 |
4 |
|
|
|
|
|
|
|
18 |
10010 |
|
–144 |
5 |
|
|
|
|
|
|
Table 20.2: Population after crossover |
|
|
Again we preserve the best |
chromosome (x = 4) and remove the worst |
(x = 18). Our random pairings this time are ranked chromosomes (1, 2) and (3, 4). This time, only pair (3, 4) has been selected by a random process to cross over, and (1, 2) is selected for mutation. It is worth noting that the (1, 2) pair had the potential to produce the optimal solution x = 6 if it had undergone crossover. This missed opportunity is characteristic of the genetic algorithm’s non-deterministic nature: the time taken to obtain an optimal solution cannot be accurately foretold. The mutation of (2), however, reintroduced some of the lost bit-string representation. With no mutate operator the algorithm would no longer be capable of representing odd values (bit strings ending with a one).
Mutation of (1) and (2)
(1)00100 o 00000 = 0
(2)00010 o 00011 = 3
Crossover of pair (3, 4)
(3)01|010 po 01000 = 8
(4)00|000 no 00010 = 2
The results of the next population fitness evaluation are presented in Table 20.3.
As before, chromosome x = 0 is removed and x = 4 is retained. The selected pairs for crossover are (1, 3) and (1, 4), of which only (1, 4) actually undergoes crossover:
(1) 001|00 po 00110 = 6
(4) 000|10 no 00000 = 0
The optimal solution of x = 6 has been obtained. At this point, we can stop the genetic algorithm because we know this is the optimal solution. However, if we let the algorithm continue, it should eventually completely converge to
Implementation of Genetic Algorithms
x |
Bit String |
f(x) |
Ranking |
|
|
|
|
|
|
|
|
4 |
00100 |
–4 |
1 |
|
|
|
|
8 |
01000 |
–4 |
2 |
|
|
|
|
3 |
00011 |
–9 |
3 |
|
|
|
|
2 |
00010 |
–16 |
4 |
|
|
|
|
0 |
00000 |
–36 |
5 |
|
|
|
|
Table 20.3: Connection between the input and output indices
x = 6. This is because the x = 6 chromosome is now persistent through subsequent populations due to its optimal nature. When another chromosome is set to x = 6 through crossover, the chance of it being preserved through populations increases due to its increased presence in the population. This probability is proportional to the presence of the x = 6 chromosome in the population, and hence given enough iterations the whole population should converge. The elitism operator, combined with the fact that there is only one maximum, ensures that the population will never converge to another chromosome.
20.5 Implementation of Genetic Algorithms
We have implemented a genetic algorithm framework in object-oriented C++ for the robot projects described in the following chapters. The base system consists of abstract classes Gene, Chromosome, and Population. These classes may be extended with the functionality to handle different data types, including the advanced operators described earlier and for use in other applications as required. The implementation has been kept simple to meet the needs of the application it was developed for. More fully featured third-party genetic algorithm libraries are also freely available for use in complex applications, such as GA Lib [GALib 2006] and OpenBeagle [Beaulieu, Gagné 2006]. These allow us to begin designing a working genetic algorithm without having to implement any infrastructure. The basic relationship between program classes in these frameworks tends to be similar.
Using C++ and an object-oriented methodology maps well to the individual components of a genetic algorithm, allowing us to represent components by classes and operations by class methods. The concept of inheritance allows the base classes to be extended for specific applications without modification of the original code.
The basic unit of the system is a child of the base Gene class. Each instance of a Gene corresponds to a single parameter. The class itself is completely abstract: there is no default implementation, hence it is more accurately described as an interface. The Gene interface describes a set of basic opera-
301
20 Genetic Algorithms
Program 20.1: Gene header
1 |
class Gene |
|
|
2 |
{ |
|
|
3 |
// Return our copy of data, suitable for reading |
4 |
virtual |
void* getData(void) = 0; |
5 |
// Return new copy of data, suitable for manipulat. |
6 |
virtual |
void* getDataCopy() = 0; |
7 |
// Copy the data from somewhere else to here |
8 |
virtual |
void |
setData(const void* data) = 0; |
9 |
// Copy data from another gene of same type to here |
10 |
virtual |
void |
setData(Gene& gene) = 0; |
11 |
// Set the |
data in this gene to a random value |
12 |
virtual |
void |
setRandom(void) = 0; |
13 |
// Mutate our data |
14 |
virtual |
void |
mutate(void) = 0; |
15 |
// Produce |
a new identical copy of this gene |
16 |
virtual |
Gene& clone(void) = 0; |
17 |
// Return the unique type of this gene |
18 |
virtual |
unsigned int type(void) = 0; |
19 |
}; |
|
|
|
|
|
|
tions that all parameter types must implement so that they can be generically manipulated consistently externally. An excerpt of the Gene header file is given in Program 20.1.
Program 20.2: Chromosome header
1class Chromosome
2{
3// Return the number of genes in this chromosome.
4int getNumGenes();
5// Set the gene at a specified index.
6int setGene(int index, Gene* gene);
7// Add a gene to the chromosome.
8int addGene(Gene* gene);
9// Get a gene at a specified index.
10Gene* getGene(int index);
11// Set fitness of chromosome as by ext. fitness function
12void setFitness(double value);
13// Retrieve the fitness of this chromosome
14double getFitness(void);
15// Perform single crossover with a partner chromosome
16virtual void crossover(Chromosome* partner);
17// Perform a mutation of the chromosome
18virtual void mutate(void);
19// Return a new identical copy of this chromosome
20Chromosome& clone(void);
21};
Implementation of Genetic Algorithms
The chromosome class stores a collection of genes in a container class. It provides access to basic crossover and mutation operators. These can be overridden and extended with more complex operators as described earlier. An excerpt of the chromosome header file is given in Program 20.2.
Finally, the population class (Program 20.3) is the collection of Chromosomes comprising a full population. It performs the iterative steps of the genetic algorithm, evolving its own population of Chromosomes by invoking their defined operators. Access to individual Chromosomes is provided, allowing evaluation of terminating conditions through an external routine.
Program 20.3: Population class
1class Population
2{// Initialise population with estimated no. chromosomes
3 |
Population(int |
numChromosomes = 50, |
|
4 |
float |
deceaseRate |
= 0.4f, |
|
5 |
float |
crossoverRate |
= 0.5f, |
); |
6 |
float |
mutationRate |
= 0.05f |
7 |
~Population(); |
|
|
|
8 |
void addChromosome(const Chromosome* c); |
9 |
10
11// Set population parameters
12void setCrossover(float rate);
13void setMutation(float rate);
14void setDecease(float rate);
16// Create new pop. with selection, crossover, mutation
17virtual void evolveNewPopulation(void);
18int getPopulationSize(void);
19Chromosome& getChromosome(int index);
21// Print pop. state, (chromosome vals & fitness stats)
22void printState(void);
24// Sort population according to fitness,
25void sortPopulation(void);
26};
As an example of using these classes, Program 20.4 shows an excerpt of code to solve our quadratic problem, using a derived integer representation class GeneInt and the Chromosome and Population classes described above.
303