# Simulated Annealing

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

## 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

Copyright 2009 Uri Wilensky.

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

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.

## 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.