mlpack_optimization_SA (3)

Public Member Functions

SA (FunctionType &function, CoolingScheduleType &coolingSchedule, const size_t maxIterations=1000000, const double initT=10000., const size_t initMoves=1000, const size_t moveCtrlSweep=100, const double tolerance=1e-5, const size_t maxToleranceSweep=3, const double maxMoveCoef=20, const double initMoveCoef=0.3, const double gain=0.3)

Construct the SA optimizer with the given function and parameters. const FunctionType & Function () const

Get the instantiated function to be optimized. FunctionType & Function ()

Modify the instantiated function. double Gain () const

Get the gain. double & Gain ()

Modify the gain. size_t InitMoves () const

Get the initial moves. size_t & InitMoves ()

Modify the initial moves. size_t MaxIterations () const

Get the maximum number of iterations. size_t & MaxIterations ()

Modify the maximum number of iterations. arma::mat MaxMove () const

Get the maximum move size of each parameter. arma::mat & MaxMove ()

Modify the maximum move size of each parameter. size_t MaxToleranceSweep () const

Get the maxToleranceSweep. size_t & MaxToleranceSweep ()

Modify the maxToleranceSweep. size_t MoveCtrlSweep () const

Get sweeps per move control. size_t & MoveCtrlSweep ()

Modify sweeps per move control. arma::mat MoveSize () const

Get move size of each parameter. arma::mat & MoveSize ()

Modify move size of each parameter. double Optimize (arma::mat &iterate)

Optimize the given function using simulated annealing. double Temperature () const

Get the temperature. double & Temperature ()

Modify the temperature. double Tolerance () const

Get the tolerance. double & Tolerance ()

Modify the tolerance. std::string ToString () const

Return a string representation of this object.

Private Member Functions

void GenerateMove (arma::mat &iterate, arma::mat &accept, double &energy, size_t &idx, size_t &sweepCounter)

GenerateMove proposes a move on element iterate(idx), and determines if that move is acceptable or not according to the Metropolis criterion. void MoveControl (const size_t nMoves, arma::mat &accept)

MoveControl() uses a proportional feedback control to determine the size parameter to pass to the move generation distribution.

Private Attributes

CoolingScheduleType & coolingSchedule

The cooling schedule being used. FunctionType & function

The function to be optimized. double gain

Proportional control in feedback move control. size_t initMoves

The number of initial moves before reducing the temperature. size_t maxIterations

The maximum number of iterations. arma::mat maxMove

Maximum move size of each parameter. size_t maxToleranceSweep

Number of sweeps in tolerance before system is considered frozen. size_t moveCtrlSweep

The number of sweeps before a MoveControl() call. arma::mat moveSize

Move size of each parameter. double temperature

The current temperature. double tolerance

Tolerance for convergence.

template<typename FunctionType, typename CoolingScheduleType = ExponentialSchedule>class mlpack::optimization::SA< FunctionType, CoolingScheduleType >

Simulated Annealing is an stochastic optimization algorithm which is able to deliver near-optimal results quickly without knowing the gradient of the function being optimized.

It has unique hill climbing capability that makes it less vulnerable to local minima. This implementation uses exponential cooling schedule and feedback move control by default, but the cooling schedule can be changed via a template parameter.

The algorithm keeps the temperature at initial temperature for initMove steps to get rid of the dependency on the initial condition. After that, it cools every step until the system is considered frozen or maxIterations is reached.

At each step, SA only perturbs one parameter at a time. When SA has perturbed all parameters in a problem, a sweep has been completed. Every moveCtrlSweep sweeps, the algorithm does feedback move control to change the average move size depending on the responsiveness of each parameter. Parameter gain controls the proportion of the feedback control.

The system is considered 'frozen' when its score fails to change more then tolerance for maxToleranceSweep consecutive sweeps.

For SA to work, the FunctionType parameter must implement the following two methods:

double Evaluate(const arma::mat& coordinates); arma::mat& GetInitialPoint();

and the CoolingScheduleType parameter must implement the following method:

double NextTemperature(const double currentTemperature, const double currentValue);

which returns the next temperature given current temperature and the value of the function being optimized.

Template Parameters:

FunctionType objective function type to be minimized.

CoolingScheduleType type for cooling schedule

Definition at line 75 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::\fBSA\fP (FunctionType &function, CoolingScheduleType &coolingSchedule, const size_tmaxIterations = \fC1000000\fP, const doubleinitT = \fC10000.\fP, const size_tinitMoves = \fC1000\fP, const size_tmoveCtrlSweep = \fC100\fP, const doubletolerance = \fC1e-5\fP, const size_tmaxToleranceSweep = \fC3\fP, const doublemaxMoveCoef = \fC20\fP, const doubleinitMoveCoef = \fC0.3\fP, const doublegain = \fC0.3\fP)

Construct the SA optimizer with the given function and parameters.

Parameters:

function Function to be minimized.

coolingSchedule Instantiated cooling schedule.

maxIterations Maximum number of iterations allowed (0 indicates no limit).

initT Initial temperature.

initMoves Number of initial iterations without changing temperature.

moveCtrlSweep Sweeps per feedback move control.

tolerance Tolerance to consider system frozen.

maxToleranceSweep Maximum sweeps below tolerance to consider system frozen.

maxMoveCoef Maximum move size.

initMoveCoef Initial move size.

gain Proportional control in feedback move control.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> const FunctionType& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Function () const\fC [inline]\fP

Get the instantiated function to be optimized.

Definition at line 117 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> FunctionType& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Function ()\fC [inline]\fP

