08. April 2013 · Comments Off on Genetic Algorithms: Examples using Genetic Algorithm Library · Categories: Programming · Tags: , ,

This post explains implementation of two simple genetic algorithms using Genetic Algorithm Library.

To build create a genetic algorithm we need to do following tasks:

  1. Choose representation of the chromosomes
  2. Define fitness operation
  3. Choose crossover and mutation operations and fitness comparator
  4. Choose selection, coupling, replacement, and scaling operations
  5. Choose type of algorithm and stop criteria

Example 1: Finding Minimum of f(x, y) = 5*x*sin(x) + 1.1*y*sin(y); x, y in interval (0, 10)

Important: before using the GAL, GaInitialize must be called. Also, before quitting the application, GaFinalize must be called.

The easiest way is to choose a multi-value chromosome’s representation which supports arithmetic operations [the Chromosome::Representation::GaMVArithmeticChromosome<double> class].

After choosing a chromosome’s representation, the user must define the fitness operation.

class fFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator() (const GaChromosome*
        chromosome) const
    {
        const vector<double>& vals=
            dynamic_cast<const GaMVArithmeticChromosome<double>*>
            (chromosome)->GetCode();

        return 5*vals[0]*sin(vals[0])+1.1*vals[1]*sin(vals[1]);
    }

    virtual GaParameters* GACALL MakeParameters() const { return NULL; }

    virtual bool GACALL CheckParameters(const GaParameters&
        parameters) const { return true; }
};

The fFitness class inherits the GaFitnessOperation class and overrides operator() which calculates the fitness value of the chromosome by evaluating the actual mathematical function.

The next step is to build a chromosome configuration block (CCB) which contains:

  1. pointer to parameters of chromosomes
  2. pointer to genetic operation functors [crossover, mutation, fitness operation, and fitness comparator]
  3. pointer to value set which defines the domain of x and y variables

The class Chromosome::Representation::GaValueInterval<T> is used as the chromosome’s value set because the domain of x and y variables is a continuous interval (0, 10). GaIntervalValueSet requires four bounds [low and high bounds to specify the interval of the original values, and low and high bounds to specify the interval of the inverted values] and a generator of random values.

GaValueIntervalBound<double /> valueInt(0,10);
GaValueIntervalBound<double /> invValueInt(0,10);
GaValueInterval<double /> valueSet(valueInt,invValueInt,
    GaGlobalRandomDoubleGenerator,false);

The CCB should be:

fFitness fitnessOperation;
GaChromosomeDomainBlock<double> configBlock(&valueSet,
    GaCrossoverCatalogue::Instance().GetEntryData(
    "GaMultiValueCrossover"),
    GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
    &fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMinFitnessComparator"),
    &chromosomeParams);

The CCB is defined to use the GaMultiValuesCrossover and GaFlipMutation operations. GaMinFitnessComparator is specified because the purpose of the algorithm is to find the minimum of the function.

When the CCB is defined, the user can build the prototype chromosome:

GaMVArithmeticChromosome<double> prototype(2,&configBlock);

Besides the prototype chromosome, the user must define the population’s parameters before the population object can be created:

  1. population size: 30
  2. resizable population: no [incremental algorithm is used, which does not require resizable population]
  3. population is sorted: yes
  4. scaled fitness is used for sorting: no
  5. tracking of the best chromosomes: 0 [population is already sorted]
  6. tracking of the worst chromosomes: 0 [population is already sorted]
GaPopulationParameters populationParams(30,false,true,false,0,0);

This population object uses the default configuration, except it changes the sort comparator:

  1. selection operations: GaSelectRouletteWheel
  2. number of selected chromosomes: 2
  3. coupling operation: GaInverseCoupling
  4. offspring produced: 2
  5. replacement operation: GaReplaceWorst
  6. chromosomes replaced: 2
  7. scaling operation: none
  8. sort comparator: GaMaxFitnessComparator [default] changed to GaMinFitnessComparator

Everything is now ready to create the population object:

GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
    &configBlock.GetFitnessComparator());

GaPopulation population( &prototype, &populationConfig );

This example uses an incremental genetic algorithm [the GaIncrementalAlgorithm class]. To create the algorithm’s object:

GaMultithreadingAlgorithmParams algorithmParams(1);
GaIncrementalAlgorithm algorithm(&population,algorithmParams);

where the user specifies the population on which the genetic algorithm will operate and the parameters of the algorithm. The constructor of the algorithm’s parameters takes the number of working threads.

