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:

- Choose representation of the chromosomes
- Define fitness operation
- Choose crossover and mutation operations and fitness comparator
- Choose selection, coupling, replacement, and scaling operations
- 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:

- pointer to parameters of chromosomes
- pointer to genetic operation functors [crossover, mutation, fitness operation, and fitness comparator]
- pointer to value set which defines the domain of
and`x`

variables`y`

The class `Chromosome::Representation::GaValueInterval<T>`

is used as the chromosome’s value set because the domain of * x* and

*variables is a continuous interval (0, 10).*

`y`

`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:

- population size: 30
- resizable population: no [incremental algorithm is used, which does not require resizable population]
- population is sorted: yes
- scaled fitness is used for sorting: no
- tracking of the best chromosomes: 0 [population is already sorted]
- 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:

- selection operations:
`GaSelectRouletteWheel`

- number of selected chromosomes: 2
- coupling operation:
`GaInverseCoupling`

- offspring produced: 2
- replacement operation:
`GaReplaceWorst`

- chromosomes replaced: 2
- scaling operation: none
- 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*

*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<char>*> (chromosome)->GetCode(); int score=0; for(int i=0;i<patternSize;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:

GaMultiValueChromosomeprototype( 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);