10 Lessons About C++(2015)
Chapter 7: A Genetic Algorithm Function Optimizer
An example is presented here on how an algorithm employing standard genetic operators crossover, mutation and selection can be applied to optimize a standard mathematical function, such as the Rosenbrock function:
The Rosenbrock function is a non-convex function used to test the efficiency and effectiveness of optimization algorithms introduced by Howard H. Rosenbrock in 1960. The Rosenbrock function is defined by:
As shown in the diagram, the global minimum lies inside a long, narrow, parabolic shaped flat valley. Locating the valley vicinity is fairly straightforward. Converging to the global minimum, located at:
is trickier. This application employs standard genetic operators crossover, mutation and selection as applied to chromosome representations of floating-point numbers. There are a number of possible ways of representing real numbers using binary arrays. In this application, the IEEE 754 standard is one such method, where the the floating-point number is represented in 32 bits. Experiments using Gray codes are also presented. In short, The first bit represents the sign (0 = plus, 1 = minus); the following 8 bits store the biased exponent (bias=127) and the remaining 23 bits represent the fractional part (mantissa). An in-depth description of how these operators work is beyond the scope of this post and there there is a wealth of material already available. The code samples given here should be reasonably self-explanatory.
The 32-bit binary encodings are implemented using the Chromosome class as a means of housing the binary values and performing other simple get/set tasks amd so forth. The Population class maintains a population of Chromosome objects and applies the standard genetic operators crossover, mutation and selection on them. It also generates an initial arbitrary population of chromosomes with random values and has other helper functions with which to convert between binary and decimal representations of the binary strings:
The GeneticAlgorithm class runs the genetic algorithm operators and applies them to the population of chromosomes with the intention of progressively improving the overall solution fitness.
Running the Genetic Algorithm using IEEE 754 encodings
I have run a number of simple experiments to see how well the algorithm converges over 10,000 iterations. For the first experiment (using the IEEE 754 bit string representation for floating-point numbers) the algorithm parameters used were as follows:
encoding_type = 1; // IEEE 754
crossover_rate = 50;
mutation_rate = 5;
population_size = 100;
tournament_size = population_size / 4;
I use tournament selection as the preferred ‘survival of the fittest’ mechanism. The code has a simple logger enabling you to dump results to a text file. In this example I enabled it return the best fitness found so far at every generation. A graph showing the best value found at every 10th iteration:

