Minimal Genetic Algorithm

Minimal Genetic Algorithm preview image

1 collaborator

F1 Cosimo Leuci (Author)

Tags

arithmetic 

Tagged by Cosimo Leuci 3 months ago

genetic algorithms 

Tagged by Cosimo Leuci 3 months ago

Part of project 'Starfish_Planet' Parent of 1 model: Flibs'NLogo preview imageFlibs'NLogo
Visible to everyone | Changeable by the author
Model was written in NetLogo 6.0.4 • Viewed 271 times • Downloaded 3 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 priciples of the organic evolution.This model is able to give us an answer to the simple arithmetic problem 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"; chromosomes can mutate on a single gene and can exchange fragments (sequence of genes) with the chromosome carried by other turtles: we can see the mechanism as a mixture of eukaryotic crossing-over and prokaryotic conjugation, here we will refer to it as a genetic-shuffling. The total sequence of genes in a chromosome can be read as a number and its value can be considered the turtles “phenotype”. A turtle will be as fit as the value expressed by its chromosome will be high. The best fitness can be easily matematically 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.

Only the fittest turtle can conjugate with another turle giving part of its chromosome. So the best answer is searched foundamentally in two steps: mutation and selective reproduction of (part of) the fittest chromosome by genetic-shuffling.

Mutations happen randomly with a given frequency on just one gene that is a digit place on the chromosome.

Genetic-shuffling takes place between a randomly choosen turtle (recipient) and the most performing one (donor) that offers a fragment of its chromosome to the first one; the two turtles involved in this process will be highlighted by a link. Genetic-shuffling leads to the formation of a new hybrid chromosome made up by the chromosome of the recipient turtle in which a fragmet of genes (digits) included between two randomly choosen positions are replaced by the corresponding genes (digits) of one of the donor turtles' chromosome.

## HOW TO USE IT

SETUP button creates the selected number of turtles having a chromosome constituted by a string long till 20 genes (digits), as choosen by the user. Initially, all chromosomes show the lowest suitability.

GO buttons launch a block of instructions that after the detecion of the current best and worst chromosomes, recall the genetic-shuffling and mutation routines.

Four displays show some data concerning the last processed genetic-shuffling: 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.

Step by step the less and the most suitable phenotypes (the numerical value of the chromosomal string) are monitored.

## THINGS TO NOTICE

1. During genetic-shuffling, the replaced chromosomal fragment can have random lenght, so sometimes it can have null extension or it could cover the entire chromosom but a gene (the fragment's final digit).

2. Because the strict correspondence between genotype and phenotype, this model doesn't need a routine selecting from the population an individual carrying the nearest traits to the desired ones, such a routine is usually required in a genetic algorithm.

## THINGS TO TRY

Search a possible statistical relationship between the number of cycles required to obtain the right answer to the problem and the the single parameter adjustable by sliders.

## EXTENDING THE MODEL

Minimal Genetic Algorithm is preliminary for Flibs'NLogo project, but it can be considered as self-standing and can be furtherly extended by adding new routines: e.g. it would be interesting to introduce a routine evaluating the genotypes diversity dinamic during the search.

## CREDITS, REFERENCES AND RELATED MODELS

- A nice introduction to genetic algoritm 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.

- Stonedahl, F. and Wilensky, U. (2008). NetLogo Simple Genetic Algorithm model. http://ccl.northwestern.edu/netlogo/models/SimpleGeneticAlgorithm. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

- Cosimo Leuci (2018) Flibs'NLogo http://modelingcommons.org/browse/one_model/5754

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 a possible answer to the problem
             fitness     ;; the numerical value of the chromosomal string
             ]

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 conter 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/fenotype-construction
   ]
end 

to genotype/fenotype-construction
  ;; the genotype (chromosome) and the corresponding fenotype (fitness) of the agent
  ;; is initially equal to the worst response to the problem; it is shown as label
  set fitness 10 ^ (genes-number - 1)
  ;; lowest fitness value is converted into string:
  ;; it will be the initial chromosome structure
  set chromosome word fitness ""
  ;; chromosome is displayed as 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, genetic-shuffling is skipped
  if best != worst [genetic-shuffling]
  if random-float 1 < mutation-rate [mutate]
  tick
end 

to genetic-shuffling
  ;; hybridization occur between the chromosome of a randomly choosen turtle (recipient)
  ;; and the chromosome of the most performing one (donor) that offer a fragment of its
  ;; chromosome to 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 chromosomosomal strings give place to hybridization with a mechanism inspired both
  ;; to crossing-over and bacterial conjugation: the recipient string will be hybridized with a fragment
  ;; of the donor one; strings are treated as circular, 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]]
    ]
  if length chromosome != genes-number [show "Invalid chromosome length"]
end 

to mutate
  ;; mutations happen randomly with a given frequency on just one digit place
  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
        if length chromosome != genes-number [show "Invalid chromosome length"]
    ]
end 

There are 11 versions of this model.

Uploaded by When Description Download
Cosimo Leuci 2 months ago adjustments in Download this version
Cosimo Leuci 2 months ago user interface update Download this version
Cosimo Leuci 2 months ago simplifications Download this version
Cosimo Leuci 2 months ago simplifications Download this version
Cosimo Leuci 2 months ago flux bug fixed Download this version
Cosimo Leuci 3 months ago Info tab new revision Download this version
Cosimo Leuci 3 months ago Info tab new revision Download this version
Cosimo Leuci 3 months ago Info tab new revision Download this version
Cosimo Leuci 3 months ago user interface and info tab update Download this version
Cosimo Leuci 3 months ago Info tab revised Download this version
Cosimo Leuci 3 months ago Initial upload Download this version

Attached files

File Type Description Last updated
Minimal Genetic Algorithm.png preview Preview for 'Minimal Genetic Algorithm' 3 months ago, by Cosimo Leuci Download

This model does not have any ancestors.

Children:

Graph of models related to 'Minimal Genetic Algorithm'