# 2D Simulated Annealing

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:

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

## COPYRIGHT NOTICE

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

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 almost 5 years ago by Kevin Brewer.

## Attached files

File | Type | Description | Last updated | |
---|---|---|---|---|

2D Simulated Annealing.png | preview | Preview for '2D Simulated Annealing' | almost 5 years ago, by Kevin Brewer | Download |

This model does not have any ancestors.

This model does not have any descendants.