2D Simulated Annealing

2D Simulated Annealing preview image

2 collaborators

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

Tags

optimization 

Tagged by Kevin Brewer over 4 years ago

Visible to everyone | Changeable by everyone
Model was written in NetLogo 5.0.2 • Viewed 876 times • Downloaded 30 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.)


WHAT IS IT?

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.

HOW IT WORKS

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.

HOW TO USE IT

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.

THINGS TO NOTICE

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

THINGS TO TRY

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?

EXTENDING THE MODEL

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.

NETLOGO FEATURES

RELATED MODELS

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

CREDITS AND REFERENCES

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

HOW TO CITE

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 NOTICE

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

CC BY-NC-SA 3.0

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
  g-y
  
  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.
]

;==========SETUP=============

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

  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 ]
     calculate-fitness
     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

  reset-ticks
end 
;=====================================

;===========GO========================

to go
;; anneal at this temperature
  anneal-turtle

;; 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 ]
  tick
end 
;=====================================

;===========CREATE-SOLUTIONS==========

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 ]
end 
;=====================================

;=======CALCULATE-FITNESS=============

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

;=======ACCEPT-CHANGE?================

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 )
end 
;=====================================

;=======ANNEAL-TURTLE================

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
             calculate-fitness
;; we don't increment the work counter, since we really already calculated it and accounted for it just previously.
           ] 
       ]
  ]
end 


; 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 over 4 years ago by Kevin Brewer.

Attached files

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

This model does not have any ancestors.

This model does not have any descendants.