When the user builds a genetic algorithm for these kind of problems, it is not possible to know the exact termination criteria of the algorithm. In these situations, it is convenient to use a stop criteria based on the duration of the evolution process or its progress. One such stop criteria is a criteria based on the number of generations. The example uses only one thread because the algorithm produces only a few new chromosomes per generation.

GaGenerationCriteriaParams criteriaParams(100000);

algorithm.SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaGenerationCriteria"),&criteriaParams);

The constructor of the criteria’s parameters takes the number of generations after which the algorithm should stop.

To monitor the evolution process, the user must specify an observer object to the genetic algorithm.

class fObserver : public GaObserverAdapter
{
    virtual void GACALL NewBestChromosome(const GaChromosome&
        newChromosome,const GaAlgorithm& algorithm)
    {
        const vector<double>& vals=
            dynamic_cast<const GaMVArithmeticChromosome<double>&>
            (newChromosome).GetCode();
        cout << "New chromosome found:\n";
        cout << "Fitness: " << newChromosome.GetFitness() << endl;
        cout << "x: " << vals[0] << " y: " << vals[1] << endl;
    }

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState
        newState,const GaAlgorithm& algorithm)
    {
        if(newState==GAS_RUNNING)
            cout << "start\n";
        else if(newState==GAS_CRITERIA_STOPPED)
            cout << "end";
    }
};

To register the observer:

fObserver observer;
algorithm.SubscribeObserver(&observer);

And to start the algorithm:

algorithm.StartSolving(false);

StartSolving‘s parameter defines whether the algorithm should continue a previously paused evolution process [true] or it should start an entirely new process [false].

Example 2: Pattern Matching

Pattern Test Application

Screenshot – Pattern Test application

This example implements a genetic algorithm that tries to guess the sequence of characters. The example defines this sequence of characters:

const char pattern[] =
"        GGGGGGGGGGGGG               AAA               LLLLLLLLLLL             "
"     GGG::::::::::::G              A:::A              L:::::::::L             "
"   GG:::::::::::::::G             A:::::A             L:::::::::L             "
"  G:::::GGGGGGGG::::G            A:::::::A            LL:::::::LL             "
" G:::::G       GGGGGG           A:::::::::A             L:::::L               "
"G:::::G                        A:::::A:::::A            L:::::L               "
"G:::::G                       A:::::A A:::::A           L:::::L               "
"G:::::G    GGGGGGGGGG        A:::::A   A:::::A          L:::::L               "
"G:::::G    G::::::::G       A:::::A     A:::::A         L:::::L               "
"G:::::G    GGGGG::::G      A:::::AAAAAAAAA:::::A        L:::::L               "
"G:::::G        G::::G     A:::::::::::::::::::::A       L:::::L               "
" G:::::G       G::::G    A:::::AAAAAAAAAAAAA:::::A      L:::::L         LLLLLL"
"  G:::::GGGGGGGG::::G   A:::::A             A:::::A   LL:::::::LLLLLLLLL:::::L"
"   GG:::::::::::::::G  A:::::A               A:::::A  L::::::::::::::::::::::L"
"     GGG::::::GGG:::G A:::::A                 A:::::A L::::::::::::::::::::::L"
"        GGGGGG   GGGGAAAAAAA                   AAAAAAALLLLLLLLLLLLLLLLLLLLLLLL";
const int patternSize=sizeof(pattern)-1;

UThe ued symbols are: G,A,L,: and a white space.

The genetic algorithm uses a Chromosome::Representation::GaMVArithmeticChromosome<double> chromosome representation with a defined domain of values by the Chromosome::Representation::GaMultiValueSet<char> class.

GaMultiValueSet<char> valueSet(false);
valueSet.Add("GAL: ","     ",5);

The fitness operation calculates the percent of matched characters and returns that number as the fitness value of the chromosomes:

class pFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator()(const GaChromosome*
        chromosome) const
    {
        const vector<char>& v=
            dynamic_cast<const GaMultiValueChromosome&ltchar>*>
            (chromosome)->GetCode();

        int score=0;
        for(int i=0;i&ltpatternSize;i++)
        {
            if(v[i]==pattern[i])
            score++;
        }

        return (float)score/patternSize*100;
    }

    virtual GaParameters* GACALL MakeParameters() const
        { return NULL; }

    virtual bool GACALL CheckParameters(const GaParameters&
        parameters) const { return true; }
};

The CCB looks like the CCB in the previous example, except it uses a new fitness operation and another fitness comparator, because its objective now is to maximize the fitness:

