Combine cellular automata with a genetic algorithm and see what happens.

In the article there are Gif (traffic!) and contrasting images. In epileptics can happen to an epileptic seizure.

Rules for cellular automata.

The simplest cellular automata one — dimensional cellular automaton (there are also zero-dimensional — ‘ll talk about them below). In one-dimensional cellular automaton we have a one-dimensional array in which every cell (cells) can take one of two States (1/0, true/false, white/black, alive/dead). The next state of a cell in the array is determined by the current state of a cell and the state of two neighbouring cells according to some rule.

There are

$2^3=8$

combinations of States of the cell and two neighboring cells:

Next, for each of the combinations, we write the state of a cell for the next iteration (for the next state of the machine):

Got a rule for a cellular automaton. Rules for one-dimensional cellular automata are encoded by 8 bits (“code Tungsten”). There are

$2^8=256$

elementary cellular automata:

256 machines can sort through manually. We will not dwell on them. Calculate the number of existing rules to two-dimensional cellular automata.

In a two-dimensional cellular automaton uses two-dimensional array. Every cell has 8 neighbours in the Moore neighbourhood (there is also a neighborhood of von Neumann, which is not taken into account the diagonal cells. Her article is not considered):

For convenience, we write the cells in the row (the order chosen will use later in the article):

For two-dimensional cellular automaton exists

$2^9=512$

combinations of state cells and 8 neighboring cells:

The rule for two-dimensional cellular automaton is encoded in 512 bits. There are

$2^{512}$

two-dimensional cellular automata:

Number:

$2^{512}\approx1.340781\times10^{154}$

more the number of atoms in the observable Universe (

$10^{80}$

).
Manually, this number of machines to sort through. If we every second of looking through one machine for the lifetime of the Universe, we would have had time to view all

$\approx4.35\times10^{17}$

machines.

A brute force search is not working, but with the help of genetic algorithm we can find the machines that best match some predetermined criteria.

Programming will be in JavaScript. All code snippets are hidden under spoilers so as not to confuse readers who are not familiar with programming languages.

Two-dimensional cellular automaton.

Write a two-dimensional cellular automaton with a random rule. The rule will be stored in the rule array, the length of which rulesize=512:

Fill the array with rule

var rulesize=512;
var rule=[];
for(var i=0;i<rulesize;i++) rule[i]=Math.the round(Math.random());

Next, fill the initial state of the machine randomized:

Fill the initial state of the machine

var sizex=89;
var sizey=89;
var size=2;
var a=[];
for(var x=0;x<sizex;x++){
a[x]=[] for(var y=0;y<sizey;y++){
a[x][y]=Math.the round(Math.random()); if(a[x][y]) context.fillRect(x*size, y*size, 1*size, 1*size);
}
}

(here and later in the article, both the width and height of the machine, taken on a random number — not very big and not too small odd number 89)

A function that computes the next state of the machine is as follows (in order not to clutter — removed the initialization of the canvas):

Consider the following state machine

function countpoints's(){ var temp=[]; var xm, xp, ym, yp, q; for(var x=0;x<sizex;x++){
xm=x-1; if(xm==-1) xm=sizex-1;
xp=x+1; if(xp==sizex) xp=0;
temp[x]=[]; for(var y=0;y<sizey;y++){
ym=y-1; if(ym==-1) ym=sizey-1;
yp=y+1; if(yp==sizey) yp=0;
q="+a[xm][ym]+a[x][ym]+a[xp][ym]+a[xm][y]+a[x][y]+a[xp][y]+a[xm][yp]+a[x][yp]+a[xp][yp]; q=parseInt(q, 2);
temp[x][y]=rule[q]; if(temp[x][y]) context.fillRect(x*size, y*size, 1*size, 1*size);
} } a=temp;
}

The variables xm and xp store the X coordinate of the left neighbor and right neighbor (x minus and x plus). Variables ym and yp are stored corresponding Y coordinates.

Here:

The field of machine rolled up in a bagel

xm=x-1; if(xm==-1) xm=sizex-1;
xp=x+1; if(xp==sizex) xp=0;

we set periodic boundary conditions (box machine — surface of the torus).

Next:

… more

q="+a[xm][ym]+a[x][ym]+a[xp][ym]+a[xm][y]+a[x][y]+a[xp][y]+a[xm][yp]+a[x][yp]+a[xp][yp]; q=parseInt(q, 2); temp[x][y]=rule[q];

