|
|
Artificial life: Evolution
You can freely download the Genimal program. Before you do, first read the copyright statement.
Genimal is an 'a-life' program. 'A-life' stands for artificial life: a phenomenon in a computer program that simulates certain aspects of real, biological life. Besides Genimal, Roorda wrote other a-life programs:
Fox Rabbit Field Model and Fox Rabbit Math Model.
Where Fox Rabbit simulates emergent group behavior and the rise and fall of populations of predator and prey species, Genimal simulates evolution through genetic algorithms, mutations and survival of the fittest.
With surprising results.
The present page will tell you everything about Genimal.
The basic idea
Life is all about evolution. And evolution is all about coincidence, genes, mutations and survival of the fittest. The Genimal program does exactly that.
When you start Genimal, you will immediately see a little animal. Or rather a genimal, as the tiny creatures of the program are called. Genimals may for instance look like this:
Compared to real life, these genimals are very simple creatures. First, they are only two-dimensional. Next, they consist of just four kinds of body parts: heads, trunks, legs and eyes. Genimals may differ hugely, but the parts they are made of are always the same - no evolution there. Not only are the genimals themselves simple creatures, their environment is, too: it consists only of an endless savanna with the occasional tree. No other genimals can be seen, as at each moment just one genimal is alive - it is a simple world, indeed. All in all, the genimal world looks like this:
The life of a genimal is all about trees. Trees provide food: already in the area surrounding a tree there is food to be found (perhaps fruits or leafs fallen down from the tree), but the ideal food is the tree itself. Genimals do only one thing: move through the landscape, looking for food. For this task they possess eyes, with an opening angle of 180 degrees. For moving around they have legs. If such a leg touches the ground, pushing the genimal, you can recognize this, as the lower part shows a tiny circle-shaped ‘foot’, as the illustration shows.
Trees can only be eaten once. When the genimal is born, there are ten trees, scattered across the landscape. No new trees will grow during the lifetime of the genimal, so that’s all it will ever have. The task for the genimal is to travel across the savanna, moving from tree to tree, to find as much food as it can.
Procreation
Actually, there is a second thing a genimal does: procreate. This happens at the very moment a genimal dies. They do die, and this is what happens when they run out of lifetime. Each genimal receives as its birth gift an amount of time: 1,000 units, to be precise. (Seconds, minutes, days, years - make your own choice.) Right from the moment of their birth, they start to die, just as - let’s face it - humans do. The clock of their lifetime counts down, and when it hits 0, the genimal dies. However, as long as they are alive, they can acquire extra time: 600 units for every tree they find. But even then, their life is finite. And when they die, they produce a child. The child is nearly identical to its parent. Nearly, but not perfectly, as you will see, which is essential, because that is where evolution comes in.
Anyway, the newborn child is placed in the exact position where its parent was, some time ago, and it starts to hunt for trees just as its predecessor. Will it perform better than its parent? That is the question that drives the whole program.
Survival of the fittest
While a genimal is moving around, it has a score. This is a number that is calculated from three data:
- the number of trees it has eaten (every such tree contributes hugely to the score),
- the proximity of the remaining trees (the nearer, the higher the score), and
- the remaining time of its life (the more time is left, the higher the score).
During the lifetime of the genimal, its score will increase and decrease, perhaps many times. The highest score it reaches in the course of its lifetime is a measure for its rate of success.
When the genimal dies, its rate of success is known. Next, its child lives its life, realizing its own rate of success. When the child dies in its turn, the success rates of parent and child are compared. If the child is at least as successful as its parent, it will procreate, just as its parent did before. But if it has less success than its parent - having reached a lower top score during its lifetime - it is considered to be a failure, and it loses its right to procreate. Instead, its parent will produce a new child, which in its turn starts the struggle for life - for the right to procreate, that is.
This is what survival of the fittest means in the Genimal program: the fittest, i.e. the one with the highest top score, gets the right to have a child.
As a consequence, a long family tree is created, a genealogical sequence of thousands or even millions of generations, in which every child differs slightly - perhaps not even visibly - from its parent.
Mutations
So why are child genimals slightly different from their parents? Because of mutations - tiny errors in the procreation process.
The genimal is completely defined through a set of genes. Completely - that is: its body shape as well as its behavior. Individual genimals don’t learn: their behavior remains the same throughout their lifetimes. (A genealogical tree does learn: through evolution, i.e. from generation to generation.) To formulate it formally: the genimal’s phenotype (i.e. what you see: the body structure and the behaviour) is defined fully by its genotype (i.e. its set of genes).
The genes each exist of a series of small numbers, bits: ones or zeros. When a genimal dies and procreates, it hands over its genes to its offspring, but always with one error - one mutation. Most likely, the mutation consists of one bit changed into its alternative: a one to a zero, or v.v. Every now and then, another kind of mutation occurs: a complete gene is doubled or left out, enlarging or diminishing the total size of the set of genes.
Every mutation is based on pure coincidence. Besides, all genes of the very first genimal standing at the root of a new family tree are selected 100% at random. In other words, no-one tells the genimals how to move around the landscape. No-one teaches them anything. And yet, in the course of a genealogical tree, they learn. In many cases they develop the ability to move in a way that makes at least a little bit of sense. In some cases they even learn how to be highly efficient, running across the savanna at high speed, finding all ten trees. Only some cases: most evolutionary processes end up in failure. Experimental data indicate that in about five percent of all evolutionary processes a genimal will reach ‘total happiness’: all ten trees found. This ability may seem like a mystery - the mystery of life.
This is the essence of evolution: no master hand is instructing life how to evolve. Just coincidence, genes, mutations & survival of the fittest. Many losers, but sometimes a glorious winner.
Motion strategies
As successful genimals are all the result of chance, it is only natural that they develop a whole range of different strategies to reach the trees. Just as in real life, this results in a wide variety of ‘species’, together forming a multicolored zoo. Or rather it would do so if the Genimal program was able to show many different genimals at the same time, which it doesn’t.
The wide variety of motion strategies is reflected in the traces they leave behind, as the image below shows.
Within the Genimal program, ten different successful genimals have been stored. With some fantasy, their motion strategies resemble those of existing animals or moving objects, like a hawk, a chick or a rowing boat.
You can watch videos of these ten strategies in the next section.
Theoretical Backgrounds
The body structure is defined as a tree structure. Each body part has a ‘mother’, i.e. another body part to which is attached. The exception to this rule is the head, which is the ‘mother of all mothers’, or the root of the tree structure.
There are no genes for the head: this is always the same.
Trunks have hexagonal shapes, and thus they have six corners. As the trunk uses one of those corners to connect to its ‘mother’, the other five corners are suitable as attachment points (nodes) for other body parts. Besides, the middles of the two longer sides also act as attachment points, so a trunk has 7 attachments points in total.
Heads have the same attachment points as trunks: even at the tip of the tongue.
Legs are one-dimensional. They are attached to their ‘mother’ with one end, and the other end is the only attachment point that is available to other body parts.
Eyes don’t have any attachment points, so no body parts can have an eye as its ‘mother’.
Each gene consists of 32 bits (= 4 bytes). One gene codes for one body part, with the exception of one type of gene, the ‘repeat gene’, which encodes for a repetition of a body part or a group of body parts.
In the body of this genimal, the effects of a repeat gene are clearly visible
The encoding is as follows:
All genes:
Bits Interpretation
1,2 Gene type:
00 = repeat gene,
01 = eye gene,
10 = trunk gene,
11 = leg gene
Repeat genes:
Bits Interpretation
3 not used
4-6 value+1 = number of genes, immediately following this gene, that are to be repeated as one block (1..8). If some of those
genes are again repeat genes, they will be read as leg genes.
7-8 value+1 = number of repetitions (1 … 4)
8-32 not used
Eye, trunk & leg genes:
Bits Interpretation
3 not used
4-8 determine the 'mother part', i.e. the body part to which the current part is attached
9-11 determine the attachment point on the 'mother' part to which the current part is attached
Eye genes:
Bits Interpretation
12-16 not used
17-20 n[1], the 1st number determining the change in the attachment angles of the trunks and legs that are attached to this eye,
see below: Rotation.
21-24 n[2], the 2nd number
25-28 n[3], the 3rd number
29-32 n[4], the 4th number
Trunk and leg genes:
Bits Interpretation
12-16 determine the maximum angle to which the body part is flexed relative to the 'mother' part (the angle is expressed in radials,
calculated with: gene value* π/90)
17-23 determine the rotation phase at t=0; see below: Rotation.
Trunks: not used.
Legs: ‘clockwisepushing’: determines when the leg touches the ground and pushes the genimal:
0 = when the phase is < 0.25 or > 0.75
1 = when the phase is between 0.25 and 0.75
25-28 determine to which eye the body part is linked.
29-32 determine the ‘reaction vector’, which plays a role in each time step when the rotation of the body part is calculated. See
below: Rotation.
Decoding the genes
At the start of each evolutionary process, first the genes are interpreted. Based on this, the phenotype (i.e. the body structure and the behavior) is calculated.
Body parts that are not expressed in the phenotype
There are many reasons why a body part that is expressed in the genotype, is not realized in the phenotype. For instance:
- The 'mother' part is the part itself (a 'floating', non-attached part)
- The 'mother' part itself does not exist, either in the genotype or the phenotype
- The ‘mother’ is an eye
- The body part tries to link to an attachment point that does not exist (e.g. the 2nd or 5th attachment point of a leg)
- The part tries to attach to an attachment point that is already occupied by another part
Lethality
There are several reasons why a chromosome structure does not encode for a genimal that is able to live. This is e.g. the case if:
- the body structure is defined as a closed ring. An example of this is when part A has part B as its ‘mother’, part B has part C
as its ‘mother’, and part C has part A as its ‘mother’.
- the genimal has no eyes at all, and so is unable to find any food.
- the genimal has no legs, and so is unable to move to other locations.
(The lack of) Symmetry
In the above description of the gene code, the word ‘symmetry’ does not appear. Indeed, symmetry is not encoded in the genes. This can be recognized in the phenotype, as genimals are hardly ever symmetric. If they are, this is pure coincidence.
In real life, many living entities show symmetry, usually mirror symmetry or rotational symmetry. Perhaps, in possible future versions of the Genimal program attempts will be made to encode for symmetry, possibly combined with the code for the repeat gene: repetitions of (groups of) body parts may be encoded to be mirror images of each other, either in their shape, or in their motion pattern, or both.
About randomness
Randomness plays an important role in the Genimal program, as evolution is supposed to proceed thanks to random mutations.
For this purpose, the program makes use of the randseed function of the programming language that was used for the Genimal Program. When this function is applied, it returns a random number between -2147483648 (-231) and 2147483647 (231-1).
Actually, this determination process is not really random, as the computer is not really capable of choosing random numbers. A repeated use of the randseed function will deliver a sequence of seemingly random numbers. But when such sequences are produced several times, each with the same starting value of randseed, the sequences will always be identical.
This fact is applied usefully in the Genimal program: if the ‘start number’, i.e. the value of randseed at the start of a fresh evolutionary process (i.e. generation = 0, t = 0) that is used to randomly create a genimal is stored, it can be used to exactly reproduce the entire process.
The start number of the evolutionary process is shown in the box on the left of the Genimal program window. The start number can be saved in a text file, which is especially worthwhile if an evolutionary process turns out to be highly successful.
The ‘randseed’ function is described as ‘pseudo random’. A pseudo random number generator is used: an algorithm, offered by MS Windows through the applied programming language, for generating a sequence of numbers that approximates the properties of random numbers.
The randomness is guaranteed sufficiently for the purposes of the Genimal program, thanks to the use of the command ‘Randomize’ at the start of the program. This procedure initializes the built-in random number generator of the programming language with a random value (obtained from the system clock). This provides a reliable method of creating an unpredictable sequence of numbers, even as they are really a part of a predetermined sequence.
Birth of a new genimal
At the start of an evolutionary process, a new genotype will be created, existing of 7 genes. All 32 bits of each gene are determined at random, making use of the ‘start number’ as described above. This start number is either selected at random by the program (when the button ‘New process, random start number’ is pressed) or by the user (if the button ‘New process, select start number’ is pressed).
Mutations
At t = 0, the newborn genimal will receive 1000 time steps. Immediately after, this value will start to decrease. By finding and consuming trees, the genimal will receive a bonus of 600 time steps. Nevertheless, there will come a moment when no time is left. At that time the genimal will lose its chances of finding trees. It will become a parent of a new genimal and die.
Next, a new genimal will be born, a child of the former one, based on a genome that is nearly identical to that of its parent. Nearly: that is to say, with the exception of one mutation.
Three kinds of mutations are possible:
- A bit change: 1 bit, arbitrarily chosen, is changed from 0 to 1 or v.v.;
- A duplication: one complete gene, consisting of 32 bits, is duplicated and thus occurs twice on the genome;
- An omission: one complete gene is erased from the copied chromosomes.
The probability of a bit change is considerably higher than that of the other two kinds of mutations.
The mutations can be made visible in the program by pressing the button ‘Show chromosomes’. A window will open in which both the genome of the parent and of the child are shown. The mutating, duplicated or omitted bits are marked in underlined red. Duplicating genes are shown in green.
If the mutated genimal appears to be lethal, the genetics of the parent are used again to produce another child, again based on a random mutation. If necessary, this goes on in a loop until a non-lethal child is produced.
In very rare cases it may happen that literally each and every mutation of a parent turns out lethal. In many hours of experimentation this has happened only once, so far. In that case, an ‘infection’ is introduced. A new gene, formed completely at random – supposed to come from another species in the surroundings – is added to the existing set of genes. This, too, is programmatically a part of a loop, which guarantees that eventually a non-lethal newborn child will come into being.
Survival of the fittest
During its lifetime, at each moment the genimal will have a score, indicating the level of success. The score is calculated, based on a combination of three values:
- the number of trees found and consumed (with a very high weighing factor);
- the time that is left (the more time left, the higher the score);
- the sum of the distances to all trees that have not yet been found & consumed (the closer, the higher the score).
The score may rise and drop during the lifetime. The present score and the highest score that has been reached during the current generation are both visible in boxes in the button bar at the top of the Genimal window.
After both a parent and its child have run through their entire life, their rates of success - i.e. both their high scores - will be compared. If the parent was more successful than its child, the parent will procreate, i.e. again act as a parent for the next generation. If the child is at least as successful, it will be the new parent and act as a source for the next genimal.
In this way, after many generations a genealogical tree will be created.
The record score that is realized during the entire evolutionary process is shown in the Genimal window, in the second row of the button bar. The value is roughly equal to 1000 times the number of trees found.
Artificial intelligence
In nearly all evolutionary processes, the genealogical tree will never lead to sensational results. This is not surprising, as the process is based on mere coincidence. But in some cases, the consecutive generations will ‘learn’ how to effectively find trees. A long series of experiments indicated that genimals will be able to find all 10 trees in about 5% of all evolutionary processes.
The interesting question is, whether these successful genimals have just learned to follow a fixed track - as the 10 trees are on fixed positions during the whole process - or really have acquired some kind of artificial intelligence.
The Genimal program offers an easy way to the user to investigate this question.
After the button ‘Show record generation’ is pressed (see the user’s manual), the program will switch to an alternative way of operating. The evolutionary process is halted; instead, the most successful genimal is shown over and over again. If this is done in a static landscape, the same route will be followed by the genimal each time. But it is possible to select a variable landscape, in which the locations of the trees will be different each time. In that case, the genimal is forced to find its way to totally new positions. In nearly all cases, genimals that were successful in a fixed landscape, finding all 10 trees, will appear to be successful again in the variable landscape, being able to all or most of the 10 trees again. In other words, the successful genimal has really acquired some kind of artificial intelligence.
The implication of this is that a successful evolutionary process has actually lead to a genome that contains an effective program for finding trees - a program that was written by no-one, it emerged by chance & selection.
Genetic drift
As mentioned before, the decision about survival of the fittest, selecting which genimal earns the right to procreate - the parent or the child - is based on their rates of success, i.e. the highest score they realize during their lifetime. This rule offers a slight advantage to the child, in comparison with its parent. If their high scores are different, the highest scoring genimal will procreate. But if the high scores are equal, it is the child that will procreate, not the parent.
This is often the case, as there is a considerable chance that the mutation that took place from parent to child only changed a ‘junk bit’: a bit that has no significance for the phenotype (i.e. for the body structure or the behaviour).
There are several possible reasons for this: a bit may be unused (see above, the gene code), or a gene encoding for a body part is not realized in the actual body, e.g. because it is encoded to be attached to a ‘mother’ part that does not exist.
As a consequence, in the course of a long series of generations the phenotype, and thus the rate of success, of a genimal may perhaps not change at all. Nevertheless, during those generations the number of mutations may accumulate. Thanks to this, a genimal that appears to be identical to an ancestor thousands of generations ago, may have a genotype that differs considerably. This effect may be called ‘genetic drift’ - over the generations, the genimal genetically drifts away further and further from its ancestor.
This drift is extremely important. If it did not exist - because the decision rule for survival of the fittest would benefit the parent instead of the child - only a very limited number of mutations would be possible. For instance, for a genimal at the start of an evolutionary tree, the genotype of this genimal will always consist of 7 genes, each consisting of 32 bits - that is how the Genimal program has been designed. For such a genimal, the maximum number of mutations is only 7 x 32 bit changes + 7 gene duplications + 7 gene omissions = 238. In other words: the first-generation genimal can only have 238 different children - differing in their genotype, that is. If children could only beat their parents by being really better - not just equally good - a genealogical tree would probably end soon, at the moment when none of the children turned out to beat a certain parent. It would suffice to test all possible direct children of a genimal, and if none of them would beat their parent, the tree would stop there and then.
Thanks to genetic drift, the situation is very different. Mutations may accumulate over many generations. All of a sudden, together they may have a large impact on the phenotype, for instance if the encoding for the type of gene (i.e. the first 2 bits) changes, e.g. from a repeat gene to a trunk, or from a trunk to a leg, causing former junk bits suddenly to become relevant.
Indeed, many practical examples have been found in which a genealogical tree did not increase its record score for thousands of generations, and it seemed to be stuck at a certain maximum score; but all of a sudden, the next generation actually did improve the score, and the genimal evolved into higher successful specimens.
In one case (start number: -221876230), the evolutionary process delivered no improvements after generation 2,143,520 until – rather unexpectedly – a new improvement occurred in generation 3,843,366: after an apparent stagnation of nearly one million and seven hundred thousand generations. As the starting number is shown here, the reader may want to reproduce this process.