NAME¶

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.

SYNOPSIS¶

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.

Detailed Description¶

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: Definition at line 75 of file sa.hpp.

Constructor & Destructor Documentation¶

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> mlpack::optimization::SA< FunctionType, CoolingScheduleType >:: SA (FunctionType &function, CoolingScheduleType &coolingSchedule, const size_tmaxIterations = 1000000, const doubleinitT = 10000., const size_tinitMoves = 1000, const size_tmoveCtrlSweep = 100, const doubletolerance = 1e-5, const size_tmaxToleranceSweep = 3, const doublemaxMoveCoef = 20, const doubleinitMoveCoef = 0.3, const doublegain = 0.3)¶

Construct the SA optimizer with the given function and parameters. Parameters:

Member Function Documentation¶

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> const FunctionType& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Function () const [inline]¶

Get the instantiated function to be optimized. Definition at line 117 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> FunctionType& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Function () [inline]¶

Modify the instantiated function. Definition at line 119 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Gain () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Gain () [inline]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::GenerateMove (arma::mat &iterate, arma::mat &accept, double &energy, size_t &idx, size_t &sweepCounter) [private]¶

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:

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t mlpack::optimization::SA< FunctionType, CoolingScheduleType >::InitMoves () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::InitMoves () [inline]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxIterations () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxIterations () [inline]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxMove () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxMove () [inline]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxToleranceSweep () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxToleranceSweep () [inline]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveControl (const size_tnMoves, arma::mat &accept) [private]¶

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:

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> size_t mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveCtrlSweep () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveCtrlSweep () [inline]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveSize () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveSize () [inline]¶

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 mlpack::optimization::SA< 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: Returns:

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Temperature () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Temperature () [inline]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Tolerance () const [inline]¶

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& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Tolerance () [inline]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::ToString () const¶

Return a string representation of this object.

Member Data Documentation¶

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> CoolingScheduleType& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::coolingSchedule [private]¶

The cooling schedule being used. Definition at line 172 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> FunctionType& mlpack::optimization::SA< FunctionType, CoolingScheduleType >::function [private]¶

The function to be optimized. Definition at line 170 of file sa.hpp.

template<typename FunctionType , typename CoolingScheduleType = ExponentialSchedule> double mlpack::optimization::SA< FunctionType, CoolingScheduleType >::gain [private]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::initMoves [private]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxIterations [private]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxMove [private]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxToleranceSweep [private]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveCtrlSweep [private]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveSize [private]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::temperature [private]¶

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 mlpack::optimization::SA< FunctionType, CoolingScheduleType >::tolerance [private]¶

Tolerance for convergence. Definition at line 182 of file sa.hpp. Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Tolerance().

Author¶

Generated automatically by Doxygen for MLPACK from the source code.