Genetic Algorithm and Direct Search Toolbox 2.4.2

Simulated Annealing Options

This demonstration shows of how to create and manage options for the simulated annealing function SIMULANNEALBND using SAOPTIMSET in the Genetic Algorithm and Direct Search Toolbox™.

Contents

Optimization Problem Setup

SIMULANNEALBND searches for a minimum of a function using simulated annealing. For this demo we use SIMULANNEALBND to minimize the objective function DEJONG5FCN. This function is a real valued function of two variables and has many local minima making it difficult to optimize. There is only one global minimum at x=(-32,-32), where f(x) = 0.998. To define our problem, we must define the objective function, start point, and bounds specified by the range -64 <= x(i) <= 64 for each x(i).

ObjectiveFunction = @dejong5fcn;
startingPoint = [-30 0];
lb = [-64 -64];
ub = [64 64];

The function PLOTOBJECTIVE in the toolbox plots the objective function over the range -64 <= x1 <= 64, -64 <= x2 <= 64.

plotobjective(ObjectiveFunction,[-64 64; -64 64]);
view(-15,150);

Now, we can run the SIMULANNEALBND solver to minimize our objective function.

[x,fval,exitFlag,output] = simulannealbnd(ObjectiveFunction,startingPoint,lb
,ub);

fprintf('The number of iterations was : %d\n', output.iterations);
fprintf('The number of function evaluations was : %d\n', output.funccount);
fprintf('The best function value found was : %g\n', fval);

Optimization terminated: change in best function value less than options.Tol
Fun.
The number of iterations was : 1338
The number of function evaluations was : 1349
The best function value found was : 2.98211

Note that when you run this demo, your results may be different from the results shown above because simulated annealing algorithm uses random numbers to generate points.

Adding Visualization

SIMULANNEALBND can accept one or more plot functions through an 'options' argument. This feature is useful for visualizing the performance of the solver at run time. Plot functions are selected using SAOPTIMSET. The help for SAOPTIMSET contains a list of plot functions to choose from, or you can provide your own custom plot functions.

To select multiple plot functions, SAOPTIMSET is used to create an options structure. For this example, we select SAPLOTBESTF, which plots the best function value every iteration, SAPLOTTEMPERATURE, which shows the current temperature in each dimension at every iteration, SAPLOTF, which shows the current function value (remember that the current value is not necessarily the best one), and SAPLOTSTOPPING, which plots the percentage of stopping criteria satisfied every iteration.

options = saoptimset('PlotFcns',{@saplotbestf,@saplottemperature,@saplo
tf,@saplotstopping});

Run the solver.

simulannealbnd(ObjectiveFunction,startingPoint,lb,ub,options);

Optimization terminated: change in best function value less than options.Tol
Fun.

Specifying Temperature Options

The temperature parameter used in simulated annealing controls the overall search results. The temperature for each dimension is used to limit the extent of search in that dimension. The toolbox lets you specify initial temperature as well as ways to update temperature during the solution process. The two temperature-related options are the InitialTemperature and the TemperatureFcn.

Specifying initial temperature

The default initial temperature is set to 100 for each dimension. If you want the initial temperature to be different in different dimensions then you must specify a vector of temperatures. This may be necessary in cases when problem is scaled differently in each dimensions. For example,

options = saoptimset('InitialTemperature',[300 50]);

InitialTemperature can be set to a vector of length less than the number of variables (dimension); the solver expands the vector to the remaining dimensions by taking the last element of the initial temperature vector. Here we want the initial temperature to be the same in all dimensions so we need only specify the single temperature.

options = saoptimset('InitialTemperature',100);

Specifying a temperature function

The default temperature function used by SIMULANNEALBND is called TEMPERATUREEXP. In the temperatureexp schedule, the temperature at any given step is .95 times the temperature at the previous step. This causes the temperature to go down slowly at first but ultimately get cooler faster than other schemes. If another scheme is desired, e.g. Boltzmann schedule or "Fast" schedule annealing, then TEMPERATUREBOLTZ or TEMPERATUREFAST can be used respectively. To select the fast temperature schedule, we can update our previously created options structure 'options' by passing 'options' to SAOPTIMSET.

options = saoptimset(options,'TemperatureFcn',@temperaturefast);

Specifying reannealing

