|
mlpack
master
|
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. More...
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. More... | |
| const FunctionType & | Function () const |
| Get the instantiated function to be optimized. More... | |
| FunctionType & | Function () |
| Modify the instantiated function. More... | |
| double | Gain () const |
| Get the gain. More... | |
| double & | Gain () |
| Modify the gain. More... | |
| size_t | InitMoves () const |
| Get the initial moves. More... | |
| size_t & | InitMoves () |
| Modify the initial moves. More... | |
| size_t | MaxIterations () const |
| Get the maximum number of iterations. More... | |
| size_t & | MaxIterations () |
| Modify the maximum number of iterations. More... | |
| arma::mat | MaxMove () const |
| Get the maximum move size of each parameter. More... | |
| arma::mat & | MaxMove () |
| Modify the maximum move size of each parameter. More... | |
| size_t | MaxToleranceSweep () const |
| Get the maxToleranceSweep. More... | |
| size_t & | MaxToleranceSweep () |
| Modify the maxToleranceSweep. More... | |
| size_t | MoveCtrlSweep () const |
| Get sweeps per move control. More... | |
| size_t & | MoveCtrlSweep () |
| Modify sweeps per move control. More... | |
| arma::mat | MoveSize () const |
| Get move size of each parameter. More... | |
| arma::mat & | MoveSize () |
| Modify move size of each parameter. More... | |
| double | Optimize (arma::mat &iterate) |
| Optimize the given function using simulated annealing. More... | |
| double | Temperature () const |
| Get the temperature. More... | |
| double & | Temperature () |
| Modify the temperature. More... | |
| double | Tolerance () const |
| Get the tolerance. More... | |
| double & | Tolerance () |
| Modify the tolerance. More... | |
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. More... | |
| 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. More... | |
Private Attributes | |
| CoolingScheduleType & | coolingSchedule |
| The cooling schedule being used. More... | |
| FunctionType & | function |
| The function to be optimized. More... | |
| double | gain |
| Proportional control in feedback move control. More... | |
| size_t | initMoves |
| The number of initial moves before reducing the temperature. More... | |
| size_t | maxIterations |
| The maximum number of iterations. More... | |
| arma::mat | maxMove |
| Maximum move size of each parameter. More... | |
| size_t | maxToleranceSweep |
| Number of sweeps in tolerance before system is considered frozen. More... | |
| size_t | moveCtrlSweep |
| The number of sweeps before a MoveControl() call. More... | |
| arma::mat | moveSize |
| Move size of each parameter. More... | |
| double | temperature |
| The current temperature. More... | |
| double | tolerance |
| Tolerance for convergence. More... | |
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.
| FunctionType | objective function type to be minimized. |
| CoolingScheduleType | type for cooling schedule |
| mlpack::optimization::SA< FunctionType, CoolingScheduleType >::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.
| 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. |
|
inline |
|
inline |
|
inline |
Get the gain.
Definition at line 137 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::gain.
|
inline |
Modify the gain.
Definition at line 139 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::gain.
|
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.
| 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. |
|
inline |
Get the initial moves.
Definition at line 117 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::initMoves.
|
inline |
Modify the initial moves.
Definition at line 119 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::initMoves.
|
inline |
Get the maximum number of iterations.
Definition at line 142 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxIterations.
|
inline |
Modify the maximum number of iterations.
Definition at line 144 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxIterations.
|
inline |
Get the maximum move size of each parameter.
Definition at line 147 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxMove.
|
inline |
Modify the maximum move size of each parameter.
Definition at line 149 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxMove.
|
inline |
Get the maxToleranceSweep.
Definition at line 132 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxToleranceSweep.
|
inline |
Modify the maxToleranceSweep.
Definition at line 134 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::maxToleranceSweep.
|
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.
| nMoves | Number of moves since last call. |
| accept | Matrix representing which parameters have had accepted moves. |
|
inline |
Get sweeps per move control.
Definition at line 122 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveCtrlSweep.
|
inline |
Modify sweeps per move control.
Definition at line 124 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveCtrlSweep.
|
inline |
Get move size of each parameter.
Definition at line 152 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveSize.
|
inline |
Modify move size of each parameter.
Definition at line 154 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::moveSize.
| 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.
| iterate | Starting point (will be modified). |
|
inline |
Get the temperature.
Definition at line 112 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::temperature.
|
inline |
Modify the temperature.
Definition at line 114 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::temperature.
|
inline |
Get the tolerance.
Definition at line 127 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::tolerance.
|
inline |
Modify the tolerance.
Definition at line 129 of file sa.hpp.
References mlpack::optimization::SA< FunctionType, CoolingScheduleType >::tolerance.
|
private |
|
private |
|
private |
Proportional control in feedback move control.
Definition at line 174 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Gain().
|
private |
The number of initial moves before reducing the temperature.
Definition at line 166 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::InitMoves().
|
private |
The maximum number of iterations.
Definition at line 162 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxIterations().
|
private |
Maximum move size of each parameter.
Definition at line 177 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxMove().
|
private |
Number of sweeps in tolerance before system is considered frozen.
Definition at line 172 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MaxToleranceSweep().
|
private |
The number of sweeps before a MoveControl() call.
Definition at line 168 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveCtrlSweep().
|
private |
Move size of each parameter.
Definition at line 179 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::MoveSize().
|
private |
The current temperature.
Definition at line 164 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Temperature().
|
private |
Tolerance for convergence.
Definition at line 170 of file sa.hpp.
Referenced by mlpack::optimization::SA< FunctionType, CoolingScheduleType >::Tolerance().
1.8.11
