2D Genetic Algorithm

2D Genetic Algorithm preview image

2 collaborators

Default-person Kevin Brewer (Author)
Uri_dolphin3 Uri Wilensky (Author)

Tags

optimization 

Tagged by Kevin Brewer about 3 years ago

Visible to everyone | Changeable by everyone
Model was written in NetLogo 5.0.2 • Viewed 940 times • Downloaded 50 times • Run 0 times
Download the '2D Genetic Algorithm' modelDownload this modelEmbed this model

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 genetic algorithm on a very simple two-dimensional problem. Genetic algorithms (GAs) are a biologically-inspired computer science technique that combine notions from Mendelian genetics and Darwinian evolution to search for good solutions to problems (including difficult problems). The GA works by generating a random population of solutions to a problem, evaluating those solutions and then using cloning, recombination and mutation to create new solutions to the problem.

In this model we use a simple problem in order to highlight the solution technique only.

HOW IT WORKS

The genetic algorithm is composed of the following steps.

1) A population of random solutions is created. Each solution consists of a random location (x and y, which we are assuming are our parameters).

2) Each solution is evaluated on the basis of how well it solves the problem. This measure of the "goodness" of the solution is called its "fitness". In this model, our goal is simply to find a solution that consists of the greatest solution value. (In real-world applications of the genetic algorithm, the goals are much more complex, but the solutions are still usually encoded as binary strings or a numeric vector.)

3) A new generation of solutions is created from the old generation, where solutions that have a higher fitness scores are more likely to be chosen as "parent" solutions than those that have low fitness scores.

A) The selection method used in this model is called "tournament selection", with a tournament size that is user defined. If the tournament size was 3, this means that 3 solutions are drawn randomly from the old generation, and the one with the highest fitness is chosen to become a parent.

B) Either one or two parents are chosen to create children. With one parent, the child is a clone or copy of the parent. With two parents, the process is the digital analog of sexual recombination -- the two children inherit part of their genetic material from one parent and part from the other.

C) There is also a chance that mutation will occur, and some of the child's genes (parameters) will be changed randomly.

4) Steps 2 and 3 above are repeated until a solution is found that successfully solves the problem.

HOW TO USE IT

Press the SETUP button to initialize the model and solution space, and create the first generation.

Press the STEP button to have one new generation created from the old generation.

Press the GO button to have the genetic algorithm run until a solution has been found.

The best solution found in each generation is displayed, along with algorithmic performance indicators.

Parameters:

The POPULATION-SIZE slider controls the number of solutions that are present in each generation.

The CROSSOVER-RATE slider controls what percent of each new generation is created through sexual reproduction (recombination or crossover between two parents' genetic material), and what percent (100 - CROSSOVER-RATE) is created through asexual reproduction (cloning of one parent's genetic material).

The MUTATION-RATE slider controls the percent chance of mutation. This chance applies to each position in the string of parameters of a new individual. For instance, if the gene string is 100 parameters long, and the mutation-rate is set at 1%, then on average one gene will be changed during the creation of each new individual.

The TOURNAMENT-SIZE slider controls the number of solutions that will be used in the tournament selection process.

The "Solution Progress" plot is used to show the best, average, and worst fitness values of the solutions at each generation.

THINGS TO NOTICE

Step through the model slowly, and look at the visual representation of the location of each solution for the current generation. Note that multiple turtles can be at the same location. How often does the best solution in Generation X+1 appear to be the offspring of the best solution in Generation X?

THINGS TO TRY

Explore the effects of larger or smaller population sizes on the number of generations it takes to solve the problem completely. What happens if you measure the amount of time (in seconds) that it takes to solve the problem completely?

Explore the effects of larger or smaller tournament sizes on the number of generations it takes to solve the problem completely.

How does asexual reproduction compare to sexual reproduction for solving this problem? (What if CLONING-RATE is 100, or CLONING-RATE is 0?)

How much mutation is beneficial for the genetic algorithm? Can the genetic algorithm find a perfect solution if there is MUTATION-RATE is 0? What about if MUTATION-RATE is 10.0? Can you find an optimal MUTATION-RATE?

EXTENDING THE MODEL

Many variations on this simple genetic algorithm exist. For example, some genetic algorithms include "elitism". In this case, the best X% of solutions from the old generation are always copied directly into the new generation. Modify this model so that it uses elitism more than it does now.

Another type of selection for reproduction that is sometimes used in genetic algorithms is called "roulette selection". In this case, you may imagine each solution in the population being assigned a wedge of a large roulette wheel. The size of the wedge is determined by dividing the fitness of each solution by the sum of the fitnesses of all solutions in the population. Thus, the probability of selecting any given solution to reproduce is directly proportional to its fitness. Try implementing this type of selection, and compare its performance to the "tournament selection" method that is currently used in this model.

As noted above, this problem is not very interesting in its own right. A natural extension of this model is to use the genetic algorithm to solve a problem that is significantly more interesting. Fortunately, you can change the problem that the genetic algorithm is solving by only modifying one thing, the "fitness function", which evaluates how good a given string of parameters is at solving whatever problem you are trying to solve. (You could add a "gene" variable to each turtle which would represent a list of solution parameters for that turtle.)

NETLOGO FEATURES

Note that NetLogo's powerful ability to work with agentsets makes it very easy to code the "tournament selection" used in this model. The following code is sufficient:

  max-one-of (n-of 3 old-generation) [ga-fitness]

RELATED MODELS

Echo is another model that is inspired by the work of John H. Holland. It examines issues of evolutionary fitness and natural selection.

There are several NetLogo models that examine principles of evolution from a more biological standpoint, including Altruism, Bug Hunt Camouflage, Cooperation, Mimicry, Peppered Moths, as well as the set of Genetic Drift models.

Sunflower Biomorph uses an artistic form of simulated evolution, driven by aesthetic choices made by the user.

CREDITS AND REFERENCES

This model is based off of work by John H. Holland, who is widely regarded as the father of the genetic algorithms. See Holland's book "Adaptation in Natural and Artificial Systems", 1992, MIT Press.

Additional information about genetic algorithms is available from a plethora of sources online.

HOW TO CITE

If you mention this model in an academic publication, we ask that you include these citations for the model itself and for the NetLogo software:

In other publications, please use:

COPYRIGHT NOTICE

Copyright 2012 Kevin Brewer. All rights reserved. Copyright 2008 Uri Wilensky. All rights reserved.

Permission to use, modify or redistribute this model is hereby granted, provided that both of the following requirements are followed:
a) this copyright notice is included.
b) this model will not be redistributed for profit without permission from Uri Wilensky and Kevin Brewer. Contact Uri Wilensky uri@northwestern.edu and Kevin Brewer (kbrewer@olivet.edu) for appropriate licenses for redistribution for profit.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

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

There is only one version of this model, created about 3 years ago by Kevin Brewer.

Attached files

File Type Description Last updated
2D Genetic Algorithm.png preview Preview for '2D Genetic Algorithm' about 3 years ago, by Kevin Brewer Download

This model does not have any ancestors.

This model does not have any descendants.