Reannaling is a part of annealing process. After a certain number of new points are accepted, the temperature is raised to a higher value in hope to restart the search and move out of a local minima. Performing reannealing too soon may not help the solver identify a minimum, so a relatively high interval is a good choice. The interval at which reannealing happens can be set using the ReannealInterval option. Here, we reduce the default reannealing interval to 50 because the function seems to be flat in many regions and solver might get stuck rapidly.

options = saoptimset(options,'ReannealInterval',50);

We can also set the Display option to control the level of display on the command prompt. Here we set the display option to 'iter' and change the display interval to 400.

options = saoptimset(options,'Display','iter','DisplayInterval',400);

Now that we have setup the new temperature options we run the solver again

[x,fval,exitFlag,output] = simulannealbnd(ObjectiveFunction,startingPoint,lb
,ub,options);

                           Best        Current           Mean
Iteration   f-count         f(x)         f(x)         temperature
     0          1        65.2159        65.2159            100
*  163        166        17.3744        17.3744        1197.38
*  346        351        17.3744        17.3747        21.2561
   400        405        17.3744        17.3747        1.70216
*  534        541        17.3744        17.4824        24.8081
*  713        722        17.3744        17.3864        18.3967
   800        809        17.3744        17.3785        1.08172
*  922        933        17.3744        17.3744        13.0276
* 1112       1125        17.3744        17.3785        24.2848
  1200       1213        12.6904        12.7479        1.08325
* 1282       1297        12.6705        12.7193        17.4678
* 1465       1482        12.6705        12.6724        14.7862
  1600       1617        12.6705        12.6708       0.702427
* 1680       1699        12.6705        12.6732        43.7115
* 1869       1890        12.6705        12.7634         51.695
  2000       2021        12.6705        12.6707       0.745243
* 2043       2066        12.6705        12.6705         15.213
* 2230       2255        12.6705        12.7033        18.5977
Optimization terminated: change in best function value less than options.Tol
Fun.

Notice that every iteration at which reannealing happens is denoted by a '*' and is always displayed.

fprintf('The number of iterations was : %d\n', output.iterations);
fprintf('The number of function evaluations was : %d\n', output.funccount);
fprintf('The best function value found was : %g\n', fval);

The number of iterations was : 2252
The number of function evaluations was : 2277
The best function value found was : 12.6705

Reproducing Results

SIMULANNEALBND is a nondeterministic algorithm. This means that running the solver more than once without changing any settings may give different results. This is because SIMULANNEALBND utilizes MATLAB® random number generators when it generates subsequent points and also when it determines whether or not to accept new points. Every time a random number is generated the state of the random number generators change.

To see this, two runs of SIMULANNEALBND solver yields:

[x,fval] = simulannealbnd(ObjectiveFunction,startingPoint,lb,ub,options);
fprintf('The best function value found was : %g\n', fval);

                           Best        Current           Mean
Iteration   f-count         f(x)         f(x)         temperature
     0          1        65.2159        65.2159            100
*  190        193        10.7632        10.7636        48.0139
*  341        346        10.7632        11.1861        25.3636
   400        405        6.95421         8.0191        1.58428
*  507        514        6.90334        6.90336        139.842
*  694        703        6.90334        6.90334        21.0805
   800        809        6.90334        6.90546       0.902635
*  880        891        6.90334        6.97337        126.471
* 1063       1076        1.99203        2.12195          393.5
  1200       1213        1.99203        2.01657       0.716154
* 1235       1250        1.99203        2.07774        24.6618
* 1417       1434        1.99203        1.99297         17.182
* 1594       1613        1.99203        1.99758        14.6529
  1600       1619        1.99203        1.99758        7.60617
* 1780       1801        1.99203        1.99554        14.8352
* 1973       1996        1.99203        1.99223        56.2426
  2000       2023        1.99203        1.99223        3.32912
Optimization terminated: change in best function value less than options.Tol
Fun.
The best function value found was : 1.99203

And,

[x,fval] = simulannealbnd(ObjectiveFunction,startingPoint,lb,ub,options);
fprintf('The best function value found was : %g\n', fval);

                           Best        Current           Mean
Iteration   f-count         f(x)         f(x)         temperature
     0          1        65.2159        65.2159            100
*  192        195        10.7632         10.932        14.7711
*  372        377        10.7632        10.7646        341.758
   400        405        10.7632        10.7646        3.28042
