Flibs'NLogo

Flibs'NLogo preview image

1 collaborator

Cosimo.leuci Cosimo Leuci (Author)

Tags

adaptive cognition 

Tagged by Cosimo Leuci almost 7 years ago

artificial life 

Tagged by Cosimo Leuci almost 7 years ago

finite automata 

Tagged by Cosimo Leuci almost 7 years ago

genetic algorithms 

Tagged by Cosimo Leuci almost 7 years ago

structural-coupling 

Tagged by Cosimo Leuci over 6 years ago

Part of project 'Starfish_Planet' Child of model Minimal Genetic Algorithm preview imageMinimal Genetic Algorithm Parent of 1 model: Flibs'NFarol preview imageFlibs'NFarol
Visible to everyone | Changeable by the author
Model was written in NetLogo 6.1.1 • Viewed 1256 times • Downloaded 151 times • Run 0 times
Download the 'Flibs'NLogo' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


Flibs'Nlogo - An Elementary Form of Evolutionary Cognition

WHAT IS IT?

Flibs'NLogo implements in NetLogo integrated modeling environment, a genetic algorithm whose purpose is evolving a perfect predictor from a pool of digital creatures constituted by finite automata (1) or flibs (finite living blobs) that are the agents of the model. The project is based on the rules described by Alexander K. Dewdney in "Exploring the field of genetic algorithms in a primordial computer sea full of flibs" from the vintage Scientific American column "Computer Recreations" (2, 3) and recollected in the book "The Armchair Universe" (4) As the same author summarized: "Flibs [...] attempt to predict changes in their environment. In the primordial computer soup, during each generation, the best predictor crosses chromosomes with a randomly selected flib. Increasingly accurate predictors evolve until a perfect one emerges. A flib [...] has a finite number of states, and for each signal it receives (a 0 or a 1) it sends a signal and enters a new state. The signal sent by a flib during each cycle of operation is its prediction of the next signal to be received from the environment" (3)

HOW IT WORKS

External signals follow cyclically a pattern of binary digits that can be inserted by the user. Even if they could be represented more properly for a human mind by a table or a graph, the repertoires of responses to environmental signals and the state-transitions of flibs are codified linearly in the chromosomal string as well as the genetic information is codified in DNA strand. The topology of flib's chromosome should be considered circular, a gene is a symbol in the chromosome and an allele is a gene at a particular locus. Flibs live in a kind of primordial soup where time flows discretely. A time unit (tick) represents a generation; each generation is made up of 100 cycles. At every cycle, flibs receive an incoming signal and in dependence of its state compute an outcoming binary signal, entering into a new state, according to the transition table codified by its chromosome. The performances of a flib will be mesured on the basis of the accordance between the outcoming signal and the next incoming environmental signal: this is the fitness operator. In addition to the fitness operator, a genetic algorithm involves at least two other types of operators: recombination and mutation. Mutation occurs at a given frequency when an allele is changed at random (think of a gene being struck by a cosmic ray); recombination occurs through a kind of unidirectional genes exchange when a chromosomic code's fragment included between two randomly chosen loci taken from one of the most performing flibs, replaces the homologous genes of another flib.

HOW TO USE IT

The SETUP button initializes the model creating a number of flibs determined by the NUM-FLIBS slider; each flib will be provided with a chromosome representing a casual transition table built on the basis of states number determined by the NUM-STATES slider. The SEARCH buttons start the genetic algorithm evaluating first the flibs' fitness and identifying the flibs with relative best and worst performances. If no flib reaches the absolute perfect forestalling performance, the algorithm executes the genetic shuffling between a flib's chromosome with current best fitness and another one randomly chosen and finally it operates the mutation of one random flib's gene. After that, the cycle starts again and a new generation begins. The model window shows flibs as emoticons labelled with their respective fitness value, a link highlights the mating flibs. There are two plots: the first shows a histogram representing the flibs' fitness distribution; the second one is a three-line graph showing generation after generation, the variation in the best, worst and average flibs' performances. In the bottom, an output window reports details about the last genetic variations.

THINGS TO NOTICE

In spite of the model described by Dewdney, Flibs'NLogo exhibits a different kind of homologous recombination, similar to bacterial recombination following conjunction events, more than eucaryotic meiotic crossing-over: indeed just the receiving chromosome (not always less performing) varies its genetic kit; on the contrary, the selected best flib replicate part of its chromosome (donor chromosome) in the corresponding loci of the second one (recipient chromosome) so that no flib is removed from the soup, but one of them changes (part of) its structure by hybridization; the two split points are chosen randomly. The mechanism was already used in the model "Minimal Genetic Algorithm".

