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

function Message_Spread_Mode
tic
load '.\Data\Link.txt'; % reads into the connection matrix % load'C:\Users\ User \Desktop\ Virus Propagation Simulation of SMS Network based on Cellular Automata \Data\ point_x.txt '; % reads the abscissa % load'C:\Users\ User \Desktop\ Virus Propagation Simulation of SMS Network based on Cellular Automata \Data\ point_y.txt '; % read ordinate % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % % distribution and state transition probability SEIR %0Susceptible state S (Susceptible) P_0_1; (P_0_3: preimmunity coefficient) %1: Latent state E (Exposed) P_1_0; P_1_2; P_1_3 %2: Infected state I (Infected) P_2_0; P_2_3 %3: the immune state of R (Recovered) P_3_0% -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % % calculation of each user node degrees De=sum(Link); % % user node degrees -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- parameters Settings and -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % N [M] = size (Link); % Size of the connection matrix I_E=0.6; % Incubation period E User infection intensity I_I=0.9; % Infection intensity lamda=sum(De)/M; % average number of messages sent per unit time by mobile phone users %P_m1: pre-immunity coefficient of mobile phone users %State: status of mobile phone users State=zeros(1,M);0: it means the vulnerable status (Susceptible) % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --- 1-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % % to discuss first user pre immune factor P_m1 TimeStep within = effect on the spread of the virus50; %input(Simulation time of virus Propagation in SMS network:);
P_m1=[0.1.0.5.0.9]; % user preimmunity coefficient % State=zeros(TimeStep,M); % Mobile phone user status G_t=5; %G_t: Duration of immunity for mobile phone users, reflecting the frequency of virus mutation F_t=5; %F_t: indicates the time from virus discovery to virus removal and virus updatefor i=1:length(P_m1)
    TimeLong_F=zeros(1,M); % Length of time the user has been infected TimeLong_E=zeros(1,M); % Latency of the user Sta= Zeros (1,M); % Cell phone user status % for preimmunization Settingsfor j=1:M
        if rand(1)<=P_m1(i)
            Sta(j)=3; % enters the immune state TimeLong_E(j)=1; % The entry and exit incubation period is1
        else
            continue; Initial random selection of a node as the disease point (can not select the immune state point at this time) % problem: [Number,Sta]=Select_Infected_Point(M,Sta,De); [Number,Sta]=Select_Infected_Point(M,Sta,De); %Number: source node %State: State matrix of the node after determining the source node State=zeros(TimeStep,M); Number_State=zeros(4,TimeStep); % Indicates the number of users in a statefor t=1:TimeStep
        if t==1
            State(t,:)=Sta;
        else% simulates the state of each user nodefor j=1:M % Determine what state the user node is in, and then determine its transition based on its stateif State(t- 1,j)==0% is in the susceptible state0Num=Select_Number_Near(j,Link); % find the neighbor of node j P=zeros(1,length(Num)); % Probability that the neighbor node infects the nodefor k=1:length(Num)
                        if State(t- 1,Num(k))==1% node in incubation period E (1), P (k) = I_E/De (Num (k)) * sum ((lambda. ^ ([1:De(Num(k))]).*exp(-lamda))./...
                                (factorial([1:De(Num(k))]- 1)));
                        else
                            if State(t- 1,Num(k))==2% node is in the infected stage I (2), P (k) = I_I/De (Num (k)) * sum ((lambda. ^ ([1:De(Num(k))]).*exp(-lamda))./(factorial([1:De(Num(k))]- 1)));
                            else
                                continue; end end end P_0_1=max(P); % The probability that a node is infected with a virusifRand <=P_0_1 % At this time, the node enters latency State(t,j)=1;
                    else
                       State(t,j)=State(t- 1,j); 
                    end
                else
                    if State(t- 1,j)= =1% are in latent state E and may metastasize to susceptible S, infected I and immune Rif rand<=1/ (1+exp(-de (j))) % transfer State(t,j)=2;
                            TimeLong_F(j)=TimeLong_F(j)+1; % The length of time user J was in the infected stateelse
                            if rand<=1/ (1+exp(-de (j))) % transfer to susceptible State S (t,j)=0;
                            else
                                if rand<=1/ (1+exp(-de (j))) % transfer to immune State R State(t,j)=3;
                                    TimeLong_E(j)=TimeLong_E(j)+1; % immunity time increased1
                                else
                                    State(t,j)=State(t- 1,j); % is in the same state and is still the incubation period E (1)end
                            end
                        end
                    else
                        if State(t- 1,j)= =2% at this point in the disease state I, may be susceptible to S, immune R transferifTimeLong_F(j)<=F_t % Indicates that the user does not handle mobile phone viruses. State(t,j)=State(t- 1,j); % The mobile phone user remains in the original stateI
                                TimeLong_F(j)=TimeLong_F(j)+2;
                            else% At this time, the mobile phone user will sterilize the mobile phone and upgrade the virus library, and enter the immune State3;
                                TimeLong_F(j)=0; % Duration of being infected (poisoned) TimeLong_E(j)=1; % Length of time to enter the immune phase endelse% The mobile phone user is in the immune phaseifTimeLong_E<=G_t % The virus does not mutate and maintains its original State R (immune State) State(t,j)=State(t)- 1,j);
                                TimeLong_E(j)=TimeLong_E(j)+1; % increased time spent in the immune phaseelse
                                if rand<=1/G_t % virus mutated, State transferred to susceptible State S State(t,j)=0;
                                    TimeLong_E(j)=0;
                                else% The user status remains unchanged State(t,j)=State(t)- 1,j);
                                    TimeLong_E(j)=TimeLong_E(j)+1; End End End End End End % Number of nodes in each state Number_State(1,t)=sum(State(t,:)==0); % Total number of nodes in susceptible state S Number_State(2,t)=sum(State(t,:)==1); % Total number of nodes in susceptible state E Number_State(3,t)=sum(State(t,:)==2); % Total number of nodes in susceptible state I Number_State(4,t)=sum(State(t,:)==3); % Total number of nodes in susceptible state R Figure (I)if rem(t,3)= =0
            plot([t- 1 t],[Number_State(1,t- 1) Number_State(1,t)],'md-'),hold on
            plot([t- 1 t],[Number_State(2,t- 1) Number_State(2,t)],'gh:'),hold on
            plot([t- 1 t],[Number_State(3,t- 1) Number_State(3,t)],'bs-.'),hold on
            plot([t- 1 t],[Number_State(4,t- 1) Number_State(4,t)],'k.-'),hold on
        else
            continue;
        end
        legend('Susceptible state Susceptible to.'Exposed'.'Infected status'.'Immune state Recovered')
        xlabel('Simulation time')
        ylabel('Number of mobile users in all states')
    end
end
P_m1=0.3; % user preimmunity coefficient % State=zeros(TimeStep,M); % Mobile phone user status % G_t=5; %G_t: Duration of immunity for mobile phone users, reflecting the frequency of virus mutation.1.5.9];
F_t=5; %F_t: indicates the time from virus discovery to virus removal and virus updatefor i=1:length(G_t)
    TimeLong_F=zeros(1,M); % Length of time the user has been infected TimeLong_E=zeros(1,M); % Latency of the user Sta= Zeros (1,M); % Cell phone user status % for preimmunization Settingsfor j=1:M
        if rand(1)<=P_m1
            Sta(j)=3; % enters the immune state TimeLong_E(j)=1; % The entry and exit incubation period is1
        else
            continue; Initial random selection of a node as the disease point (can not select the immune state point at this time) % problem: [Number,Sta]=Select_Infected_Point(M,Sta,De); [Number,Sta]=Select_Infected_Point(M,Sta,De); %Number: source node %State: State matrix of the node after determining the source node State=zeros(TimeStep,M); Number_State=zeros(4,TimeStep); % Indicates the number of users in a statefor t=1:TimeStep
        if t==1
            State(t,:)=Sta;
        else% simulates the state of each user nodefor j=1:M % Determine what state the user node is in, and then determine its transition based on its stateif State(t- 1,j)==0% is in the susceptible state0Num=Select_Number_Near(j,Link); % find the neighbor of node j P=zeros(1,length(Num)); % Probability that the neighbor node infects the nodefor k=1:length(Num)
                        if State(t- 1,Num(k))==1% node in incubation period E (1), P (k) = I_E/De (Num (k)) * sum ((lambda. ^ ([1:De(Num(k))]).*exp(-lamda))./...
                                (factorial([1:De(Num(k))]- 1)));
                        else
                            if State(t- 1,Num(k))==2% node is in the infected stage I (2), P (k) = I_I/De (Num (k)) * sum ((lambda. ^ ([1:De(Num(k))]).*exp(-lamda))./...
                                    (factorial([1:De(Num(k))]- 1)));
                            else
                                continue; end end end P_0_1=max(P); % The probability that a node is infected with a virusifRand <=P_0_1 % At this time, the node enters latency State(t,j)=1;
                    else
                       State(t,j)=State(t- 1,j); 
                    end
                else
                    if State(t- 1,j)= =1% are in latent state E and may metastasize to susceptible S, infected I and immune Rif rand<=1/ (1+exp(-de (j))) % transfer State(t,j)=2;
                            TimeLong_F(j)=TimeLong_F(j)+1; % The length of time user J was in the infected stateelse
                            if rand<=1/ (1+exp(-de (j))) % transfer to susceptible State S (t,j)=0;
                            else
                                if rand<=1/ (1+exp(-de (j))) % transfer to immune State R State(t,j)=3;
                                    TimeLong_E(j)=TimeLong_E(j)+1; % immunity time increased1
                                else
                                    State(t,j)=State(t- 1,j); % is in the same state and is still the incubation period E (1)end
                            end
                        end
                    else
                        if State(t- 1,j)= =2% at this point in the disease state I, may be susceptible to S, immune R transferifTimeLong_F(j)<=F_t % Indicates that the user does not handle mobile phone viruses. State(t,j)=State(t- 1,j); % The mobile phone user remains in the original stateI
                                TimeLong_F(j)=TimeLong_F(j)+2;
                            else% At this time, the mobile phone user will sterilize the mobile phone and upgrade the virus library, and enter the immune State3;
                                TimeLong_F(j)=0; % Duration of being infected (poisoned) TimeLong_E(j)=1; % Length of time to enter the immune phase endelse% The mobile phone user is in the immune phaseifTimeLong_E<=G_t(I) % The virus does not mutate at this time and maintains its original State R (immune State) State(t,j)=State(t)- 1,j);
                                TimeLong_E(j)=TimeLong_E(j)+1; % increased time spent in the immune phaseelse
                                if rand<=1/G_t(I) % virus mutation, State transfer to susceptible State S State(t,j)=0;
                                    TimeLong_E(j)=0;
                                else% The user status remains unchanged State(t,j)=State(t)- 1,j);
                                    TimeLong_E(j)=TimeLong_E(j)+1; % The duration of the immune phase increasesCopy 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)