in the above order of the recorded contents of the cells in the row. Translate a string into a decimal number. For this combination we find in the rule array is a condition that needs to be the cell with coordinates x and y.

Optimized version


q=a[xm][ym];
q=(q<<1)+a[x][ym];
q=(q<<1)+a[xp][ym];
q=(q<<1)+a[xm][y];
q=(q<<1)+a[x][y];
q=(q<<1)+a[xp][y];
q=(q<<1)+a[xm][yp];
q=(q<<1)+a[x][yp];
q=(q<<1)+a[xp][yp]; temp[x][y]=rule[q];

After all iterations of the model to a previous state of the machine new:

model previous state new

Machine-drawn with the function setInterval:

setInterval

timerId = setInterval(function() {
countpoints's();
}, 1);

To run in the browser

I recommend 10-20 times to start the machine with a random rules before you continue reading the article.

We can very long to run the machine with different random rules. The picture we get will not be different from the picture on the TV screen when no signal:

Then move on to setting up our “TV” using the genetic algorithm.

Genetic algorithm.

The size of the initial population of 200 machines (individuals). For rules, instead of a one-dimensional array rule we will use a two-dimensional array population. The first index (n) — number of individuals in the population.

Create the population

var PopulationSize=200;
var rulesize=512;
var population=[];
var fitness=[];
for(var n=0;n<PopulationSize;n++){
population[n]=[];
fitness[n]=0; for(var i=0;i<rulesize;i++){
population[n][i]=Math.the round(Math.random());
}
}

The fitness array contains the coefficients of adaptation for each species. This array is populated in the selection process. After run selection the evolutionary process.

Evolutionary process.

Of our population take half of the fittest (the multiplier fitness) of individuals. The remaining half consume. Next, take the two surviving species and crossed them.

For breeding select a random position in the two genotypes of their ancestors. Prior to this position, I take genes from one ancestor, and after this position from the other. Put the selected genes in the genotype of one offspring. The remaining genes — to another. Two ancestors and two descendants are placed in the new population. In this case, each individual involved in the crossing once.

Mutation. A 5% chance each individual is mutated (inverted) one randomly chosen gene. If we increase the likelihood of mutations — good mutants becomes more but however, a good mutant may not be able to leave successful offspring before mutating again unsuccessfully. This issue will come back later.

The function of the evolute();

evolute function(){ var sizehalf=PopulationSize/2; var sizequarter=sizehalf/2; var arrayt=[]; for(var n=0; n<PopulationSize; n++) arrayt[n]=[population[n], fitness[n]];
arrayt.sort(sortf);
arrayt.length=sizehalf;
population=[];
fitness=[]; for(var i=0; i<sizequarter; i++){ var i0=i*4; var i1=i*4+1; var i2=i*4+2; var i3=i*4+3; var removed1=Math.floor(Math.random()*(arrayt.length)); var parent1f = arrayt.splice(removed1,1); var parent1=parent1f[0][0]; var removed2=Math.floor(Math.random()*(arrayt.length)); var parent2f = arrayt.splice(removed2,1); var parent2=parent2f[0][0]; var child1=[]; var child2=[]; var qen=Math.floor(Math.random()*rulesize); var temp0=parent1; var temp1=parent2; var temp2=temp0.splice(qen,rulesize); var temp3=temp1.splice(qen,rulesize); var parent1=temp0.concat(temp2); var parent2=temp1.concat(temp3); var child1=temp1.concat(temp2); var child2=temp0.concat(temp3); population[i0]=parent1;
population[i1]=parent2;
population[i2]=child1;
population[i3]=child2; fitness[i0]=0;
fitness[i1]=0;
fitness[i2]=0;
fitness[i3]=0;
} var mutation=document.getElementById("mutatepercent").value*1; var m=100/mutation; var m2=0;//0 for(var i=0; i<PopulationSize; i++){ var rnd=Math.floor(Math.random()*(m))+1;
if(rnd==1){ var rnd2=Math.floor(Math.random()*(m2))+1; for(var j=0;j<rnd2;j++){ var gen=Math.floor(Math.random()*(rulesize));
if(population[i][gen])
population[i][gen]=0;
else
population[i][gen]=1;
}
}
}
}

Natural selection.

