﻿ ﻿A Genetic Algorithm Function Optimizer - 10 Lessons About C++ (2015)

# 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.

﻿