THINGS TO TRY

Explore the relationship between the length of environmental signals pattern and the flibs' number of states to get the best predictor flib within a given number of generation (or before your patience is exhausted). Obviously, there is a limit to the highest theoretical fitness (the adaptability that in this case means forestalling ability) in a given environmental signals pattern: this theme is discussed by Dewdney (2) The success of genetic algorithms often depends greatly on some details as the size of the population and the probabilities of recombination and mutation (5). Test the influence of these parameters acting on the sliders NUM-FLIBS, MATE-RATE, and MUTATION-RATE. Is adaptation easier in large populations where a great number of candidate answers to environmental challenges are available, or in a small population where genetic drift can offer an unexpected chance to adaptation? In flibs' primordial sea, are more influential mutations or genetic shuffling in evolution; in other words: are flibs "hopeful monsters" or gradualist species?

EXTENDING THE MODEL

How does the length of the environmental cycle, the sates number, the mutation-rate or the mate-rate affect the amount of time it takes for a perfect predictor to evolve? The genetic variability of flibs population has an influence over the probability to obtain a perfect predictor. An operator exploring this feature could enlighten the relationship between biodiversity and adaptability. Dewdney notices: "the concept of a flib is so flexible that input and output can represent a great variety of specific biological phenomena. For example, an input signal could represent a chemical or temperature gradient. The corresponding output symbol could be a command to an effector that controls cilia, or a spore forming mechanism" (2). The model could be extended from a conceptual point of view: some scholars think of biological adaptation as a cognitive process or vice versa, in this case, individual and collective flibs' activity could be regarded as a mental process, as well (6).

NETLOGO FEATURES

Flibs' chromosomes have the double feature as strings and as ordered numerical data collection. 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 genetic shuffling 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. Besides, "mod" function helps to treat strings (e.g. chromosomes and environmental signals pattern) as circular structures.

RELATED MODELS

Leuci, Cosimo (2020, January 30). “MGA - Minimal Genetic Algorithm” (Version 1.1.0). CoMSES Computational Model Library. Retrieved from: https://doi.org/10.25937/db7w-zt41

CREDITS AND REFERENCES

  1. Brian Hayes "On the finite-state machine, a minimal model of mousetraps, ribosomes and the human soul" Scientific American, Vol. 249, No. 6 (December 1983), pages 19-28. Available at: https://tinyurl.com/ycukjtor
  2. A. K. Dewdney “Exploring the field of genetic algorithms in a primordial computer see full of flibs” Scientific American Vol. 253, No. 5 (November 1985), pages 21-33. Partially available at: https://tinyurl.com/y84bnear
  3. A. K. Dewdney "The king (a chess program) is dead, long live the king (a chess machine)" Scientific American Vol. 254, No. 2 (February 1986), page 21. Available at: https://tinyurl.com/ycphyqqm
  4. A. K. Dewdney “The Armchair Universe: An Exploration of Computer Worlds" 1988 W. H. Freeman & Co. New York
  5. Melanie Mitchell "An introduction to genetic algorithms" 1999 MIT Press Ltd, Cambridge, Massachusetts. Available at: http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf
  6. Karl Popper "All life is problem solving" 1999 Routledge, New York. Available at: https://tinyurl.com/yc5s2y3e

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

;;  ----------   FLIBS'NLOGO   ----------------------------------------------------------------------------------
;;  -------------------------------------------------------------------------------------------------------------



breed   [flibs flib]     ;; FLiBs (finite living blobs) are the agents of the model: they are structured as
                         ;; finite automata (1, 2). They have "a finite number of states; an input signal
                         ;; causes it to change automatically from one state to another.
                         ;; The kind of automaton used in a flib also generates signals. Incoming and outgoing
                         ;; signals are represented within the automaton by symbols. When a signal is received,
                         ;; the automaton changes its state and emits a second signal" (2). A flib is considered
                         ;; perfect predictor i.e. very well adapted when its outgoing signals (previsions)
                         ;; is equal to the next incoming environmental signal. Signals are always binary digits.