Before starting the evolutionary process it is necessary to make a selection. Selection can be both natural and artificial. Artificial selection is done manually — about it later. For natural selection, we will establish some criteria and we will select the machines that best meet the criteria.

What criteria can be determined in advance? Let’s take the easiest. Our “TV” is blinking too much. Save two-state cellular automaton — 99 and 100 iterations. Count the number of cells that have not changed. The resulting number will be used as a factor in fitness. Obviously, one criterion is not enough. It is easy to manually pick the machine that will best meet the given criteria: automatic [0,0,0,…,0] and the machine [1,1,1,…,1]. These two machine in the first iteration are filled with zeros or ones and cease to change its state. We define a second criterion: the difference between the number 0 and 1 (cells) in the machine does not exceed 100 (the number taken “from Baldy”).

array1 — the state of the machine on the 99th iteration. array2 — 100-th iteration:

Believe

countfitness function(array1, array2){ var sum=0; var a0=0; var a1=0; for(var x=0;x<sizex;x++){ for(var y=0;y<sizey;y++){ if(array1[x][y]==array2[x][y]) sum++;
if(array1[x][y]==0){
a0++;
}else{
a1++;
}
}
} if(Math.abs(a0-a1)<100) return sum; return 0;
}

Run. The optimal solution is found at the 421-th cycle of evolution. On the chart you can see the progress:

Graph scaled on the y axis. bottom point is 0, the top point — 7921. Obviously, 7921 — optimal solution (all cells in the machine 89х89 match the given criteria). After 100 iterations none of the cell does not change its state.

Blue dots on chart is the best individual in the population. Red is the worst (taking into account only those individuals that meet the second criterion). The black dots represent the average rate of adaptation for the entire population (including individuals not satisfying the second criterion). The second criterion (the balance between white and black) very hard. Some machines do not meet the second criterion, even after the 421 cycle of evolution. Therefore, the black dots below the red.

The gene pool of the population (Y — axis specimens, the X — axis is the genes):

Look at the channel caught our “TV”:

The solution is not unique optimal. If you re-run evolution (with random starting genotypes) — find other optimal solutions. One of them:

Change the selection criteria.
We assume the number of cells in the Moore neighbourhood of order 2 there is some pattern. Pattern let’s take the easiest:

This criterion is interesting because we check 25 cells at a time, like an automaton calculates the state of a cell based on the States of the 9 cells.

The criterion is very hard. If you take a random slot machine, after 100 iterations it looks like this:

Not one cell in this machine does not match the specified criterion. So a little tender criterion:
1. Allowed to make one mistake in the pattern.
2. The pattern will look not at the last iteration, and the last 50 iterations.

The second criterion (the balance between white and black) remove.

Run. Chart:

On the Y-axis scale is arbitrary. (In the previous machine, the optimal solution is 7921. This machine is about 30.)
X-axis — 3569 cycles of evolution. The two white vertical lines indicate 500 and 1000 cycles of evolution.
Blue points — the best individual in a population, red is the worst, black is the average coefficient for the entire population.

The solution was found in the first 500 cycles of evolution. Following 500 cycles of the solution improves. And then the system practically ceases to evolve.

Three pictures below: 500 cycles, 1000 cycles and 3569 cycles of evolution:

The gene pool (3569):

In dynamics:

In the picture below you can see how is the oscillator (glider) in this machine:

We can start the machine with the initial state in which only one cell. Continue to record all combinations of cells that occur in the next iterations of the machine. An array of genes (the genotype of the machine) — an array of all possible combinations. Highlighting of them only occurring combinations, we can easily mark all genes that are involved in the formation of the oscillator. Grey lines — the genes that do not participate in the formation of the oscillator:

Mutations in the mentioned genes do not survive due to the fact that breaking the pattern is formed.

In our machine, pattern (square) is formed around the black cells. Try to run the evolutionary process with the second criterion: the difference between the number of white and black cells does not exceed 400.

Launched 3569 cycles of evolution. Chart:

On the graph the black dots represent the average rate of adaptation in populations. White point — the average coefficient of adjusted previous machine. The solution is found with one error in the pattern.

The gene pool:

The first 100 iterations:

Last (100) iteration:

Not the little result that we expected. The black squares are, white — no. Tightened the second criterion: the difference between the number of white and black cells does not exceed 100.

