Simulated Annealing

2 collaborators

Uri Wilensky (Author)

WHAT IS IT?

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 value of some global "energy" function is sought. This model attempts to find a minimal energy state of a simple function on a black and white image.

HOW IT WORKS

In this model, the energy function takes a black and white image as an input. The energy is defined locally for each pixel (square patch) of a the image, and the "global energy" function is the sum of the energy from all of the individual pixels. Energy is minimized by having each pixel be the same as the pixels above and below it, but different from pixels to the left and right of it. The initial image has exactly 50% black and 50% white pixels, assigned randomly. An optimal (lowest energy) configuration is a series of alternating vertical black and white lines.

The optimization works as follows. The system has a "temperature", which controls how much change is allowed to happen. Small changes (swapping adjacent pixel values) in the image are considered, and either accepted or rejected. Changes that result in a lower energy level are always accepted (changes that result in no change of energy level will also always be accepted if the ACCEPT-EQUAL-CHANGES? switch is turned on). Changes that result in a higher energy level are only accepted with some probability, which is proportional to the "temperature" of the system. The temperature of the system decreases over time, according to some cooling schedule, which means that initially changes that increase global energy 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 SETUP to initialize the model. The image will be half black and half white pixels, and the system temperature is set at 1.00.

Press GO to run simulated annealing on the image.

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

The SWAP-RADIUS slider controls how far apart a pixel can be from another pixel to consider a swap with it.

If the ACCEPT-EQUAL-CHANGES? switch is ON, then the system will always accept a pixel swap that yields no change in global energy. If it is OFF, then equal-energy swaps are treated the same as swaps that increase the global energy, and only accepted probabilistically based on the system temperature.

The GLOBAL ENERGY monitor and plot show how the energy of the system decreases over time, through the simulated annealing process.

THINGS TO NOTICE

With the default settings (SWAP-RADIUS = 1, ACCEPT-EQUAL-CHANGES? = OFF), slower cooling rates lead to more optimal low-energy image configurations (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 SWAP-RADIUS. Does this help the system to reach more optimal configurations?

EXTENDING THE MODEL

Currently, the probability of accepting a change that decreases the total system energy is always 1, and the probability of accepting a change that increases the total system energy is based purely on the "temperature" of the system. In neither case does the amount by which the energy has changed (for better or worse) figure into the probability. Try extending the model to make more "sophisticated" 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

This model uses the patch-set primitive to define a small set of patches that are affected by a pixel swap. This is useful for efficiently computing the change in energy resulting from the swap (as opposed to computing the energy for all of the patches).

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:

Stonedahl, F. and Wilensky, U. (2009). NetLogo Simulated Annealing model. http://ccl.northwestern.edu/netlogo/models/SimulatedAnnealing. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

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.

Comments and Questions

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

Click to Run Model

globals [ temperature global-energy ]
patches-own [ brightness ]

to setup
  clear-all
  ask n-of ((count patches) / 2) patches
  [
    set brightness 1
  ]
  ask patches [ update-visual ]
  set global-energy (sum [find-energy] of patches )
  plot global-energy
  set temperature 1
  reset-ticks
end 

to go
  repeat 1000
  [
    ask one-of patches [
      try-swap
    ]
  ]
  ; we lower the temperature after 1000 attempted swaps
  set temperature temperature * (1 - cooling-rate / 100)
  set global-energy (sum [find-energy] of patches )
  plot global-energy
  tick
end 

to update-visual
  set pcolor brightness * 9.9  ; 0 = black, 9.9 = white
end 

;; The swap (change in state) will always be accepted if the new energy level is lower.
;; There is a switch in the interface (accept-equal-changes) which determines whether
;;   to always accept swaps that lead to equal energy levels.
;; Lastly, even if the swap increases energy, it may be accepted (with probability
;;   proportional to the current "temperature" of the system.)

to-report accept-change? [ old-energy new-energy ]
  report (new-energy < old-energy)
         or (accept-equal-changes? and new-energy = old-energy)
         or ((random-float 1.0) < temperature)
end 

to try-swap
  let p2 one-of (patches in-radius swap-radius)
  if (brightness = [brightness] of p2) ; if same color, no point in swapping.
    [ stop ]
  ;; For efficiency, we only compute the change in energy in the region of patches
  ;;    affected by the swap.
  let affected-patches (patch-set self p2 neighbors4 ([neighbors4] of p2))
  let old-energy sum [find-energy] of affected-patches
  swap-values self p2
  let new-energy sum [find-energy] of affected-patches
  ifelse (accept-change? old-energy new-energy)
  [
    update-visual
    ask p2 [ update-visual ]
  ]
  [
    swap-values self p2
  ]
end 

to swap-values [ p1 p2 ]
  let temp [ brightness ] of p1
  ask p1 [ set brightness [brightness] of p2 ]
  ask p2 [ set brightness temp ]
end 

;; this is the "energy" function for a single patch, which simulated annealing is
;; trying to minimize globally

to-report find-energy  ; patch-procedure
  let unhappiness 0.0
  ask patch-at 0 1 [ set unhappiness unhappiness + (brightness - [brightness] of myself) ^ 2 ]
  ask patch-at 0 -1 [ set unhappiness unhappiness + (brightness - [brightness] of myself) ^ 2 ]
  ask patch-at 1 0 [ set unhappiness unhappiness + 1 - (brightness - [brightness] of myself) ^ 2 ]
  ask patch-at -1 0 [ set unhappiness unhappiness + 1 - (brightness - [brightness] of myself) ^ 2 ]
  ; maximum of 4, minimum of 0
  report unhappiness
end 


; Copyright 2009 Uri Wilensky.
; See Info tab for full copyright and license.

There are 10 versions of this model.

Uploaded by	When	Description	Download
Uri Wilensky	over 11 years ago	Updated to NetLogo 5.0.4	Download this version
Uri Wilensky	about 12 years ago	Updated version tag	Download this version
Uri Wilensky	about 12 years ago	Updated to version from NetLogo 5.0.3 distribution	Download this version
Uri Wilensky	almost 13 years ago	Updated to NetLogo 5.0	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Model from NetLogo distribution	Download this version
Uri Wilensky	over 14 years ago	Simulated Annealing	Download this version

Attached files

File	Type	Description	Last updated
Simulated Annealing.png	preview	Preview for 'Simulated Annealing'	over 11 years ago, by Uri Wilensky	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo