MatMod logo

Maximizing Vitality (cells)

Run LPL Code  ,  PDF Document

Problem

This one-dimensional 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 n1, and the right neighbor of cell n1 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.


PIC

Figure 1: The 8 Rules for the Automaton


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.


PIC

Figure 2: The Cellular Automaton for 11 Periods


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

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

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

    ¬xl(i),t ∧ ¬xi,t ∧ ¬xr(i),t → ¬xi,t+1   forall i,t < m - 1
  3. 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 :

    xl(i),t ∧ ¬xi,t ∧ ¬xr(i),t → xi,t+1   forall i,t < m  - 1
  4. 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.

  5. We want to maximize the number of cells to be alive over the given time interval, hence:

       ∑ max   xi,t    i,t

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+i-1)%n,t] expresses xl(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 xr(i),t, r(i) being the right cell of cell i on a given time period t.

Listing 1: The Complete Model implemented in LPL [4]

model Cells "Maximizing Vitality"; 
  parameter n:=20 "number of cells"; 
            m:=11 "time periods"; 
  set i := 0..n-1; 
      t := 0..m-1; 
  --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,t|t<m-1}: ~x[(n+i-1)%n,t] and ~x[i,t] and ~x[(i+1)%n,t] -> ~x[i,t+1]; 
    R2{i,t|t<m-1}:  x[(n+i-1)%n,t] and ~x[i,t] and ~x[(i+1)%n,t] ->  x[i,t+1]; 
    R3{i,t|t<m-1}: ~x[(n+i-1)%n,t] and  x[i,t] and ~x[(i+1)%n,t] ->  x[i,t+1]; 
    R4{i,t|t<m-1}: ~x[(n+i-1)%n,t] and ~x[i,t] and  x[(i+1)%n,t] ->  x[i,t+1]; 
    R5{i,t|t<m-1}:  x[(n+i-1)%n,t] and  x[i,t] and ~x[(i+1)%n,t] -> ~x[i,t+1]; 
    R6{i,t|t<m-1}:  x[(n+i-1)%n,t] and ~x[i,t] and  x[(i+1)%n,t] -> ~x[i,t+1]; 
    R7{i,t|t<m-1}: ~x[(n+i-1)%n,t] and  x[i,t] and  x[(i+1)%n,t] ->  x[i,t+1]; 
    R8{i,t|t<m-1}:  x[(n+i-1)%n,t] and  x[i,t] and  x[(i+1)%n,t] -> ~x[i,t+1]; 
    --FIXROW0{i}: x[i,0] = r0; 
    H1{i,t|t<m-1}:  x[(i-1)%n,t] + x[i,t] + x[i,t+1] + x[(i+1)%n,t] <= 3; 
    H2{i,t|t<m-1}:  x[(i-1)%n,t] + x[(i+1)%n,t] + x[i,t+1] <= 2; 
    H3{i,t|t<m-1}:  x[(i-1)%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,t|x} Draw.Circle(i+.5,t+.5,.5): 
  Draw.Text('Vitality: '&(100*Round(obj/m/n,-4))&'%',0,m+.6); 
end

PIC

Figure 3: The Optimal Cellular Automaton


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:

x [l(i),t] + x[i,t] + x [i,t + 1] + x[r(i),t] <= 3  forall i,t < m - 1 x [l(i),t] + x[r(i),t] + x [i,t + 1] <= 2  forall i,t < m - 1 x [l(i),t] + x[i,t] + x [i,t + 1] <= 2  forall i,t < m - 1

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

  1. Implement a heuristic for larger automaton with high vitality.

Answers

  1. The paper [3] proposed a genetic-based 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.