The global minimum for this particular function is 0.0 and in this run the algorithm got it down to 0.02. As you can see, no further reduction takes place for the next 800 or so iterations.
Feel free to try out this code and improve upon it, or apply it to your own area of interest.
Running the Genetic Algorithm using Gray codes
As a follow up to this experiment, I have included an additional means of interpreting the binary chromosomes presented to the genetic algorithm. For the next experiment I used a Gray encoding, whereby two successive values differ by only one bit. For a 32-bit Gray code, I used the first bit as the sign bit, so that a ‘0’ corresponds to a plus and a ‘1’ corresponds to a minus.
For the remaining bits, I extract the decimal value and then divide this by 2^n - 1 to get the real number in the interval 0 to 1.
After doing a some experiments with parameter values I found that a nice combination seemed to be:
encoding_type = 0; // Gray code
crossover_rate = 70;
mutation_rate = 5;
population_size = 100;
tournament_size = population_size / 4;
My perception is that the algorithm performance using Gray codes seemed to converge somewhat more easily than those of IEEE 754.
However, this observation is only on the basis of the few simple experiments I have done so far. The algorithm in this case managed to get the value of f(x,y) down to 0.00538112 (x = 0.932924,y = 0.873316) within the same number of iterations. A plot for this run is shown below.
Full Code Listings
Chromosome.h
#pragma once
const int chrSize = 64;
class Chromosome
{
public:
Chromosome(void);
~Chromosome(void);
void SetFitness( const double& value );
void SetChromosome( const int& index, const unsigned char& value );
unsigned char GetChromosome( const int& index );
double GetFitness() const;
int size() const;
void Print( const int& index ) const;
private:
unsigned char chr[ chrSize ];
double fitness;
};
GeneticAlgorithm.h
#pragma once
#include "Population.h"
#include "Log.h"
class GeneticAlgorithm
{
public:
GeneticAlgorithm(void);
~GeneticAlgorithm(void);
void Initialize( const int& enc,
const int& crate,
const int& mrate,
const int& psize,
const int& iter,
const int& csize,
const int& tsize,
const std::string& path );
void Run();
private:
void CreatePopulation();
double Evaluate();
void Crossover();
void Mutate();
void Select();
void SetParameters( const int& enc,
const int& crate,
const int& mrate,
const int& psize,
const int& iter,
const int& csize,
const int& tsize );
void LogResult( const double& result,
const int& iter,
const int& count );
private:
int encoding;
int mutationRate;
int crossoverRate;
int populationSize;
int numberIterations;
int chromosomeSize;
int tournamentSize;
int bestFitnessIndex;
double bestFitness;
float best_x;
float best_y;
Population pop;
Log log;
};
Log.h
#pragma once
#include <fstream>
class Log
{
public:
Log();
Log( char* );
~Log();
void Write( char* txt );
void Open( const char* );
private:
std::ofstream m_stream;
};
Population.h
#pragma once
#include <vector>
#include <string>
#include "Chromosome.h"
const double infinity = 9999999999999;
class Population
{
public:
enum Encoding {
GRAY = 0,
IEEE_754,
};
Population(void);
~Population(void);
void SetChromosomeEncoding( const int& type );
void SetChromosomeSize( const int& size );
void CreateRandomPopulation( const int& size );
void Crossover( const int& index1,
const int& index2,
const int& point );
void Crossover( const int& index1,
const int& index2,
const int& point1,
const int& point2 );
void Mutation( const int& index );
double EvaluatePopulation( float& bx, float& by );
double CalcChromosomeFitness( const int& index,
float& xv,
float& yv);
double GetChromosomeFitness( const int& index ) const;
void CopyChromosome( const int& source, const int& dest );
private:
Chromosome* CreateRandomChromosome();
std::string GetXstring( Chromosome* chr );
std::string GetYstring( Chromosome* chr );
float GetFloat32_IEEE754( std::string Binary );
float GetFloat32_Gray( std::string Binary );
int Binary32ToHex( std::string Binary );
double CalculateFitnessFunction( const float& x,
const float& y );
double CalcChromosomeFitness_IEEE754( const int& index,
float& xv, float& yv);
double CalcChromosomeFitnessGray( const int& index,
float& xv, float& yv );
std::string Gray2Bin( std::string gray );
long Bin2Dec( std::string bin );
private:
std::vector< Chromosome* > pop;
int chrSize;
int encoding;
};
Chromosome.cpp
#include "Chromosome.h"
#include <iostream>
// Constructor
Chromosome::Chromosome(void) {}
// Destructor
Chromosome::~Chromosome(void) {}
// Set chromosome element
void Chromosome::SetChromosome( const int& index, const unsigned char& value )
{
if ( index < 0 || index >= chrSize ) return;
chr[ index ] = value;
}
// Get chromosome element
unsigned char Chromosome::GetChromosome( const int& index )
{
unsigned char element = chr[ index ];
return element;
}
// Set fitness of chromosome
void Chromosome::SetFitness( const double& value )
{
fitness = value;
}
// Get chromosome fitness
double Chromosome::GetFitness() const
{
return fitness;
}
// Get number of elements in the chromosome
int Chromosome::size() const
{
return chrSize;
}
// Output the chromosome and its fitness
void Chromosome::Print( const int& index ) const
{
std::string str;
for ( int i = 0; i < chrSize; i++ ) {
unsigned char value = chr[ i ];
str.append( value == 0 ? "0" : "1" );
}
std::cout << index << "\t" << str.c_str() << "\t" << fitness << std::endl;
}
GeneticAlgorithm.cpp
#include "GeneticAlgorithm.h"
#include <sstream>
#include <stdlib.h>
#include <math.h>
const std::string filepath = "C:\\dump\\best.txt";
GeneticAlgorithm::GeneticAlgorithm(void)
{
// Give it some default parameters
encoding = 0;
mutationRate = 5;
crossoverRate = 90;
populationSize = 100;
numberIterations = 10000;
chromosomeSize = 64;
tournamentSize = populationSize / 5;
bestFitness = infinity;
}
GeneticAlgorithm::~GeneticAlgorithm(void)
{}
// Initialize parameters, generate population etc
void GeneticAlgorithm::Initialize( const int& enc,
const int& crate,
const int& mrate,
const int& psize,
const int& iter,
const int& csize,
const int& tsize,
const std::string& path )
{
SetParameters( enc, crate, mrate, psize, iter, csize, tsize );
CreatePopulation();
log.Open( path.c_str() );
}
// Run the genetic algorithm
void GeneticAlgorithm::Run()
{
for ( int i = 0; i < numberIterations; i++ ) {
LogResult( Evaluate(), i, 10 );
Select();
Crossover();
Mutate();
}
}
// Evaulate fitnesses of population chromosomes
double GeneticAlgorithm::Evaluate()
{
float bx = -1;
float by = -1;
double best = pop.EvaluatePopulation( bx, by );
if ( best < bestFitness ) {
bestFitness = best;
best_x = bx;
best_y = by;
}
return bestFitness;
}
// Apply crossover to selected chromosome pairs
void GeneticAlgorithm::Crossover()
{
for ( int i = 0; i < populationSize; i++ ) {
int r = rand() % 100;
if ( r < crossoverRate ) {
int index1 = rand() % populationSize;
int index2 = rand() % populationSize;
while ( index1 == index2 ) {
index2 = rand() % populationSize;
}
// Get crossover points
// Point1: 0 - 31
int point1 = rand() % chromosomeSize / 2;
// Point1: 32 - 64
int point2 = chromosomeSize / 2 +
rand() % ( chromosomeSize / 2 );
while ( point1 == point2 ) {
point2 = chromosomeSize / 2 +
rand() % ( chromosomeSize / 2 );
}
if ( point1 > point2 ) {
int tmp = point1;
point1 = point2;
point2 = tmp;
}
// Do 1-point crossover
pop.Crossover( index1, index2, point1, point2 );
}
}
}
// Mutate selected chromosomes
void GeneticAlgorithm::Mutate()
{
for ( int i = 0; i < populationSize; i++ ) {
int r = rand() % 100;
if ( r < mutationRate ) {
pop.Mutation( i );
}
}
}
// Select population chromosomes according to fitness
// Using a pairwise tournament selection mechanism
void GeneticAlgorithm::Select()
{
// For each pair of chromosomes selected
int i = 0;
while ( i < tournamentSize ) {
// Get the chromosome pair for tournament selection
int index1 = rand() % populationSize;
int index2 = rand() % populationSize;
while ( index1 == index2 ) {
index2 = rand() % populationSize;
}
double fitness1 = fabs( pop.GetChromosomeFitness( index1 ) );
double fitness2 = fabs( pop.GetChromosomeFitness( index2 ) );
// We seek to find [x,y] that minimizes this function
// The bigget the value returned, the lower its fitness
if ( fitness1 > fitness2 ) {
// Copy chromosome 1 elements into chromosome 2
pop.CopyChromosome( index2, index1 );
}
else {
// Copy chromosome 2 elements into chromosome 1
pop.CopyChromosome( index1, index2 );
}
i++;
}
}
// Set mutation rate, population size etc
void GeneticAlgorithm::SetParameters( const int& enc,
const int& crate,
const int& mrate,
const int& psize,
const int& iter,
const int& csize,
const int& tsize )
{
mutationRate = mrate;
crossoverRate = crate;
populationSize = psize;
numberIterations = iter;
chromosomeSize = csize;
tournamentSize = tsize;
pop.SetChromosomeEncoding( enc );
}
// Create initial random population of chromosomes
void GeneticAlgorithm::CreatePopulation()
{
pop.CreateRandomPopulation( populationSize );
}
// Log the value to a text file
void GeneticAlgorithm::LogResult( const double& result,
const int& iter,
const int& count )
{
if ( iter % count == 0 ) {
std::stringstream ss;
ss << iter << "\t" << result << "\t" << best_x << "\t" << best_y;
log.Write( (char*) ss.str().c_str() );
}
}
Log.cpp
#include "Log.h"
Log::Log()
{}
Log::Log( char* filename )
{
m_stream.open( filename, std::fstream::app );
}
void Log::Write( char* txt )
{
m_stream << txt << std::endl;
}
Log::~Log()
{
m_stream.close();
}
// Open the log file for writing
void Log::Open( const char* filename )
{
m_stream.open( filename, std::fstream::app );
}
Population.cpp
#include "Population.h"
#include <bitset>
#include <iostream>
#include <math.h>
#include <stdlib.h>
const int divisor_32 = 4294967295; // 2 ^ 32 - 1
const int divisor_31 = 2147483647; // 2 ^ 31 - 1
Population::Population(void)
{
// Set default chromosome size
chrSize = 64;
}
Population::~Population(void)
{
int size = (int) pop.size();
for ( int i = 0; i < size; i++ ) {
Chromosome* chr = pop.at( i );
if ( chr ) {
delete chr;
}
}
pop.clear();
}
// Set the type of chromosomal encoding used: IEEE 754, Gray etc
void Population::SetChromosomeEncoding( const int& type )
{
encoding = type;
}
// Create initial arbitrary population of chromosomes
void Population::CreateRandomPopulation( const int& size )
{
for ( int i = 0; i < size; i++ ) {
Chromosome* chr = CreateRandomChromosome();
pop.push_back( chr );
}
}
// Apply one-point crossover to selected chromosome pair
void Population::Crossover( const int& index1, const int& index2,
const int& point )
{
if ( point < 0 || point >= chrSize ) return;
Chromosome* chr1 = pop.at( index1 );
Chromosome* chr2 = pop.at( index2 );
for ( int i = point; i < chrSize; i++ ) {
unsigned char v1 = chr1->GetChromosome( i );
unsigned char v2 = chr2->GetChromosome( i );
chr1->SetChromosome( index1, v2 );
chr2->SetChromosome( index1, v1 );
}
}
// Apply one-point crossover to selected chromosome pair
void Population::Crossover( const int& index1, const int& index2,
const int& point1, const int& point2 )
{
if ( point1 < 0 || point1 >= chrSize ) return;
if ( point2 < 0 || point2 >= chrSize ) return;
int p1 = point1;
int p2 = point2;
if ( p1 > p2 ) {
int tmp = p1;
p1 = p2;
p2 = tmp;
}
Chromosome* chr1 = pop.at( index1 );
Chromosome* chr2 = pop.at( index2 );
// Do crossover on x portion of chromosome:
// either before or after point p1
int start = 0;
int end = p1;
if ( rand() % 100 < 50 ) {
start = p1;
end = chrSize / 2;
}
for ( int i = start; i < end; i++ ) {
unsigned char v1 = chr1->GetChromosome( i );
unsigned char v2 = chr2->GetChromosome( i );
chr1->SetChromosome( i, v2 );
chr2->SetChromosome( i, v1 );
}
// Do crossover on x portion of chromosome
// either before or after point p2
start = 0;
end = p2;
if ( rand() % 100 < 50 ) {
start = p2;
end = chrSize;
}
for ( int i = start; i < end; i++ ) {
chr1->SetChromosome( i, chr2->GetChromosome( i ) );
chr2->SetChromosome( i, chr1->GetChromosome( i ) );
}
}
// Apply mutation to selected chromosome: x part or y part
void Population::Mutation( const int& index )
{
Chromosome* chr = pop.at( index );
bool xpart = rand() % 100 < 50 ? true : false;
int start = xpart ? 0 : chrSize / 2;
int end = xpart ? chrSize / 2 : chrSize;
for ( int i = start; i < end; i++ ) {
unsigned char value = chr->GetChromosome( i );
value = value == 0 ? 1 : 0;
chr->SetChromosome( i, value );
}
}
// Evaluate the population fitnesses
double Population::EvaluatePopulation( float& bx, float& by )
{
double totalFitness = 0.0;
//double aveFitness = 0.0;
double bestFitness = infinity;
int bestFitnessIndex = 0;
for ( int i = 0; i < (int) pop.size(); i++ ) {
float x, y;
double fitness = CalcChromosomeFitness( i, x, y );
Chromosome* chr = pop.at( i );
chr->SetFitness( fitness );
// Output the chromosome (optional - comment out if desired)
chr->Print( i );
totalFitness += fitness;
// Store best solution
if ( i == 0 ) bestFitness = fitness;
if ( fitness < bestFitness ) {
bestFitness = fitness;
bestFitnessIndex = i;
bx= x;
by= y;
}
}
std::cout << "\n\n";
//aveFitness = totalFitness / pop.size();
return bestFitness;
}
// Create an arbitrary random chromosome
Chromosome* Population::CreateRandomChromosome()
{
Chromosome* chr = new Chromosome();
// Randomize chromosome elements
for ( int i = 0; i < chr->size(); i++ )
{
unsigned char value = rand() % 100 < 50 ? 0 : 1;
chr->SetChromosome( i, value );
}
return chr;
}
// Calculate chromosome fitness according to chromosome encoding used
double Population::CalcChromosomeFitness(
const int& index,
float& xv,
float& yv)
{
if ( encoding == GRAY )
{
return CalcChromosomeFitnessGray( index, xv, yv );
}
else
{
return CalcChromosomeFitness_IEEE754( index, xv, yv );
}
}
// Get fitness of selected chromosome according to IEEE 754 coding
double Population::CalcChromosomeFitness_IEEE754(
const int& index,
float& xv,
float& yv )
{
// Get the chromosome elements
Chromosome* chr = pop.at( index );
// Put the first 32 bits (X) into a string
std::string xstr = GetXstring( chr );
// Get x value by converting from IEEE 754 into decimal
float x = GetFloat32_IEEE754( xstr );
// Put the next 32 bits (Y) into a string
std::string ystr = GetYstring( chr );
// Get y value by converting from IEEE 754 into decimal
float y = GetFloat32_IEEE754( ystr );
double fitness = CalculateFitnessFunction( x, y );
// Return the chromosome fitness
xv = x;
yv = y;
return fitness;
}
// Get fitness of selected chromosome according to Gray coding
double Population::CalcChromosomeFitnessGray(
const int& index,
float& xv,
float& yv )
{
// Get the chromosome elements
Chromosome* chr = pop.at( index );
// Put the first 32 bits (X) into a string
std::string xstr = GetXstring( chr );
// Get x value by converting from Gray into decimal
float x = GetFloat32_Gray( xstr );
// Put the next 32 bits (Y) into a string
std::string ystr = GetYstring( chr );
// Get y value by converting from Gray into decimal
float y = GetFloat32_Gray( ystr );
double fitness = CalculateFitnessFunction( x, y );
// Return the chromosome fitness
xv = x; yv = y;
return fitness;
}
// Set the size of the chromosome
void Population::SetChromosomeSize( const int& size )
{
chrSize = size;
}
// Get the 'X' string portion of tye chromsome
std::string Population::GetXstring( Chromosome* chr )
{
std::string xstr;
for ( int i = 0; i < chrSize / 2; i++ )
{
unsigned char value = chr->GetChromosome( i );
xstr.append( value == 0 ? "0" : "1" );
}
return xstr;
}
// Get the 'Y' string portion of the chromsome
std::string Population::GetYstring( Chromosome* chr )
{
std::string ystr;
int start = chrSize / 2;
for ( int i = start; i < chrSize; i++ )
{
unsigned char value = chr->GetChromosome( i );
ystr.append( value == 0 ? "0" : "1" );
}
return ystr;
}
// Convert 32-bit binary into the decimal
// IEEE 754 encoding for 32 bit binary string
float Population::GetFloat32_IEEE754( std::string Binary )
{
int HexNumber = Binary32ToHex( Binary );
bool negative = !!(HexNumber & 0x80000000);
int exponent = (HexNumber & 0x7f800000) >> 23;
int sign = negative ? -1 : 1;
// Subtract 127 from the exponent
exponent -= 127;
// Convert mantissa into decimal using last 23 bits
int power = -1;
float total = 0.0;
for ( int i = 0; i < 23; i++ )
{
int c = Binary[ i + 9 ] - '0';
total += (float) c * (float) pow( 2.0, power );
power--;
}
total += 1.0;
float value = sign * (float) pow( 2.0, exponent ) * total;
return value;
}
// Convert 32-bit gray encoding into the decimal equivalent
float Population::GetFloat32_Gray( std::string Binary )
{
// Get sign bit
int sign = Binary.at( 0 ) == '0' ? 1 : -1;
// Get remaining string
std::string rem = Binary.substr( 1 );
std::string bin = Gray2Bin( rem );
long bin_val = Bin2Dec( bin );
float val = (float) bin_val / (float) divisor_31;
val *= sign;
return val;
}
// Convert the 32-bit binary encoding into hexadecimal
int Population::Binary32ToHex( std::string Binary )
{
std::bitset<32> set(Binary);
int hex = set.to_ulong();
return hex;
}
// Calculate the overall fitness, f(x, y)
double Population::CalculateFitnessFunction( const float& x,
const float& y )
{
// Rosenbrock: (1-x)^2 + 100(y-x*x)^2
// (see http://en.wikipedia.org/wiki/Rosenbrock_function)
double fitness = ( pow( (double)( 1.0 - x ), 2 ) ) +
100 * ( pow( (double) ( y - ( x * x ) ), 2 ) ) ;
return fitness;
}
// Get fitness of selected chromosome
double Population::GetChromosomeFitness( const int& index ) const
{
// Get the chromosome
Chromosome* chr = pop.at( index );
return chr->GetFitness();
}
// Copy the contents of the source chromosome into destination
void Population::CopyChromosome( const int& source, const int& dest )
{
// Get the chromosomes
Chromosome* chr1 = pop.at( source );
Chromosome* chr2 = pop.at( dest );
// Copy elements and fitness of source chromosome
// into the destination chromosome
for ( int i = 0; i < chrSize; i++ ) {
// Get source chromosome element
unsigned char value = chr1->GetChromosome( i );
// Write this element value into the destination element
chr2->SetChromosome( i, value );
}
// Set the destination chromosome fitness
double fitness = chr1->GetFitness();
chr2->SetFitness( fitness );
}
// Convert gray encoding into binary
std::string Population::Gray2Bin( std::string gray )
{
int len = gray.length();
std::string bin = gray;
for ( int i = len - 2; i >= 0; i-- )
{
int bk = bin.at( i + 1 ) - '0';
int gi = gray.at( i + 1 ) - '0';
if ( bk == 0 )
{
bin[ i ] = gi == 1 ? '1' : '0';
}
else
{
bin[ i ] = gi == 1 ? '0' : '1';
}
}
return bin;
}
// Binary to int
long Population::Bin2Dec( std::string bin )
{
char * ptr;
long parsed = strtol( bin.c_str(), & ptr, 2 );
return parsed;
}
main.cpp
#include "Log.h"
#include <sstream>
#include "GeneticAlgorithm.h"
const int encoding_type = 0;
const int crossover_rate = 70;
const int mutation_rate = 5;
const int population_size = 100;
const int number_iterations = 10000;
const int chromosome_size = 64;
const int tournament_size = population_size / 4;
int main()
{
// Run the GA!
GeneticAlgorithm ga;
ga.Initialize( encoding_type,
crossover_rate,
mutation_rate,
population_size,
number_iterations,
chromosome_size,
tournament_size,
"C:\\dump\\best.txt" );
ga.Run();
return 0;
}
Chapter Summary
To summarize, this master lesson provides:
·A practical example of how to develop a genetic algorithm application in C++ and apply it to a difficult optimization problem to generate better solutions over successive iterations.
·A demonstration of how it is possible to improve the performance of a genetic algorithm by experimenting with binary encodings such as IEEE 754 and Gray and by varying the rates of genetic operator crossover, mutation and selection.