flibs-own [chromosome    ;; every flib owns a chromosome that is a string coding its state transition table;
           state         ;; the current state of the flib
           fitness]      ;; a measure of its forestalling ability


globals [counter         ;; a counter useful in different procedures
         new-input       ;; the incoming environmental signal
         average         ;; mean of flibs population performances
         best            ;; the best flibs performance value
         worst           ;; the worst flibs performance value
         donor           ;; one very performing flib sharing part of its genes
         recipient       ;; one flib acquiring genes from a donor
         a-split         ;; a first cut in the recipient's chromosome
         b-split         ;; a second cut in the recipient's chromosome
         wild-type       ;; a natural state chromosome
         optimal]        ;; the flib's chromosome showing a perfect prevision ability



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

to setup                 ;; initializing the model
  clear-all
  reset-ticks
  set counter 0
  create-flibs num-flibs [
    set shape "face happy"
    set size 1.8
    set chromosome ""
    set label fitness
    fd 2 + random 7]
  ask flibs [chromosome-genesis]
end 

to chromosome-genesis   ;; chromosomes are strings randomly built through an iterative procedure: even string's
                        ;; positions are 0 or 1: they represent a possible outgoing signal; odd string's
                        ;; positions represent possible flib's states determined by NUM-STATES slider
  set chromosome word chromosome (word (random 2) (random num-states))
  set counter counter + 1
  ifelse counter < num-states * 2 [chromosome-genesis]
    [set counter 0]
end 



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

to search
  ;; testing flibs' prevision ability along 100 cycles and results are analyzed
  set counter 0
  ask flibs [set fitness 0 set state 0]
  ask flibs [chrom-test]
  performances-analysis

  ;; a new generation begins
  tick
  ask flibs [move]
  output-print ""
  output-print word "tick: " ticks

  ;; if flibs population harbours a perfect predictor, the goal of the genetic algorithm is reached
  if best = 100 [final-message stop]

  ;; if flibs population doesn't harbour any perfect predictor, genetic algorithm activates two operators:
  ;; genetic shuffling (as a consequence of mating processes) and mutagenesis

  ;; every generation one recombination event occurs by default, this frequency can be
  ;; lowered by the slider "MATE-RATE"
  ifelse random-float 1 < mate-rate [conjugation]
    [output-print "no mating event"]

  ;; every generation, one mutagenesis process occurs  by default, this frequency can be
  ;; lowered by the slider MUTATION-RATE
  ifelse random-float 1 < mutation-rate
    [set wild-type [who] of one-of flibs ask flib wild-type [mutate]]
    [output-print "no mutation event"]
end 

to final-message
  output-print "        EUREKA!!!"
  set optimal [who] of one-of flibs with [fitness = 100]
  ifelse best > 9  [output-type word "id: " optimal] [output-type word "id: 0" optimal]
  output-type word " optimal predictor:         " [chromosome] of flib optimal
  output-print word "     fitness: " [fitness] of flib optimal
  output-print ""
  output-print "--- no genetic variation (look at the previous generation) ---"
  output-print ""
end 

to-report  patches-ahead [ rad dis ] ; reports to turtles a set of patches ahead
  report [ patches in-radius rad ] of patch-ahead dis
end 

to move
   ifelse (any? other turtles-on patches-ahead 1 1)
    [ bk 0.1 lt random-float 360]
    [fd 0.01]
end 


;; Operator 1: FITNESS EVALUATION
;; --------------------------------------------------------------------------------------------------------------

to chrom-test
  ;; an environmental input symbol is read from the given sequence
  set new-input read-from-string item (counter mod (length environmental-cycle)) environmental-cycle
  ;; only 0 or 1 symbols are accepted
  if new-input != 0 and new-input != 1 [
    show "error: invalid environmental value"
    stop]
  ;; each flibs prevision ability is tested and fitness is updated
  if read-from-string  item (4 * state + 2 * new-input) chromosome =
        read-from-string item ((counter + 1) mod (length environmental-cycle)) environmental-cycle
            [set fitness (fitness + 1)]
  ;; new flibs state is computed
  set state read-from-string item (4 * state + 2 * new-input + 1) chromosome
  set counter counter + 1
  ;; the cycle is repeated 100 times
  if counter < 100 [chrom-test]
  set counter 0
end 

