08. April 2013 · Comments Off on AI for Target Number Game using Genetic Algorithm · Categories: Programming · Tags: , ,

In this game, the player has the task to find a mathematical expression whose value is closest to a randomly chosen value using only basic operations and a predefined set of numbers. The game has other restrictions: all intermediate results and the final result must be positive integer numbers. Additional restrictions are also placed on the selected and target numbers. The player gets four random numbers between 1 and 9, one number from the { 10, 15, 20 } set and one from the { 25, 50, 75, 100 } set. The target number is randomly chosen from the interval [100,999]. The player can use the selected numbers only once. Whoever has the expression with the closest number to the target wins, and if there is a tie, the player who was choosing the numbers wins.

ga_tng_app

Number of Possible Expressions

Before implementing the actual algorithm for solving this problem, it would be interesting to see how many expressions we can make using the selected numbers and basic operations. The number of possible expression trees for a defined number of leafs (numbers used in the expression) is defined by the Catalan number where n should be the number of leafs minus 1.

The number of possible expressions is also governed by the number of performed operations and the number of combinations of the selected numbers. The number of combinations is defined by the binomial coefficient where n is the count of selected numbers and k is the count of numbers that we actually use in the expression (expression tree leafs).

The final formula for calculating the number of expressions that can be made using n numbers, assuming that we only use the basic math operations { +, -, *, / } is where n is the count of selected numbers that we can use. The actual count of expressions that we should search using brute force algorithm can be reduced to since expressions that don’t use all the selected numbers are already represented by the subtrees of the longest possible expressions (the ones that use all the numbers). This formula yields around 600,000 expressions for 6 numbers, but many of these expressions are not valid (they may contain division by zero or division operations that don’t produce an integer result), or they are not different in any significant way from other expressions, so the actual count can be reduced even further.

Genetic Algorithm

In this example, a genetic algorithm is used instead of the brute force algorithm. Genetic Algorithm Library is used to implement the algorithm. Detailed information for implementing custom genetic operations are provided in the referenced article and they won’t be discussed here.

Chromosome

The first that should be considered is how to represent an expression with a chromosome in GA that will be suitable for performing the various genetic operations and which will allow them to preserve and propagate the good characteristics to the offspring.

Representation

This example will use a tree representation of the expression which will allow crossover and mutation operations to be implemented easily. Another thing that should be considered is that the genetic algorithm can produce many erratic expressions, introduce useless operations into an expression, or build many chromosomes with different expression trees for expressions that are essentially the same. Solutions for these problems are discussed in the next two sections.

A node of the expression tree is represented by the TngNode struct.

struct TngNode
{

  TngNodeType _type;
  int _value;

  /* structure of the tree */
  TngNode* _left;
  TngNode* _right;
  TngNode* _parent;

  /* ... */

};

The _type field stores the type of the node (whether the node is a number or operation, and if it is an operation, which operation it is). If the node type is number, the _value field stores the index of the selected number stored in the node; otherwise, this field is unused.

The chromosome is represented by the TngChromosome class. The selected and target numbers are stored in a chromosome configuration block represented by TngConfigBlock.

class TngConfigBlock : public Chromosome::GaChromosomeOperationsBlock
{

private:

  int _numbers[ TNG_NUMBER_COUNT ];
  int _targetNumber;

public:

  TngConfigBlock(Chromosome::GaCrossoverOperation* crossoverOperation,
    Chromosome::GaMutationOperation* mutationOperation,
    Chromosome::GaFitnessOperation* fitnessOperation,
    Chromosome::GaFitnessComparator* fitnessComparator,
    Chromosome::GaChromosomeParams* parameters);

  TngConfigBlock(const int* numbers,
    int targetNumber,
    Chromosome::GaCrossoverOperation* crossoverOperation,
    Chromosome::GaMutationOperation* mutationOperation,
    Chromosome::GaFitnessOperation* fitnessOperation,
    Chromosome::GaFitnessComparator* fitnessComparator,
    Chromosome::GaChromosomeParams* parameters);

