# Minimal Genetic Algorithm

### 1 collaborator

Cosimo Leuci (Author)

### Tags

arithmetic

Tagged by Cosimo Leuci 18 days ago

genetic algorithms

Tagged by Cosimo Leuci about 1 month ago

Part of project 'Starfish_Planet' Parent of 1 model: Flibs'NLogo
Visible to everyone | Changeable by the author
Model was written in NetLogo 6.0.4 • Viewed 234 times • Downloaded 2 times • Run 0 times

## 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

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
set donor [who] of one-of turtles with [fitness = best]
set recipient [who] of one-of turtles with [fitness != best]
set counter 0
set a-split random genes-number
set b-split random genes-number
set chromcopy [chromosome] of turtle donor
hybridization
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
[set chromosome replace-item random genes-number chromosome word random 10 ""
set label fitness
if length chromosome != genes-number [show "Invalid chromosome length"]
]
end
```

There are 11 versions of this model.

Cosimo Leuci 19 days ago Info tab new revision Download this version
Cosimo Leuci 22 days ago Info tab new revision Download this version
Cosimo Leuci 28 days ago Info tab new revision Download this version