2D Simulated Annealing

2D Simulated Annealing preview image

2 collaborators

Default-person Kevin Brewer (Author)
Uri_dolphin3 Uri Wilensky (Advisor)



Tagged by Kevin Brewer about 10 years ago

Visible to everyone | Changeable by everyone
Model was written in NetLogo 5.0.2 • Viewed 1638 times • Downloaded 48 times • Run 0 times
Download the '2D Simulated Annealing' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


This model demonstrates the use of a simulated annealing algorithm on a very simple two-dimensional problem. Simulated annealing is an optimization technique inspired by the natural annealing process used in metallurgy, whereby a material is carefully heated or cooled to create larger and more uniform crystalline structures. In simulated annealing, a minimum (or maximum) value of some global "energy" function is sought. This model attempts to find a maximal solution in a two-dimensional grid.

We use such a simple problem in this model in order to highlight the solution technique only.


In this model, the objective function is defined for each patch in our 2D world. The location of each patch (x and y coordinates) can be thought of as the parameter values of the objective function.

The optimization works as follows. The system has a "temperature", which controls how much change is allowed to happen. A random location for an initial solution is defined, and then for each step, a potential move to a new solution (location) is either accepted or rejected. Changes that result in a greater solution value are always accepted (changes that result in no change of solution value will also always be accepted if the ACCEPT-EQUAL-CHANGES? switch is turned on). Changes that result in a lower solution value are only accepted with some probability, which is proportional to the "temperature" of the system using the Boltzmann Distribution. The temperature of the system decreases over time, according to some cooling schedule, which means that initially changes that decrease solution values will often be accepted, but as time goes on they will be accepted less and less frequently. This is similar to cooling a material slowly in natural annealing, to allow the molecules to settle into nice crystalline patterns. Eventually the temperature approaches zero, at which point the simulated annealing method is equivalent to a random mutation hill-climber search, where only beneficial changes are accepted.


Press the SETUP button to initialize the model and solution space.

Press the STEP button to go from one temperature to the next lower temperature.

Press the GO button to have the algorithm run until a solution has been found.

Adjust the COOLING-RATE slider to change how quickly the temperature drops.
The current temperature is shown in the TEMPERATURE monitor.

The DELTA-MAX slider controls how far a potential movement can be.

If the ACCEPT-EQUAL-CHANGES? switch is ON, then the system will always accept a new solution that yields no change in solution value. If it is OFF, then equal solutions are treated the same as those decrease the solution value, and thus are only accepted probabilistically based on the system temperature.

The Solution monitors and plot show how the algorithm is performing and the best solution that has been found.


Slower cooling rates lead to higher optimal solutions (on average).


If you turn ACCEPT-EQUAL-CHANGES? to ON, does slow cooling still work better than fast cooling?

Try varying the DELTA-MAX. Does this help the system to reach more optimal configurations?


Currently, the probability of accepting a change that increases the best solution value is always 1, and the probability of accepting a change that decreases the solution value is based on the temperature of the system and the amount by which the solution has changed. Try extending the model to make more alternative acceptance decision criteria.

Simulated annealing can be used on a wide variety of optimization problems. Experiment with using this technique on different "energy/cost" function, or even entirely different problems.



Particle Swarm Optimization, Simple Genetic Algorithm, Crystallization Basic, Ising


Original papers describing a simulated annealing
S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, Vol 220, Number 4598, pages 671-680, 1983.
V. Cerny, A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications, 45:41-51, 1985


If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:


Copyright 2012 Kevin Brewer. All rights reserved. Copyright 2009 Uri Wilensky. All rights reserved.


This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu and Kevin Brewer at kbrewer@olivet.edu

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