  TngConfigBlock(const TngConfigBlock& rhs);
  inline void GACALL SetNumbers(const int* numbers);
  inline int* GetNumbers();
  inline const int* GetNumbers() const;
  inline void GACALL SetTargetNumber(int number);
  inline int GACALL GetTargetNumber() const;

};

class TngChromosome : public Chromosome::GaDynamicOperationChromosome
{

private:

  TngNode* _root;
  TngNode* _backup;

public:

  TngChromosome(TngConfigBlock* configBlock) ;
  TngChromosome(const TngChromosome& c, bool setupOnly);
  virtual ~TngChromosome();
  virtual Chromosome::GaChromosomePtr GACALL MakeCopy(
    bool setupOnly) const;
  virtual Chromosome::GaChromosomePtr GACALL MakeNewFromPrototype() const;
  virtual void GACALL PreapareForMutation();
  virtual void GACALL AcceptMutation();
  virtual void GACALL RejectMutation();
  inline void GACALL SetRoot(TngNode* root);
  virtual int GACALL GetCodeSize(void) const;
  inline TngNode* GACALL GetRoot();
  inline const TngNode* GACALL GetRoot() const;
  virtual bool GACALL operator ==(const Chromosome::GaChromosome& c) const;

};

Calculating the value of an expression is performed by in-order traversal of the expression tree calculating the value of each node.

int GACALL TngAdd(int a, int b) { return a + b; }
int GACALL TngSub(int a, int b) { return a - b; }
int GACALL TngMul(int a, int b) { return a * b; }
int GACALL TngDiv(int a, int b) { return !b || a % b ? a : a / b; }

typedef int (GACALL *TngOp)(int, int);
TngOp TngOps[] = { TngAdd, TngSub, TngMul, TngDiv };

inline int GACALL TngOpExec(TngNodeType nodeType,
  int a,
  int b) { return TngOps[ nodeType - 1 ]( a, b ); }

int GACALL TngCalculateValue(const TngNode* node,
  const int* values)
{
  if( node->_type == TNT_NUMBER )
    return values[ node->_value ];

    return TngOpExec( node->_type,
      TngCalculateValue( node->_left, values ),
      TngCalculateValue( node->_right, values ) );
}

Notice that the division operation has special cases for invalid operands. Why such situations are handled in this way is explained in the next section.

Reduction of Expression Tree

The purpose of the reduction operation is to remove useless and erratic operations from the expression. Cases which will trigger reduction are:

  • division by zero,
  • division that does not produce an integer number, and
  • operations that yield the same result as one of their sub-expressions (i.e., multiplying or dividing by an expression that has a value of 1, and adding or subtraction of expressions that has a value of 0).

This operation replaces the expression with its sub-expression that yields the same result if such a sub-expression exists. As it is explained in the previous section, invalid division operations return a result as if the operation was not performed, effectively eliminating it from the expression.

reduction of + operation reduction of * operation
reduction of invalid / operation reduction to an equivalent sub tree

Reduction is implemented by the TngReduceTree function.

Normalization of Expression Tree

Normalization transforms encoding by changing the order in which successive + and * operations are performed and the order of their operands. Operands or sub-expressions of these operations are sorted by their value in increasing order. That way, we can transform many seemingly different expressions to a single form.

normalization of + and * operations

Similar transformations can be applied to successive – and / operations, but these are not implemented in this example.

While the motivation for a reduction operation is quite clear, the need for normalization operation is not so obvious. Allowing different encodings to represent the same solution effect of implicit parallelism is diminished as one of the strongest features of a genetic algorithm, and its performance is severely reduced. Performing this transformation ensures that encodings obey convention that reduces the number of duplicate encodings, effectively narrowing the search space and improving the algorithm’s performance.

Normalization is implemented by the TngNormalizeTree function.

Fitness assignment

The fitness operation calculates how far off is the value of the expression from the targeted number. The actual fitness function is , where t is the target number and n is the calculated value of the expression. This means that the fitness values are in the range (0,1] and a greater value means the chromosome is closer to the target number. The algorithm can stop when a chromosome with a fitness value of 1 is found.

Crossover

