Flibs'NLogo

Flibs'NLogo preview image

1 collaborator

F1 Cosimo Leuci (Author)

Tags

adaptive cognition 

Tagged by Cosimo Leuci about 1 month ago

artificial life 

Tagged by Cosimo Leuci 3 months ago

finite automata 

Tagged by Cosimo Leuci 3 months ago

flibs 

Tagged by Cosimo Leuci about 1 month ago

genetic algorithms 

Tagged by Cosimo Leuci 3 months ago

Part of project 'Starfish_Planet' Child of model Minimal Genetic Algorithm preview imageMinimal Genetic Algorithm
Visible to everyone | Changeable by the author
Model was written in NetLogo 6.0.4 • Viewed 274 times • Downloaded 2 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.)


## WHAT IS IT?

Flibs'NLogo reproduces in NetLogo programming language and its integrated modeling environment, a genetic algorithm whose purpouse is evolving a perfect predictor from a pool of digital creatures constituted by finite automata 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" (1) and recollected in the book "The Armchair Universe"

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" (2)

## HOW IT WORKS

External signals follow ciclically 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 resposes 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 filament.

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 by 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: crossover 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); crossover in this case is substituted by a more generic genetic shuffling: it occurs through a kind of unidirectional genes exchange when a chromosomic fragment included between two loci randomly choosen on one of the most performing flibs, replaces the corresponding alleles 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 builted on the basis of states number detrmined 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 performaces. 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 choosen and finally it operates the mutation of one random flib's gene. After that, the cycle starts again and a new generation begin.

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 genetic shuffling different from a true crossing-over: indeed just the receiving chromosome (not always less performing) varies its genetic kit; on the contrary the best flib donates part of its chomosome to the second one, so that no flib is removed from the soup, but one of them changes its structure by hybridization. The mechanism was already used in the model "Minimal Genetic Agorithm".

## THINGS TO TRY

Explore the relationship between the lenght 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 exausted). 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 (1)

The success of genetic algorithms often depends greatly on some details as the size of the population and the probabilities of genetic shuffling and mutation. 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 environment challenges are availeble, or in small population where genetic drift can offer an unexepted chance to adaptation? In flibs' primordial sea, are more influencial mutations or genetic shuffling in evolution; in othr words: are flibs "hopeful monsters" or gradualist species?

## EXTENDING THE MODEL

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 relatioship 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". The model could be extended from a conceptual point of view: some scholars think to 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.

## NETLOGO FEATURES

Flibs' chomosomes have the double feature as strings and as ordered numeric digits 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

Cosimo Leuci (2018) Minimal Genetic Algorithm http://modelingcommons.org/browse/one_model/5742

## CREDITS AND REFERENCES

1. 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://www.jstor.org/stable/24967834?seq=1#page_scan_tab_contents

2. 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: http://archive.computerhistory.org/projects/chess/related_materials/text/3-2%20and%203-3%20and%205-2.Computer_recreations.Dewdney-AK.Scientific_American.Feb-1986/Computer_recreations.Dewdney-AK.Scientific_American.Feb-1986.062303022.sm.pdf

3. A. K. Dewdney “The Armchair Universe: An Exploration of Computer Worlds" 1988 W. H. Freeman & Co. New York

4. 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

5. Wikipedia contributors "Deterministic finite automaton". Wikipedia, The Free Encyclopedia. (November 22, 2018, 12:41 UTC). Available at: https://en.wikipedia.org/w/index.php?title=Deterministic_finite_automaton&oldid=870108161

6. 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: http://bit-player.org/wp-content/extras/bph-publications/SciAm-1983-12-Hayes-FSA.pdf

7. Karl Popper "All life is problem solving" 1999 Routledge, New York. Available at: http://www.blc.arizona.edu/courses/schaffer/249/Darwin%20and%20Philosophers/Popper%20-%20The%20Logic%20and%20Evolution%20of%20Scientific%20Theory.pdf

## COPYRIGHT AND LICENSE

Copyright 2018 Cosimo Leuci.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.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

