Cellular automata introduction

Cellular automata was originally proposed by Von Neumann in the 1950s to simulate the self-replication of biological cells. Cellular automata came to the attention of scientists in 1970 when John Holden Conway of Cambridge University designed a computer game called “The Game of Life”.

S. Wolram published a series of papers in 1983. In this paper, the models generated by 256 rules of elementary cellular machine are studied and their evolution is described by entropy. Cellular automata are classified into stationary, periodic, chaotic and complex types.

Cellular automata (CA) is a method used to simulate local rules and local connections. Cellular automata are typically defined on a grid, where each point represents a cell and a finite state. The change rule applies to each cell and simultaneously. The rules of change typically depend on the state of the cell and the state of its (4 or 8) neighbors.

Change rules for 3 cells & change rules for cell states typically depend on the state of a cell and the states of its (4 or 8) neighbors.

Application of cellular automata Cellular automata has been applied to physical simulation, biological simulation and other fields.

5 Cellular automata MATLAB programming combined with the above, we can understand cellular automata simulation needs to understand three points. One is cellular, which can be understood as a square block composed of one or more points in the matrix in MATLAB. Generally, we use a point in the matrix to represent a cellular. The second is the change rule. The change rule of cellular determines the state of cellular at the next moment. The third is the state of the cell. The state of the cell is self-defined and usually opposite, such as the living state or death state of the creature, the red light or the green light, the point with or without obstacles, and so on.

One dimensional cellular automata — traffic rulesDefinition: 6.1 Cells are distributed on a one-dimensional linear grid. 6.2 Cells have only two states: car and empty. Two-dimensional cellular automata — The Game of lifeDefinition: 7.1 Cells are distributed on a two-dimensional square grid. 7.2 Cells have only two states of life and death.The cellular state is determined by its eight neighbors. Rules:Skull: death; Smiley face: if there are three smiley faces around you, the middle will become smiley face less than two or more smiley faces, and the middle will become death.

What is cellular automata discrete system: cellular is defined in finite time and space, and the state of cellular is finite. Dynamical system: The behavior of cellular automata is characterized by dynamics. Simplicity and complexity: Cellular automata simulate complex worlds by controlling interacting cells with simple rules.

9 Constituent Elements (1) Cell Cell is the basic unit of cellular automata: state: Every cell has the function of memory storage state. Discrete: In the simple case, there are only two possible states of cellular; In more complex cases, cells have multiple states. Update: cellular states are constantly updated according to dynamic rules.(2) LatticeDifferent dimensional gridCommon two-dimensional grid (3) Neighborhood (4) Boundary Reflective: the state with itself as the boundary absorbing: regardless of the boundary (the car disappears when it reaches the boundary)

(5) Rules (State transition function)Definition: The dynamic function of the cellular state at the next moment is determined according to the current state of the cell and its neighbors. Simply speaking, it is a state transfer function. Classification: Summation type: the state of a cell depends on and only depends on the current state of all its neighbors and its own current state. Legal: The sum rule belongs to the legal rule. However, if the rules of cellular automata are limited to summation type, cellular automata will be limited.6. Forest fires Green: trees; Red: fire; Black: empty space. Tree: Becomes fire when there is fire around or when struck by lightning. Open space: with probability P into trees rational analysis: red for fire; Ash is empty space; Green is the treeThe sum of the three states of cell density is 1The density of fire to open space is equal to the density of open space to trees (new trees are equal to burned trees)F is the probability of lightning: much less than the probability of tree generation; T smax T_{smax}T smax is the time scale for a whole bunch of trees to burnProgram implementationPeriodic boundary condition purchasesThe numbers are numbered to construct the neighbor matrixThe numbers in the above matrix correspond to the upper neighbor numbers of the same position numbers of the original matrix, and 1 and 1 correspond to the same principle: (7) Transportation conceptDistance and densityFlow equationConservation equationSpacetime trajectory (horizontal axis is space and vertical axis is time)The intersection of the red line and the blue line indicates the position of the car at each time. If it’s a vertical line, it’s the time the car was in that position

Macro continuous model:The most commonly used rules:The red bar means the velocity is full.

1 Acceleration rule: do not exceed v max (2 grids /s) v_{Max} (2 grids /s) v Max (2 grids /s) 2 Collision prevention: do not exceed the vehicle distance

Theoretical analysis:Result analysis: density and flowThe first graph: the abscissa is the normalized density, and the ordinate is the traffic flow. Second figure: theoretical value versus CA result

Result analysis: space-time trajectoryThe dark area in the middle is a traffic jam.

