Genetic Algorithm Class Design
By ai-depot | June 30, 2002
Most GA libraries today are intended for pure optimisation, and in most cases are ill-suited to game-like world simulations. This feature discusses a new approach to GA class design, using an object oriented server-client paradigm. A C++ interface skeleton is provided.
Written by Alex J. Champandard.
Introduction & Motivation
Introduction
So you�ve plodded through all the information you could find in the Genetic Algorithms Warehouse, and you�ve decided you�re ready to implement something. If you want to get off on the right foot by designing an elegant flexible solution, then you�ll have to think about it yourself ;) This tutorial simply intends to introduce a radically new approach to GA class design, which has many advantages over the standard approach. It is then your choice which you prefer and which implementation fits in best with your requirements.
Those of you familiar with standard GA implementations will have noticed some unpleasing aspects of the code, and may welcome the new ideas presented here.
Problems
Most Genetic Algorithm implementations I�ve seen so far work on the same principle: the GA takes control of the simulation. We�ll take as an example the reference of Genetic Algorithm Libraries: Matthew Wall�s GALib.
Notice how the main optimisation loop is defined and controlled by the library:
// from example 17
GASteadyStateGA ga(genome);
ga.populationSize(popsize);
ga.pMutation(pmut);
ga.pCrossover(pcross);
ga.evolve();// alternatively, from the more explicit example 23
while (!ga.done())
{
ga.step();
}
More specifically, this is possible since a feedback hook was provided to a user-defined fitness function:
// from example 15
float objective(GAGenome &);GABin2DecGenome genome(map, objective, (void *)target);
Though this is one of the best libraries I�ve seen and remains the reference in the field, this paradigm is ill-suited to anything but raw optimisation. When the GA is no longer allowed to be in control, like in a complex environment simulation this approach fails.
Note: Having the GA run as a separate process may suit your requirements, but for some this raises other crucial design issues… read on!
Motivation
Lets assume you have modelled a realistic world, like in a real-time game. This environment is the main focus of the application, and its handling takes the centre stage. As such the GA must be considered as a third-party library that contributes to the simulation of the world, and no longer the main loop itself.
This environment hosts a wide variety of creatures, each more or less based on Evolutionary Algorithms. Some agents have components based on a shared GA library, and others are entirely based on their own Genetic Algorithm. Each of these agents are embedded within physical creatures and though their fitness can be evaluated explicitly, it is more of an implicit consequence of the agent �living� for a small amount of time.
Having the GA library work as a black box makes all this possible in a very elegant fashion. The agents request candidate solutions when they need them, and return the results of the evaluation when they consider the time is right. Additionally, this implies that optimisation and simulation can be handled in the same fashion: once satisfactory results are observed in the behaviour, the best solution can be requested from the GA library. This model is therefore well suited to online evolution, but off-line optimisation is just as easy.
Tags: none
Category: tutorial |
