Genotype (format f4) 

This encoding scheme is an indirect developmental encoding, devised by Adam Rotaru-Varga.



The f4 encoding resembles the f1 encoding, with an important conceptual difference: f1 is composed of codes which are interpreted as structural elements (sticks, neurons), or their attributes. On the other hand, f4 codes are interpreted as instructions to cells. An f4 genotype describes the developmental process of an organism. Development starts with a single ancestor cell, which starts to execute instructions from the start of the genetic code. As the cell divides, new cells are created, which execute different instructions in parallel (differentiation). The development stops when all cells mature, and the final shape of the creature is the result of the whole development process.
Developmental encoding models biological growth of an individual. Some features of a developed creature are not encoded by a particular gene, but by an interplay between developing parts. These interactions are modeled during the development process.

The developmental process. A developing creature is composed of interconnected cells. A cell is either a stick, or a neuron, or still undifferentiated -- this is the type of the cell. Undifferentiated cells can turn into a stick or neuron (as a result of developmental instructions), but not the other way around.
Development starts with a single, undifferentiated ancestor cell, executing the start of the genotype.
During each step, each cell executes one (or more) instructions, in parallel. A new step is started whenever a division or a change in type occurs. Development stops when all cells stop changing. At this point, there should be no undifferentiated cells.

The minimal example. The minimal f4 genotype looks like this: '/*4*/ X' (ex0). This says to the ancestor cell to turn into a stick (X), and stop development. The end result is a single stick -- corresponding to f1 genotype 'X'.

Two-sticks example. /*4*/ <X>X (ex1). This looks more interesting: '<'; denotes cell division. It will create two cells, the first will execute the instruction immediately following the '<', while the other will execute the instruction after the corresponding '>'. Now, it looks like '<' and '>' act like parantheses, but that's only superficial. In fact, '>' means 'stop development'.
The exact process looks like this:.
step 0. Initially, there is the ancestor cell, no 1, undifferentaited.
step 1. cell 1 executes '<' (division), creates cell 2 undifferentaited.
step 2. cell 1 executes 'X', turns into a stick.
(cont) cell 2 executes 'X' (the other one), turns into a stick.
step 3. cell 1 executes '>' -- stops development.
(cont) cell 2 stops development.
The end result is two connected sticks, the same structure created by f1 genotype 'XX'.


An f4 genotype is identified by the prefix '/*4*/ '. This is not part of the genotype, but a comment identifying that it is of type f4.

Most f4 codes are one-letter codes, with some exceptions. An f4 genotype is expressed as a string of codes. However, because division branches the sequence of instruction in two, the genotype can be conceptualised as a binary tree of codes. The string representation corresponds to a pre-order traversal. (Note that an f1 can be conceptualised as a tree as well.)

Codes are the following:

'<' Division. Creates a new cell. The new cell will be connected to the old one. This is the only way of creating a new cell.
After division, the two cells will execute different codes. The '<' is followed by the codes executed by the first cell (ending in a '>'), and then the codes to be executed by the second cell. Thus the code to be executed by the second cell can be found after the corresponding '>'. Note that both code sequences can contain further divisions. The general form is:
< ...cell 1 code... > ...cell 2 code... >
If there are n divisions in a genotype, they will create n+1 cells. This also means n+1 cell-stop markers '>'. However, the very last '>' can be omitted. This is because the last stop is not followed by anything else, and to have an equal number of '<' and '>' codes.
Example: <LL<X>X>llX (ex53)
In this case, after the first division, the first cell will continue with the 'L' (pos 2.), while the second, freshly created cell with the 'l' (pos 9).
Usually undifferentiated cells divide, and later differentiate into sticks or neurons. However, a neuron can divide, and in this case the new cell will be a neuron as well, with the same characteristics as the old cell. Existing links are also duplicated. Sticks cannot divide.

'X' Turn into stick. Turns the cell into a stick. The cell must be undifferentiated. It will remain a stick, since a stick cannot change its type (nor divide).

