Code covered by the BSD License  

Highlights from
General simulated annealing algorithm

4.15625

4.2 | 32 ratings Rate this file 149 Downloads (last 30 days) File Size: 3.77 KB File ID: #10548
image thumbnail

General simulated annealing algorithm

by

 

28 Mar 2006 (Updated )

Minimizes a function with the method of simulated annealing

| Watch this File

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

This file inspired Solution To Economic Dispatch By Simulated Annealing and Simulated Annealing Optimization.

MATLAB release MATLAB 7.0.1 (R14SP1)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (51)
10 Jun 2014 Joshua

From my understanding, this isn't a strict simulated annealing program, but more of a pure Monte Carlo.
To be simulated annealing, the 'Generator' would need to be modified so that the size of the changes it makes to the model parameters shrinks as the temperature shrinks.

27 Mar 2014 lvlin  
21 Sep 2013 Joachim Vandekerckhove

To those who are looking to constrain parameters to a certain range, the easiest way is to constrain the Generator option. For example: Generator = @(x) (rand(3,1)); will only return results in the unit cube. You can also make your own Generator = @(x)myRand(x); to return only points in any domain you choose.

28 Aug 2013 Emmanuel Farhi

That's a very good optimizer, especially on noisy problems.

22 Jun 2013 Luke S

Hi,

This function worked really well right off the bat, thanks! Is there a way to incorporate bounds for the parameters? I'm simulating some electrophysiological data, and I want to constrain the parameters to realistic values.

Thanks,
Luke

13 Jan 2012 LIAO xj  
15 Aug 2011 Sanjay Manohar

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 aymen

how we can adjust PID parameter by this algorithm

19 Oct 2010 Nik

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

Thank you.

04 Aug 2010 Brecht

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

http://biomath.ugent.be/~brecht/downloads.html

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 David Schwartz

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 OLAWALE ADEWALE

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

02 Jun 2010 Chih-Ying Hsiao

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 Christophe  
26 Jun 2009 Terrance Nearey  
17 Jun 2009 Jorge Garriga

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 Seyed Iman

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 David  
21 Apr 2009 Joachim Vandekerckhove

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.

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

Also, the link to the SA paper above is dead. Here is a new link:

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

03 Feb 2009 Allen

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 ato Xu

thks

09 Sep 2008 Yongguo SHI  
28 Aug 2008 Joachim Vandekerckhove

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 Hom Gharti

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 woosung yang

good

23 Jun 2008 Vlad Lazar

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 Joachim Vandekerckhove

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 Travis Johnson

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 Joachim V

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 MAS Sahabi

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

17 Jan 2008 Joachim Vandekerckhove

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 ibrahim mady

matlap annealing

10 Dec 2007 ibrahim mady

programing simulated

05 Dec 2007 pyari lal

good one

10 Nov 2007 atefe naderifard

hello
please send informatiom about simuated anealing.

30 Oct 2007 huilin zhou  
22 Oct 2007 Alireza Sarand  
22 Aug 2007 L Taylor

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 robert bolding

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 Graeme Doole

A nice, efficient annealing algorithm to adapt as required.

18 May 2007 Laurent Ferro-Famil

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

Congratulations

14 May 2007 Saeed Soltani  
06 May 2007 Ahmed Bin Ezra

very well-expalained and very easily traced.

19 Feb 2007 Peng YU  
15 Feb 2007 felix prasad  
28 Nov 2006 Dmitrey Kroshko

I connected Joachim Vandekerckhove's files to the OpenOpt project
http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=13115&objectType=file
& informed him
if any pretensions will be received, I promise to exclude the one

27 Sep 2006 Joachim Vandekerckhove

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

25 Aug 2006 Christopher Schwalm

I've found the function useful.

Please change ct to camel in the example.

07 May 2006 Joachim Vandekerckhove

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 ralph guo  
29 Mar 2006 John D'Errico

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.

Updates
26 Apr 2006

Changed interface and added help.

31 Aug 2006

Corrected typo in help

Contact us