pFitness fitnessOperation;
GaChromosomeDomainBlock<char /> configBlock(&valueSet,
    GaCrossoverCatalogue::Instance().GetEntryData(
    "GaMultiValueCrossover"),
    GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
    &fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMaxFitnessComparator"),
    &chromosomeParams);

Prototype chromosome:

GaMultiValueChromosome prototype( patternSize, &configBlock );

This example uses a genetic algorithm with non-overlapping populations, and it produces the entire population. To increase the diversity of the produced chromosomes, the number of selected chromosomes is increased. Note that this type of an algorithm requires a resizable population. The population object and its configuration:

GaPopulationParameters populationParams(30,true,true,false,0,0);

GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
    &configBlock.GetFitnessComparator());
populationConfig.Selection().GetParameters().SetSelectionSize(6);

GaPopulation population(&prototype, &populationConfig);

As mentioned, this example uses the Algorithm::SimpleAlgorithms::GaSimpleAlgorithm class for the genetic algorithm.

GaSimpleAlgorithmParams algorithmParams(10,2);
GaSimpleAlgorithm algorithm(&population,algorithmParams);

The first argument of the parameters’ constructor is the elitism depth and the second is the number of working threads. This algorithm produces much more chromosomes per generation than the previous one, so it is suitable for parallelization.

In this example, the exact termination condition is known: when the algorithm finds the chromosome with a fitness value of 100 [100% match]. The right stop criteria is Algorithm::StopCriterias::GaFitnessCriteria:

GaFitnessCriteriaParams criteriaParams(100,GFC_EQUALS_TO,
    GSV_BEST_FITNESS);
algorithm.SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaFitnessCriteria"),
    &criteriaParams);

The observer of the algorithm displays the best chromosomes as they are found:

class pObserver : public GaObserverAdapter
{
public:
    virtual void GACALL NewBestChromosome(const GaChromosome&
        newChromosome,const GaAlgorithm& algorithm)
    {
        const vector<char>& v=
        dynamic_cast<const GaMultiValueChromosome<char>&>
            (newChromosome).GetCode();

        cout<<"Generatiron: "<<
            algorithm.GetAlgorithmStatistics().GetCurrentGeneration()
            <<endl;
        cout<<"Fitness: "<<newChromosome.GetFitness();
        cout<<"\n-------------------------\n";

        for(int i=0;i<v.size();i++)
        {
            if(!(i%78))
                cout<<endl;

            cout<<v[i];
        }
        cout<<"\n-------------------------\n";
    }

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState
        newState,const GaAlgorithm& algorithm)
    {
        if(newState==GAS_CRITERIA_STOPPED)
            cout<<"end.";
    }
};

The subscription of the observer is the same as in the previous example:

pObserver observer;
algorithm.SubscribeObserver( &observer );

The starting of the evolution:

algorithm.StartSolving(false);

Downloads

Source code and Demo applications

08. April 2013 · Comments Off on A Very Brief Introduction to Genetic Algorithms · Categories: Programming · Tags: ,

Genetic algorithms operate on a set of possible solutions called chromosomes. Chromosomes store coded solution and an addition value fitness value. Because of the random nature of genetic algorithms, solutions found by an algorithm can be good, poor, or infeasible [defective, erroneous] and this information is represented by fitness value and it tells genetic algorithm how good the solution is. These are the two main components of a chromosome.

Chromosomes are grouped into population [set of solutions] on which the genetic algorithm operates. In each step [generation], the genetic algorithm selects chromosomes from a population [selection is usually based on the fitness value of the chromosome] and combines them to produce new chromosomes [offspring]. These offspring chromosomes form a new population [or replace some of the chromosomes in the existing population] in the hope that the new population will be better than the previous ones. Populations keep track of the worst and the best chromosomes, and stores additional statistical information which can be used by the genetic algorithm to determine the stop criteria.

A chromosome, in some way, stores the solution which it represents. This is called the representation [encoding] of the solution. There are a number of probable ways to represent a solution in such a way that it is suitable for the genetic algorithm [binary, real number, vector of real number, permutations, and so on] and they mostly depend on the nature of the problem.

Chromosome representation

Diagram – Chromosome representations [for maximization of a single-parameter function]

Chromosome representation

Diagram – Chromosome representations [Traveling Salesman Problem]

Genetic algorithms produce new chromosomes [solutions] by combining existing chromosomes. This operation is called crossover. A crossover operation takes parts of solution encodings from two existing chromosomes [parents] and combines them into a single solution [new chromosome]. This operation depends on the chromosome representation, and can be very complicated. Although general crossover operations are easy to implement, building specialized crossover operations for specific problems can greatly improve the performance of the genetic algorithm.

