Index of Genetic Algorithm


1. Introduction

A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (EA) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).

Definition by Wikipedia

In general the genetic algorithm uses the following search strategy:

  1. Creates an initial population
  2. Repeat until a good solution is found or time exceeded
    1. Evaluate the fitness of each individual
    2. Select individuals for reproducation
    3. Create new individuals using the crossover and mutation
    4. Replace individuals in the population

Each loop of the reproduction is called a generation. To quit the loop there are two common possibilities: If a good solution is found or after a given number of generations (time).

The genetic algorithm of Zeus-Framework is implememted in ZeusMath Package. It implements it in a very abstract way, so it can be used and adapted for different problem domains. There are may different options for each step of the genetic algorithm. Some are implemented in the current version of Zeus-Framework.


2. Structure

The main structure is the population. The population is a set of possible solution items, called individuals. The number of individuals can vary from problem to problem. In some cases a grows is wished. In the implementation of Zeus only a constant number of individuals is supported.

The individual is built out of chromosomes. Each chromosome defines a specific problem of the individual. For simple problems one chromosome is enough.

A chromosome contains genes. Each gene contains a parameter of the problem represented by the whole chromosome.

2.1 Population

The population in Zeus-Framework is the main object and is represented with the class TGAPopulation. Lots of different options can be set for the population:

  • Evaluation types
    • Small fitness is better
    • Large fitness is better
  • How to cross the individuals
    • Crossing of the best individuals only
    • Crossing using all individuals, but giving the best individuals a better chance to get crossed
  • How many individuals have to be crossed for each generation.
  • How large is the mutation propability
  • How to replace the individuals for new population
    • Replace all crossed individuals
    • Replace all individuals
    • Keep the best individuals of the existing population

To create a population a factory method is needed to create specific individuals. Look at the example how to create a population.

2.2 Individual

The individual class is abstract and must be adapted for different problem findings. It contains a list of chromosomes. Each chromosome represents a complete problem description. If there are multible problems to be solved at once using an overall fitness evaluation, each problem can be encoded in a seperate chromosome. Of course we could encode it also in one chromosome, but there are two good reasons to use different chromosomes:

  1. It's easier to encode and test problems seperately and merge them together later
  2. Depending on the problem the crossing might be different. Each chromosome can have a different method in crossing over.

2.3 Chromosome

The class TGAChromosome represents the chromosome of an individual. In general the chromosome is a data array and can be seen as a binary data string. This data string is split into different sections called genes. Each gene has a specific meaning and represents a parameter of the problem space. In the current implementation the size of the genes is fixed for a chromosome.

The genes are an important structure in genetic algorithm. When ever chromosomes are crossed over the genes mark the border line for crossing. It's not possible to split genes. But depending of the crossing method genes of the child might be different from the parent. Lets look at the crossing methods.

There exist different methods of crossing.

  • Multi point crossover
  • Uniform crossover
  • Intermediate Recombination
  • Line recombination

2.3.1 Multi point crossover

This crossover method is widly used to shuffle the different characteristics of an individual and create children out of parents inheriting the characteristics directly. A chromosome of the Parent A and the same chromosomes of the Parent B are aligned. Each border of the genes can be used as a crossing point (1).

Depending on the number of multi crossing points the crossing method choses the crossing points randomly (2).

Once chosen this points the children can be created. Lets start with child A. Child A gets the first genes of parent A until the first crossing point is reached. Then all genes of parent B are copied to the chromosome of child A until the next crossing point is reached. This procedure is continued until the whole chromosome of child A is generated (3).

The chromosome of child B is created in the similar way but starting copying the genes of parent B first (4).

2.3.2 Uniform crossover

The uniform crossover works in the similar way than the multi crossover method, but uses a binary crossover mask with the same length as the chromosome. The parity of the mask bits tell whether to use the information of parent A or B. Using this method crossing at any point is possible (bit tells the borders not the genes). This crossing is not yet supported with Zeus-Framework.

2.3.3 Intermediate Recombination

The inter recombination method can be used for genes of integer or real value type. Each gene can be seen as a component of a chromosome vector. The new genes of the child can be found inside an area called value space. To keep is simple it is implemented as a rectangle (cube etc, depending on the number of dimensions). The space can overlapp. For each gene a factor between [-overlapp] and [1 + overlapp] is chosen randomly.

2.3.4 Line Recombination

This recombination method works in the similar way as inter recombination does. But instead of finding a children in a value space, the children are found on a line. Therefore the randomly chosen factor is used for all genes.

2.3.5 Mutation

Using the mutation some features are randomly changed. Using this method can lead to new individuals in the problem space, where no individuals created by regular crossing exists. Sometimes this can lead to new and better results. Mathematically we can say that using crossing over will find a local optima, where as with mutation new and better optima can be found.

Mutation is not applied to every new child, but applied with a low probability, typically between 0.001 and 0.01. The mutation can be applied directly to the chromosome meaning the binary data string. Or it can be applied as a numerical value, where a number between a defined range is randomly chosen.

In Zeus-Framework the binary mutation is applied if multicrossover is used. For intermediate and line recombination the numerical mutation is used


3. 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

4. Links


5. Introduction Example

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.

Within the Zeus-Framework there are examples included for

  • Goldstein Price problem
  • Travelling Salesman Problem

6. First step: The main program

6.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.

6.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());
}

6.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;
}


7. 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);
}