Code covered by the BSD License

Highlights fromGeneral simulated annealing algorithm

4.06897

4.1 | 29 ratings Rate this file 102 Downloads (last 30 days) File Size: 3.77 KB File ID: #10548

General simulated annealing algorithm

28 Mar 2006 (Updated 02 Jun 2008)

Minimizes a function with the method of simulated annealing

File Information
Description

anneal Minimizes a function with the method of simulated annealing (Kirkpatrick et al., 1983)

ANNEAL takes three input parameters, in this order:

LOSS is a function handle (anonymous function or inline) with a loss function, which may be of any type, and needn't be continuous. It does, however, need to return a single value.

PARENT is a vector with initial guess parameters. You must input an initial guess.

OPTIONS is a structure with settings for the simulated annealing. If no OPTIONS structure is provided, anneal uses a default structure. OPTIONS can contain any or all of the following fields (missing fields are filled with default values):

Verbosity: Controls output to the screen.
0 suppresses all output
1 gives final report only [default]
2 gives temperature changes and final report
Generator: Generates a new solution from an old one. Any function handle that takes a solution as input and gives a valid solution (i.e. some point in the solution space) as output. The default function generates a row vector which slightly differs from the input vector in one element: @(x) (x+(randperm(length(x))==length(x))*randn/100). Other examples of possible solution generators: @(x) (rand(3,1)): Picks a random point in the unit cube. @(x) (ceil([9 5].*rand(2,1))): Picks a point in a 9-by-5 discrete grid.
Note that if you use the default generator, ANNEAL only works on row vectors. For loss functions that operate on column vectors, use this generator instead of the default: @(x) (x(:)'+(randperm(length(x))==length(x))*randn/100)'
InitTemp: The initial temperature, can be any positive number. Default is 1.
StopTemp: Temperature at which to stop, can be any positive number smaller than InitTemp. Default is 1e-8.
StopVal: Value at which to stop immediately, can be any output of LOSS that is sufficiently low for you. Default is -Inf.
CoolSched: Generates a new temperature from the previous one. Any function handle that takes a scalar as input and returns a smaller but positive scalar as output. Default is @(T) (.8*T).
MaxConsRej: Maximum number of consecutive rejections, can be any positive number. Default is 1000.
MaxTries: Maximum number of tries within one temperature, can be any positive number. Default is 300.
MaxSuccess: Maximum number of successes within one temperature, can be any positive number. Default is 20.

Usage:
[MINIMUM,FVAL] = ANNEAL(LOSS,NEWSOL,[OPTIONS]);
MINIMUM is the solution which generated the smallest encountered value when input into LOSS.
FVAL is the value of the LOSS function evaluated at MINIMUM.
OPTIONS = ANNEAL();
OPTIONS is the default options structure.

Example:
The so-called six-hump camelback function has several local minima in the range -3<=x<=3 and -2<=y<=2. It has two global minima, namely f(-0.0898,0.7126) = f(0.0898,-0.7126) = -1.0316. We can define and minimise it as follows:
camel = @(x,y)(4-2.1*x.^2+x.^4/3).*x.^2+x.*y+4*(y.^2-1).*y.^2;
loss = @(p)camel(p(1),p(2));
[x f] = anneal(loss,[0 0])
We get output:
Initial temperature: 1
Final temperature: 3.21388e-007
Consecutive rejections: 1027
Number of function calls: 6220
Total final loss: -1.03163
x =
-0.0899 0.7127
f =
-1.0316
Which reasonably approximates the analytical global minimum (note that due to randomness, your results will likely not be exactly the same).

Acknowledgements
MATLAB release MATLAB 7.0.1 (R14SP1)
Tags for This File
Everyone's Tags
Tags I've Applied
13 Jan 2012
15 Aug 2011

Thanks so much! worked first time, out of the box, without modification to my previous code, to solve a family of problems that fminsearch could not. Which is better than most built-in matlab functions manage!

21 Oct 2010

how we can adjust PID parameter by this algorithm

19 Oct 2010

Can anybody suggest how to incorporate constraints (inequality/equality) to the optimization? Especially in a discrete space?

Thank you.

04 Aug 2010

An implementation of the SIMPSA algorithm, a combination of simulated annealing and the simplex algorithm, can be found here:

The SIMPSA algorithm was developed and described in:

Cardoso, M. F., Salcedo, R., and Feyo de Azevedo, S. (1996). The simplex-simulated annealing approach to continuous non-linear optimization. Computers and Chemical Engineering, 20(9):1065-1080.

23 Jul 2010

There is a minor bug in anneal, it fails to keep/return the best solution found when it is not the final cooled solution. Easily fixed.

15 Jun 2010

Anybody to help me out with how to generate examination timetable using Hybrid of GA/SA with the help of Matlab

02 Jun 2010

I optimized a likelihood function of 15 parameters. Some parameters still do not attain their minimum. However, this method improve my previous results a lot. Thank you.

26 Mar 2010
26 Jun 2009
17 Jun 2009

I am using your SA code from this repository to minimize reaction rate constants for parameter estimation. Is there any way to constrain the optimization? I keep getting negative rate constants when they should be positive.

02 Jun 2009

I have a nonconvex problem, I have a gradient method to find local optima, can I use this code to generate initial values for local optima?

Can I give multiple initial guesses to this code? (the local optimas i get by gradient method)

07 May 2009
21 Apr 2009

Unless I'm misunderstanding, you can do that by defining the anonymous function dynamically, like so;

min2logL = @(x,y) x*log(y);
const = -2;
loss = @(p)min2logL(const,p);
[x f] = anneal(loss,[0 0])

... or similar.

-------------------------

http://www-stat.wharton.upenn.edu/~stroud/classics/KirkpatrickGelattVecchi83.pdf

03 Feb 2009

You should allow the Loss function to take in additionally arguments like csminwel does. I could just use global variables but that is bad programming.

30 Sep 2008

thks

09 Sep 2008
28 Aug 2008

Yes, for an erratic function like that, you'd need to change the options a bit. I would expect that you need a lot of exploring in the beginning (set InitTemp to 100), slow cooling (set CoolSched to @(T).95*T), and probably you want steps in multiple directions simultaneously (set Generator to @(x)x+randn(1,2)/10). Those setting always find the GO (although after many steps).

09 Jul 2008

It's very nice code. But I could not obtain the correct minimum value for Goldstein-Price's function as defined in http://www.geatbx.com/docu/fcnindex-01.html. Do I have to change something in the option?

05 Jul 2008

good

23 Jun 2008

Its a nice general purpose implementation. Could make it more versatile by allowing uphill steps with different probability distributions (this uses Boltzmann) and different freezing conditions

01 Jun 2008

Thank you for the comment, Travis. The error is thrown by the default generator function, which only operates on row vectors. To work with column vectors, you can pass the following generator to ANNEAL:
@(x) (x(:)'+(randperm(length(x))==length(x))*randn/100)'

I'll add that to the help shortly (the submission portal seems to be down at the moment).

29 May 2008

Great job, I like the program and so do the faculty here.

One suggestion though: right now it fails (in a non-helpful way) if you give it a loss function that works on column vectors (and a parent that is a column vector). Everything in the optimization toolbox works on functions of both row and column vector functions.

If you can't fix it to work on column vectors, at least add a note to the comments saying that it needs to be a row vector.

02 Apr 2008

Any suggestions? The file now allows you to provide a custom generator, so the choice of generator is basically unlimited, unless it should it be giving multiple outputs (which I can't really imagine).

31 Mar 2008

Thank you,good program, though the generator needs some improvements.

17 Jan 2008

Since I receive many requests for the Kirkpatrick et al. paper, it can be found online here:

http://www.cs.virginia.edu/cs432/documents/sa-1983.pdf

10 Dec 2007

matlap annealing

10 Dec 2007

programing simulated

05 Dec 2007

good one

10 Nov 2007

hello

30 Oct 2007
22 Oct 2007
22 Aug 2007

Extremely thankful that I found this. Found it accessible, even though I'm new to simulated annealing. Thank you! Great paired with Wikkipedia's entry on SA.

25 Jul 2007

the code accepts the input function to be optimized only via the function handle, that is it has to be known in advance in its explicit form; now i wonder if it is possible to use the code also with functions whose explicit form is not known; thank you

04 Jun 2007

A nice, efficient annealing algorithm to adapt as required.

18 May 2007

Simple, efficient and generic.
Can be easily adapted to particular contexts.

Congratulations

14 May 2007
06 May 2007

very well-expalained and very easily traced.

19 Feb 2007
15 Feb 2007
28 Nov 2006

I connected Joachim Vandekerckhove's files to the OpenOpt project
& informed him
if any pretensions will be received, I promise to exclude the one

27 Sep 2006

Corrected the typo. Incidentally, the function doesn't work on 5.1 anymore (it now uses anonymous functions).

25 Aug 2006

I've found the function useful.

Please change ct to camel in the example.

07 May 2006

John, I've taken all of your suggestions to heart. The interface is now closer to the standard in the Optimization Toolbox, I've put in defaults for everything, and given the user (optional) control over the annealing schedule.
The previous help didn't include anonymous functions because the algorithm was written in version 5.1, now it's written in 7.0.1. I'm not sure if it'll still work in 5.1, perhaps someone could test?

21 Apr 2006
29 Mar 2006

This does work, after a fashion. What did I not like about the code? Mainly the interface. The author has given you very much (perhaps too much) control over one part of the annealing process, in terms of how perturbations are generated. The help is somewht confusing, especially about the newsol function that you must provide. Why not provide some default for this? Surely there is an easier interface to use here?
The annealing schedule itself is something you have been given absolutely no control over, so if your problem did not converge quickly enough, your only choice is to edit the code, or keep rerunning it until you are happy. There is no tolerance to decide that it has converged before the time is up.
Finally, a minor point - the author refers often to the use of inline functions, but uses anonymous functions in the examples. Either type of function should work here.

26 Apr 2006