Genetic Algorithm Module Design

The preceding two sections mentioned that most of the work is done in custom genetic operators. The evolutionary procedure itself is relatively simple, too. This predicament is quite common, so the need for a genetic algorithm code is often as a set of helper functions. Common idioms and patterns for evolutionary algorithms are easily created as standalone functions.

Having the genetic algorithm as a separate module is very debatable in this case, and in fact, we may not use it at all. However, creating a robust genetic algorithm module will give us the luxury of the choice. The component will come in handy in other situations where more robust solutions are required. Ideally, we want a module that brings together the common evolutionary patterns and genetic operators, one that also allows configurability and customizability.

Role of the Genetic Algorithm

It's important to realize that the genetic algorithm is nothing more than an optimization strategy in most cases. This implies that the functionality of the evolved object does not change in any way; only a different quality of service is provided.

Many genetic algorithm libraries focus on the evolutionary loop and provide various hooks for evaluating custom objects defined by the user. This approach is appropriate when there is one simple component being optimized as a precomputation. For complex systems with multiple components, or animats that evolve throughout their lifetime, however, the genetic algorithm needs to take a supporting role—leaving the center stage to the components providing the functionality.

Interfaces

The external interface (exported) of the genetic algorithm consists of a unique entry point, used to report the fitness of the candidate currently being evaluated. This could easily be handled by message passing if this proves more convenient:

void ReportFitness( const float f );

The internal interface (imported) lies between the genetic algorithm and the component being evolved (for instance, rule-based system). This interface is called evolvable, exported by all components that can be optimized by an evolutionary algorithm.

The main principle to implement a truly flexible genetic algorithm module is to let the evolved component perform all the genetic operations. This avoids the major overhead (in coding and execution time) of converting each of the phenotypes to genotypes and back. This is sometimes known as evolutionary data structures, although I prefer the term phenotype-specific operators. The main idea is that it is unnecessary—and inconvenient—to convert between representations. The genetic operators often need to be customized anyway. When standard data structures and genetic operators are used, common helper functions can be reused.

The phenotype-specific operators are exposed by the evolvable interface. There are also functions available to initialize the population and control the evaluation:

void Crossover( const Individual& a, const Individual& b, Individual& c );
void Mutate( const Individual& a, const Individual& b, Individual& c );
void Randomize( Individual& a );
void Allocate( vector<Individual*>& population );
void Deallocate( vector<Individual*>& population );
void Evaluate( const Individual& a );

The genetic algorithm is thereby completely independent from the implementation details of the client component. The Individual is an empty base class defined with a pure virtual copy operator (so that the genetic algorithms can perform assignments without knowing the details of the data structure).

To use the genetic algorithms module to evolve our sequences of actions, we need to implement each of these functions. Most of this functionality will need to be implemented anyway, so it's mainly a matter of preference whether it's modular or not.