Difference between iteration and objective function evaluation in simulated annealing?

I am trying to implement simulated annealing in a pose finding problem where I am fitting a 3D human model to a silhouette. I have a basic grasp of the simulated annealing algorithm and am not trying to tune my code. I have several questions all dealing with the same subject. First, there are optios for a max # of iterations and a max # of objective functions evaluations - what is the difference between the two? Does an objective function evaluation not happen with every iteration?

Second, what criteria does matlab use to know when the optimization has reached "thermal equilibrium" and should drop the temperature?

Thanks everyone

Answer 1

[Alan Weiss]

If you look at the algorithm description, you will see that the reannealing step includes some gradient estimation. This increases the function count over the iteration count. Also, there is an initial error-check that evaluates the objective function before any iterations take place.

But, if you look at iterative display, you do indeed see that the two are almost the same.

Alan Weiss

MATLAB mathematical toolbox documentation

One run with iterative display begins like this (you can see a change at the line beginning with *, which is where a reannealing step took place):

                           Best        Current           Mean
Iteration   f-count         f(x)         f(x)         temperature
     0          1        12.6705        12.6705            100
    10         11        12.6705        12.6705          56.88
    20         21        12.6705        12.6705        34.0562
    30         31        6.90337        6.90337        20.3907
    40         41        6.90337         29.776        12.2087
    50         51        6.90337         29.776        7.30977
    60         61        6.90337         29.776        4.37663
    70         71        6.90337         29.776        2.62045
    80         81        6.90337        11.7646        1.56896
    90         91        6.90337        11.9592       0.939395
   100        101        6.90337         11.726        0.56245
   110        111        6.90337        11.7893        0.33676
   120        121        6.90337        11.7187       0.201631
   130        131        6.90337        11.7188       0.120724
   140        141        6.90337        11.7187      0.0722817
   150        151        6.90337        11.7187      0.0432777
   160        161        6.90337        11.7187       0.025912
   170        171        6.90337        11.7187      0.0155145
   180        181        6.90337        11.7187     0.00928908
   190        191        6.90337        11.7187     0.00556171
   200        201        6.90337        11.7187        0.00333
*  210        213        6.90337        11.7187        51.2535
   220        223        6.90337        11.7187        30.6874
   230        233        6.90337        11.7187        18.3737
   240        243        6.90337        11.7187         11.001

[Anthony]

perfect. thanks!

Answer 2

[Alan Weiss]

I do not understand your question. Do you have a Global Optimization Toolbox license, and you are using simulannealbnd? Or are you coding up your own simulated annealing solver?

If you are using simulannealbnd, then the algorithm description is here. There are some more details in the options descriptions.

After you read those sections, if you have more questions, feel free to ask again.

Alan Weiss

MATLAB mathematical toolbox documentation

[Anthony]

Thanks for your help, please see my response

Answer 3

[Anthony]

Hi Allen,

Thanks for your help. I have the global optimization toolbox and am using simulannealbnd, and I have read the documentation. I have read papers describing simulated annealing as 2 nested loops, the inner being a loop that finds "thermal equilibrium" at the current temperature, and the outer loop that checks stopping criteria and drops the according to the cooling schedule. Within this format, I do not see how an iteration and an objective function evaluation differ, because it seems that in the inner loop, every iteration would also include an objective function evaluation, yet each has it's own value in the options. So, why would the algorithm reach an objective function evaluation limit before an iteration limit or vice versa?

[Alexis Tugilimana]

Hi,

I am currently working on optimization procedures involving a simulated annealing. Therefore, I also contemplated working with the optimization toolbox already implemented into MATLAB. I was wondering, according to what I saw in the documentation and to the answer of the previous questions, how is that possible that the number of function evaluation stays close to the number of iterations (corresponding to a decrease of the temperature) since each temperature modification should involve a search of equilibrium by running a Markov chain process. Thus, for each temperature value, an inner loop should be executed, in which multiple function evaluation should be performed. I know this question is basically the same to yours but I wanted to know if, after all these years, you would have been able to find an answer.

Thank you in advance,

Alexis