Crossover makes an offspring chromosome by copying an expression tree of one of its parents, but it removes a random sub-tree from the copy and inserts a random sub-tree of the other parent in place of the one removed. Crossover must ensure that the inserted sub-tree does not contain numbers already used in the rest of the offspring tree. To do this, it selects a pair of sub-trees that will not produce an expression tree with more numbers than is allowed; after that, if it detects that the expression uses a number more times than is allowed, the operation simply replaces it with an unused number. After crossover, reduction and normalization are performed.

Crossover is implemented by the TngCrossover class.

Mutation

There are two types of mutation performed on a chromosome. The first one swaps positions of two random sub-trees and the second flips an operation or number randomly. Each type of mutation has equal chances of being performed. After a mutation is performed, chromosomes are reduced and normalized.

Mutation type I
Mutation type II

Mutation is implemented by the TngMutation class.

Algorithm Setup

In each generation, the algorithm selects eight parents using roulette wheel selection and produces eight parents using simple coupling that uses the custom crossover and mutation operations described previously. The algorithm replaces chromosomes which have the worst fitness with the produced offspring. Offspring chromosomes that are already in the population are not inserted.

CpuPlayer wraps the genetic algorithm and provides an interface to the other parts of the application. The constructor of the class initializes parameters and configurations of the genetic algorithms, and the Start method make an instance of the algorithm and starts it.

CpuPlayer::CpuPlayer(CStatic* cpuStatus,
  CListCtrl* populationContent) : _result(0), _cpuStatus(cpuStatus),
  _populationContent(populationContent), _algorithm(NULL),
  _chromosomeParams( 0.3f, 1, false, 0.8f, 1 ),
  _configBlock( &_crossover, &_mutation,
    &_fitnessOperation, GaFitnessComparatorCatalogue::Instance()
    .GetEntryData( "GaMaxFitnessComparator" ),
    &_chromosomeParams ),
  _populationParams( 32, false, true, false, 0, 0 ),
  _populationConfig( _populationParams,
    &_configBlock.GetFitnessComparator(),
    GaSelectionCatalogue::Instance().GetEntryData(
    "GaSelectRouletteWheel" ),
    &Population::SelectionOperations::GaSelectDuplicatesParams( false, 8 ),
    GaReplacementCatalogue::Instance().GetEntryData(
    "GaReplaceWorst" ),
    &Population::GaReplacementParams( 8 ),
    GaCouplingCatalogue::Instance().GetEntryData(
    "GaSimpleCoupling" ),
    &Population::GaCouplingParams( 8 ),
    NULL, NULL),
  _algorithmParams( 2 ) { } 
Algorithm parameters
mutation probability: 30%
mutation size: 1 gene
only accept mutations that improve fitness: yes
crossover probability: 80%
crossover points: 1
population size: 32 chromosomes
sorted population: yes
fitness sorting: maximization
selection type: roulette wheel
selection size: 8
coupling type: simple coupling
number of offsprings to produce: 8
replacement type: replace worst
chromosomes to replace: 8
number of worker threads: 2
void CpuPlayer::Start(const NumberGenerator& numbers)
{
  _populationContent->DeleteAllItems();

  _configBlock.SetNumbers( numbers.GetGenerated() );
  _configBlock.SetTargetNumber(
    numbers[ NumberGenerator::NUMBERS_TO_GENERATE - 1 ] );

  TNG::TngChromosome prototype( &_configBlock );
  Population::GaPopulation population( &prototype, &_populationConfig );
  Algorithm::SimpleAlgorithms::GaIncrementalAlgorithm algorithm(
    &population, _algorithmParams );

  _algorithm = &algorithm; 

  TNG::TngStopCriteriaParams criteriaParams( GAME_TIME - 2 );
  algorithm.SetStopCriteria( &_stopCriteria, &criteriaParams);

  algorithm.SubscribeObserver( this );

  algorithm.StartSolving( false );
  algorithm.WaitForThreads();
}

Custom stop criteria are implemented by the TngStopCriteria class. It causes the genetic algorithm to stop when chromosomes with a fitness value of 1 is found or just before time expires. Parameters for this stop criteria are handled by TngStopCriteriaParams and they store the time when the algorithm was started and the duration of the game.