Run 14865 cycles of evolution.
Chart comparison of average coefficients of adaptation of populations. Blue point — our machine. White and black — the previous machines.

Automatic evolyutsioniruet so cheerfully, that it may seem that he is not evolyutsioniruet. The second graph scaled on the y axis. the Two white lines 500 and 1000 cycles.

From the best individuals in the average of 6 cells match the given criteria.

Look at random machine from the population.
50 iterations:

Latest (50) iteration:

An acceptable result was not found. The second criterion makes it hard to find, so we give it up (later in the article do not use). Leave this pattern and look for some other patterns.

Pattern:

Run. 3000 cycles of evolution. Chart:

The gene pool:

In the dynamics (100 iterations):

Last (100) iteration:

Pattern:

In the previous machines we were allowed to make one mistake in the pattern. This time look for the exact pattern.

Launched 4549 cycles of evolution. Chart:

White vertical line — 2500 cycles of evolution. At this point (a bit earlier) the fitness of the population began to grow rapidly. Preserved population, to look at an interim solution. An interim solution was much more interesting decisions on the 4549-th cycle of evolution.

The solution found on the 4549-th cycle of evolution:

On Gif 100 iterations. Even after some number of iterations (about 500-2000) state of the automaton is almost completely sequenced (the height and width of machine are specially selected odd numbers, so that the machine could not be ordered in full):

Machine with an even number of dimensions of the sides, after some number of iterations adopts a fully ordered state. Automatic 90×90, approximately 1200 iterations:

An intermediate solution (found in the 2500-th cycle of evolution):

This machine is also able to recycle some of the initial chaotic state to a final order (the final ordered state, the offset of the pattern along the X axis to the left + a few cells-oscillators).

Machine 16×16 settling in around 100 iterations:

32×32 — about 1000 iterations:

64h64 6,000 iterations:

90×90 — about 370,000 iterations:

11×11 (odd field dimensions of the machine) — about 178700 iterations:

Automatic 13×13 didn’t happen in a reasonable time.

In the picture below, the machine on the field on a 256×256 100000-th iteration:

I recommend to look at this gun in the dynamics on a large field — it is very interesting to observe the process of self-organization of chaos in this machine: to run in the browser

The gene pool of the intermediate population:

Re-run the evolutionary process allows you to find other solutions. One of them:

Another pattern:

When searching for the pattern again allowed to make one error (no error system with the selected pattern does not evolyutsioniruet).

Run. 5788 cycles of evolution. Chart:

The scale is arbitrary.

The gene pool:

In dynamics:

The ordered state of the machine (offset of the pattern up on the Y axis + a few cells-oscillators):

Much more interesting to watch not by the machine, and the mutants that appear in this population:

Gif machine 256×256. 200 iterations. Other iterations can view in the browser.

This could end with natural selection and go to artificial, but I want to show how

$2^{512}$

a huge number of. Among this number of machines we can find a machine which draws any given pattern (with some accuracy for more complex patterns).

The following pattern:

In previous experiments we considered the amount of cells, around which is formed a pattern (if one mistake — to the sum add 1, if no errors — added 2). The amount received was used as coefficient of adaptation for genetic algorithm.

For more complex pattern such method is not working. Automatic, in which fewer cells more accurately fits the given criteria (number of cells matched with the pattern in the neighborhood cells), each time will lose the machine, in which a larger number of cells less accurately fits the given criteria. As in the example with the squares above:

To the desired pattern, on the 100th iteration of each machine in the population, surrounded by every cell will count the number of cells matching the pattern. We will take only the best result for each machine. The number of cells that matched the pattern, we will use as a factor of fitness. The pattern consists of 7х17=119 cells. This number will be considered the optimal solution. 6000 cycles of evolution has enabled them to find a machine that draws a pattern with 5 errors (114 cells coincides with the pattern).

The graph in arbitrary scale:

The increase in the percentage of mutations did not impair the fitness of the population.

In the gene pool of a population of a lot of mutants:

Random machine from the population dynamics:

The best machine on the 100-th iteration:

Searched and found the patterns:

Play around with selection criteria, the size field of the machine and the percentage of mutations that happened to improve the population and find a machine that makes only 3 error in the pattern.

The gene pool:

Automatic 100-th iteration:

Searched and found the patterns:

2 errors