Crossover Operation Examples

Diagram – Crossover operation examples

Before a genetic algorithm finishes the production of a new chromosome, after it performs a crossover operation, it performs a mutation operation. A mutation operation makes random, but small, changes to an encoded solution. This prevents the falling of all solutions into a local optimum and extends the search space of the algorithm. Mutations as well as crossover operations depend on the chosen representation.

Mutation Operation Examples

Diagram – Mutation operation examples [swap mutation is performed over the first, and over the second, an invert mutation is performed]

Crossover and mutation operations are not always performed when producing a new chromosome. If crossover is not performed, the genetic algorithm produces a new chromosome by copying one of the parents. The rates of crossover and mutation operations are called crossover probability and mutation probability, respectively. The crossover probability is usually high [about 80%], and the mutation probability should be relatively low [about 3%, but for some problems, a higher probability gives better results]. A higher mutation probability can turn the genetic algorithm in to a random search algorithm.

The last operations defined by genetic algorithms used to manipulate chromosomes are fitness operations and fitness comparators. A fitness operation measures the quality of the produced solution [chromosome]. This operation is specific to the problem, and it actually tells the genetic algorithm what to optimize. Fitness comparators [as their name suggests] are used to compare chromosomes based on their fitness. Basically, a fitness comparator tells the genetic algorithm whether it should minimize or maximize the fitness values of chromosomes.

Choosing parents for the production of new chromosomes from a population is called selection. Selection can be based on many different criteria, but it is usually based on the fitness value. The idea behind this is to select the best chromosomes from the parents in the hope that combining them will produce better offspring chromosomes. But, selecting only the best chromosomes has one major disadvantage, all chromosomes in a population will start to look the same very quickly. This narrows the exploration space, pushes the genetic algorithm into the local optimum, and prevents the genetic algorithm from finding possibly better solutions that reside in inaccessible areas of the exploration space. To preserve the diversity of chromosomes [and a wider exploration space] within the population, selection operations usually introduce a factor of randomness in the selection process. Some implementations of selection operations are entirely random.

One problem may occur with selection operations that are based on fitness values. When there is a chromosome with a dominant fitness value, it will be selected most of the times, thus it will cause problems similar to the existing ones. To prevent this, fitness values can be scaled [transformed] to lower the difference between dominant chromosome(s) and the rest of the population [this allows other chromosomes to be selected]. There are many ways to transform a fitness value. Usually, they are implemented by applying a mathematical transformation to the fitness value, but there are other methods like ranking based scaling that use the rank [based on the raw fitness values of chromosomes] of a chromosome as the scaled fitness value.

Scaling Fitness Values

Diagram – Scaling fitness value [shows the selection probability of chromosomes]

A coupling operation defines how the selected chromosomes [parents] are paired for mating [mating is done by performing a crossover operation over the paired parents and applying a mutation operation to the newly produced chromosome]. This operation gives better control over the production of new chromosomes, but it can be skipped and new chromosomes can be produced as the selection operation selects parents from the population.

Coupling Operation Flowchart

Diagram – Coupling operation flowchart

Selection Operation with no Coupling Operation Flowchart

Diagram – Selection operation without coupling operation flowchart

The next step performed by a genetic algorithm is the introduction of new chromosomes into a population. Offspring chromosomes can form a new population and replace the entire [previous] population [non-overlapping population], or they can replace only a few chromosomes in the current population [overlapping population]. For overlapping populations, the replacement operation defines which chromosomes are removed [usually the worst chromosomes] from the current population and which offspring chromosomes are inserted. By replacing chromosomes, there is a chance that the genetic algorithm will lose the best chromosome[s] [found so far]. To prevent this, the concept of elitism is introduced into genetic algorithms. Elitism guarantees that the best chromosome[s] from the current generation are going to survive to the next generation.

An algorithm performs the previously described steps one by one in sequence, and when they have been performed, it is said that a generation has passed. At the end of each generation, the genetic algorithm checks the stop criteria. Because of the nature of genetic algorithms, most of the time, it is not clear when the algorithm should stop, so a criteria is usually based on statistical information such as the number of the generation, the fitness value of the best chromosome, or the average fitness value of the chromosomes in the population, the duration of the evolution process…

Genetic Algorithm Flowchart

Diagram – Flowchart of a genetic algorithm [overlapping population coupling operation]

Genetic Algorithm Flowchart

Diagram – Flowchart of a genetic algorithm [overlapping population without coupling operation]

Genetic Algorithm Flowchart

Diagram – Flowchart of a genetic algorithm [non-overlapping population with coupling operation]