turtles-own [
  fitness        ;; equal to the solution value of the objective function at the turtle's current location

patches-own [
  solution       ;; the solution (energy or fitness) for the x,y values (may be negative)

globals [
  winner         ;; not really necessary since there is only one turtle at a time, but it is the turtle 
                 ;; that currently has the best solution
  total-work     ;; amount of work that is has been done. Essentially the number of times a solution value
                 ;; has been calculated
  best-fitness   ;; the current best solution - again, not really "best" since there is only one current solution 
  global-best-fitness  ;; the best solution that has ever been found during the progress
  global-best-loc      ;; where the best solution was found
  g-x   ;; temporary variables that hold the best x and y location
  temperature   ;; the current temperature of the system. Starts at 100 and the algorithm terminates when it gets below 1.

  max-solution  ;; the greatest patch value prior to scaling. used during setup.
  top-solution  ;; the ultimate greatest patch value after scaling.
  low-solution  ;; the lowest patch value prior to scaling. used during setup.


to setup
;; create the 2D domain of solutions
  set max-solution -100
  set top-solution 400

  set total-work 0 ;; we start off at 0 work performed, obviously.

;; create the turtle that will represent the algorithm's current parameter set (i.e., location).
  create-turtles 1 [
     setxy random-xcor random-ycor ;; start the turtle at a random solution point
     set color cyan
     set shape "circle"
     ifelse trace-on? [ pen-down ] [ pen-up ]
     set total-work (total-work + 1) ;; everytime we calculate a solution, we add 1 to our total work counter.

;; populate the variables with "best" solution information
  set winner max-one-of turtles [fitness]
  set best-fitness [fitness] of winner
  set global-best-fitness best-fitness
  set g-x [xcor] of winner
  set g-y [ycor] of winner
  set global-best-loc (list g-x g-y)
;; set the initial temperature of the system
  set temperature 100



to go
;; anneal at this temperature

;; populate the variables with "best" solution information
  set winner max-one-of turtles [fitness]
  set best-fitness [fitness] of winner
  if best-fitness > global-best-fitness [ 
      set global-best-fitness best-fitness 
      set g-x [xcor] of winner
      set g-y [ycor] of winner
      set global-best-loc (list g-x g-y)

;; reduce the temperature based on user input
  set temperature temperature * (1 - cooling-rate / 100)
;; determine if we stop. If so, put the overall best solution in the monitors.
  if (temperature < 1)
    [ ask turtles 
      set color yellow
      setxy (item 0  global-best-loc) (item 1  global-best-loc)
      stop ]


to create-solutions
;; solutions are stored as the "solution" patch variable
  ask patches [
;; for each patch, we initially set the solution to zero, just so something is in the variable at each location.
    set solution 0
;; we will now put a bunch of "single spires" in the patch. We will eventually smooth these individual spires to make them "humps".
      if random-float 1 < .5 
       [ ;; controls the number of spires, on a per patch basis - so want a low probability
          ifelse random-float 1 < 0.25 
             [set solution -.25]
             [set solution 1 ]
          set solution (solution * random (top-solution * 100))
;; smooth the spires to make humps    
     repeat 100 [ diffuse solution 1.0 ]
;; now we will add a bit of small scale variability to the solution space - i.e., bumps.
  ask patches [
    set solution ( solution + random (top-solution / 20)) 
;;Now for the scaling of solution
;; adjust all solutions to a height proportional to the overall solution of the patch
  set max-solution max [solution] of patches
  if max-solution > 0 
    [ ask patches 
      [ set solution ((solution   /  max-solution  ) * top-solution ) ]
  set max-solution max [solution] of patches
  set low-solution min [solution] of patches
;; now we will color the patches to make a nice visualization  
  ask patches [
     set pcolor scale-color brown solution low-solution top-solution 
;; let's highlight the best solution (maximum patch) by coloring it red  
  let best-patch max-one-of patches [solution]
  ask best-patch [ set pcolor red ]


to calculate-fitness       
;; a turtle procedure that returns the patch solution where the turtle is
  set fitness [solution] of patch-here


to-report accept-change? [ old-energy new-energy ]
;; a reporter that will return true or false to indicate whether the turtle will move (accept)
;; the new solution location, or stay where it is.

  report (new-energy > old-energy)       ;; always accept new location if better.
         or (accept-equal-changes? and new-energy = old-energy) ;; accept new location at equal value if user control says so
;; the following line is the key simulated annealing control. The idea is that as the temperature is reduced, it is less likely
;; to move to a poorer new location. When the temperature is high, the probabily of moving to poorer locations is greater.
;; this follows the Boltzmann Distribution
         or ( exp ((old-energy - new-energy) * -1 / (0.1 * temperature)) > random-float 1.0 )


to anneal-turtle
;; figure out what the new potential solution is, and determine whether to move there or stay put.
  ask turtles [ ;; there is only one turtle...
;; in this 2D example, a new solution can be found by going a distance in a direction. We will use
;; the built-in turtle moving routines to make this easy to program.
;; pick a random direction
    right random 360
;; get a random distance that is limited by the user control
    let my-distance max-pxcor  * delta-max / 100 * random-float 1.

;; figure out what the solution is for the new distance and compare to current solution
    if ( can-move? my-distance )
       [ let o-energy fitness
         let n-energy [solution] of patch-ahead my-distance 
         set total-work (total-work + 1)
         if (accept-change? o-energy n-energy )
;; we have determined to move to the new solution, so do it!
             move-to patch-ahead my-distance
;; we don't increment the work counter, since we really already calculated it and accounted for it just previously.

; Portions COpyright 2012 Kevin Brewer. All rights reserved.
; Portions Copyright 2008 Uri Wilensky. All rights reserved.
; The full copyright notice is in the Information tab.

There is only one version of this model, created about 10 years ago by Kevin Brewer.

Attached files

File Type Description Last updated
2D Simulated Annealing.png preview Preview for '2D Simulated Annealing' about 10 years ago, by Kevin Brewer Download

This model does not have any ancestors.

This model does not have any descendants.