Supporting Classes

Generating numbers is managed by the NumberGenerator class. Timing is implemented in the Timer class. The InputManager class manages, parses, and calculates the player’s input. The Results struct stores the state of the game after it ends. The game flow is implemented by the Master class. These classes are located in the Game namespace.

Parsing User’s Expression

Parsing and calculating user’s expressions is implemented by the two classes Lexer and Parser located in the Parsing namespace.

Lexer reads tokens from input and feeds the parser. A token is represented by the LexSymbol struct.

struct LexSymbol
{
  LexSymbolType _type;
  int _value;
  int _position;

  /* ... */
};

_type stores a type of token, the _value field stores information that depends on the type of token, and _position stores the position of the token’s first character in the input.

LexSymbolType defines the allowed token types:

enum LexSymbolType
{
  LEX_ST_PARENS_OPEN,
  LEX_ST_PARENS_CLOSE,
  LEX_ST_NUMBER,
  LEX_ST_OPERATOR,
  LEX_ST_END
};

For the LEX_ST_NUMBER token, the value field stores the actual number, and for LEX_ST_OPERATOR, the field stores the type of operator:

enum LexOperatorType
{
  LEX_OT_PLUS,
  LEX_OT_MINUS,
  LEX_OT_TIMES,
  LEX_OT_OVER
};

The Get method of the Lexer class implements tokenization of the input string and returns the next token. If the end of input is reached, the method returns a LEX_ST_END token. When an invalid character is detected, it throws a SyntaxException.

LexSymbol Lexer::Get()
{
  int c = GetChar();
  switch( c )
  {
  case '(':
    return LexSymbol( LEX_ST_PARENS_OPEN, GetPosition() );
  case ')':
    return LexSymbol( LEX_ST_PARENS_CLOSE, GetPosition() );
  case '+':
    return LexSymbol( LEX_ST_OPERATOR, LEX_OT_PLUS, GetPosition() );
  case '-':
    return LexSymbol( LEX_ST_OPERATOR, LEX_OT_MINUS, GetPosition() );
  case '*':
    return LexSymbol( LEX_ST_OPERATOR, LEX_OT_TIMES, GetPosition() );
  case '/':
    return LexSymbol( LEX_ST_OPERATOR, LEX_OT_OVER, GetPosition() );
  case -1:
    return LexSymbol( LEX_ST_END, GetPosition() );

  default:
    if( !IsDigit( c ) ) throw SyntaxException( GetPosition() );

    int pos = GetPosition(), num = ToNum( c );
    while( IsDigit( PeekChar() ) )
      num = num * 10 + ToNum( GetChar() );

    return LexSymbol( LEX_ST_NUMBER, num, pos );
  }
}

The Parse method of the Parser class analyzes tokens and calculates the value of the user’s expression. This method will throw one of the following exceptions: SyntaxException, InputException, or ArithmeticException, or it will return the value of the expression if there were no errors. If a list of allowed numbers is provided as an argument to the method, it will throw an InputException if the illegal number is detected in the user’s input; otherwise, all numbers are allowed. An ArithmeticException is thrown when an illegal arithmetic operation is detected (such as a division by zero), and finally, a SyntaxException is thrown when there is a syntax error in the user’s input.

int Parser::Parse(int count/* = 0*/,
       const int* allowedNumbers/* = NULL*/)
{
  for( int i = count - 1; i >= 0; i-- )
    _allowedNumber[ allowedNumbers[ i ] ]++;

  while( 1 )
  {
    LexSymbol symbol = _lexer.Get();

    switch( symbol._type )
    {

    case LEX_ST_END: return Calculate( symbol._position );
    case LEX_ST_PARENS_OPEN:
      OpenParens( symbol._position );
      break;
    case LEX_ST_PARENS_CLOSE:
      CloseParens( symbol._position );
      break;
    case LEX_ST_NUMBER:
      StoreNumber( symbol._value, symbol._position );
      break;
    case LEX_ST_OPERATOR:
      StoreOperator( symbol._value, symbol._position );
      break;
    }
  }

  throw SyntaxException( -1 );
}