In the process of writing, the system has continued to evolve. For a more accurate search, the size field of the machine is increased to 513х513. Found automatic, making only two errors in the pattern:

Four charts you can see how evolyutsioniruet system with different probabilities of mutation (1 mutated gene):

Red dots indicate the average rate of adaptation in populations. The black dots represent the ratio of fitness of each individual. 3000 cycles of evolution for each system.

The gene pools of the populations (in the same order):

The machines on the 100-th iteration:

We will conduct another experiment. The pattern is the same. The initial genotypes filled with random genes. The probability of mutation is 5%. From 1 to 8 genes are mutated (for each individual takes a random number of mutating genes). 100 cycles of evolution.

A graph is a heat map. The size of the points on the graph of 5 pixels. The origin is the upper left corner.
On the Y axis (0 to 100) cycles of evolution. On the X-axis (0 to 119) — the number of cells matching a pattern (for each individual in the population take the best result). Brightness — the number of individuals with the specified (X coordinate) result.

Run 4 times the genetic algorithm with the same parameters (100 cycles, 5% of mutations, up to 8 genes mutate). On the chart, all 5 runs:

The following 5 launches: 25% of mutations, up to 8 genes are mutated:

The sample is small, but it is possible to draw conclusions about the effectiveness of increasing the percentage of mutations.

Next, show the inefficiency of article used in the method of crossing.

The previously used method:

Instead of dividing the genotype into two parts, the descendants will inherit the random genes of their ancestors:

5% of mutations:

25%:

Next, we use this method of crossing.

This with natural selection are done. If someone has interesting ideas about the criteria for natural selection, please voice them in the comments.

For artificial selection are going to use cellular automata of the second order.

Second-order cellular automaton

Consider a zero-dimensional cellular automaton first order (all cellular automata that we have considered above — the first order). A zero-dimensional cellular automaton consists of a single cell. The cell can be in one of two States. The next state of the cell (t) is determined by the current state of a cell (t-1). There are 4 zero-dimensional cellular automaton (one oscillator):

In the cellular automaton of the second order, the next state of the cell (t) is determined by the current state (t-1) and the previous state of the cell (t-2). There are 4 combinations of two States of the cell.

$2^{4}=16$

— the number of zero-dimensional cellular automata of the second order:

These cellular automata exhibit more complex oscillators.

$2^{8}=256$

cellular automata of the third order:

$2^{16}=65536$

cellular automata of the fourth order one picture show will not work.

Search of a cellular automaton

$n$

-order with a period of oscillation equal

$n$

is non — trivial and very interesting. This topic deserves a separate article.

In one-dimensional cellular automata of the second order, the next state of a cell is determined by the current state of the three cells and the previous state of a single cell:

There

$2^{16}=65536$

one-dimensional cellular automata of the second order.

Code:

One-dimensional cellular automata of the second order

var rule=[];
for(var i=0;i<16;i++) rule[i]=Math.the round(Math.random()); var a=[];
var b=[];
var temp;
for(var x=0;x<sizex;x++){
a[x]=0;
b[x]=0;
}
b[63]=1; var xm, xp, q;
for(var y=2;y<sizey;y++){
temp=[]; for(var x=0;x<sizex;x++){
xm=x-1; if(xm<0) xm=sizex+xm;
xp=x+1; if(xp>=sizex) xp=xp-sizex; q=b[xm];
q=(q<<1)+b[x];
q=(q<<1)+b[xp];
q=(q<<1)+a[x]; temp[x]=rule[q]; if(temp[x]) context.fillRect(x*size, y*size, size, size);
}
a=b;
b=temp;
}

Cellular automata of the second order draw more complex patterns than the cellular automata of the first order.

In the pictures below, a few random machines of the second order (in the left part of the picture — in condition t-1 filled one cell on the right for random-state t-1 and t-2, the binary code — the contents of the array rule):

0011111011001000:

0101101110011110:

0110000110010010:

0110011010010110:

1110011010010110:

0110111010000101:

1111101001110110:

1001010001100000:

This automaton 256×256:

512h512

Other machines can be found here:
One-dimensional cellular automata of the second order.
One-dimensional cellular automaton of the third order.

About one-dimensional cellular automata of the second order can be found in the book Wolfram “A New Kind of Science”.

Artificial selection

Like one-dimensional cellular automaton of the second order in two-dimensional cellular automaton of the second order will use an additional cell from the previous (t-2) state of the automaton.

