A class to implement the Genetic Algorithm optimization method. More...

#include <GeneticAlgorithm.hpp>

Inheritance diagram for Unfit::GeneticAlgorithm:

Public Member Functions
	GeneticAlgorithm ()

virtual	~GeneticAlgorithm ()

int	FindMin (GenericCostFunction &CostFunction, std::vector< double > &coordinates) override
	A method to find a minimum point of a function using a Genetic Algorithm approach. More...

void	Reset () override

Public Member Functions inherited from Unfit::GenericOptimizer
	GenericOptimizer ()

virtual	~GenericOptimizer ()

void	ResetGenericOptimizer ()

virtual double	GetCost (std::size_t index=0) const noexcept

virtual bool	GetIsPopulationBased () const noexcept

virtual std::size_t	GetNumberOfIterations () const noexcept

virtual std::size_t	GetNumberOfFunctionEvaluations () const noexcept

virtual std::vector< std::vector< double > >	GetPopulation () const

virtual std::vector< double >	GetSolution (std::size_t index=0) const

virtual void	SetPopulation (const std::vector< std::vector< double >> &population)

Private Member Functions
void	GeneratePopulation (GenericCostFunction &CostFunction)

void	InitialiseBounds ()

void	CrossOver (const std::vector< double > &parent_1, const std::vector< double > &parent_2, std::vector< double > &offspring_1, std::vector< double > &offspring_2)

void	Reproduce (GenericCostFunction &CostFunction)

std::pair< unsigned, unsigned >	GetMatingPair ()

void	MutateGenes (GenericCostFunction &CostFunction)

void	CalculateRanks ()

int	ProcessFindMin (GenericCostFunction &CostFunction)

Private Attributes
unsigned	n_keep_

unsigned	dimensions_

std::vector< double >	ranks_

std::mt19937	generator_

std::vector< std::uniform_real_distribution< double > >	distributions_

Friends
class	TestGeneticAlgorithm

Additional Inherited Members
Public Attributes inherited from Unfit::GenericOptimizer
Unfit::Bounds	bounds

Unfit::Options	options

Protected Member Functions inherited from Unfit::GenericOptimizer
virtual bool	CalculateCost (GenericCostFunction &CostFunction, std::vector< double > &x)

void	GeneratePopulation (GenericCostFunction &CostFunction, std::size_t dimensions)

void	GenerateRandomEngines ()

virtual bool	IsConverged (const std::vector< double > &best_member, std::size_t truncated_index=0) const
	Checks to see if the population has converged. More...

virtual void	PrintInitialOutput (double best_cost) const

virtual void	PrintIterationOutput (double best_cost) const

virtual void	PrintFinalOutput () const

virtual void	SortPopulation () noexcept

Protected Attributes inherited from Unfit::GenericOptimizer
std::vector< std::vector< double > >	population_

std::vector< std::mt19937 >	random_engines_

std::atomic< std::size_t >	function_evaluations_

std::atomic< std::size_t >	iterations_

bool	is_population_based_

Detailed Description

A class to implement the Genetic Algorithm optimization method.

This class implements the Genetic Algorithm optimization method. It requires a cost function (written by the user) and an initial guess of the unknown parameters. The initial guess is only needed to obtain the number of unknowns, so make sure it is of the correct length. The algorithm will proceeds to try to find a set of parameters that minimize the cost function

The inspiration for this implementation was derived from the book: Practical Genetic Algorithms, by Randy L. Haupt, Sue Ellen Haupt. In particular, look at Chapter 3 on continuous GA as this implementation largely follows their recommendations.

Constructor & Destructor Documentation

◆ GeneticAlgorithm()

Unfit::GeneticAlgorithm::GeneticAlgorithm ( )

The constructor sets all of the parameters to their default values.

◆ ~GeneticAlgorithm()

virtual Unfit::GeneticAlgorithm::~GeneticAlgorithm ( )

inlinevirtual

As we could derive from this class, the destructor should be virtual. In this case the default destructor is just fine as we are putting everything into std::vectors which take care of themselves.

Member Function Documentation

◆ CalculateRanks()

void Unfit::GeneticAlgorithm::CalculateRanks ( )

private

This implementation of GeneticAlgorithm uses rank weighting to determine which surviving chromosomes make up a pair of parents. This information is static for the life of the problem, and the ranking coefficients are calculated using this method.

◆ CrossOver()

void Unfit::GeneticAlgorithm::CrossOver	(	const std::vector< double > &	parent_1,
		const std::vector< double > &	parent_2,
		std::vector< double > &	offspring_1,
		std::vector< double > &	offspring_2
	)

private

CrossOver is called by Reproduce to make a new chromosome (offspring) from a pair of parents. There are many approaches on how to do this. Here we follow the Practical Genetic Algorithms book, swapping where needed and blending at the cross over point.

Parameters

parent_1	First parent of the mating pair
parent_2	Second parent of the mating pair
offspring_1	First offspring of the parents
offspring_2	Second offspring of the parents

◆ FindMin()

int Unfit::GeneticAlgorithm::FindMin	(	GenericCostFunction &	CostFunction,
		std::vector< double > &	coordinates
	)

overridevirtual

A method to find a minimum point of a function using a Genetic Algorithm approach.

