Flibs'NLogo
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
- 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
- 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
- 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
- A. K. Dewdney “The Armchair Universe: An Exploration of Computer Worlds" 1988 W. H. Freeman & Co. New York
- 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
- 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
;; ---------- 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.
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 |