How to structure a Genetic Algorithm class hierarchy?

Question

I'm doing some work with Genetic Algorithms and want to write my own GA classes. Since a GA can have different ways of doing selection, mutation, cross-over, generating an initial population, calculating fitness, and terminating the algorithm, I need a way to plug in different combinations of these. My initial approach was to have an abstract class that had all of these methods defined as pure virtual, and any concrete class would have to implement them. If I want to try out two GAs that are the same but with different cross-over methods for example, I would have to make an abstract class that inherits from GeneticAlgorithm and implements all the methods except the cross-over method, then two concrete classes that inherit from this class and only implement the cross-over method. The downside to this is that every time I want to swap out a method or two to try out something new I have to make one or more new classes.

Is there another approach that might apply better to this problem?

Answer 1

your implementation looks like a Decorator pattern.

Answer 2

I would approach the GA as a collaboration of many objects, rather than one big Class encapsulating the whole algorithm. Basically, you could have an abstract class for every big point of variation, and concrete classes for every implementation choice you want. You then combine the concrete classes you want into many varieties of GA.

Also, you might want to familiarize yourself with the Strategy Pattern: http://en.wikipedia.org/wiki/Strategy%5Fpattern

Answer 3

I think you are over complicating things in your approach. Suggest you download the GAlib package. Even if you only pull the doc in html or pdf format. These libs have been around for a while and I am real sure that you will learn how to structure your lib from looking how is has been done in GAlib.

Answer 4

Some random bits from my part:

• a project you should check out (as a approach) is watchmaker
• the hardest part of building GAs is to find a sensible genetic representation for your problem and building a fitness functions with a good distribution of fitness for a given population
• when dealing with (m)any hard constraints, you could think about introducing a Translator class wich handles the hard constraints, at the cost of (possible) junk DNA and a little performance

Answer 5

Hey.
As people say, don't make it one giant class. That would be horrible. Encapsulate behavior in different classes. Strategy is a solution.
If you need examples download sources and examples of JGAP. It has support for Genetic Programming and Genetic Algorithms. You will see there nice nice design. Mutation,Crossover,Selection,Population,Gene - all this are separate classes. You just setup Configuration object where you initiate defined interfaces with implementations you want to use, pass proper algorithm parameters and you run it. Really package is huge, javadoc nice, and you can always look into the source or check mail group for some answers. When I was looking for GA package I saw GAlib and others but I think this one is most complete with really nice design.

Answer 6

Hi there

The approach I took when implementing my GA framework was as follows: Create the following classes: Generation GeneticAlgorithm GeneticAlgorithmAdapter GeneticAlgorithmParameters Population Individual

Although I didn't implement the strategy pattern for the various operations, I am sure it would be trivial to create various GA operation implementations as parameters on the GeneticAlgorithm instance.

The GeneticAlgorithm class captures the basic algorithm. It really just defines the various steps (population creation, individual randomisation, selection, cross-over, mutation, etc) and manages the populations of individuals as the algorithm runs. I imagine that here you could plug in different operations if you wanted to.

The real magic lies in the adapter. This is what adapts the problem domain (your specific sub classes of the individuals, with all their relevant data) to the genetic algorithm. I use generics a lot here so that the specific types of the population, parameters and individuals are passed into the implementation. This gives me intellisense and strong-type checking for the implementation of the adapter. The adapter basically needs to define how to perform the specific operations for the given individuals (and their genomes). For example, here is the interface for the adapter:

