Getting started

This guide will lead you through the example implementation of a simple genetic algorithm.
Source codes for this example can be found in trunk/Nage/Nage.Examples.Rastrigin and trunk/Nage/Nage.GeneticAlgorithm folders.

The problem

In this example we will try to solve the minimization problem of the Rastrigin's function.
the Rastrigin function is a non-convex function used as a performance test problem for optimization algorithms.
It is a typical example of non-linear multimodal function.
It is a fairly difficult problem due to its large search space and its large number of local minima.

The Rastrigin function is defined by:


where A = 10 and
It has a global minimum at f(0) = 0

Rastrigin function of two variables looks like this:

The representation

Let's now create a representation of individuals in the population by creating a class Coordinates.
Solution implementation should implement Nage.Algorithms.Solution.ISolution interface.
All we know that it is a vector of double values, and that each indivitual should contain its fitness value.

Coordinates.cs

Now let's create a class responsible for creating individuals.
Such classes are called factories and should implement Nage.Algorithms.Solution.ISolutionFactory<TSol> parametrized with the type of solution (in our case Coordinates class)

CoordinatesFactory.cs

Solution factories provide useful methods for creating empty and initialized individuals in our population.
To initialize Coordinates a Random number generator is used to populate each vector with values that matches the domain of our problem.

Let's also create a class representing a population called CoordinatesPopulation - the container for individuals.
It should implement Nage.Algorithms.Population.IPopulation<TSol> interface
parametrized with a type of solution. To make it possible to iterate through the population
we should also derived the class from Collection<TSol>.

CoordinatesPopulation.cs

The last thing to do is to create a class that is able to create the whole initialized population.
This is also going to be a factory but this time it should implement Nage.Algorithms.Population.IPopulationFactory<TSol> paramertized as previously.
Let's call it CoordinatesPopulationFactory

CoordinatesPopulationFactory.cs

Thanks to CreatePopulation method we are able to create a complete population
at once. It is assumed that population factories should contain a reference to proper solution factory and should use it in CreatePopulation method respectively.

The evolution

To define the evolution procedure we should start with our cost function.
It should take Coordinates as parameter and return the double fitness value.
Thanks to the cost function we will be able to evalute each and every population's individual
and choose the best solutions in current population to reproduction.
Let's create a RastriginFunctionEvaluator class. Our fitness function should
implement Nage.Algorithms.Solution.ISolutionEvaluator<TSol> interface parametrized with a type of our solution.
The function implements Evaluate method which is basically the coded equivalent of mathematical notation described in the problem section of this article.

RastriginFunctionEvaluator.cs

Afterwards, lets move on to evolution operators: Mutation and Recombination.
The mutation operator in our case should modify coordinates within delta parameter with a given probability.
Let's create a CoordinatesMutation class. Our mutation operator should implement
Nage.Algorithms.Evolution.ISolutionMutation<TSol> interface parametrized with a type of our solution.

CoordinatesMutation.cs

This class implements Mutate method which should return a new, mutated individual.

The recombination operator in our case should take two individuals as parents and return two
children with Coordinates vector partially taken from first parent and partially from second (divison based on probability).
Let's create a CoordinatesRecombination class. Our recombination operator should implement
Nage.Algorithms.Evolution.ISolutionRecombination<TSol> interface parametrized with a type of our solution.

CoordinatesRecombination.cs

The last thing to do is to define evolution strategy that uses both previously created operators and our cost function.
Let's create a CoordinatesEvolution class which derives from Nage.Algorithms.Evolution.Evolution<TSol> class parametrized with a type of our solution.
This class, or the implementation of an abstract method Evolve to be precise, provides a logic to switch between generations.

CoordinatesEvolution.cs

The Evolve method ranks the current generation by applying the fitness function,
generates the next generation by roulette selection of individuals that should breed and applying the evolution operators on their children.

Putting it all together

So far we have created all of the components that needed to be implemented in our genetic algorithm.
The last thing we are going to need is the stop condition.
We can make use of predefined Nage.Algorithms.Stop.FixedStepsStopCondition
or create a custom stop condition that implements Nage.Algorithms.Stop.IStopCondition
For the purpose of this example let's use the first one.

Let's wrap it all together with Nage's genetic algorithm container.
We can do it by using either procedural or declarative approch.

Procedural approach

We can create RastriginProblem class that derives from Nage.Algorithms.GeneticAlgorithm<Coordinates>,
set all of the properties in the constructor and then use the instance of this class
to solve our problem.

RastriginProblem.cs

This approach, however, is not flexible when it comes to algorithm's parameters configuration.

Declarative approach