This is the main method to call to perform a minimization of the provided cost function. Here a Genetic Algorithm optimization technique is adopted. There are a few points worth noting before starting the optimization. First, make sure that the length of the coordinates vector that is passed in to this function matches the number of unknowns you have in your cost function. As the cost function is user supplied there is no way of checking these match up. The values you supply are not important as the initial population is randomly generated. The final result (coordinates with best fit) is returned in the vector. Second, it is advisable to add bounds to each of the variables in the fit. The algorithm generates possible answers between the provided bounds, and if no bounds are provided the bounds are +/- the maximum double the computer can represent. Chances are you know enough about the problem to make more sensible choices. Convergence with +/- 1e8, for example, is still much faster than the default bounds.

Intended use: int rc = object.FindMin(CostFunction, coordinates)

Parameters

CostFunction	The user-supplied function to minimise
coordinates	On input must be the same size as the number of parameters in the cost function. On exit returns the unknowns that provided the minimum cost.

Returns: Zero upon success, non-zero upon failure.
-1 = Empty coordinate vector
1 = Maximum number of function evaluations was reached
2 = Maximum number of iterations was reached

Implements Unfit::GenericOptimizer.

◆ GeneratePopulation()

void Unfit::GeneticAlgorithm::GeneratePopulation ( GenericCostFunction & CostFunction )

private

This method generates a population of random guesses of the unknown parameters for the cost function between the bounds. Any guess that does not compute a valid cost is automatically discarded. Updates the population_ member variable with a sorted (based on cost) initial population.

Parameters

CostFunction Returns the residuals of the model

◆ GetMatingPair()

std::pair< unsigned, unsigned > Unfit::GeneticAlgorithm::GetMatingPair ( )

private

GetMatingPair is called by Reproduce. This method randomly selects a pair of surviving chromosomes to be parents for the next generation. At present rank weighting is used, so the chromosomes with the best cost are more likely to be selected. The pair is unique, in that the parent chromosomes are forced to be different.

Returns: The mating pair

◆ InitialiseBounds()

void Unfit::GeneticAlgorithm::InitialiseBounds ( )

private

Creates the default bounds for all variables (+/- maximum double) that have not previously been set by the user. This method also initialises a random number generator for each variable that generates uniform real numbers between the specified bounds.

◆ MutateGenes()

void Unfit::GeneticAlgorithm::MutateGenes ( GenericCostFunction & CostFunction )

private

As the name suggests, this method replaces randomly selected genes with random mutations. The number of mutations to be inserted is gamma * the population size. The elite chromosomes (with the lowest costs) are immune from the mutation process (see Set/GetElitism). If a mutation causes an invalid response from the cost function it is discarded and another mutation is attempted.

Parameters

CostFunction Returns the residuals of the model

◆ ProcessFindMin()

int Unfit::GeneticAlgorithm::ProcessFindMin ( GenericCostFunction & CostFunction )

private

This method is called by FindMin and contains the main iteration loop. Here is where the actual optimisation takes place, the population reproduces and is mutated, and convergence is determined.

Parameters

CostFunction Returns the residuals of the model

Returns: Zero upon success, non-zero upon failure
1 = Maximum number of function evaluations was reached
2 = Maximum number of iterations was reached

◆ Reproduce()

void Unfit::GeneticAlgorithm::Reproduce ( GenericCostFunction & CostFunction )

private

Reproduce takes the population that survived in the current generation, generates random pairings, and repopulates the population via offspring from these pairs such that the overall population size remains constant across generations. Set/GetSurvivalRate determines how many survive and how many are replaced.

Parameters

CostFunction Returns the residuals of the model

◆ Reset()

void Unfit::GeneticAlgorithm::Reset ( )

overridevirtual

Resets the GeneticAlgorithm back to its default state. This is equivalent to destroying the object and creating a new one.

Implements Unfit::GenericOptimizer.

Friends And Related Function Documentation

◆ TestGeneticAlgorithm

friend class TestGeneticAlgorithm

friend

For unit testing purposes only

Member Data Documentation

◆ dimensions_

unsigned Unfit::GeneticAlgorithm::dimensions_

private

The number of dimensions in the problem

◆ distributions_

std::vector<std::uniform_real_distribution<double> > Unfit::GeneticAlgorithm::distributions_

private

Store the distributions for each variable

◆ generator_

std::mt19937 Unfit::GeneticAlgorithm::generator_

private

A random number engine for all random needs

◆ n_keep_

unsigned Unfit::GeneticAlgorithm::n_keep_

private

The number of chromosomes retained at each iteration

◆ ranks_

std::vector<double> Unfit::GeneticAlgorithm::ranks_

private

Stores the rank of each retained chromosome for rank weighting

The documentation for this class was generated from the following files:

include/GeneticAlgorithm.hpp
src/GeneticAlgorithm.cpp

Public Member Functions

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ GeneticAlgorithm()

◆ ~GeneticAlgorithm()

Member Function Documentation

◆ CalculateRanks()

◆ CrossOver()

◆ FindMin()

◆ GeneratePopulation()

◆ GetMatingPair()

◆ InitialiseBounds()

◆ MutateGenes()

◆ ProcessFindMin()

◆ Reproduce()

◆ Reset()

Friends And Related Function Documentation

◆ TestGeneticAlgorithm

Member Data Documentation

◆ dimensions_

◆ distributions_

◆ generator_

◆ n_keep_

◆ ranks_