Index of Genetic Algorithm

• 1. Introduction
• 2. First step: The main program
  • 2.1 Creating the Population
  • 2.2 Best fitness
  • 2.3 Factory function to create individuals
• 3. Second step: The individuals
• 4. Downloads

1. Introduction

The following example illustrates how to use and implement genetic algorithm. The example shows the typical problem of "the travelling salesman", witch takes a long time to solve using a deterministic algorithm.

2. First step: The main program

2.1 Creating the Population

First we must create a population. The population is a container for individuals. To create those individuals we must register a factory function at the population and set several flags to tell it how to cross the individuals and how to replace a old generation.

TAutoPtr>TGAPopulation> pPopulation = 
  new TGAPopulation(
          /*Factory function*/
          createExampleIndividuals,
          /*Keep the best parent individuals*/
          TGAPopulation::etKeepBestParents,
          /*The best will have more chance to be crossed*/
          TGAPopulation::etCrossBestPrior,
          /*Priorize smaller fitness (shorter way to visit cities)*/  
          TGAPopulation::etSmallerBetter, 
          /*Replace 80% of the population with new children*/  
          80.0
        );

We must create now our individuals (100 examples in our demo). To do so we call following method:

pPopulation->createPopulation(100);

This will create 100 individuals using the factory function, we have registered before. This generation of individuals is called initial generation.

Now we are ready for our little evolution process. We want to cross those 100 individuals and produce children, hoping those will inhire the good genes of their parents. In our example we will produce generations automatically and we want to abort after 40 generation, if no better individual has been found. The return value of this method contains the count of generations totally produced.

long dCount = pPopulation->makeGenerations(40);

An other way to produce generations is the method makeNewGeneration(). You may call this method iterativly inside a loop.

2.2 Best fitness

Its time to get the best individual and its fitness:

TAutoPtr<IGAIndividual> pIndividual = NULL;
if (pPopulation->getBestIndividual(pIndividual) == RET_NOERROR)
{
  printf("\nFitness of the best is: %f\n", pIndividual->getFitness());
}

2.3 Factory function to create individuals

We are almost done. We need a factory function, witch creates our own individuals. This function has a defined signature shown above:

static unsigned long createExampleIndividuals(
                        IGAIndividual*& ind, 
                        bool create_chromosones)
{
  ind = new TExIndividual(g_SalesManProblem);
    
  if (create_chromosones)
  {
    ind->createChromosones();
  }
  return RET_NOERROR;
}

3. Second step: The individuals

In this section we will show how to implement an individual. The Zeus-Framework provides an abstract class TGAIndividual. You may inherit from this class. Only two method have to be implemented, the getFitness() and the createChromosones().

class TExIndividual : public TGAIndividual
{
  public:
    TExIndividual(TTravellingSalesMan& salesman); 
    
    //Methods of IGAIndividual
    virtual double MQUALIFIER getFitness();
    virtual void MQUALIFIER createChromosones();

    ...

  protected:
    virtual ~TExIndividual();
  
  private:
    ///Travelling sales man object
    TTravellingSalesMan& m_SalesMan;
};

At the beginning we have to create chromosones for each individual. A chromosone is a set of data, stored in genes. Each chromosone type has a unique type id. Only chromosones with the same type id can be crossed. A chromosone has a specific way of crossing. In our case we use customized crossing and therefore we have to register our crossing function. Our chromosone represents the the order how we visit the cities. This is generated using the random function of the TTravellingSalesMan class.

Note:
Each individual can have more than just one chromosone.

void MQUALIFIER TExIndividual::createChromosones()
{
  TGAChromosome* pChrom = new TGAChromosome(0, 
                                            TGAChromosome::etCustom, 
                                            customCrossFunction);
  TArrayList<long> lstCities;
  m_SalesMan.getRandomWay(lstCities);
  long lCount = lstCities.getCount();
  for(int i = 0; i < lCount; i++)
  {
    TAutoPtr<TGAGene> pGene = new TGAGene(lstCities[i]);
    pChrom->addGene(*pGene);
  } 

  this->m_lstChromosomes.add(pChrom);
}

The fitness tells the selection witch individual to prefere. Individuals with a good fitness are prefered, means the chance to get crossed is higher. In our travelling sales man problem we use the class TTravellingSalesMan, witch calculates the length of the route.

double MQUALIFIER TExIndividual::getFitness()
{
  TArrayList<long> lstCities;
  TAutoPtr<IGAChromosome> pChromosome = NULL;
  if (this->getChromosome(0, pChromosome) == RET_NOERROR)
  {
    long lCount = pChromosome->getGeneCount();
    for(int i = 0; i < lCount; i++)
    {
      TAutoPtr<IGAGene> pGene = NULL;
      if (pChromosome->getGene(i, pGene) == RET_NOERROR)
      {
        lstCities.add(pGene->getIntContent());
      }
    }
  }
  return m_SalesMan.calcWay(lstCities);
}

4. Downloads

The examble is included in the Zeus-Framework. You find the code in the /src/examples/genetic/ directory.
Go to the download page here