'N' Turn into neuron/muscle. Turns the cell into a neuron. The cell must be undifferentiated. It will remain a neuron, since a neuron cannot change its type.

'>' Stop development of cell. Cell should not be undifferentiated. This symbol also has the role of a delimiter.

',' Increase branching angle (comma). Increase the branching count (angle) of future divisions. Changes takes effect when the dividied daughter cell turns into a stick. Cell can be undifferentiated or a stick. Example: ex3.

'L'/'l' Increase/decrease length of stick. L: increases length by 0.3*(2.5-len). l: decreases length by 0.3*(len-0.3). Works with sticks and undifferentiated cells.

'R'/'r' Increase/decrease rotation by 45 degrees. Works with sticks and undifferentiated cells.

'C'/'c' Increase/decrease curvedness.

'Q'/'q' Increase/decrease twist.

Neural parameters can be modified by a sequence of increasing/decreasing codes. (Note that in f1 these are set using concrete numerical values.) These codes are of the form ':+X:' or ':-X:' for increasing and decreasing respectively.

':+!:' Increase neural force, by (1.0 – force) * 0.2.

':-!:' Decrease neural force, by force * 0.2.

':+=:' Increase neural inertia, by (1.0 – inertia) * 0.2.

':-=:' Decrease neural inertia, by inertia * 0.2.

':+/:' Increase neural sigmoid value, multiply by 1.4.

':-/:' Decrease neural sigmoid value, divide by 1.4.

'[...:...]' Add a neural link. Adds a neural link to a neuron (cell must be neuron). The format is: '[' (input link) ':' (weight) ']'.
Input link is an integer number, interpreted as the relative reference to the neuron where the link is originating. 1 means the 'next' neuron, -1 the previous, 0 this one, 3 three from here on, and so on. Note that relative references are based on the current structure, and not the final one!
There are special input codes for senses: 'G' for gyroscope (adds a gyroscope sense to the stick the neuron is connected to), 'T' for touch sensor, and 'S' for smell sensor.
The weight is a real number representing the weight of the link. Examples: ex9, ex11.

'|' Turn into a bending muscle. Turns the cell into a bending muscle. The cell must be a neuron. Examples: ex10, ex51.

'@' Turn into a rotating muscle. Turns the cell into a rotating muscle. The cell must be a neuron. Examples: ex11, ex52.

Codes that affect biological properties:

'A'/'a' Increase/decrease assimilation.
'I'/'i' Increase/decrease ingestion.
'S'/'s' Increase/decrease stamina.
'M'/'m' Increase/decrease muscle strength.
'F'/'f' Increase/decrease stick strength.
'W'/'w' Increase/decrease stick mass.
'E'/'e' Increase/decrease stick energy.

'#' Repetition marker. This code allows certain other codes to be repeated more than once. The explanation of this code requires certain general details, left out from the discussion so far for the sake of clarity. This code is quite tricky, but it is also powerful: it can create repetitions of the same codes (and thus substructures) withouth the dupication of the codes themselves.
Each cell has a pointer to the currenty executing code. But they have another pointer, which is the 'to repeat' pointer. They also have an associated 'to repeat' counter. The '#' code creates a branching in the genotype tree, much like the '<' (it does not create new cells though). It is also associated by a number, like in '#3'. The action is this: set the repeat counter of the cell to the number associated with '#', and make it execute the first child. However, make it also remember it in the repeat pointer. For repetion to actually work, we have to modify the semantics of the '>' as well: if the repeat counter is 0, it means regular 'stop', as described above. However, if the counter is not 0, it is decremented, and if it still not zero, the cell 'jumps' back to the repeat pointer. If the repeat counter gets to 0, the second child of the '#' is executed to finish off.
What all this means is that a genotype of the form
#n ...repcode... > ...endcode...
means that the repcode part will be repeated n times, and the endcode once in the end.
There's one more detail: when a cell divides ('<'), only the new cell inherits the repeat counters, and not the old one. Thus only one cell will continue the repetition.
Examples: ex8a, ex15. ex16. ex17.