Two, some source code

CLC clear all close all %% data=[CLC clear all close all %%102    0      0  inf 0; % % the first layer65  1150      0  inf 0 ;
    16  1150  - 2780.   63 4 ;
    66  6850      0  inf 0 ;
    17  6850  - 2780.   63 4 ;
    67  9220      0  inf 0 ;
    18  9220  - 2770.   63 4 ;
    68  13020     0  inf 0 ;
    11  13020  2960   60 0 ;
    69  15020     0  inf 0 ;
    19  15020 - 2710.   72 4 ;
    70  18480     0  inf 0 ;
    20  18480 - 2710.   72 4 ;
    71  21100     0  inf 0 ;
    72  24180     0  inf 0 ;
    21  24180 - 2710.   72 4 ;
    73  27640     0  inf 0 ;
    22  27640 - 2710.   72 4 ;
    74  33040     0  inf 0 ;
    23  33040 - 2710.   72 4 ;
    104  34770    0  inf 0 ;
    52  6850   6960  inf 0; % % the second floor2   6850   9340   68 4 ;
    51  5150   6960  inf 0 ;
    9   5150   4160   33 0 ;
    50  3100   6960  inf 0 ;
    8   3100   4000   69 4 ;
    49  1470   6960  inf 0 ;
    101 0      6960  inf 0;
    1   1470   9340   68 4 ;
    53  10110  6960  inf 0 ;
    10  10110  3920   75 4 ;
    54  11060  6960  inf 0 ;
    3   11060  9780   68 4 ;
    55  13030  6960  inf 0 ;
    4   13030  9640   44 0 ;
    56  16160  6960  inf 0 ;
    12  16160  4120   75 4 ;
    57  18540  6960  inf 0 ;
    47  18540 10670   12 0 ;
    58  19260  6960  inf 0  ;
    59  21670  6960  inf 0 ;
    13  21670  4120   75 4 ;
    60  22340  6960  inf 0 ;
    5   22340  9670   72 4 ;
    61  25800  6960  inf 0 ;
    6   25800  9670   72 4 ;
    62  27370  6960  inf 0 ;
    14  27370  4120   75 4 ;
    63  30130  6960  inf 0 ;
    7  30130  9730   72 4 ;
    64  31500  6960  inf 0 ;
    15  31500  4160   69 4 ;
    103  33230  6960  inf 0 ;
    25  6850  13360   68 4; % the fourth floor78  6850  10980  inf 0 ;
    77  5150  10980  inf 0 ;
    32  5150   8180   33 0 ;
    76  3100  10980  inf 0 ;
    31  3100   8020   69 4 ;
    75  1470  10980  inf 0 ;
    24  1470  13360   68 4 ;
    105    0  10980  inf 0 ;
    79  10110 10980  inf 0 ;
    33  10110  7940   75 4 ;
    80  11060 10980  inf 0 ;
    26  11060 13800   68 4 ;
    81  13030 10980  inf 0 ;
    27  13030 13660   44 0 ;
    82  16160 10980  inf 0 ;
    35  16160  8140   75 4 ;
    48  18540 12870   12 0; % % the stairs83  18540 10980  inf 0 ;
    84  19260 10980  inf 0  ;
    85  21670 10980  inf 0 ;
    36  21670  8140   75 4 ;
    86  22340 10980  inf 0 ;
    28  22340 13690   72 4 ;
    87  25800 10980  inf 0 ;
    29  25800 13690   72 4 ;
    88  27370 10980  inf 0 ;
    37  27370  8140   75 4 ;
    89  30130 10980  inf 0 ;
    30  30130 13750   72 4 ;
    90  31500 10980  inf 0 ;
    38  31500  8180   69 4 ;
    107  33230 10980  inf 0 ;
    106    0   4020  inf 0; % % the third floor91  1150   4020  inf 0 ;
    39  1150   1240   63 4 ;
    92  6850   4020  inf 0 ;
    40  6850   1240   63 4 ;
    93  9220   4020  inf 0 ;
    41  9220   1240   63 4 ;
    94  13020  4020  inf 0 ;
    34  13020  6980   60 0 ;
    95  15020  4020  inf 0 ;
    42  15020  1310   72 4 ;
    96  18480  4020  inf 0 ;
    43  18480  1310   72 4 ;
    97  21100  4020  inf 0 ;
    98  24180  4020  inf 0 ;
    44  24180  1310   72 4 ;
    99  27640  4020  inf 0 ;
    45  27640  1310   72 4 ;
    100 33040  4020  inf 0 ;
    46  33040  1310   72 4 ;
    108  34770 4020  inf 0; ] ; %% The first column is the starting point, the second column is the end point, the third column is the length, the fourth column is the channel capacity, the fifth column is the number of passage at each step, the sixth column is the number of current passage, % the seventh column is the number of passage at the current moment, the eighth column is the number and the ninth column is the channel area R=[65 102 1150 4  2  0 0 101 1; The first layer %16  65 2780 8  2  0 0  16 2
    66  65 5700 29 3  0 0  65 8
    66  17 2780 8  2  0 0  17 2
    66  67 2370 12 3  0 0  66 3
    18  67 2770  8 2  0 0  18 2
    68  67 3800 19 3  0 0  67 5
    11  68 2960  7 2  0 0  11 2
    69  68 2000 10 3  0 0  68 3
    19  69 2710  8 3  0 0  19 2
    70  69 3460 17 3  0 0  69 5
    20  70 2710 8  3  0 0  20 2
    70  71 2620 22 2  0 0  70 4
    72  71 3080 15 3  0 0  71 4
    21  72 2710 8  3  0 0  21 2
    73  72 3460 17 3  0 0  72 5
    22  73 2710  8 3  0 0  22 2
    74  73 5400 27 3  0 0  73 8
    23  74 2710  8 3  0 0  23 2
    74 104 1730  6 2  0 0 103 2
    49 101 1470  5 2  0 0 100 1The second floor %1  49  2380  8 2  0 0   1 2
    49 50  1630  8 3  0 0  49 2
    8  50  2960  8 2  0 0   8 2
    51 50  2050 10 3  0 0  50 3
    9  51  2800 8  2  0 0   9 2
    52 51  1700 10 3  0 0  51 2
    2  52  2380 8  2  0 0   2 2
    52  66 6960 35 2  0 0 109 2
    53  52 3260 15 3  0 0  52 5
    10  53 3040  9 2  0 0  10 2
    54  53 950   6 3  0 0  53 1
    3   54 2820  8 2  0 0   3 2
    55  54 2920 16 2  0 0  54 4
    4   55 2680  8 2  0 0   4 2
    56  55 3130 16 3  0 0  55 4
    12  56 2840  8 2  0 0  12 2
    57  56 2380 12 3  0 0  56 3
    47  57 3710 10 2  0 0  47 3
    58  57 720   4 3  0 0  57 1
    71  58 6960 35 3  0 0  59 10
    59  58 2410 12 3  0 0  58 3
    13  59 2840  8 2  0 0  13  2
    60  59 670   3 2  0 0  60  1
    5   60 2710  8 2  0 0   5  2
    61  60 3460 17 3  0 0  61  5
    6   61 2710  8 2  0 0   6  2
    61  62 1570  8 3  0 0  62  2
    62  63 2760 14 3  0 0  63  4
    14  62 2840 8  2  0 0  14  2
    7   63 2760 8  2  0 0  7   2
    64  63 1370  7 3  0 0  64  2
    15  64 2800  8 2  0 0  15  2
    64 103 1730  6 2  0 0  102 2
    91 106 1150 4  2  0 0  105 1; % the third layer39  91 2780 8  2  0 0  39  2
    92  91 5700 29 3  0 0  91  8
    40  92 2780 8  2  0 0  40  2
    93  92 2370 12 3  0 0  92  3
    41  93 2770  8 2  0 0  41  2
    93  94 3800 19 3  0 0  93  5
    34  94 2960  7 2  0 0  34  2
    94  95 2000 10 3  0 0  94  3
    42  95 2710  8 3  0 0  42  2
    96  95 3460 17 3  0 0  95  5
    43  96 2710 8  3  0 0  43  2
    96  97 2620 22 2  0 0  96  4
    97  98 3080 15 3  0 0  97  4
    44  98 2710 8  3  0 0  44  2
    98  99 3460 17 3  0 0  98  5
    45  99 2710  8 3  0 0  45  2
    99 100 5400 27 3  0 0  99  8
    46 100 2710  8 3  0 0  46  2
    100 108 1730  6 2  0 0  107 2
    75 105 1470  5 2  0 0  104 1% of the first4layer24 75  2380  8 2  0 0  24  2
    75 76  1630  8 3  0 0  74  2
    31 76  2960  8 2  0 0  31  2
    77 76  2050 10 3  0 0  75  3
    32 77  2800 8  2  0 0  32  2
    78 77  1700 10 3  0 0  76  2
    25 78  2380 8  2  0 0  25  2
    78 92  6960 35 2  0 0  78 10
    78 79  3260 15 3  0 0  77  5
    33 79  3040  9 2  0 0  33  2
    79 80  950   6 3  0 0  79  1
    26 80  2820  8 2  0 0  26  2
    80 81  2920 16 2  0 0  80  4
    27 81  2680  8 2  0 0  27  2
    81 82  3130 16 3  0 0  81  4
    35 82  2840  8 2  0 0  35  2
    82 83  2380 12 3  0 0  82  3
    48 83  3710 10 2  0 0  48  2
    83 84  720   4 3  0 0  83  1
    84 97  6960 35 3  0 0  85  10
    84 85  2410 12 3  0 0  84  3
    36 85  2840  8 2  0 0  36  2
    85 86  670   3 2  0 0  86  1
    28 86  2710  8 2  0 0  28  2
    86 87  3460 17 3  0 0  87  5
    29 87  2710  8 2  0 0  29  2
    88 87  1570  8 3  0 0  88  2
    88 89  2760 14 3  0 0  89  4
    37 88  2840 8  2  0 0  37  2
    30 89  2760 8  2  0 0  30  2
    89 90  1370  7 3  0 0  90  2
    38 90  2800  8 2  0 0  38  2
    90 107 1730  6 2  0 0 106  2
    47 48  2200  14 3 0 0 108  6   ];