*  549        556        10.7632        10.7801         18.467
*  731        740        10.7632        11.1537        27.8118
   800        809        10.7632        10.9556        1.37057
*  925        936        10.7632        10.9567        16.2344
* 1101       1114        10.7632        10.7632         14.662
  1200       1213        10.7632        10.7632       0.939015
Optimization terminated: change in best function value less than options.Tol
Fun.
The best function value found was : 10.7632

In the previous two runs SIMULANNEALBND gives different results.

We can reproduce our results if we reset the states of the random number generators between runs of the solver by using information returned by SIMULANNEALBND. SIMULANNEALBND returns the states of the random number generators at the time SIMULANNEALBND is called in the output argument. This information can be used to reset the states. Here we reset the states between runs using this output information so the results of the next two runs are the same.

[x,fval,exitFlag,output] = simulannealbnd(ObjectiveFunction,startingPoint,lb
,ub,options);
fprintf('The best function value found was : %g\n', fval);

                           Best        Current           Mean
Iteration   f-count         f(x)         f(x)         temperature
     0          1        65.2159        65.2159            100
*  183        186        10.7632        10.7632        42.8905
*  376        381        6.90334         6.9766        15.8481
   400        405        6.90334         6.9766         3.2773
*  537        544        6.90334        6.90343        17.9096
*  742        751        6.90334        6.90457        17.6062
   800        809        6.90334         10.966        1.56986
*  918        929        6.90334        6.90437        19.1435
* 1091       1104        6.90334        7.02723        27.9327
  1200       1213        6.90334         6.9042       0.885399
Optimization terminated: change in best function value less than options.Tol
Fun.
The best function value found was : 6.90334

We reset the state of the random number generator.

set(RandStream.getDefaultStream,'State',output.rngstate.state);

Now, let's run SIMULANNEALBND again.

[x,fval] = simulannealbnd(ObjectiveFunction,startingPoint,lb,ub,options);
fprintf('The best function value found was : %g\n', fval);

                           Best        Current           Mean
Iteration   f-count         f(x)         f(x)         temperature
     0          1        65.2159        65.2159            100
*  183        186        10.7632        10.7632        42.8905
*  376        381        6.90334         6.9766        15.8481
   400        405        6.90334         6.9766         3.2773
*  537        544        6.90334        6.90343        17.9096
*  742        751        6.90334        6.90457        17.6062
   800        809        6.90334         10.966        1.56986
*  918        929        6.90334        6.90437        19.1435
* 1091       1104        6.90334        7.02723        27.9327
  1200       1213        6.90334         6.9042       0.885399
Optimization terminated: change in best function value less than options.Tol
Fun.
The best function value found was : 6.90334

Modifying the Stopping Criteria

SIMULANNEALBND uses six different criteria to determine when to stop the solver. SIMULANNEALBND stops when the maximum number of iterations or function evaluation is exceeded; by default the maximum number of iterations is set to Inf and the maximum number of function evaluations is 3000*numberOfVariables. SIMULANNEALBND keeps track of the average change in the function value for StallIterLimit iterations. If the average change is smaller than the function tolerance, TolFun, then the algorithm will stop. The solver will also stop when the objective function value reaches ObjectiveLimit. Finally the solver will stop after running for TimeLimit seconds. Here we set the TolFun to 1e-8.

options = saoptimset(options,'TolFun',1e-5);

Run the SIMULANNEALBND solver.

[x,fval,exitFlag,output] = simulannealbnd(ObjectiveFunction,startingPoint,lb
,ub,options);
fprintf('The number of iterations was : %d\n', output.iterations);
fprintf('The number of function evaluations was : %d\n', output.funccount);
fprintf('The best function value found was : %g\n', fval);

                           Best        Current           Mean
Iteration   f-count         f(x)         f(x)         temperature
     0          1        65.2159        65.2159            100
*  157        160        10.7632        10.7663        15.5743
*  352        357        10.7632        10.7639        17.4469
   400        405        10.7632        10.7639        1.85999
*  522        529        10.7632        10.7645        32.2143
*  720        729        10.7632        10.7778        14.3023
   800        809        10.7632        10.7812         1.1402
*  926        937        10.7632        10.7843        17.6084
Optimization terminated: change in best function value less than options.Tol
Fun.
The number of iterations was : 1105
The number of function evaluations was : 1116
The best function value found was : 10.7632