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

% Main program entry CLC; clear; gcf=figure('Position'[300 200 500 400].'NumberTitle'.'off'.'name'.'Six Grid');

L=1; % Cell side length HL=0; % Adjacent mode// Flat or pointed
HW=0; % highlight mode// The first cell of the first row (column) is higher than the first cell of the second row (column)
xy=[0.0]; % lower left coordinate lamda=10; % Space size rande=0.1; % random birth rate0 - 1
Generation=100; You can customize the update rule B= by changing the contents of the EvolutionRules() function2; % Number of neighbors S=3; % Dead neighbors % Create and initialize space array CellData=rand(lamda,lamda); % Random birth CellData(CellData< RANDe)=1; % less than birth rate survival CellData(CellData<1) =0; % Other dead CellDataTemp=CellData; % % % cache array according to drawing timing tic shows plotSixGrid (x, y, L, lambda, lambda, CellData, GCF, HL, HW) toc %for key=1:100% per second10frame1 / 0.1 = 10 fps
    pause(0.1);
    
    if (ishandle(gcf)==false)
        disp('Window closed, stopped running');
        break; End tic % iterates through each cellfor i=1:lamda % Obtains the coordinates of its neighbors from the type of grid and the coordinates of the grid NeiIJ=U_ij(I,j,HL); % temporary variable used to store the state of six neighbors initialized to zero CellState=[0 0 0 0 0 0]; % Traverses the coordinates of the six neighbors to get their state and store itfor k=1:6
                p=NeiIJ{k}(1);
                q=NeiIJ{k}(2); % determine if the coordinate is out of bounds. If it is out of bounds, its state is zero.if p ~= 0 && p<=lamda && q~=0&& q<=lamda CellState(k)=CellData(p,q); CellDataTemp(I,j)=EvolutionRules(B,S,CellState); End End % Draws a hexagonal grid based on the state arraytry
    
        disp('Window closed, stopped running');
        break; End % Update the status array to the contents of the cache array CellData=CellDataTemp;toc
    
end
disp('Run completed');
a=rand(10.1000);
s1=a;
s2=a;


tic
s2(s2>0.5)=0;
toc

tic
s1(find(s1>0.5))=0; Toc function State = EvolutionRules(B,S,AdjacentElements) % EvolutionRules determine the State of next cycle elements % B survival line % S death line % AdjacentElements Neighbor state % Calculates the number of viable neighbors. If the number is larger than the survival line and smaller than the death line, the current cell survives; otherwise, death K=sum(AdjacentElements);if K>=B&&K<=S
    State=1;
else
    State=0;
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)