to performances-analysis
  ask flibs [
  set average mean [fitness] of flibs
  set best max [fitness] of flibs
  set worst min [fitness] of flibs
  set label fitness
  ;; flibs performances are visually represented through emoticons language
  ifelse fitness < 55
    [set shape "face sad"] [ifelse fitness < 85
    [set shape "face neutral"]
    [set shape "face happy"]]
  ]
end 


;; Operator 2: RECOMBINATION
;; --------------------------------------------------------------------------------------------------------------

to conjugation
  clear-links
  ;; the conjugation process requires two flibs' chromosomes: the donor and the recipient
  ;; just the second one undergoes to recombination
  select-flibs
  ;; a link highlighted the two mating flibs
  ask flib donor [create-link-to flib recipient]
  ask flib recipient [recombination]
end 

to select-flibs
  set donor [who] of one-of flibs with [fitness = best]
  set recipient [who] of one-of flibs
  if donor = recipient [select-flibs]     ;; self conjugation is forbidden
  ;; generating report about the selection process
  ifelse donor > 9  [output-type word "id: " donor] [output-type word "id: 0" donor]
  output-type word " donor chromosome:      " [chromosome] of flib donor
  output-print word "     fitness: " [fitness] of flib donor
  ifelse recipient > 9  [output-type word "id: " recipient]  [output-type word "id: 0" recipient]
  output-type word " recipient chromosome:  " [chromosome] of flib recipient
  output-print word "     fitness: " [fitness] of flib recipient
end 

to recombination
  ;; a gene's sequence included between a-split and b-split restriction sites is randomly chosen
  set a-split random (num-states * 4)
  set b-split random (num-states * 4)
  if a-split = b-split [recombination]
  set counter 0
  hybridization
  ;; generating a report about genetic shuffling
  ifelse recipient > 9  [output-type word "id: " recipient]  [output-type word "id: 0" recipient]
  output-print word " hybridized chromosome: " chromosome
  output-type "- flanking positions of replaced fragment:  [ "
  output-type word a-split " - "
  output-print word b-split " [ "
end 

to hybridization
 ;; the genes' sequence included between a-split and b-split restriction sites on a random
 ;; flib is replaced by the homologous sequence of one of the most performing flibs;
 ;; chromosomes are treated as circle-shaped
 if a-split < b-split [
    set chromosome replace-item (a-split + counter)
    chromosome (item (a-split + counter) [chromosome] of flib donor)
    set counter (counter + 1) if counter < b-split - a-split
    [hybridization]]
 if a-split > b-split [
    set chromosome replace-item ((a-split + counter) mod (num-states * 4))
    chromosome (item ((a-split + counter) mod (num-states * 4)) [chromosome] of flib donor)
    set counter (counter + 1) if counter < (num-states * 4) - (a-split - b-split)
    [hybridization]]
  set counter 0
end 


;; Operator 3: MUTAGENESIS
;; --------------------------------------------------------------------------------------------------------------

to mutate
  ;; managing mutation and generating a report
  ifelse wild-type > 9  [output-type word "id: " wild-type]  [output-type word "id: 0" wild-type]
  output-type word " wild-type chromosome:  " [chromosome] of flib wild-type
  output-print word "     fitness: " [fitness] of flib wild-type
  ;; mutations occur randomly at a given frequency on just one locus
  let dice random length chromosome
  let muton read-from-string item dice chromosome
  ifelse dice mod 2 = 0
    [set chromosome replace-item dice chromosome word ((muton + 1) mod 2) ""]
    [set chromosome replace-item dice chromosome word ((muton + 1) mod num-states) ""]
  ifelse wild-type > 9  [output-type word "id: " wild-type] [output-type word "id: 0" wild-type]
  output-print word " mutant chromosome:     " [chromosome] of flib wild-type
end 

There are 8 versions of this model.

Uploaded by When Description Download
Cosimo Leuci over 5 years ago Rev. 1.0.1 Download this version
Cosimo Leuci over 5 years ago Rev. 1.0.0 Download this version
Cosimo Leuci almost 7 years ago Rev. 0.9.8 Download this version
Cosimo Leuci almost 7 years ago Rev. 0.9.7 Download this version
Cosimo Leuci almost 7 years ago Rev. 0.9.5 Download this version
Cosimo Leuci almost 7 years ago Rev. 0.9.4 Download this version
Cosimo Leuci almost 7 years ago Rev. 0.9 Download this version
Cosimo Leuci almost 7 years ago Initial upload Download this version

Attached files

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