A class to implement the Simulated Annealing optimization method. More...

#include <SimulatedAnnealing.hpp>

Inheritance diagram for Unfit::SimulatedAnnealing:

Public Member Functions
	SimulatedAnnealing ()

virtual	~SimulatedAnnealing ()=default

int	FindMin (GenericCostFunction &CostFunction, std::vector< double > &coordinates) override
	A method to find a minimum point of a function using a Simulated Annealing 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
int	ProcessFindMin (GenericCostFunction &CostFunction, std::vector< double > &coordinates)

void	InitialiseParameters ()

void	GenerateTrialPoint (std::vector< double > &trial_point, int i)

void	UpdateStepSizes () noexcept

void	ResetStepSizes (double step_size) noexcept

Private Attributes
std::size_t	cost_

std::size_t	dimensions_

double	previous_best_cost_

std::vector< double >	step_sizes_

std::vector< double >	acceptance_ratios_

std::mt19937	generator_

std::uniform_real_distribution< double >	uniform_dist_

Friends
class	TestSimulatedAnnealing

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 Simulated Annealing optimization method.

This class implements the Simulated Annealing 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 proceed to try finding a set of parameters that minimizes the cost function.

The inspiration for this implementation was derived from the book: Belegundu, A. D., & Chandrupatla, T. R. (2011). Optimization concepts and applications in engineering. Cambridge University Press. In particular, look at Chapter 7 for their recommendations of the Simulated Annealing algorithm implementation.

Constructor & Destructor Documentation

◆ SimulatedAnnealing()

Unfit::SimulatedAnnealing::SimulatedAnnealing ( )

A constructor that sets all parameters to their default values.

◆ ~SimulatedAnnealing()

virtual Unfit::SimulatedAnnealing::~SimulatedAnnealing ( )

virtualdefault

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 would take care of themselves.

Member Function Documentation

◆ FindMin()

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

overridevirtual

A method to find a minimum point of a function using a Simulated Annealing approach.

This is the main method to call so as to perform a minimization of the provided cost function. Here, a Simulated Annealing 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 passed in to this function matches the number of unknowns you have in your cost function. As the cost function is supplied by user, there is no way of checking if the two match up. By default, the vector you supply is not used (other than to see it's length, and a random initial guess is generated within the specified bounds. However, if you want to start from your guess simply call:

sa.options.SetAddInitialToPopulation(true);

before you call FindMin, and we will use yours. Next, it is highly 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 (read - slow). Chances are you know enough about the problem to make a more sensible choice. Lastly, the final result (answer with the best fit) is returned in the coordinates vector.

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

Parameters

CostFunction	The user-supplied function to minimize
coordinates	On input, it must be the same size as the number of unknown parameters in the cost function. On exit, it returns the values of the unknown parameters that provided the minimum cost.

Returns: Zero upon success, non-zero upon failure.
-1 = Empty coordinate vector
-2 = Initial user supplied coordinates are out of bounds
-3 = Cost of the initial coordinates is inf or nan
1 = Maximum number of function evaluations was reached
2 = Maximum number of iterations was reached

Implements Unfit::GenericOptimizer.

◆ GenerateTrialPoint()

void Unfit::SimulatedAnnealing::GenerateTrialPoint	(	std::vector< double > &	trial_point,
		int	i
	)

private

This method generates a trial point from the current vector of coordinates by perturbing one of the values. The trial point, perturbing direction i, is generated by:

trial_point[i] += random_number*step_size[i]

where random_number is a uniform random number in the range of -1 to 1.

Parameters

trial_point	The coordinate vector to be perturbed
i	The coordinate/direction to perturb

◆ InitialiseParameters()

void Unfit::SimulatedAnnealing::InitialiseParameters ( )

private

Once we know the dimensions of the problem, this method is called to initialize the relevant private member variables.

◆ ProcessFindMin()

int Unfit::SimulatedAnnealing::ProcessFindMin	(	GenericCostFunction &	CostFunction,
		std::vector< double > &	coordinates
	)

private

This method is called by FindMin and it contains the main iteration loop where the actual optimization takes place.

Parameters

CostFunction	The user-supplied function to minimize
coordinates	On input, it must be the same size as the number of unknown parameters in the cost function. On exit, it returns the values of the unknown parameters that provided the minimum cost.

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

◆ Reset()

void Unfit::SimulatedAnnealing::Reset ( )

overridevirtual

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

Implements Unfit::GenericOptimizer.

◆ ResetStepSizes()

void Unfit::SimulatedAnnealing::ResetStepSizes ( double step_size )

privatenoexcept

The step size may take a low values eventually and may not allow a step to accept a point with higher cost even at moderate temperatures. To overcome this issue, this method resets each step size at the end of each temperature loop.

Parameters

step_size A scaling factor for setting the step sizes. The actual updated size will be this factor multiplied by the difference between the upper and lower bounds for each variable.

◆ UpdateStepSizes()

void Unfit::SimulatedAnnealing::UpdateStepSizes ( )

privatenoexcept

This method updates the step sizes after a cycle has been completed. The value of the acceptance ratios are used to update the step sizes. After the step sizes have been adjusted, the acceptance ratios are reset to 1.

Friends And Related Function Documentation

◆ TestSimulatedAnnealing

friend class TestSimulatedAnnealing

friend

For unit testing purposes only

Member Data Documentation

◆ acceptance_ratios_

std::vector<double> Unfit::SimulatedAnnealing::acceptance_ratios_

private

A vector of acceptance ratios

◆ cost_

std::size_t Unfit::SimulatedAnnealing::cost_

private

The index of the cost of each point

◆ dimensions_

std::size_t Unfit::SimulatedAnnealing::dimensions_

private

Variable to store the number of dimensions

◆ generator_

std::mt19937 Unfit::SimulatedAnnealing::generator_

private

A random number engine

◆ previous_best_cost_

double Unfit::SimulatedAnnealing::previous_best_cost_

private

The cost from the previous iteration

◆ step_sizes_

std::vector<double> Unfit::SimulatedAnnealing::step_sizes_

private

A vector of step sizes

◆ uniform_dist_

std::uniform_real_distribution<double> Unfit::SimulatedAnnealing::uniform_dist_

private

A uniform distribution over the interval [0, 1]

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

include/SimulatedAnnealing.hpp
src/SimulatedAnnealing.cpp

Public Member Functions

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SimulatedAnnealing()

◆ ~SimulatedAnnealing()

Member Function Documentation

◆ FindMin()

◆ GenerateTrialPoint()

◆ InitialiseParameters()

◆ ProcessFindMin()

◆ Reset()

◆ ResetStepSizes()

◆ UpdateStepSizes()

Friends And Related Function Documentation

◆ TestSimulatedAnnealing

Member Data Documentation

◆ acceptance_ratios_

◆ cost_

◆ dimensions_

◆ generator_

◆ previous_best_cost_

◆ step_sizes_

◆ uniform_dist_