CA rules of radius 3 evolved with a GA for the Density and AND Tasks

  1. Intro
  2. GA with fitness function computed by AND alone
  3. GA with fitness function computed by AND and Density task.
  4. Evolutionary Considerations


I tried to evolve CA rules with radius 3 which would solve both the density task and the AND task. To implement this last task, I divide the lattice in two halves (the center cell is not used). I consider the first half the first bit, and the second half the second bit. A bit is on if there is a majority of on cells in its half, and off otherwise. So the AND task would be:

0 0 -> 0
1 0 -> 0
0 1 -> 0
1 1 -> 1

I tried a few things.

First of all let me refer to the rule you have previously evolved (0504058705000F77037755837BFFB77F) as Rule 1. It's graphic form is:

Also. P_Dens is the unbiased performance of a rule to the density task, while P_AND is the performance for the AND task. The P_AND is also an unbiased random generation of 10000 IC's. Each cell has 0.5 probability of being on or off. Thus, the probabilities of the each lattice being (0,0), (0,1), (1,0), and (1,1) in terms of the first and second bit halves is 0.25 for each.

P_Dens (rule 1) = 0.77
P_AND (rule 1) = 0.71
Avg = 0.74.

I - GA with fitness function computed by AND alone

I tried to evolve rules that would solve the AND task. Notice that to have good results here one must make sure that each rule is presented with IC's that half the time should lead the final lattice to 0, and the other half to 1. If were to use an unbiased generation of lattices, only 25% of the time would a (1, 1) be generated, making rules that tend to 0 almost always too favorable. This is the case of rule 4: 0B42D6BF647FA7336EFA083C3C599A1F, with space-time patterns of the type:

P_Dens (rule 4): 0.5
P_AND (rule 4): 0.79

Therefore the fitness function of the AND task is biased to a uniform distribution of lattices leading to (0, 0), (0,1), (1,0) 50% of the time, and (1,1) the other 50%. I set up a GA with this fitness function, and injected a few good rules on the first population, including rule 1 and a few others I have evolved. Two interesting rules evolved were:

Rule2: 0504058705000E77037755837AFFB77F, which is almost identical to rule 1, but yields P_Dens(rule 2) = 0.70 and P_And (rule 2) = 0.79, average 0.75.

However, it does evolve a different, similar,  set of particle interactions, more suitable for the AND than the Density task:

But since this GA was evolving rules that solve the AND task alone, this rule did not stick around and was quickly over ruled by rules like Rule 3: 2D0008000000008F77FFBFFF27F7FFFF, with P_Dens(rule 3) = 0.58 and P_AND(Rule 3) = 0.80. This rule is a block expansion rule:


II - GA with fitness function computed by AND and Density task.

So now the cool stuff. Naturally what I am interested is in evolving rules that can solve both tasks well. So I changed the GA for a fitness function that presents 50 IC's to be evaluated by the Density task (the way you did), and 50 IC's with the AND task as discussed above. two rules evolved, observing particle computation, were quite interesting:

Rule 5:  0504058505000D77073755437BFFB77F, P_Dens(Rule 5) = 0.75 and P_AND (rule 5) = 0.77, average 0.76. Which is clearly related to rule 1 but evolves different particle interactions that are suitable for both tasks. It can solve the AND task well wothou sacrificing the density task.

Rule 8: 0504058F050025750337578B7BFFB77F , P_Dens(Rule 6) = 0.77 and P_AND (rule 5) = 0.75, average 0.76. Which has results symmetrical to rule 6.

Now, very interestingly, in these simulations I evolved a rule that solves the density task better than rule 1. Rule 7: 05040587050025770377578B7BFFB77F with P_DEns(Rule 7) = 0.79 and P_AND (Rule 7) = 0.66. It did not stick around because its fitness for the AND task is not very good. But it is VERY good with the density task. Have you evolved this one before? It is clearly related to rule 1.


Other neat rules evolved include Rule 9:  0544058705000E770375554373FF977F, with P_Dens(Rule9) = 0.62 and P_AND (Rule 9) = 0.83, Average = 0.72. This rule has a set of particles that is excellent for the AND task, but not so good for the density task:

It is related to Rule 1, but with a few more differences:


Notice that when rules are evolved with a fitness function designed tol solve both the density and the AND task, it is not an option to come up with rules that tend to 0 a lot. Such rules would have good P_AND, but lousy P_Dens, besides, I defined a fitness function (see I) that avoids such rules.

A few other rules evolved were also interesting, but you can check those out in the text file attached to this.

III - Evolutionary Considerations

I think the results of these runs are quite interesting. First of all they show that there is a family of particle computation rules which with a few mutations can develop a system of particle computation that can solve two different, yet related, tasks. Notice that other rules (e.g. rule 9) can observe good results without particle computation for just one of the tasks. But the particle computation ones seem to have an easier time adapting to a new environment that starts requiring the solution of two tasks.

It is also interesting to note that the evolution of rules that can solve the two tasks evolved rule 7 which is excellent for the density task, and rule 9 which is excellent for the AND task.

Regarding what we discussed earlier, it is great to note that the particle computation system can evolutionarily adapt to perform more complicated computations that require the solution of two similar but distinct tasks. There is clearly evolutionary advantage to this adaptation potential. Furthermore, solving different tasks makes the case that these particles set up a proper syntax stronger.

Now I should try to evolve other logical gates. I want to incorporate these results into the paper I gave you eventually. Let me know what you think.

Intersting Rules:

# Rule P_Dens P_AND Avg. File Notes

1 - 0504058705000F77037755837BFFB77F 0.77 0.71 0.74 rule1.txt Original Particle

2 - 0504058705000E77037755837AFFB77F 0.70 0.79 0.75 rule2.txt particle (popped up in the same run of 3 but did not stick because it was evolved with AND alone)

3 - 2D0008000000008F77FFBFFF27F7FFFF 0.58 0.80 0.69 rule3.txt block exp with dif boundaries. Evolved with AND alone with good rules from dens injected at start (tends to all 0)

4 - 0B42D6BF647FA7336EFA083C3C599A1F 0.50 0.79 0.65 rule4.txt Tends to 0 always. Evolved with AND only and random initial pop.

5 - 0504058505000D77073755437BFFB77F 0.75 0.77 0.76 rule5.txt Particle. Evolved with both AND/Density.

6 - 0500058705000777037757817BFFB77F 0.70 0.80 0.75 rule6.txt Particle. Evolved with both AND/Density. Much better for AND.

7 - 05040587050025770377578B7BFFB77F 0.79 0.66 0.73 rule7.txt Particle. Evolved with both AND/Density. Solves Density REALLY well, not so good for AND.

8 - 0504058F050025750337578B7BFFB77F 0.77 0.75 0.76 rule8.txt Particle. Evolved with both AND/Density. Good for both. Simetrical with 5.

9 - 0544058705000E770375554373FF977F 0.62 0.83 0.72 rule9.txt particle. Evolved with both AND/Density. Very Good for AND, VERY bad for Density.

10 - 05000587050007570373758B7BFFB77F 0.73 0.79 0.76 rule10.txt particle. Evolved with both AND/Density. Good average.

11 - 05000587250007770373158B7BFFB77F 0.74 0.77 0.76 rule11.txt Particle. Evolved with both AND/Density.

12 - 0504058301020F7F037755A37BFFB37F 0.74 0.77 0.75 rule12.txt Particle. Evolved with both AND/Density.

13 - 0504058705000F77037555837BFFA77F 0.71 0.80 0.75 rule13.txt Particle. Evolved with both AND/Density.

14 - 050405C705000F77017755837BBFB77F 0.74 0.79 0.76 rule14.txt Particle. Evolved with both AND/Density.

15 - 050405C705000F77077755C13BFFB77F 0.77 0.67 0.72 rule15.txt Particle. Evolved with both AND/Density. Very Good for Density Task.

16 - 0504058704000F73037755937BFFF77F 0.76 0.77 0.77 rule16.txt Particle. Evolved with both AND/Density. Very Good for Both.

17 - 0504258704000F73077755937BFFF77F 0.78 0.60 0.69 rule17.txt Particle. Evolved with both AND/Density. Very Good for Density.

18 - 0504059505001F7F037455833BFFF77F 0.78 0.72 0.75 rule18.txt Particle. Evolved with both AND/Density. Very Good for Density and Not bad for AND.