# 2D Simulated Annealing

### 2 collaborators

Kevin Brewer (Author)

### Tags

optimization

Tagged by Kevin Brewer over 6 years ago

Visible to everyone | Changeable by everyone
Model was written in NetLogo 5.0.2 • Viewed 1043 times • Downloaded 34 times • Run 0 times

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

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

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