StoreOperator, StoreNumber, OpenParens, and CloseParens store operations that should be performed, and calculates the order (priority) of their execution. The Calculate method performs stored operations according to their priority and calculates the expression’s value.

Downloads

Source code and Demo application

08. April 2013 · Comments Off on Solving Traveling Salesperson Problem using Genetic Algorithm · Categories: Programming · Tags: , ,

We are going implement genetic algorithm that solves Traveling Salesperson Problem using Genetic Algorithm Library.

Traveling Salesperson Problem Application

Screenshot – TSP application

The chromosome is an array of cities [pointers to objects of the TspCity class] in the order in which they are visited. It is implemented by the TspChromosome class. The class inherits GaMultiValueChromosome to implement a custom initialization of the chromosome by overriding the MakeFromPrototype method. This method copies cities into the chromosomes’ code and then it shuffles their positions. This class also overrides the MakeCopy method and defines a copy constructor.

class TspChromosome : public GaMultiValueChromosome<const TspCity*>
{
public:
    TspChromosome(GaChromosomeDomainBlock<const TspCity*>* configBlock) :
        GaMultiValueChromosome(configBlock) { }

    TspChromosome(const TspChromosome& chromosome,
        bool setupOnly) :
        GaMultiValueChromosome<const TspCity*>(chromosome, setupOnly) { }

    virtual GaChromosomePtr GACALL MakeCopy(bool setupOnly) const
        { return new TspChromosome( *this, setupOnly ); }

    virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;

    int GACALL GetCityPosition(const TspCity* city) const;
};

Using a simple single-point or multi-point crossover operation will generate a large amount of invalid solutions which degrades the algorithm’s performance and results. To prevent the generation of invalid solutions, the algorithm uses a custom crossover operation. The operation takes a random city from one parent and copies it to the child chromosome. Then, it searches for the cities which are connected to the chosen city [in both parents] and takes the nearest one [and copies it to the child chromosome] if it is not already taken. It is taken if the operation chooses another connected city. If all the connected cities are taken, the operation randomly chooses a city that has not been taken. Then, the crossover uses that city to extend the path in the same way. The process is repeated to select all the cities. The TspCrossover class implements this crossover operation:

class TspCrossover : public GaCrossoverOperation
{
public:
    virtual GaChromosomePtr GACALL operator ()(
        const GaChromosome* parent1,
        const GaChromosome* parent2) const;

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

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

private:
    inline void SelectNextCity(const TspCity* previousCity,
        const TspCity** currentBestNextCity,
        const TspCity* nextCity) const;
};

The algorithm uses the built-in GaSwapMutation operation. The fitness value is equal to the length of the path. The TspFitnessOperation class implements the fitness operation:

class TspFitness : public GaFitnessOperation
{
public:
    virtual float GACALL operator ()(
        const GaChromosome* chromosome) const;

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

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

Parameters of chromosomes:

  1. mutation probability: 3%
  2. mutation size: 2
  3. improving only mutations: no
  4. crossover probability: 80%
  5. number of crossover points: 1 [ignored]

CCB:

  1. TspCrossover
  2. TspSwapMutation
  3. TspFitnessOperation
  4. TspMinFitnessComparator
  5. Value set is not defined

Population parameters:

  1. population size: 100
  2. resizable population: no [an incremental algorithm is used which does not require a 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]

Configuration of the population:

  1. GaSelectRandomBest selection which selects 8 chromosomes
  2. GaSimpleCoupling which produces 8 offspring chromosomes
  3. GaRandomReplaces which replaces 8 chromosomes in each generation, with an elitism size of 10 chromosomes
  4. No scaling operation

The algorithm uses GaFitnessProgressCriteria because the exact termination condition is not known. The criteria will stop the algorithm if it is unable to improve the fitness value for more than 1 in 50000 generations. The genetic algorithm is incremental.

The TSP class is the container for the object of the algorithm. The TspCity class represents and stores information about a city [such as its coordinates and name]. It has the GetDistance method which calculates the distances between the cities. TspCities manages the collection of cities entered by the user.

Downloads

Source code and Demo application

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