2D Simulated Annealing

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.