## 1, Introduction to cellular automata

Development of cellular automata

The original cellular automata was proposed by von Neumann in the 1950s to simulate the self replication of biological cells, but it has not been paid attention to by the academic community

In 1970, after John Horton Conway of Cambridge University designed a computer game "life game", cellular automata attracted the attention of scientists

In 1983, S.Wolfram published a series of papers. The models generated by 256 rules of elementary cellular machines were deeply studied, and their evolution behavior was described by entropy. Cellular automata were divided into stationary type, periodic type, chaotic type and complex type

2. Preliminary understanding of cellular automata

Cellular automata (CA) is a method used to simulate local rules and local connections. A typical cellular automata is defined on a grid. The grid at each point represents a cell and a finite state. The change rule applies to each cell and is performed simultaneously. Typical change rules depend on the state of the cell and the state of its (4 or 8) neighbors.

The change rule of 3-cell & cell state

Typical change rules depend on the state of the cell and the state of its (4 or 8) neighbors.

Application of 4-cellular automata

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

matlab programming of 5-cell cellular automata

Combined with the above, we can understand that cellular automata simulation needs to understand three points. One is cell. In matlab, it can be understood as a square block composed of one or more points in the matrix. Generally, we use a point in the matrix to represent a cell. The second is the change rule, which determines the state of the cell at the next moment. The third is the state of cells. The state of cells is user-defined and usually opposite, such as the living state or death state of organisms, red light or green light, obstacles or no obstacles at this point, etc.

6 one dimensional cellular automata -- traffic rules

definition:

6.1 cells are distributed on one-dimensional linear grid

6.2 cells have only two states: car and empty

7 two dimensional cellular automata -- life game

definition:

7.1 cells are distributed on two-dimensional square grid

7.2 cells have only two states of life and death

The cellular state is determined by the surrounding eight neighbors

Rules:

Skeleton: death; Smiling face: survival

If there are three smiling faces around, the middle becomes a smiling face

Less than two smiling faces or more than three, the middle becomes death.

8 what is cellular automata

Discrete system: cell is defined in finite time and space, and the state of cell is finite

Dynamic system: the behavior of cellular automata has dynamic characteristics

Simplicity and complexity: cellular automata uses simple rules to control interacting cells to simulate a complex world

9 constituent elements

(1) Cell

Cell is the basic unit of cellular automata:

State: each cell has the function of memory storage state

Discrete: in simple cases, there are only two possible states of cells; In complex cases, cells have many states

Update: the state of the cell is constantly updated according to the dynamic rules

(2) Mesh (Lattice)

Different dimensional grid

Common 2D mesh

(3) Neighbors

(4) Boundary

Reflective: a state with itself as a boundary

Absorption type: regardless of the boundary (the car disappears when it reaches the boundary)

(5) Rule (state transition function)

Definition: determine the dynamic function of the cell state at the next time according to the current state of the cell and its neighbors. In short, it is a state transition function

Classification:

Summation: the state of a cell depends on and only depends on the current state of all its neighbors and its own current state

Legitimacy: summation rules belong to legitimacy rules. However, if the rules of cellular automata are limited to summation, cellular automata will have limitations

(6) Forest fire

Green: trees; Red: fire; Black: open space.

Three state cycle transitions:

Tree: when there is fire around or struck by lightning, it becomes fire.

Open space: change into trees with probability p

Rational analysis: red is fire; Ash is open space; Green is a tree

The density sum of the three states of the cell is 1

The density of fire into open space is equal to the density of open space into trees (newly grown trees are equal to burned trees)

f is the probability of lightning: far less than the probability of tree generation; T s m a x T_{smax}T smax

It's a time scale for a large group of trees to be burned

Program implementation

Periodic boundary conditions

Buy

The number is number

Building neighbor matrix

The number in the above matrix corresponds to the upper neighbor number of the same position number of the original matrix, one by one

Similarly:

