Genetic Algorithm Class Design

By ai-depot | June 30, 2002

Interface Specification

Rationale

As you may expect, there�s more than one way of implementing this approach. I can think of two major ones, but I�m sure you could think of plenty more.

Template Based

Essentially, you implement a template within a header file, and assume that the candidates provide the necessary functions.

  • Advantages: Deals directly with your candidate class, plain and simply… no overhead for virtual functions, simple constructor calls.
  • Disadvantages: It�s inline code within a header, and not a static class. Using multiple instances will penalise your code size.

Generic Class

Using this approach, the GA class takes a virtual candidate which you need to extend for your own solution. I�m currently using the template approach, but I�m thinking of moving to this more robust approach.

  • Advantages: Standalone compiled C++, of which there�ll be only one instance.
  • Disadvantages: To create new instances, you need a factory; or an embryo and ability to clone it. You also may suffer slightly from virtual function calls.

Interface

Both interfaces are based on the solution that you wish to optimise. This is done via a candidate class, which we�ll define in the next page since we don�t need to know its specification to design the GA class.

Skeleton GA Template

Though the class should come with suitable default parameters, you may want to define a simple interface for passing new custom parameters.

Also, depending on the type of your implementation, you may want to pass Candidate Id�s rather than pointers. This will be especially useful for parallel implementations.

//===================================================================
// GeneticAlgorithm
//===================================================================
template
class GeneticAlgorithm
{
public:

/**
* Fetch a new candidate for the evaluation.
*
* @return A solution that needs to be evaluated.
*/
T * GetCandidate();

/**
* After evaluation, pass back the fitness of a given candidate.
*
* @param candidate Pointer to the candicate which was just evaluated.
* @param fitness Result of the evaluation procedure.
*/
void Report( T * candidate, const float fitness );

}; // class GeneticAlgorithm

That�s pretty much all the functionality you need! Everything else is wrapped inside the class, as a black box. More complex implementations will still seem simple to the user.

Generic Class

This approach has the same type of interface as the template, but it uses virtual candidates. You�ll also need a factory, passed in the constructor.

// Constructor needs a factory
GeneticAlgorithm( const Factory& factory );

// Fetch a new candidate for the evaluation.
Candidate * GetCandidate();

// After evaluation, pass back the fitness of a given candidate.
void Report( Candidate * c, const float fitness );

Note that you will have to type cast the abstract candidates returned by GetCandidate to your own type.

Server Interaction

The game can now run independently from the GA. You�ll run your environment simulation code in the main loop, and do the evolution within the agent�s �think�:

void Agent::Think()
{
// evolve every minute
if (level.time() - start_evolution > 60.0f)
{
// pass back the neural network to the GA
ga.Report( nn, fitness );
// and fetch a new one
nn = ga.GetCandidate();
// store the current time
start_evolution = level.time();
// and reset fitness
fitness = 0;
}

// code based on the candidate
turn = nn->Simulate( getDist(left), getDist(right) );

// fitness evaluation
fitness -= fabsf( turn );
if (Collision())
fitness -= 10.0f;

} // Agent::Think()

Naturally, you can do much more funky stuff just before reporting the fitness, such as saving the best individual, or asking the GA for the best solution after a while. The framework has been established.

Pages: 1 2 3 4

Tags: none
Category: tutorial |

Comments