For convenience, this cage will place at the beginning of the binary string:

The convenience lies in the fact that the coincidence of the first and second half of the genotype, the machine can be seen as a machine of the first order:

Adding one cell, we increased the number of available machines in

$2^{512}$

time.

$2^{512} \times 2^{512} = 2^{1024}$

— the number of existing two-dimensional automata of the second order.

For natural selection, we have identified some criteria and compare the machines based on this criterion. In the process of artificial selection, we choose the machines manually, using some vague principle: “this machine is interesting, and that’s not very”.

This principle allows you to choose the best machine among random slots:

There are several ways to solve this problem. I propose to consider four options.

1. In the initial state of the machine filled one cell

One way is to observe the evolution of a cellular automaton, the initial state of which is filled with one cell.

Fill in the initial population of random machines. Some vending machines from the initial population (30 iterations for each):

These two are flashing

In the population there is a small number of machines that demonstrate less random behavior. They will be selected for crossing:

20 random machines from the initial population (the status of machines on the 30-th iteration):

After three cycles of evolution:

After eight cycles of evolution:

Eight cycles of evolution was enough to fill the entire machine population with a certain characteristic (automatic drawing triangles).

2. Genotype is only partially filled

If you disrupt the balance of ones and zeros in the genotype — violated the ratio of ones and zeros in the phenotype.

In the genotype (rule) of the machine contains the following state of the cells for all possible combinations of a cell and neighboring cells. If the genotype has more zeros (or ones) in the following States in the automaton accumulate zero (or units). Curious to see the correlation between the ratio of ones and zeros in the genotype and ratio of ones and zeros in the phenotype.

We construct a graph.

Create a population of 200 machines. Genotypes filled with zeros (1024 gene in the genotype of two-dimensional second order). Further

$n$

genes fill units. For the first population

$n=0$

for the 513-th population

$n=512$

. Axis

$x$

— the number of the population. Axis

$y$

celebrate (white dots), the ratio of ones and zeros in the gene pool of a population. Got the hyperbole:

For each machine (with the dimensions of the field 89х89) we consider 100 iterations. On the 100th iteration count the number of ones and zeros in the state (phenotype) of each machine. Note the ratio of ones and zeros (the total number of all units divided by the total number of all zeros). Got curve:

Total is the ratio of ones and zeros in all phenotypes, it is possible to look at the ratio of ones and zeros in each phenotype:

In the left part of the graph is the point with the greatest deviation from the mean. We can assume that those machines, the genotypes of which zero gene equal to one. Suggested — checked. Gene set null is always zero. Draw a new chart:

Comparable to machines, in which the null gene is always equal to one:

In machines of the second order there is another “zero” Kyung — 512-th. Let’s see how this gene affects the phenotype.

0-th, or 512-th gene is always zero:

The 0-th gene is always zero. 512-th gene is always equal to one:

Once again not to mock our distinguished epileptics, the 0-th and 512 th gen will fill with zeroes in the initial population of the genetic algorithm.

Look at the machines, which we got rid of setting the zeros in the 0-th and 512 th genes.

The first 8-state machine, which filled only the 0-th gene (the gene of zero equal to one and the rest zeros):

The machine, which filled only 512-th gene is:

The machine, which filled only the 0-th and 512 th genes:

Select the place on the chart where the population is divided by groups:

The genotypes are filled to 25%.

Compare two populations.

The first population. 30 random machines on the 1,000 th iteration. Genotypes filled to 50% (512 ones and 512 zeros):

A second population. 30 random machines on the 1,000 th iteration. Genotypes are filled to 25% (256 units and 768 zeros):

The second population is suitable for artificial selection. We can easily select some of the signs in these machines. For example: “darker”, “less chaotic” (the machines, in which the white cells are grouped together), etc.

Select “darker”. The probability of mutation is 10%, up to 4 genes mutate. After the first selection:

After the second selection:

In the population there was an interesting machine.

256 x 256, state machine 1000-th iterations:

The machine gradually fills with population.

After the eighth selection process:

There is another interesting machine.

256 x 256, state machine 1000-th iterations:

Population after thirteen selections:

Several machines of this population. 256×256, 1000-th iteration of for each. Under the picture is a link, clicking on which, you can look at the machine in movement:


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.

3. Machine Conway and others like him