breed   [flibs flib]     ;; FLiBs (finite livig blobs) are the agents of the model: they are structured
                         ;; as finite automata. 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 reiceved,
                         ;; the automaton changes state and emits a second signal" (1). 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 conter useful in different blocks
         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           ;; a performing flib sharing part of its genes
         recipient       ;; a flib acquiring genes from a donor
         a-split         ;; a first cut in the flib's chromosome
         b-split         ;; a second cut in the flib's chromosome
         wild            ;; 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 state word 0 ""
    set label fitness
    chromosome-genesis
    fd 2 + random 7]
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
  ;; checking chromosome dimension
  ask flibs [if length chromosome != num-states * 4
    [show "error: invalid chromosome lenght" stop]]

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

  ;; a new generation begins
  tick
  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 consequence of mating processes) and mutagenesis

  ;; every generation one chromosomic genetic shuffling occurs by default, this frequency can be
  ;; lowered by slider "mate-rate"
  ifelse random-float 1 < mate-rate [mate]
    [output-print "no mating event"]

  ;; in every generation one mutagenesis process occurs  by default, this frequency can be
  ;; lowered by MUTATION-RATE slider
  ifelse random-float 1 < mutation-rate
    [set wild [who] of one-of flibs ask flib wild [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 (see to previous generation) ---"
  output-print ""
end 



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

to chrom-test
  ;; an environmental input symbol is read from the given sequence
  set new-input 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 item (4 * read-from-string state + 2 * read-from-string new-input) chromosome =
        item ((counter + 1) mod (length environmental-cycle)) environmental-cycle
            [set fitness (fitness + 1)]
  ;; new flibs state is computed
  set state item (4 * read-from-string state + 2 * read-from-string new-input + 1) chromosome
  ;; test is iterated 100 times
  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 is 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: GENETIC SHUFFLING
;; --------------------------------------------------------------------------------------------------------------

to mate
  clear-links
  select-flibs   ;; selection of the mating flibs
  ask flib donor [create-link-to flib recipient]
  ;; just a flibs' chromosome undergoes to genetic-shuffling
  ask flib recipient [genetic-shuffling]
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 selection
  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 genetic-shuffling
  ;; a genes sequence included between a-split and b-split restriction sites is randomly choosen
  set a-split random (num-states * 4)
  set b-split random (num-states * 4)
  set counter 0
  hybridization
  ;; generating 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 chromsome positions on a random
 ;; flib is replaced by the corresponding sequence on one of the most performing flibs;
 ;; chromosomes are treated as circular
 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]]
  if length chromosome != num-states * 4 [show "Invalid chromosome length"]
end 


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

to mutate
  ;; managing mutation and generating report
  ifelse wild > 9  [output-type word "id: " wild]  [output-type word "id: 0" wild]
  output-type word " wild chromosome:       " [chromosome] of flib wild
  output-print word "     fitness: " [fitness] of flib wild
  ;; 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 > 9  [output-type word "id: " wild] [output-type word "id: 0" wild]
  output-print word " mutated chromosome:    " [chromosome] of flib wild
end 

There are 6 versions of this model.

Uploaded by When Description Download
Cosimo Leuci about 1 month ago Rev. 0.9.8 Download this version
Cosimo Leuci 2 months ago Rev. 0.9.7 Download this version
Cosimo Leuci 3 months ago Rev. 0.9.5 Download this version
Cosimo Leuci 3 months ago Rev. 0.9.4 Download this version
Cosimo Leuci 3 months ago Rev. 0.9 Download this version
Cosimo Leuci 3 months ago Initial upload Download this version

Attached files

File Type Description Last updated
f'nl_100.jpg jpeg screenshot 3 months ago, by Cosimo Leuci Download
f'nl_100_15.jpg jpeg screenshot 3 months ago, by Cosimo Leuci Download
Flibs'NLogo.png preview Preview for "Flibs'NLogo" 3 months ago, by Cosimo Leuci Download

Parent: Minimal Genetic Algorithm

This model does not have any descendants.

Graph of models related to 'Flibs'NLogo'