(7) Traffic concept

Distance and density

Flow equation

conservation equation

Spatiotemporal trajectory (horizontal axis is space and vertical axis is time)

The intersection of the red line and the blue line indicates the location of each time car.

If it is a vertical line, it indicates the corresponding time of the vehicle in this position

Macro continuous model:

Most common rules:

The red bar indicates that the speed is full.

1. Acceleration rule: no more than v m a x (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 flow

The first figure: the abscissa is the normalized density, and the ordinate is the traffic flow. The second figure: theoretical values and CA results

Result analysis: spatiotemporal trajectory

The dark area in the middle is the area of traffic jam.

## 2, Partial source code

function main % Cellular automata simulates three lane trunk roads with large enterprises in the middle and one lane auxiliary roads on both sides during peak hours % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Sidex1 Sidex2 % +---------------+ Sidey = 2 % | | % | | % ======+===============+==== Mainy % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % T Total simulated actual time % Arrival Total traffic flow % Mainlength Trunk road chief % Mainy Longitudinal coordinate of trunk road % Mainwide Trunk road width % Sidewide Auxiliary road width % Sidex1 Sidex2 Abscissa of auxiliary road % Sidey Auxiliary road ordinate % Sidelengthh The auxiliary road is long from north to south % Sidelengthw The auxiliary road is long from east to west % MP map matrix % 1 Empty 2 vehicle 3 boundary % lightmp traffic lights % lighttime Traffic light interval % v Vehicle speed matrix % vmainmax Highest speed of trunk road % vsidemax Maximum speed of auxiliary road % time Car time matrix % dt unit time % tt Image refresh time % h handle % sumtime Total vehicle time % alltime Total car time % changepro Right lane entry paving probability clear;clc T = 3000; Mainlength = 200; Mainwide = 3; vmainmax = 6; %Sidelengthh = 25; Sidelengthw = 100; Sidewide = 1; vsidemax = 4; Sidex1 = 30; Sidex2 = 150; Sidey = 2; Mainy = 26; [mp, v, time,lightmp] = init_mp(Sidex1,Sidex2,Sidey,Mainy,Mainlength,Mainwide); h = print_mp(mp, NaN, 0.1); dt = 1.2; tt=0.1; sumtime = 0; sumpassed =0; lighttime = 20; changepro = 1; alltime=0; %mp(25,comy)=2; cy2=130; mp(25,cy2)=2; for i = 1:T sumtime=sumtime+dt; % Brush car if(rem(i,2)&(mp(27,8)~=2||v(27,8)~=0))[mp, v] = new_cars(dt,mp,v,vmainmax); end; % Software Park if(rem(i,2))mp(24,cy2)=1;else mp(24,cy2)=2;end; mp(26,cy2)=2;v(26,cy2)=0; % Lane change chos_road2 radical chos_road conservative [mp, v, time] = chos_road(mp,v,time); % variable speed [mp, v, time] = change_speed(mp,v,time,vmainmax); flag = (mp(Mainy,Sidex2)==0) % Auxiliary road if(flag) [mp, v, time] = fulu(mp,v,time,vsidemax,Sidex1,Sidex2,Sidey,changepro); end; % displacement&Car elimination [alltime, mp, v, time , sumpassed ] = move(alltime,sumpassed,mp,v,time,dt); % Auxiliary road if(~flag) [mp, v, time] = fulu(mp,v,time,vsidemax,Sidex1,Sidex2,Sidey,changepro); end; % output h = pr % w= getframe; % imind =frame2im(w); % [imind ,cm]=rgb2ind(imind,256); % if(i~=1) % imwrite(imind, cm, 'example1.gif','gif','WriteMode','append','DelayTime',0.01); % else % imwrite(imind, cm, 'example1.gif','gif','Loopcount',inf,'DelayTime',0.01); % end; end function [mp, v, time] = chos_road(mp,v,time) % % % % % % % [N, M] = size(mp); for y=M-1:-1:2 for x=26:28 if(mp(x,y)==2 & mp(x,y+1)~=1) if(mp(x-1,y)==1 & mp(x+1,y)==1 ) if(rand<0.5) mp(x+1,y)=2; mp(x,y)=1; v(x+1,y)=v(x,y); v(x,y)=0; time(x+1,y)=time(x,y); time(x,y)=0; else mp(x-1,y)=2; mp(x,y)=1; v(x-1,y)=v(x,y); v(x,y)=0; time(x-1,y)=time(x,y); time(x,y)=0; end; elseif(mp(x+1,y)==1) mp(x+1,y)=2; mp(x,y)=1; v(x+1,y)=v(x,y); v(x,y)=0; time(x+1,y)=time(x,y); time(x,y)=0; elseif(mp(x-1,y)==1) mp(x-1,y)=2; mp(x,y)=1; v(x-1,y)=v(x,y); v(x,y)=0; time(x-1,y)=time(x,y); time(x,y)=0; end; end; end; end; function [mp, v, time] = chos_road(mp,v,time) % % % % % % % [N, M] = size(mp); dis=zeros(N,M)-1; for y=M:-1:2 for x=26:28 if (mp(x,y)==2|mp(x,y)==3) dis(x,y) = 0; end; end; end; for y=M-1:-1:2 for x=26:28 if (dis(x,y)==-1 && dis(x,y+1)~=-1 ) dis(x,y) = dis(x,y+1)+1; end; end; end; for y=2:M-1 for x=26:28 if(mp(x,y)==2) if(dis(x,y+1)==-1)dis(x,y)=123; else dis(x,y)=dis(x,y+1)+1; end; end; end; end; for y=2:M-1 for x=26:28 if(mp(x,y)==2 & (dis(x,y)-1<v(x,y)||mp(x,y+1)==2)) if(mp(x-1,y)==1 & dis(x-1,y)>dis(x,y) & mp(x+1,y)==1 & dis(x+1,y)>=dis(x,y)) if(rand<0.5) mp(x+1,y)=2; mp(x,y)=1; v(x+1,y)=v(x,y); v(x,y)=0; time(x+1,y)=time(x,y); time(x,y)=0; else mp(x-1,y)=2; mp(x,y)=1; v(x-1,y)=v(x,y); v(x,y)=0; time(x-1,y)=time(x,y); time(x,y)=0; end; elseif(mp(x+1,y)==1 & dis(x+1,y)>=dis(x,y)) mp(x+1,y)=2; mp(x,y)=1; v(x+1,y)=v(x,y); v(x,y)=0; time(x+1,y)=time(x,y); time(x,y)=0; elseif(mp(x-1,y)==1 & dis(x-1,y)>dis(x,y)) mp(x-1,y)=2; mp(x,y)=1; v(x-1,y)=v(x,y); v(x,y)=0; time(x-1,y)=time(x,y); time(x,y)=0; end; end; end; end;

## 3, Operation results

## 4, matlab version and references

1 matlab version

2014a

2 references

[1] Cai Limei. MATLAB image processing theory, algorithm and example analysis [M]. Tsinghua University Press, 2020

[2] Yang Dan, Zhao Haibin, long Zhe. Detailed explanation of MATLAB image processing examples [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. Research on face recognition method based on PCA-SVM [J]. Science and technology vision. 2021, (07)

[6] Zhang Na, Liu Kun, Han Meilin, Chen Chen. Research on a face recognition algorithm based on PCA and LDA fusion [J]. Electronic measurement technology. 2020,43 (13)

[7] Chen Yan. Analysis of face recognition method based on BP neural network [J]. Information and computer (theoretical Edition). 2020,32 (23)

[8] Dai Lirong, Chen Wanmi, Guo Sheng. Research on face recognition based on skin color model and SURF algorithm [J]. Industrial control computer. 2014,27 (02)