Problem
This onedimensional cellular automaton consists of n (here n = 20) cells arranged in a horizontal line with the leftmost being cell 0. Each cell i has two neighbors: a left one l(i) and a right one r(i). The left neighbor of cell 0 is cell n– 1, and the right neighbor of cell n– 1 is cell 0.
At each point in time, each cell is either alive or dead. To start up the cellular automaton, we just need to decide which cells will be alive and which one will be dead at time t = 0. Then to run it, we simply apply a set of rules (see Figure 1) over and over again.
For example, Rule 1 says: if a cell i and its two neighbors are dead in time period t then the cell i is also dead in time period t + 1. The first application of the rule set determines the states of the cells at time period t = 1. The second application determines the states of the cells at time period t = 2. And so on. In the example pattern (see Figure 2), cell 0 is alive at time 1 because of Rule 3, which states that if cell i is alive at time t and cells l(i) and r(i) are dead at time t, then cell i must be alive at time t + 1. Cell 1 is dead at time 1 due to Rule 6, and cell 2 is alive at time 1 due to Rule 7, etc. Hence, if the starting pattern at period 0 is given, then the live of each cell can be deterministically calculated from period to period just by applying the predefined rules.
The problem is to find an initial assignment of states (alive or dead) for each cell (at time t = 0) that maximizes the average vitality of the cellular automaton over a given time interval [0,m – 1] (here m = 11). (The vitality of a cell over a time interval is the fraction of the time it is alive; the average vitality of the cellular automaton over a time interval is the average of all cells’ vitalities over that time interval.) The average vitality of automaton in Figure 2 is 50%. The problem was described in [3] and [2].
Modeling Steps

We introduce a binary variable x_{i,t} for each cell i ∈{0,…,n–1} in the time interval t ∈{0,…,m – 1}. x_{i,t} is 1 (true) if the cell i in time period t is alive, and 0 if the cell is dead.

For each of the eight rule we introduce a constraint. Rule 1, for example, says that, if the cells x_{l(i),t}, x_{i,t}, and x_{r(i),t} are all dead then cell x_{i,t+1} is also dead. This can be formulated as a Boolean expression as :

The second rule says, if a cell and its right neighbor are dead but the left neighbor is alive in period t then the cell is alive in period t + 1 :

All the rules have the same structure. So it is easy to derive the other rules from this structure: If a cell is alive we use x, if it is dead we use ¬x.

We want to maximize the number of cells to be alive over the given time interval, hence:
Solution
The automaton with the highest average vitality given the 8 rules is displayed in Figure 3. It has a average vitality of 60%.
Further Comments
The LPL syntax x[(n+i1)%n,t] expresses x_{l(i),t}, l(i) being the left cell of cell i on a given time period t. This wraps the horizontal line. The LPL syntax x[(i+1)%n,t] expresses x_{r(i),t}, r(i) being the right cell of cell i on a given time period t.
model Cells "Maximizing Vitality";
parameter n:=20 "number of cells";
m:=11 "time periods";
set i := 0..n1;
t := 0..m1;
parameter r0{i}:=[1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0];
binary variable x{i,t};
constraint
R1{i,tt<m1}: ~x[(n+i1)%n,t] and ~x[i,t] and ~x[(i+1)%n,t] > ~x[i,t+1];
R2{i,tt<m1}: x[(n+i1)%n,t] and ~x[i,t] and ~x[(i+1)%n,t] > x[i,t+1];
R3{i,tt<m1}: ~x[(n+i1)%n,t] and x[i,t] and ~x[(i+1)%n,t] > x[i,t+1];
R4{i,tt<m1}: ~x[(n+i1)%n,t] and ~x[i,t] and x[(i+1)%n,t] > x[i,t+1];
R5{i,tt<m1}: x[(n+i1)%n,t] and x[i,t] and ~x[(i+1)%n,t] > ~x[i,t+1];
R6{i,tt<m1}: x[(n+i1)%n,t] and ~x[i,t] and x[(i+1)%n,t] > ~x[i,t+1];
R7{i,tt<m1}: ~x[(n+i1)%n,t] and x[i,t] and x[(i+1)%n,t] > x[i,t+1];
R8{i,tt<m1}: x[(n+i1)%n,t] and x[i,t] and x[(i+1)%n,t] > ~x[i,t+1];
FIXROW0{i}: x[i,0] = r0;
H1{i,tt<m1}: x[(i1)%n,t] + x[i,t] + x[i,t+1] + x[(i+1)%n,t] <= 3;
H2{i,tt<m1}: x[(i1)%n,t] + x[(i+1)%n,t] + x[i,t+1] <= 2;
H3{i,tt<m1}: x[(i1)%n,t] + x[i,t] + x[i,t+1] <= 2;
maximize obj: sum{i,t} x;
Draw.Scale(40,40);
Draw.Rect(0,0,n,m,1,0);
{i} Draw.Text(i&'',i+.3,.1);
{t} Draw.Text(t&'',.5,t+.6);
{i} Draw.Line(i,0,i,m);
{t} Draw.Line(0,t,n,t);
{i,tx} Draw.Circle(i+.5,t+.5,.5):
Draw.Text('Vitality: '&(100*Round(obj/m/n,4))&'%',0,m+.6);
end
If we only want to calculate the vitality of a given automaton (with a predefined first row) then we add a parameter and a constraint as follows:
parameter r0{i}:=[1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0];
constraint FIXROW0{i}: x[i,0] = r0;
The code generates exactly the automaton in Figure 2. Interestingly, Gurobi finds the solution very quickly.
This suggests a method to find a high average vitality for larger automatons: Generate randomly or in a systematic way (for example using Genetic Algorithms) the first row, run the model to find the average vitality, and repeat. Store the automaton with the highest vitality.
It is also possible to add constraint to help the solver finding solution faster. For example, from the 8 rules above, one can derive to following constraints:
One may add these constraints to the model. They may or may not help the solver the find solution faster. In our case, they definitely help Gurobi 6.0 to find the solution much faster.
Questions

Implement a heuristic for larger automaton with high vitality.
Answers

The paper [3] proposed a geneticbased heuristic as indicated above.
References
[1] MatMod. Homepage for Learning Mathematical Modeling : https://matmod.ch.
[2] Bosch R. Mind Sharpener. OPTIMA MPS Newsletter, January 2000.
[3] Bosch R. Maximizing Vitality. OPTIMA MPS Newsletter, March 1999.
[4] Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.