The most famous two-dimensional cellular automaton rst-order automaton Conway’s Game “Life”.

The rules for Conway’s automaton is written as follows:
If around 3 dead cells living cells — the cell is alive (otherwise, it remains dead).
If you are around a living cell with 2 or 3 living cells — the cell remains alive (otherwise it dies).
Dead cell — 0, live cell — 1.

Around the cage can be from 0 to 8 living cells. 9 options live around and around the dead cells. Write all options in the array r:

the array r

r=[
0,0,0,1,0,0,0,0,0,
0,0,1,1,0,0,0,0,0
];

The first half of the array for dead cells, the other for living.

Can paint the machine Conway’s rule for all possible (512-ti) combinations of cells and 8 neighboring cells:

Paint rule

r=[
0,0,0,1,0,0,0,0,0,
0,0,1,1,0,0,0,0,0
];
var rule=[];
var q1, q2;
for(var i=0;i<512;i++){ var ii=i.toString(2); for(var j=ii.length;j<9;j++) ii='0'+ii;
q1=1*ii[4];
q2=1*ii[0]+1*ii[1]+1*ii[2]+1*ii[3]+1*ii[5]+1*ii[6]+1*ii[7]+1*ii[8];
if(q1==0)
rule[i]=r[q2];
else
rule[i]=r[q2+9];
}
Optimized version

r=[
0,0,0,1,0,0,0,0,0,
0,0,1,1,0,0,0,0,0
];
var rule=[];
for(var i=0;i<512;i++){ var q=((i>>4)&1)*8; for(var j=0;j<9;j++){
q+=(i>>j)&1;
}
rule[i]=r[q];
}

To second order, the second half of the array is copied from the first rule:

Copy

for(var i=0;i<512;i++){
if(rule[i]==0)
rule[i+512]=0;
else
rule[i+512]=1;
}

Run the machine with the specified rule. See typical gliders and oscillators. Several iterations of this machine:

The array r consists of 18 cells. There

$2^{18}=262144$

machines like the automaton Conway (which you can record the same rules: the number of live cells surrounded by dead, in which a cage comes to life and few live cells in the live environment under which the cell dies).
You look at them here (by default, runs automatic Conway, the button “Change rule” populates the array r is random).

A few random machines (binary — array r):

110010011001111111

100001100110111110

011111000100101110

010000110000110010

001111010011100111

000111001000000110

000101100010100001

000001111101011111

000001100110111111

The genetic algorithm as the genotype, can be used as an array r (

$2^{18}$

combinations), and a rule array (

$2^{512}$

combinations for a cellular automaton, first order and

$2^{1024}$

for cellular automata of the second order).

$2^{18}$

— a relatively small number. This number allows you to choose a rule for the machine manually, without the use of a genetic algorithm (actually, what did Conway).

If you fill an array with random rule machines of this type and use this array as a genotype — then the experiment can be considered a failure to some extent (enough to not show the article the results of this experiment). The rules of cellular automata of this type has symmetry. For example, the following combinations of cells:

… and for those

the state of a cell at the next iteration is the same. After the first crossing symmetry is violated in the rules individuals-descendants. Individual-ancestors accumulate mutations that also destroy the symmetry. Symmetry breaking in the genotype causes a disturbance of symmetry in the phenotype.

You can see the manifestation of this symmetry in the phenotype, if the initial state of the machine to fill one cell.

Let’s experiment. To preserve symmetry, the genotype will use the array r. 5% of mutations, mutate 1 gene. In the initial state filled one cell.

30 machines from a random initial population. The status of machines on the 30-th iteration:

Let’s try to identify those that are most slow to develop (grow) from a single cell.





After the first selection got rid of the machines, which do not develop:

In the new population there are several such machines (which do not develop) — it’s an unfortunate descendants and mutants.

Next, we will choose mostly the machines with a white background (cells to which the machine is not developed).

Black machines are flashing.

If the null gene is equal to zero (if surrounded by a black square all black cell remains black) — these machines are developed with the same speed. Machines with this gene (zero zero) does not correspond to our criteria (the lowest speed of development). The number of slots decreases with each selection. If zero, the gene is equal to one on the first (odd) iteration, the background changes to white. Further background can be white or flashing (on an odd iteration — white, even black). The 30th iteration, where we produce selection — even. Getting rid of guns with black background (on the 30-th iteration) — get rid of blinking (once again not to mock our distinguished epileptics).