R(:,7) =0; % The seventh column is the current channel number R(:,10) =1400; % channel initial speed D=zeros(108.108);
fa=1; % Ship tilting velocity attenuation factor figure(1)
plot(data(:,2),data(:,3),'bs'.'MarkerSize'.15);
hold on
for i=1:size(data,1)
text(data(i,2),data(i,3),num2str(data(i,1)),'FontSize'.10);

end
for i=1:size(R,1)
    D(R(i,1),R(i,2))=R(i,3); % distance matrix end Kt is equal to1.54;
D(47.48)=D(47.48)*Kt; % fire point path equivalent wc1=0.05;
D(68.69)=D(68.69) * (1+wc1);
D(69.70)=D(69.70) * (1+wc1); % path equivalent wc2= near the fire0.02;
D(67.68)=D(67.68) * (1+wc2);
D(70.71)=D(70.71) * (1+wc2);
D=D+D';
D(find(D==0))=inf ; Will a = %0Mm =sum(data(:,5)); Number nn % =1;
people=zeros(mm,8); % sequence number in column 1, position in column 2, position in column 3, speed in column 4, waiting time in column 5, starting point in column 6, arrival point in column 7, pause time in column 8101 102 103 104 105 106 107 108];

for i=1:size(data,1)
    tt=data(i,5);
    for pp=1:tt
        people(nn,1)=nn; % people(nn,2)=data(i,2); % people(nn,3)=data(i,3); %% initial ordinate people(nn,4) =1400; %% initial speed people(nn,5) =0; % initial wait time people(nn,6)=data(i,1); % starting pointfor j=1:8
            start=people(nn,6); Starting point % [dist (j), the path {nn, j}] = dijkstra (D, start, dest (j)); End [short_dist(nn),indx_path]=min(dist); % determine which exit people(nn,7)=dest(indx_path); % the finish short_path {nn} = path {nn, indx_path}; % short_dist(nn)=dist(indx_path); % records the person's shortest path nn=nn+1;
    end
end
     

Copy the code

3. Operation results

Matlab version and references

1 matlab version 2014A

2 Reference [1] CAI Limei. MATLAB Image Processing — Theory, Algorithm and Case Analysis [M]. Tsinghua University Press, 2020. [2] Yang Dan, ZHAO Haibin, LONG Zhe. Examples of MATLAB Image Processing In detail [M]. Tsinghua University Press, 2013. [3] Zhou Pin. MATLAB Image Processing and Graphical User Interface Design [M]. Tsinghua University Press, 2013. [4] LIU Chenglong. Proficient in MATLAB Image processing [M]. Tsinghua University Press, 2015. [5] MENG Yifan, LIU Yijun. [6] Zhang Na, Liu Kun, Han Meilin, Chen Chen. A PCA-SVM based Face Recognition Method [J]. Science and Technology Vision, 2021,(07) A face recognition algorithm based on PCA and LDA fusion [J]. Electronic measurement technology, 2020,43(13) [7] Chen yan. [8] dai lirong, Chen wanmi, guo sheng. Analysis of face recognition method based on BP neural network [J]. Information and computer (theory edition), 2020,32(23). Research on face recognition based on skin color model and SURF algorithm [J]. Industrial control computer, 2014,27(02)