With help of Unity IoC Container we can declare the structure of our algorithm in xml file. It's as easy as building a brick wall.

Let's create a new Console Application with the following Main method

static void Main(string[] args)
{
    IUnityContainer container = new UnityContainer();
    UnityConfigurationSection section = (UnityConfigurationSection)ConfigurationManager.GetSection("unity");
    section.Configure(container);

    IGAWrapper wrapper = container.Resolve<IGAWrapper>();
    wrapper.Solve();

    Console.Read();
}

And the App.config file:

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
    <configSections>
      <section name="unity" type="Microsoft.Practices.Unity.Configuration.UnityConfigurationSection, Microsoft.Practices.Unity.Configuration"/>
    </configSections>

  <unity xmlns="http://schemas.microsoft.com/practices/2010/unity">
      <assembly name="Nage.Algorithms" />
      <namespace name="Nage.Algorithms" />
      <namespace name="Nage.Algorithms.Solution" />
      <namespace name="Nage.Algorithms.Population" />
      <namespace name="Nage.Algorithms.Evolution" />
      <namespace name="Nage.Algorithms.Stop" />

      <assembly name="Nage.Examples.Rastrigin" />
      <namespace name="Nage.Examples.Rastrigin" />
      <namespace name="Nage.Examples.Rastrigin.Solution" />
      <namespace name="Nage.Examples.Rastrigin.Population" />
      <namespace name="Nage.Examples.Rastrigin.Evolution" />

      <alias alias="SolutionType" type="Nage.Examples.Rastrigin.Solution.Coordinates, Nage.Examples.Rastrigin" />
    
      <container>        
        <register name="SolutionFactory" type="ISolutionFactory[SolutionType]" mapTo="CoordinatesFactory">
          <constructor>
            <param name="min" value="-5" />
            <param name="max" value="5" />
            <param name="dimensions" value="10" />
          </constructor>
        </register>
        
        <register name="PopulationFactory" type="IPopulationFactory[SolutionType]" mapTo="CoordinatesPopulationFactory">
          <constructor>
            <param name="populationSize" value="100" />
            <param name="solutionFactory" dependencyName="SolutionFactory"/>
          </constructor>
        </register>
        
        <register name="SolutionEvaluator" type="ISolutionEvaluator[SolutionType]" mapTo="RastriginFunctionEvaluator"></register>
        
        <register name="StopCondition" type="IStopCondition" mapTo="FixedStepsStopCondition">
          <constructor>
            <param name="stepCount" value="1000" />
          </constructor>
        </register>

        <register name="Mutation" type="ISolutionMutation[SolutionType]" mapTo="CoordinatesMutation">
          <constructor>
            <param name="mutationRate" value="0.1" />
            <param name="delta" value="0.5" />
          </constructor>
        </register>

        <register name="Recombination" type="ISolutionRecombination[SolutionType]" mapTo="CoordinatesRecombination" />
        
        <register name="Evolution" type="IEvolution[SolutionType]" mapTo="CoordinatesEvolution">
          <constructor>
            <param name="mutation" dependencyName="Mutation"/>
            <param name="recombination" dependencyName="Recombination"/>
            <param name="crossoverRate" value="0.8" />
          </constructor>
        </register>
        
        <register name="GeneticAlgorithm" type="IGeneticAlgorithm[SolutionType]" mapTo="GeneticAlgorithm[SolutionType]">
          <property name="PopulationFactory" dependencyName="PopulationFactory"/>
          <property name="SolutionEvaluator" dependencyName="SolutionEvaluator"/>
          <property name="StopCondition" dependencyName="StopCondition"/>
          <property name="Evolution" dependencyName="Evolution"/>
        </register>

        <register type="IGAWrapper" mapTo="GAWrapper[SolutionType]">
          <property name="Algorithm" dependencyName="GeneticAlgorithm"/>
        </register>
        
      </container>
    </unity>
  </configuration>

The definition file:
  • alias SolutionType defines a type of individuals
  • SolutionFactory provides a mapping for solution factory implementation
  • PopulationFactory provides a mapping for population factory implementation
  • SolutionEvaluator provides a mapping for particular cost function implementation
  • Mutation provides a mapping for mutation operator
  • Recombination provides a mapping for recombination operator
  • Evolution provides a mapping for evolution strategy (note that it uses both evolution operators and cost function implementation)
  • GeneticAlgorithm binds the whole algorithm together
  • IGAWrapper provides a solution type-unaware wrapper for our algorithm.

Now we can modify and play with all of the parameters without code interfering.

Last edited Jan 7, 2013 at 9:23 PM by marochm, version 13

Comments

No comments yet.