Population after the second selection:

3 selection:

5 selections:

8 selections:

13 selections:

The same machine at the 60th iteration:

21 selection. The status of machines on the 30-th iteration:

The status of machines on the 60th iteration:

34 selection. The status of machines on the 30-th iteration:

The status of machines on the 60th iteration:

Further, the system does not evolyutsioniruet. Three machine of this population (for 100 iterations):

[1,0,1,1,1,0,0,1,0,0,1,1,0,1,0,1,1,1]

[1,0,1,1,1,0,0,1,0,0,0,1,0,1,0,1,1,1]

[1,0,0,1,1,0,0,1,1,0,1,0,1,1,0,1,1,1]

For comparison, a random machine:

[1,0,0,1,1,1,0,1,1,1,0,0,1,1,0,0,0,1]

4. Machine Conway and others like him (2)

In slot machines with rules Koniavska type, we count the number of survivors (units) of cells in the Moore neighbourhood. This neighborhood can be divided into 4 pairs and counting the number of living cells in these pairs:

Thus, we increase the number of machines, but maintain a symmetry in the phenotype.

In each pair can be from 0 to 2-x of living cells. Par 4. The number of combinations

$3^4=81$

. At the 81st combination living around and around the dead cells. There are

$2^{162}$

machines of this type.

Number:

$2^{162}\approx5.846\times10^{48}$

Quite astronomical and fit for the genetic algorithm.

The size of the genotype of each individual — gene 162:

Fill the population with random machines

var rulesize=162;
for(var n=0;n<PopulationSize;n++){
population[n]=[];
fitness[n]=0; for(var i=0;i<rulesize;i++){
population[n][i]=Math.the round(Math.random());
}
}

Then paint it a rule for all possible combinations of a cell and eight neighboring cells:

Function fillrule();

fillrule function(){ var r; for(var n=0;n<PopulationSize;n++){
rule[n]=[];
r=population[n]; var q1, q2, q3, q4, q5; var q; for(var i=0;i<512;i++){ var ii=i.toString(2); for(var j=ii.length;j<9;j++) ii='0'+ii;
q1=1*ii[4];
q2=1*ii[0]+1*ii[8];
q3=1*ii[1]+1*ii[7];
q4=1*ii[2]+1*ii[6];
q5=1*ii[3]+1*ii[5];
q=parseInt("+q2+q3+q4+q5,3);
if(q1==0)
rule[n][i]=r[q];
else
rule[n][i]=r[q+81];
}
}
}

Array rule we will use in calculating the next state of the automaton. Function fillrule() is called after page load and after the function call evolute().

The initial population looks chaotic. 30 random machines, 1000-th iteration:

This chaos is slightly different in dynamics and machines are quite suitable for selection, but make it simple — we will choose “the dark”.

The population after five selections:

Next, you can look for the machines with the most complex oscillators. The whole process spread is meaningless. Below are some of the most interesting machines, found using a genetic algorithm.

256×256, 10000-I for each iteration. Under the picture is a link, clicking on which, you can look at the machine in movement:


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.


Look in the dynamics.

And to play?

But to play here:

Two-dimensional cellular automata of the second order.

Interface:

The Start button starts the machines.
Stop — stops.
One — one iteration.
Clear — stops the machine and populates the initial state randomized.
Clear (1 cell) — stops the machine and fills one cell in the initial state.
Other buttons in this row, consider the specified number of iterations for each machine.
Drawing machine on the canvas (canvas) eats all performance. If you need to quickly calculate 200 iterations — shake to Count 200. Button Count 5000 not too tight — it may hang the browser.

Below are 20 random machines (population size 200 machines). Under the guns checkboxes. Note the most interesting. Press Select — the adaptation (fitness) of the machine will increase by the number specified on the right side.
Mutations — probability mutations.
Gens is the number of mutating genes.

Start evolution — starts the mechanism of hybridization and mutations.

Fill genotype — fills a specified number of genes in the genotype of each machine.
Conway fills the population with machine guns Koniavska type.

Below two lines:
The numbers shown machines.
The contents of the array fenotype.

The gene pool of the population even lower.

All progress is saved to local storage (Local Storage).

With guns Koniavska type (those discussed in the last article), you can play here:

4. Machine Conway and others like him (2).

Source