GAL Demo Applications
Contents
IMPORTANT: before using GAL
GaInitialize must be called, also before quitting application
GaFinalize must be called.
The easiest way is to choose multi-value chromosome's representation which supports arithmetic operations [
Chromosome::Representation::GaMVArithmeticChromosome<double> class].
After choosing chromosome's representation, user must define 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; }
};
fFitness class inherits
GaFitnessOperation class and overrides
operator() which calculates fitness value of the chromosome by calculate evaluating actual mathematical function.
Next step is to build 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 domain of
x and y variables
Class
Chromosome::Representation::GaValueInterval<T> is used as chromosome's value set because the domain of
x and
y variables is continuous interval (0, 10).
GaIntervalValueSet requires four bounds [low & high bound to specify interval of original values and low & high bound to specify interval of inverted values] and generator of random values.
GaValueIntervalBound valueInt(0,10);
GaValueIntervalBound invValueInt(0,10);
GaValueInterval valueSet(valueInt,invValueInt,
GaGlobalRandomDoubleGenerator,false);
CCB should be:
fFitness fitnessOperation;
GaChromosomeDomainBlock<double> configBlock(&valueSet,
GaCrossoverCatalogue::Instance().GetEntryData(
"GaMultiValueCrossover"),
GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
&fitnessOperation,
GaFitnessComparatorCatalogue::Instance().GetEntryData(
"GaMinFitnessComparator"),
&chromosomeParams);
CCB is defined to use
GaMultiValuesCrossover and
GaFlipMutation operations.
GaMinFitnessComparator is specified because the purpose of the algorithm is to find minimum of the function.
When CCB is defined user can build prototype chromosomes:
GaMVArithmeticChromosome<double> prototype(2,&configBlock);
Beside prototype chromosome, user must define 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 default configuration, except it changes sort comparator:
- selection operations:
GaSelectRouletteWheel
- number of selected chromosome: 2
- coupling operation:
GaInverseCoupling
- offspring produced: 2
- replacement operation:
GaReplaceWorst
- chromosomes replaced: 2
- scaling operation: none
- sort comparator:
GaMaxFitnessComparator [default] changed to GaMinFitnessComparator
Everything now is ready to create population object:
GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
&configBlock.GetFitnessComparator());
GaPopulation population( &prototype, &populationConfig );
This example use incremental genetic algorithm [
GaIncrementalAlgorithm class]. To create algorithm's object:
GaMultithreadingAlgorithmParams algorithmParams(1);
GaIncrementalAlgorithm algorithm(&population,algorithmParams);
Where the user specify population on which genetic algorithm will operate and parameters of the algorithm. Constructor of the algorithm's parameters takes number of working threads.
When user builds genetic algorithm for these kind of problems it is not possible to know exact termination criteria of the algorithm. In these situations it is convenient to use stop criteria based on duration of evolution process or its progress. On of such stop criteria is criteria based on number of generations. Example uses only one thread because the algorithm produces only few new chromosomes per generation.
GaGenerationCriteriaParams criteriaParams(100000);
algorithm.SetStopCriteria(
GaStopCriteriaCatalogue::Instance().GetEntryData(
"GaGenerationCriteria"),&criteriaParams);
Constructor of criteria's parameters takes number of generations after which the algorithm should stop.
To monitor evolution process user must specify 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 observer:
fObserver observer;
algorithm.SubscribeObserver(&observer);
And to start algorithm:
algorithm.StartSolving(false);
StartSolving's parameter defines whether the algorithm should continue previously paused evolution process [
true] or it should start entirely new process [
false].
Screenshot - Pattern Test application
Next example implements genetic algorithm that tries to guess sequence of characters. 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;
Used symbols are:
G,
A,
L,
: and white space.
Genetic algorithm uses
Chromosome::Representation::GaMVArithmeticChromosome<double> chromosome representation with defined domain of values by
Chromosome::Representation::GaMultiValueSet<char> class.
GaMultiValueSet<char> valueSet(false);
valueSet.Add("GAL: "," ",5);
Fitness operation calculates percent of matched characters and returns that number as 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; }
};
CCB looks like the CCB in the previous example, except it uses new fitness operation and another fitness comparator, because it is now objective to maximize the fitness:
pFitness fitnessOperation;
GaChromosomeDomainBlock 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 genetic algorithm with non-overlapping populations, and it produces entire population. To increase diversity of produced chromosomes the number of selected chromosomes is increased. Note that this type of algorithm requires resizable population. 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
Algorithm::SimpleAlgorithms::GaSimpleAlgorithm class for the genetic algorithm.
GaSimpleAlgorithmParams algorithmParams(10,2);
GaSimpleAlgorithm algorithm(&population,algorithmParams);
The first argument of the parameters' constructor is elitism depth and the second is number of working threads. This algorithm produces much more chromosomes per generation then the previous, so is it is suitable for parallelization.
In this example exact termination condition is known: when the algorithm finds chromosome with 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);
Observer of the algorithm displays the best chromosome 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.";
}
};
Subscription of observer is the same as in previous example:
pObserver observer;
algorithm.SubscribeObserver( &observer );
Starting of evolution:
algorithm.StartSolving(false);
Screenshot - TSP application
Chromosome is an array of cities [pointers to objects of
TspCity class] in order in which they are visited. It is implemented by
TspChromosome class. The class inherits
GaMultiValueChromosome to implement custom initialization of the chromosome by overriding
MakeFromPrototype method. This method copies cities into chromosomes' code and then it shuffles their positions. This class also overrides
MakeCopy method and defines 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 simple single-point or multi-point crossover operation will generate large amount of invalid solutions which degrades algorithm's performance and results. To prevent generation of invalid solutions the algorithm uses custom crossover operation. The operation takes random city from one parent and copies it to 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 child chromosome] if is not already taken. It is taken the operation chooses another connected city. If all 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 cities.
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 built-in
GaSwapMutation operation. Fitness value is equal length of the path.
TspFitnessOperation class implements 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:
- mutation probability: 3%
- mutation size: 2
- improving only mutations: no
- crossover probability: 80%
- number of crossover points: 1 [ignored]
CCB:
TspCrossoverTspSwapMutationTspFitnessOperationTspMinFitnessComparator- Value set is not defined
Population parameters:
- population size: 100
- 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]
Configuration of the population:
GaSelectRandomBest selection which selects 8 chromosomesGaSimpleCoupling which produces 8 offspring chromosomesGaRandomReplaces which replaces 8 chromosomes in each generation, with elitism size of 10 chromosomes- No scaling operation
Algorithm uses
GaFitnessProgressCriteria because exact termination condition it is not know. Criteria will stop algorithm if it is unable to improve fitness value for more then 1 in 50000 generations. Genetic algorithm is incremental.
TSP class is container for the object of the algorithm.
TspCity class represents and stores information about city [such as its coordinates and name]. It has
GetDistance method which calculates distances between the cities.
TspCities manages collection of cities entered by the user.