2D Genetic Algorithm

;; Each potential solution is represented by a turtle.

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 [
  running_fitness  ;; this is a set of the most recent best solution values. Used to determine when to stop 
                   ;; (if no better solution has been determined in these listed iterations)
  winner           ;; 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 best solution for the current generation of solutions
  avg-fitness      ;; the average solution for the current generation of solutions
  worst-fitness    ;; the worst solution for the current generation of solutions
  bst-bits         ;; the parameter values (x and y) for the current best solution

  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.
  
;; the following parameters are just temporary placeholders used in the algorithm
  p1x p2x p1y p2y
  g-x g-y
]

;==========SETUP=============

to setup
  clear-all
  
;; create the 2D domain of solutions
  set max-solution -100
  set top-solution 400
  create-solutions 
  
  
;; create an initial set of solution values, all at zero except for the first one (so the algorithm doesn't immediately stop!)
  set running_fitness n-values 100 [0]
  set running_fitness replace-item 0 running_fitness 100
  

  set total-work 0 ;; we start off at 0 work performed, obviously.

;; create the initial population of solution turtles
  create-turtles population-size [
     setxy random-xcor random-ycor ;; start each turtle at a random solution point
     set color green
     set shape "circle"
     calculate-fitness
  ]
  
;; populate the monitor variables with the current generation solution information
  let fitness-list  ([fitness] of turtles) 
  set best-fitness max fitness-list
  set avg-fitness mean fitness-list
  set worst-fitness min fitness-list
  set winner max-one-of turtles [fitness]
  set g-x [xcor] of winner
  set g-y [ycor] of winner
  set bst-bits (list g-x g-y)
;; use the solution values set as a first in, first out stack.
  set running_fitness lput best-fitness running_fitness
  set running_fitness but-first running_fitness

  reset-ticks
end 
;=====================================

;===========GO========================

to go
;; for each new generation, first thing to do is to create it!
  create-next-generation
  
;; populate the monitor variables with the current generation solution information
  let fitness-list ([fitness] of turtles)
  set best-fitness max fitness-list
  set avg-fitness mean fitness-list
  set worst-fitness min fitness-list
  set winner max-one-of turtles [fitness]
  set g-x [xcor] of winner
  set g-y [ycor] of winner
  set bst-bits (list g-x g-y)

  set running_fitness lput best-fitness running_fitness
  set running_fitness but-first running_fitness

;; determine if there has been any significant improvement to the best solution value over the past 100 generations
;; if no signficant improvement, stop
  if abs ((mean running_fitness - last running_fitness)) < 0.001
    [ 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 total-work (total-work + 1)
  set fitness [solution] of patch-here
end 
;=====================================

;=======CREATE-NEXT-GENERATION========

to create-next-generation
  ; The following line of code looks a bit odd, so we'll explain it.
  ; if we simply wrote "LET OLD-GENERATION TURTLES",
  ; then OLD-GENERATION would mean the set of all turtles, and when
  ; new solutions were created, they would be added to the breed, and
  ; OLD-GENERATION would also grow.  Since we don't want it to grow,
  ; we instead write "TURTLES WITH [TRUE]", which makes OLD-GENERATION
  ; an agentset, which doesn't get updated when new solutions are created.
  let old-generation turtles with [true]

  ; CROSS-OVER
  ; Some number of the population is created by crossover each generation
  ; we divide by 2 because each time through the loop we create two children.
  let crossover-count  (floor (population-size * crossover-rate / 100 / 2))

  repeat crossover-count
  [
    ; We use "tournament selection" with a user defined tournament size.
    ; This means, we randomly pick tournament-size solutions from the previous generation
    ; and select the best one of those to reproduce with another "best".

    let parent1 max-one-of (n-of tournament-size old-generation) [fitness]
    let parent2 max-one-of (n-of tournament-size old-generation) [fitness]

;; we will now "cross" the x and y parts and create two new turtles based on those new locations.
;; with only two "genes", the cross-over doesn't really make sense except to create a different child
;; than the parents.
    
    ask parent1 [
      set p1x xcor
      set p1y ycor
    ]
    
    ask parent2 [
      set p2x xcor
      set p2y ycor
    ]
    
; create the two children, with their new genetic material
    ask parent1 [ hatch 1 [ move-to patch-at p1x p2y ] ]
    ask parent2 [ hatch 1 [ move-to patch-at p2x p1y ] ]
  ]

; the remainder of the new generation is created by cloning tournament selected members of the previous generation
  repeat (population-size - crossover-count * 2)
  [
    ask max-one-of (n-of tournament-size old-generation) [fitness]
      [ hatch 1 ]
  ]
  
;; we will now get the "winner" from the old-generation and make sure it is cloned into the new generation
  ask max-one-of old-generation [fitness]
      [ hatch 1 ] 

;; kill all the old folks!
  ask old-generation [ die ]

; now we're just talking to the new generation of solutions here
; consider mutating the genes of each new turtle
  ask turtles
  [
    mutate
  ]
  
; since we added in the best turtle from the previous generation, we need to kill a random one off first 
;; to maintain constant total turtle population count. Note that there is a chance that we are killing off our best turtle.
  ask one-of turtles [die]
  
; finally we update the solution values for each turtle for this new generation
  ask turtles [
    calculate-fitness
  ]
end 
;=====================================

;=======MUTATE========================

to mutate   
;; a turtle procedure that will randomly change the "genes" of a turtle, with the probability based on the user control.
;; 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 distance and direction
  let mydist random max-pxcor
  right random 360
;; make the change if probabilities work out
  if (random-float 100.0 < mutation-rate) 
     and  (can-move? mydist )
       [ move-to patch-ahead mydist] 
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.