Genetic operators

Mutation produces some localised changes in an f4 genotype. Mutation operates on the tree representation of a genotype. A single mutation can change a code, change a parameter of a code, add a new code (division, neural link, repetition marker, or simple code), or delete a code. A mutation operator can consist of several single mutations. The amount of change of a mutation is estimated from the ratio of number of changed codes and total number of codes.

Crossover operates on f4 genotype trees, and exchanges two subtrees of two genotypes. The size of the subtrees varies, between 10 and 90 percent of the genotype.


Example no. f4 genotype Corresponding f1 genotype (approximate) Description
ex0 X X a single stick
ex1 <X>X XX two sticks connected one-after-the-other
ex2 <<X>X>X X(X,X) two sticks connected to the same third one (branching)
ex3 <,<,,<,X,,>X>X>X X(,X,,,X,,X,,) a 3-way branching with different brancing angles
ex4 <X><X><<X>X><X>X XXX(XX,X) more branching
ex5 <<X><<X>X>X>X X(X,X(X,X)) more complex branching
ex6 <X>l<X>l<<X>X>LLLX XlXlX(LLLX,X) different length factors
ex7 <<X>RR<<X>X>X>X X(X,RRX(X,X)) branching with rotation R
ex8a #3<X>lC>X XlCXlCXlCX repetition, C
ex8b <X>lC<X>lC<X>lCX" XlCXlCXlCX curvedness C
ex9 <X><N[1:2]>N[-1:3] X[1:2][-1:3] a stick with two neurons attached to it. The two neurons are connected to each other
ex10 <X><X><N|[1:2]>N[-1:3.5] XX[|1:2][-1:3.5] a structure with two neurons and a bending muscle
ex11 <X><<,<X,><N@[1:20]> N[G:30]>X>X XX[@1:20][G:30](X,,X,) a structure with a rotating muscle and a gyroscope sense
ex12 <X>N|[*:1][G:2] X[|*:1,G:2] a stick with a bending muscle
ex13 <X>N<[*:0]>[-1:10]<> X[*:0][-1:10][-2:10] duplicating links upon neuron division
ex14 <X><<X>N|[0:1]><X> <N@[-1:1.2][1:2.3]>N[G:1] XX[|0:1]X[@-1:1.2,1:2.3][G:1] various neurons and links
ex15 #10,<<X>X>>LLX X(,,X(,,X(,,X(,,X(,, X(,,X(,,X(,,X(,,X(,LLX, X)X)X)X)X)X)X)X)X)X) repeating division 10 times
ex16 #10,<<X><<X>X>X>>LLX X(,X(,X(,X(,X(,X(,X(, X(,X(,X(,LLX,X(X,X)), X(X,X)),X(X,X)),X(X,X)), X(X,X)),X(X,X)),X(X,X)), X(X,X)),X(X,X)),X(X,X)) even more repetitions
ex17 rr<X>#9<,<X>RR<<llX>LX>LX>>X rrXX(,X(,X(,X(,X(,X(,X(,X(,X(,X, llRRX(LLX,LLX)),llRRX(LLX,LLX)), llRRX(LLX,LLX)),llRRX(LLX,LLX)), llRRX(LLX,LLX)),llRRX(LLX,LLX)), llRRX(LLX,LLX)),llRRX(LLX,LLX)),llRRX(LLX,LLX)) a worm-like creature, composed of repeated identical segments ('kukac')
ex51 <X><X>N| XX[|] /* ?? */ two sticks and a bending muscle between them.
ex52 <X><X>N@ XX[@] /* ?? */ two sticks and a rotating muscle between them.
ex53 <LL<X>X>llX LLX(llllLX,X) 3 sticks in a Y formation

Related links