194 Agent-Based Modeling and Simulation with Swarm
TABLE 7 .5: Self-reproducing loop transition rules
0 0 000 0 0 0001 2 0 0002 0 0 0003 0 0 000 5 0
0 0 006 3 0 0007 1 0 0011 2 0 0012 2 0 001 3 2
0 0 021 2 0 0022 0 0 0023 0 0 0026 2 0 002 7 2
0 0 032 0 0 0052 5 0 0062 2 0 0072 2 0 010 2 2
0 0 112 0 0 0202 0 0 0203 0 0 0205 0 0 021 2 5
0 0 222 0 0 0232 2 0 0522 2 0 1232 1 0 124 2 1
0 1 252 5 0 1262 1 0 1272 1 0 1275 1 0 142 2 1
0 1 432 1 0 1442 1 0 1472 1 0 1625 1 0 172 2 1
0 1 725 5 0 1752 1 0 1762 1 0 1772 1 0 252 7 1
1 0 001 1 1 0006 1 1 0007 7 1 0011 1 1 001 2 1
1 0 021 1 1 0024 4 1 0027 7 1 0051 1 1 010 1 1
1 0 111 1 1 0124 4 1 0127 7 1 0202 6 1 021 2 1
1 0 221 1 1 0224 4 1 0226 3 1 0227 7 1 023 2 7
1 0 242 4 1 0262 6 1 0264 4 1 0267 7 1 027 1 0
1 0 272 7 1 0542 7 1 1112 1 1 1122 1 1 112 4 4
1 1 125 1 1 1126 1 1 1127 7 1 1152 2 1 121 2 1
1 1 222 1 1 1224 4 1 1225 1 1 1227 7 1 123 2 1
1 1 242 4 1 1262 1 1 1272 7 1 1322 1 1 222 4 4
1 2 227 7 1 2243 4 1 2254 7 1 2324 4 1 232 7 7
1 2 425 5 1 2426 7 1 2527 5 2 0001 2 2 000 2 2
2 0 004 2 2 0007 1 2 0012 2 2 0015 2 2 002 1 2
2 0 022 2 2 0023 2 2 0024 2 2 0025 0 2 002 6 2
2 0 027 2 2 0032 6 2 0042 3 2 0051 7 2 005 2 2
2 0 057 5 2 0072 2 2 0102 2 2 0112 2 2 012 2 2
2 0 142 2 2 0172 2 2 0202 2 2 0203 2 2 020 5 2
2 0 207 3 2 0212 2 2 0215 2 2 0221 2 2 022 2 2
2 0 227 2 2 0232 1 2 0242 2 2 0245 2 2 025 2 0
2 0 255 2 2 0262 2 2 0272 2 2 0312 2 2 032 1 6
2 0 322 6 2 0342 2 2 0422 2 2 0512 2 2 052 1 2
2 0 522 2 2 0552 1 2 0572 5 2 0622 2 2 067 2 2
2 0 712 2 2 0722 2 2 0742 2 2 0772 2 2 112 2 2
2 1 126 1 2 1222 2 2 1224 2 2 1226 2 2 122 7 2
2 1 422 2 2 1522 2 2 1622 2 2 1722 2 2 222 7 2
2 2 244 2 2 2246 2 2 2276 2 2 2277 2 3 000 1 3
3 0 002 2 3 0004 1 3 0007 6 3 0012 3 3 004 2 1
3 0 062 2 3 0102 1 3 0122 0 3 0251 1 4 011 2 0
4 0 122 0 4 0125 0 4 0212 0 4 0222 1 4 023 2 6
4 0 252 0 4 0322 1 5 0002 2 5 0021 5 5 002 2 5
5 0 023 2 5 0027 2 5 0052 0 5 0202 2 5 021 2 2
5 0 215 2 5 0222 0 5 0224 4 5 0272 2 5 121 2 2
5 1 222 0 5 1242 2 5 1272 2 6 0001 1 6 000 2 1
6 0 212 0 6 1212 5 6 1213 1 6 1222 5 7 000 7 7
7 0 112 0 7 0122 0 7 0125 0 7 0212 0 7 022 2 1
7 0 225 1 7 0232 1 7 0252 5 7 0272 0
Cellular Automata Simulation 195
FIGURE 7.10: Self-replicating loop of Langton.
The Swarm implementation of the Langton loop on the two-dimensional
FoodSpace grid contains eight types o f bait, while only bug is updated. How-
ever, state [ ] store s (5 digit number) the current state (own state and 4
neighbors’ states). The array that represents the next sta te is nextstate[ ].
Here, if the current state is represented by x (5 digit number),
state[i]==x
finds i, and the next s tate x_next is dec ided as follows:
x_next = nextstate[i]
This process is ex e c uted by the method getRuleArrayValue, as shown below,
inside Bug.java.
private int getRuleArrayValue(int v[]){
int val=-1;
int i;
int index=getMinIndex(v);
index+=v[0]*10000;
for(i=0;i<state.length;i++){
if(state[i]==index){
val = nextstate[i];
break;
}
}
return val;
}
However, getMinIndex is a process to implement the transition rule shown in
Table 7.5 and it is alright if it matches any of the 4 directions, in a clockwise
direction. The colors of 8 states are defined as below in buildObjects of
ObserverSwarm.java.
196 Agent-Based Modeling and Simulation with Swarm
colorMap=new ColormapImpl(this);
colorMap.setColor$ToName((byte)0,"black");
colorMap.setColor$ToName((byte)1,"red");
colorMap.setColor$ToName((byte)2,"green");
colorMap.setColor$ToName((byte)3,"red");
colorMap.setColor$ToName((byte)4,"red");
colorMap.setColor$ToName((byte)5,"red");
colorMap.setColor$ToName((byte)6,"red");
colorMap.setColor$ToName((byte)7,"red");
In other words, state 0 is black, state 2 is green, and all others are being
turned red.
7.3 Program that replicates itself
Making a prog ram that outputs its source code looks easy but is a very
difficult problem. In particular, care is necessary in treating newline characters
and spaces. The following is an example of a self-replicating code in C.
#include <stdio.h>
char *s="#include <stdio.h>%cchar *s=%c%s%c;main(){printf(s,10,34,s,34,10);return 0;}%c";main(){printf(s,10,34,s,34,10);return 0;}
Character strings are used effectively. There should be no carelessly in-
serted newline characters in this code: when a newline character is inserted,
the code must be changed to output this additional newline character. Note
that 10 and 34 in ASCII code are the newline and " characters, respectively.
Therefore, executing printf(s,10,34,s,34,10); in the main function prints
the first and second lines of the code.
To confirm that the ab ove is a self-replicating code, copy the above file
as a source file such as ev.c and ex e c ute the following. You can confirm that
the output file and the source c ode are the same (it is recommen ded that you
use the diff command that displays the differe nce between two files). The
following is an example of how the self-replicating code is executed.
iba@fs(~/tmp)[514]: cat ev.c
#include <stdio.h>
char *s="#include <stdio.h>%cchar *s=%c%s%c;main(){printf(s,10,34,s,34,10);return 0;}%c";main(){printf(s,10,34,s,34,10);return 0;}
iba@fs(~/tmp)[515]: gcc ev.c
iba@fs(~/tmp)[516]: ./a.out > ev2.c
iba@fs(~/tmp)[517]: diff ev.c ev2.c
It is also possible to compile code that outputs its source code in languages
other than C. For example, the following line in Lisp which is us e d in artificial
intelligence,
(setf f ’(lambda (x) ‘(,x ’,x)))
Cellular Automata Simulation 197
results in self-replication. The famous computer scientist Knuth said the fol-
lowing in his lecture after receiving the Turing award, the e quivalent of the
Nob e l Prize in computer science [74, p. 672]:
Some years a go the students at Stanford were excited about finding
the shortest FORTRAN pro gram which prints itself out, in the
sense that the program’s output is identical to its own source text.
The same problem was considered for many other languages. I
don’t think it was a waste of time for them to work on this.
7.4 Simulating forest fires with Swarm
Simulations based on CA are applied in various fields such as the following:
• Life sciences, especially in heredity, immunity, e c ological formation
• Prediction of freeway congestion (silicon traffic)
• Disasters: mar ine pollution from o il spills, for e st fire s
• Materials and manufacturing
• Fractal formation
These simulations are considered to be an effective method for observing crit-
ical behavior in pha se transitions.
This section is on the simulation of disasters. The area over which a forest
fire can spread depends o n the percentage of empty space with no trees. A
CA model can therefore be used to observe the ratio between the percentage
of empty space and the affected area.
The forest fire model uses CA and follows these rules:
(1) There are three states: trees, fire, and empty space.
(2) Trees can grow on empty space with a fixed probability.
(3) Trees catch fire w ith a fixed probability.
(4) Fire extends to neighboring trees.
(5) There will be no fire on an empty space.
(6) Spaces will be empty after the fire.
This simple model can show how a fire will spread.
The following is a spe c ific algo rithm used in a forest fire model. Cells on
a square lattice can be either trees (value 1), trees on fire (value 2), or empty
space (value 0). All cells are updated under the following rules:
198 Agent-Based Modeling and Simulation with Swarm
• If the cell has trees:
– It will catch fire with probability (1 − g) if at least one adjacent
cell is on fire.
– It will catch fire with probability f ×(1 −g) if no adjacent cells are
on fire.
• A cell on fire will become an empty spac e .
• Empty space will become tr e e s with probability p.
Here, the parameters are the probability of catching fire f, immunity g, and
the probability of tree growth p. The following parameter values are used:
probability of catching fire f = 0, immunity g = 0.01, and probability of tree
growth p = 0. Figure 7.1 1 shows the a rea of fo rest fire with respect to various
percentages F of area with trees in the forest before the fire starts. Red cells
are fire, green cells are trees, and black cells are empty space in the figure .
The large black area indica tes the burned area.
The experiments showed that the fire spread over the entire forest when
F > 0.59 and did not when F < 0.59. Threshold values such as F = 0.59
are called critical values and are important parameters in the simulation of
complex systems.
7.4.1 Simulation of forest fires
A forest fire model is simulated using Swarm. Here, the intermediate
state is newly defined by extending the model of the three traditional states
(trees/wood, fire, nothing). In other words, a total of seven states—three states
of fire and forest each and a state of nothing—are take n to simulate a more
complex model.
The definition of fire and states, a nd the list of parameters used are shown
in Tables 7.6 and 7.7, re sp e c tively. If we assume our own cell state of “state”
of four neighboring cells as N1, N2, N3, N4 and the random number in the
range [0,1] is “rand,” then the rules of fire will be as follows:
if (state=0 & rand<grow1) then state=1
if (state=1 & rand<grow2) then state=2
if (state=2 & rand<grow3) then state=3
if (state=4 & rand<cool1) then state=5
if (state=5 & rand<cool2) then state=6
if (state=6 & rand<cool3) then state=0
if (state=3 & rand<fire) then state=4
if (state=3 &
(N1=4 or N2=4 or N3=4 or N4=4) & rand<diffuse)
then state=4
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.