NetLogo Models Library:
Sample Models/Computer Science/Unverified

Note: This model is unverified. It has not yet been tested and polished as thoroughly as our other models.

(back to the library)

Simulated Annealing

If you download the NetLogo application, this model is included. You can also Try running it in NetLogo Web

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 or the NetLogo software in a publication, we ask that you include the citations below.

For the model itself:

• 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 University, Evanston, IL.

Please cite the NetLogo software as:

• Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, 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 https://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.

(back to the NetLogo Models Library)