Modify the instantiated function.

Definition at line 119 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Gain () const\fC [inline]\fP

Get the gain.

Definition at line 147 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::gain.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Gain ()\fC [inline]\fP

Modify the gain.

Definition at line 149 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::gain.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> void \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::GenerateMove (arma::mat &iterate, arma::mat &accept, double &energy, size_t &idx, size_t &sweepCounter)\fC [private]\fP

GenerateMove proposes a move on element iterate(idx), and determines if that move is acceptable or not according to the Metropolis criterion. After that it increments idx so the next call will make a move on next parameters. When all elements of the state have been moved (a sweep), it resets idx and increments sweepCounter. When sweepCounter reaches moveCtrlSweep, it performs MoveControl() and resets sweepCounter.

Parameters:

iterate Current optimization position.

accept Matrix representing which parameters have had accepted moves.

energy Current energy of the system.

idx Current parameter to modify.

sweepCounter Current counter representing how many sweeps have been completed.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::InitMoves () const\fC [inline]\fP

Get the initial moves.

Definition at line 127 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::initMoves.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::InitMoves ()\fC [inline]\fP

Modify the initial moves.

Definition at line 129 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::initMoves.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MaxIterations () const\fC [inline]\fP

Get the maximum number of iterations.

Definition at line 152 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxIterations.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MaxIterations ()\fC [inline]\fP

Modify the maximum number of iterations.

Definition at line 154 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxIterations.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> arma::mat \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MaxMove () const\fC [inline]\fP

Get the maximum move size of each parameter.

Definition at line 157 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxMove.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> arma::mat& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MaxMove ()\fC [inline]\fP

Modify the maximum move size of each parameter.

Definition at line 159 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxMove.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MaxToleranceSweep () const\fC [inline]\fP

Get the maxToleranceSweep.

Definition at line 142 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxToleranceSweep.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MaxToleranceSweep ()\fC [inline]\fP

Modify the maxToleranceSweep.

Definition at line 144 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxToleranceSweep.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> void \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MoveControl (const size_tnMoves, arma::mat &accept)\fC [private]\fP

MoveControl() uses a proportional feedback control to determine the size parameter to pass to the move generation distribution. The target of such move control is to make the acceptance ratio, accept/nMoves, be as close to 0.44 as possible. Generally speaking, the larger the move size is, the larger the function value change of the move will be, and less likely such move will be accepted by the Metropolis criterion. Thus, the move size is controlled by

log(moveSize) = log(moveSize) + gain * (accept/nMoves - target)

For more theory and the mysterious 0.44 value, see Jimmy K.-C. Lam and Jean-Marc Delosme. `An efficient simulated annealing schedule: derivation'. Technical Report 8816, Yale University, 1988.

Parameters:

nMoves Number of moves since last call.

accept Matrix representing which parameters have had accepted moves.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MoveCtrlSweep () const\fC [inline]\fP

Get sweeps per move control.

Definition at line 132 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveCtrlSweep.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MoveCtrlSweep ()\fC [inline]\fP

Modify sweeps per move control.

Definition at line 134 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveCtrlSweep.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> arma::mat \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MoveSize () const\fC [inline]\fP

Get move size of each parameter.

Definition at line 162 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveSize.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> arma::mat& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::MoveSize ()\fC [inline]\fP

Modify move size of each parameter.

Definition at line 164 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveSize.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Optimize (arma::mat &iterate)

Optimize the given function using simulated annealing. The given starting point will be modified to store the finishing point of the algorithm, and the final objective value is returned.

Parameters:

iterate Starting point (will be modified).

Returns:

Objective value of the final point.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Temperature () const\fC [inline]\fP

Get the temperature.

Definition at line 122 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::temperature.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Temperature ()\fC [inline]\fP

Modify the temperature.

Definition at line 124 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::temperature.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Tolerance () const\fC [inline]\fP

Get the tolerance.

Definition at line 137 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::tolerance.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::Tolerance ()\fC [inline]\fP

Modify the tolerance.

Definition at line 139 of file sa.hpp.

References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::tolerance.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> std::string \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::ToString () const

Return a string representation of this object.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> CoolingScheduleType& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::coolingSchedule\fC [private]\fP

The cooling schedule being used.

Definition at line 172 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> FunctionType& \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::function\fC [private]\fP

The function to be optimized.

Definition at line 170 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::gain\fC [private]\fP

Proportional control in feedback move control.

Definition at line 186 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Gain().

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::initMoves\fC [private]\fP

The number of initial moves before reducing the temperature.

Definition at line 178 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::InitMoves().

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::maxIterations\fC [private]\fP

The maximum number of iterations.

Definition at line 174 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxIterations().

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> arma::mat \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::maxMove\fC [private]\fP

Maximum move size of each parameter.

Definition at line 189 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxMove().

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::maxToleranceSweep\fC [private]\fP

Number of sweeps in tolerance before system is considered frozen.

Definition at line 184 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxToleranceSweep().

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::moveCtrlSweep\fC [private]\fP

The number of sweeps before a MoveControl() call.

Definition at line 180 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveCtrlSweep().

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> arma::mat \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::moveSize\fC [private]\fP

Move size of each parameter.

Definition at line 191 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveSize().

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::temperature\fC [private]\fP

The current temperature.

Definition at line 176 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Temperature().

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double \fBmlpack::optimization::SA\fP< FunctionType, CoolingScheduleType >::tolerance\fC [private]\fP

Tolerance for convergence.

Definition at line 182 of file sa.hpp.

Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Tolerance().

Generated automatically by Doxygen for MLPACK from the source code.