Minimal Genetic Algorithm

turtles-own [chromosome  ;; a string of digits representing one candidate solution to the problem
             fitness     ;; the numerical value of the chromosomal strings
             ]

globals [best            ;; the numerical value of the chromosome  closer to the goal
         worst           ;; the numerical value of the chromosome more distant from the goal
         donor           ;; the agent having the best chromosome
         recipient       ;; an agent not having the best chromosome
         chromcopy       ;; the copy of the best chromosome
         a-split         ;; the position of one extreme of a chromosome's fragment
         b-split         ;; the position of the second extreme of a chromosome's fragment
         counter         ;; a counter usefull in different blocks
         ]



;;  ----------   SETUP PROCEDURES   -----------------------------------------------------------------------------
;;  -------------------------------------------------------------------------------------------------------------

to setup                 ;; reset parameters and create a number of agents given by the user
  clear-all
  set counter 0
  reset-ticks
  create-turtles turtles-number [
    set shape "circle 2"
    set size 1.8
    fd 7
    genotype/phenotype-construction
   ]
end 

to genotype/phenotype-construction
  ;; the genotype (chromosome) and the corresponding fenotype (fitness) of the agent
  ;; is initially equal to the worst solution; it is shown as a label
  set fitness 10 ^ (genes-number - 1)
  ;; the lowest fitness value is converted into a string:
  ;; it will be the initial chromosome structure
  set chromosome word fitness ""
  ;; chromosome is displayed as a label
  set label chromosome
end 



;;  ----------   RUNTIME PROCEDURES   ---------------------------------------------------------------------------
;;  -------------------------------------------------------------------------------------------------------------

to search
  ;; worse and best fitness value are detected
  set worst min [fitness] of turtles
  set best max [fitness] of turtles
  ;; the problem is resolved when an agent gain the higher value of fitness having a
  ;; user-specified number of digits
  if best = 10 ^ genes-number - 1 [show "DONE!!!" stop]
  ;; when  diversity between chromosomes is null, rercombination is skipped
  if best != worst [rercombination]
  ;; mutations occur according to a frequency set by the user
  if random-float 1 < mutation-rate [mutate]
  tick
end 

to rercombination
  ;; recombination occurs between the chromosome of a randomly chosen turtle (recipient) and
  ;; the chromosome of (one of) the most performing turtle (donor) that offers a code's fragment
  ;; of its chromosome to the first turtle; the two involved agents are highlighted by a link
  clear-links
  set donor [who] of one-of turtles with [fitness = best]
  set recipient [who] of one-of turtles with [fitness != best]
  ask turtle donor [create-link-to turtle recipient ]
  set counter 0
  set a-split random genes-number
  set b-split random genes-number
  set chromcopy [chromosome] of turtle donor
  ask turtle recipient [
     hybridization
     set fitness read-from-string chromosome
     set label fitness
    ]
end 

to hybridization
  ;; the two selected chromosomal strings give place to hybridization according to a mechanism similar to
  ;; the crossing-over following to bacterial conjugation; strings are looped,
  ;; as occur in bacterial chromosomes or plasmids
  ifelse a-split < b-split [set chromosome
            replace-item (a-split + counter) chromosome (item (a-split + counter) chromcopy)
            set counter (counter + 1)
            if counter < b-split - a-split [hybridization]]
       [if b-split < a-split [set chromosome
              replace-item ((a-split + counter) mod genes-number)
                  chromosome (item ((a-split + counter) mod genes-number) chromcopy)
              set counter (counter + 1)
              if counter < genes-number - a-split + b-split [hybridization]]
    ]
end 

to mutate
  ;; mutations happen randomly with a given frequency on just one digit (gene)
  ask turtle random turtles-number
       [set chromosome replace-item random genes-number chromosome word random 10 ""
        set fitness read-from-string chromosome
        set label fitness
       ]
end