/// <summary>
/// The interface for an adapter that adapts a domain problem so that it can be optimised with a genetic algorithm.
    /// It is a strongly typed version of the adapter.
    /// </summary>
    /// <typeparam name="TGA"></typeparam>
    /// <typeparam name="TIndividual"></typeparam>
    /// <typeparam name="TPopulation"></typeparam>
    public interface IGeneticAlgorithmAdapter<TGA, TIndividual, TGeneration, TPopulation> : IGeneticAlgorithmAdapter
        where TGA : IGeneticAlgorithm
        where TIndividual : class, IIndividual, new()
        where TGeneration : class, IGeneration<TIndividual>, new()
        where TPopulation : class, IPopulation<TIndividual, TGeneration>, new()
    {
        /// <summary>
        /// This gets called before the adapter is used for an optimisation.
        /// </summary>
        /// <param name="pso"></param>
        void InitialiseAdapter(TGA ga);

        /// <summary>
        /// This initialises the individual so that it is ready to be used for the genetic algorithm.
        /// It gets randomised in the RandomiseIndividual method.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="individual">The individual to initialise.</param>
        void InitialiseIndividual(TGA ga, TIndividual individual);

        /// <summary>
        /// This initialises the generation so that it is ready to be used for the genetic algorithm.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="generation">The generation to initialise.</param>
        void InitialiseGeneration(TGA ga, TGeneration generation);

        /// <summary>
        /// This initialises the population so that it is ready to be used for the genetic algorithm.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="population">The population to initialise.</param>
        void InitialisePopulation(TGA ga, TPopulation population);

        void RandomiseIndividual(TGA ga, TIndividual individual);

        void BeforeIndividualUpdated(TGA ga, TIndividual individual);
        void AfterIndividualUpdated(TGA ga, TIndividual individual);

        void BeforeGenerationUpdated(TGA ga, TGeneration generation);
        void AfterGenerationUpdated(TGA ga, TGeneration generation);

        void BeforePopulationUpdated(TGA ga, TPopulation population);
        void AfterPopulationUpdated(TGA ga, TPopulation population);

        double CalculateFitness(TGA ga, TIndividual individual);

        void CloneIndividualValues(TIndividual from, TIndividual to);

        /// <summary>
        /// This selects an individual from the population for the given generation.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="generation">The generation to select the individual from.</param>
        /// <returns>The selected individual.</returns>
        TIndividual SelectIndividual(TGA ga, TGeneration generation);

        /// <summary>
        /// This crosses over two parents to create two children.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="parentsGeneration">The generation that the parent individuals belong to.</param>
        /// <param name="childsGeneration">The generation that the child individuals belong to.</param>
        /// <param name="parent1">The first parent to cross over.</param>
        /// <param name="parent2">The second parent to cross over.</param>
        /// <param name="child">The child that must be updated.</param>
        void CrossOver(TGA ga, TGeneration parentsGeneration, TIndividual parent1, TIndividual parent2, TGeneration childsGeneration, TIndividual child);

        /// <summary>
        /// This mutates the given individual.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="generation">The individuals generation.</param>
        /// <param name="individual">The individual to mutate.</param>
        void Mutate(TGA ga, TGeneration generation, TIndividual individual);

        /// <summary>
        /// This gets the size of the next generation to create.
        /// Typically, this is the same size as the current generation.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="currentGeneration">The current generation.</param>
        /// <returns>The size of the next generation to create.</returns>
        int GetNextGenerationSize(TGA ga, TGeneration currentGeneration);


        /// <summary>
        /// This gets whether a cross over should be performed when creating a child from this individual.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="currentGeneration">The current generation.</param>
        /// <param name="individual">The individual to determine whether it needs a cross over.</param>
        /// <returns>True to perform a cross over. False to allow the individual through to the next generation un-altered.</returns>
        bool ShouldPerformCrossOver(TGA ga, TGeneration generation, TIndividual individual);

        /// <summary>
        /// This gets whether a mutation should be performed when creating a child from this individual.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="currentGeneration">The current generation.</param>
        /// <param name="individual">The individual to determine whether it needs a mutation.</param>
        /// <returns>True to perform a mutation. False to allow the individual through to the next generation un-altered.</returns>
        bool ShouldPerformMutation(TGA ga, TGeneration generation, TIndividual individual);
    }

I have found that this approach works nicely for me because I can easily reuse the GA implementation for different problem domains, just be writing the appropriate adapter. In terms of the different selection, cross-over or mutation implementations, the adapter can call the implementation that it is interested in. What I normally do is comment out different ideas in the adapter while I am investigating an appropriate strategy.

Hope this helps. I can give more guidance where necessary. It's hard to do the design justice like this.