Minimal Genetic Algorithm

Minimal Genetic Algorithm preview image

1 collaborator

Cosimo.leuci Cosimo Leuci (Author)

Tags

arithmetic 

Tagged by Cosimo Leuci almost 7 years ago

genetic algorithms 

Tagged by Cosimo Leuci almost 7 years ago

Part of project 'Starfish_Planet' Parent of 2 models: Flibs'NLogo preview imageFlibs'NLogo and HyperMu’NmGA preview imageHyperMu’NmGA
Visible to everyone | Changeable by the author
Model was written in NetLogo 6.1.1 • Viewed 1597 times • Downloaded 285 times • Run 0 times
Download the 'Minimal 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?

Genetic algorithms try to solve a computational problem following some principles of organic evolution. This model has educational purposes; it is able to give us an answer to the simple arithmetic problem on how to find the highest number composed by a given number of digits. We approach the task using a genetic algorithm, where the possible answers to the problem are represented by agents that in logo programming environment are usually named "turtles".

HOW IT WORKS

Every turtle owns a “chromosome” made up by a string of digits each one representing a "gene"; genes can mutate into an allele (point-mutation) and chromosomes can exchange fragments with the chromosome carried by other turtles (recombination). The total sequence of genes in a chromosome can be read as a number and its value will be the turtles “phenotype” as well as a candidate solution to the problem. A turtle will be as fit as the value expressed by its chromosome will be high. The best theoretical fitness can be easily mathematically established as the nearest to the result of a simple formula. If n is the number of digits in a string, the higher number having n digits is: (10 ^ n) - 1, that is a sequence of n 9s; on the contrary, 10 ^ (n - 1) will give the lower number composed by n digits; in other words, the two formulas give us the extremes of search space. So the algorithm searches the best answer fundamentally in two steps: mutation and selective reproduction of part of the fittest chromosome by recombination. Mutations happen randomly with a given frequency on just one gene. Recombination takes place between a randomly chosen turtle (recipient) and (one of) the most performing turtles (donor) that gives away the code of a randomly chosen chromosomal fragment to the first one; the fragment code will replace the homologous sequence of the recipient turtle; both turtles involved in this process will be highlighted by a link.

HOW TO USE IT

SETUP button creates a number of turtles having a chromosome constituted by a string long till 20 genes (digits), as chosen by the user. Initially, all chromosomes show the lowest suitability. SEARCH buttons launch a block of instructions that after the detection of the current best and worst chromosomes, recall the rercombination and mutation operators. Four displays show some data concerning the last processed rercombination: the starting point (a-split) and the ending point (b-split) of the donor's fragment insertion (the first extreme is included into the fragment but not the second one) and the number of genes replaced; the resulting hybridized chromosome is reported, as well. Generation after generation the less and the most suitable phenotypes (the numerical value of the chromosomal string) are monitored.

THINGS TO NOTICE

  1. During recombination, the replaced chromosomal fragment can have random length, so sometimes it can have a null extension or it could cover the entire chromosome but a gene (the fragment's final digit).
  2. Because of the strict correspondence between genotype and phenotype, this model doesn't require the computation of a fitness function: such value is enbedded in the same chromosome.
  3. In sciences, mathematical language is largely used to describe natural systems and to compute their future evolution. In this case, the language of natural sciences is utilized to compute the solution of an arithmetic problem.

THINGS TO TRY

Search a possible statistical relationship between the number of cycles required to obtain the right answer to the problem and the single parameters adjustable by sliders. Particularly interesting could be the relationship between mutation rate and the average of cycles' number required to reach the right answer to the problem.

EXTENDING THE MODEL

Another approach requires a code variation, to test if it is more determinant the influence of the random mutations or the selective recombination or a balanced ratio between the two factors to obtain efficiently the final goal.

NETLOGO FEATURES

In this model, chromosomes have two features: as a string and as a number. To switch them each other, two NetLogo commands are very useful: "read-from-string" interprets the given chromosome and reports the resulting numerical value; on the contrary "word" command allows to revert a number into a string (because it requires two inputs, the second one could be double quotation marks: "") A third command is useful in mutation and recombination operators: "replace-item" allows an easy single gene variation as well as a substitution with a chromosome fragment from a donor turtle into the corresponding loci of a recipient turtle.

RELATED MODELS

CREDITS AND REFERENCES

A nice introduction to genetic algorithms could be the chapter nine of the book "Complexity - A guided tour" by Melanie Mitchel (2009 - Oxford University Press) where the GA "Robby the Robot" is described; see also Mitchell, M., Tisue, S. and Wilensky, U. (2012). NetLogo Robby the Robot model http://ccl.northwestern.edu/netlogo/models/RobbytheRobot. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

Copyright 2018 Cosimo Leuci.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Comments and Questions

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

Click to Run Model

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 

There are 22 versions of this model.

Uploaded by When Description Download
Cosimo Leuci over 5 years ago Reverted to older version Download this version
Cosimo Leuci over 5 years ago Rev. 1.1.1 Download this version
Cosimo Leuci over 5 years ago Reverted to older version Download this version
Cosimo Leuci over 5 years ago Reverted to older version Download this version
Cosimo Leuci over 5 years ago Reverted to older version Download this version
Cosimo Leuci over 5 years ago Rev. 1.1.1 Download this version
Cosimo Leuci over 5 years ago Reverted to older version Download this version
Cosimo Leuci over 5 years ago Reverted to older version Download this version
Cosimo Leuci over 5 years ago Rev. 0.3 Download this version
Cosimo Leuci over 5 years ago Rev. 1.1.0 Download this version
Cosimo Leuci over 5 years ago Rev. 1.0.0 Download this version
Cosimo Leuci almost 7 years ago adjustments in Download this version
Cosimo Leuci almost 7 years ago user interface update Download this version
Cosimo Leuci almost 7 years ago simplifications Download this version
Cosimo Leuci almost 7 years ago simplifications Download this version
Cosimo Leuci almost 7 years ago flux bug fixed Download this version
Cosimo Leuci almost 7 years ago Info tab new revision Download this version
Cosimo Leuci almost 7 years ago Info tab new revision Download this version
Cosimo Leuci almost 7 years ago Info tab new revision Download this version
Cosimo Leuci almost 7 years ago user interface and info tab update Download this version
Cosimo Leuci almost 7 years ago Info tab revised Download this version
Cosimo Leuci almost 7 years ago Initial upload Download this version

Attached files

File Type Description Last updated
Minimal Genetic Algorithm.png preview Preview for 'Minimal Genetic Algorithm' almost 7 years ago, by Cosimo Leuci Download
READ_ME.txt data attachment almost 2 years ago, by Cosimo Leuci Download

This model does not have any ancestors.

Children:

Graph of models related to 'Minimal Genetic Algorithm'