元胞自動機概述與MATLAB實現

什么是元胞自動機?

元胞自動機(cellular automata,CA) 是一種時間、空間、狀態都離散,空間相互作用和時間因果關系為局部的網格動力學模型,具有模擬復雜系統時空演化過程的能力。它能構建隨時間推移發生狀態轉移的系統,細胞存在于一維或多維網格中,每個細胞都有一個或多個狀態,每個細胞都有鄰居(即鄰近的細胞)。

元胞自動機分類

平穩型:自任何初始狀態開始,經過一定時間運行后,元胞空間趨于一個空間平穩的構形,這里空間平穩即指每一個元胞處于固定狀態。不隨時間變化而變化。 周期型:經過一定時間運行后,元胞空間趨于一系列簡單的固定結構(Stable Patterns)或周期結構(Perlodical Patterns)。由于這些結構可看作是一種濾波器(Filter),故可應用到圖像處理的研究中。 混沌型:自任何初始狀態開始,經過一定時間運行后,元胞自動機表現出混沌的非周期行為,所生成的結構的統計特征不再變止,通常表現為分形分維特征。 復雜型:出現復雜的局部結構,或者說是局部的混沌,其中有些會不斷地傳播。

奇偶規則

奇偶規則是定義在二維網格上的一種元胞自動機。每個網格的狀態用0各1表示。

(1)???? 對應于每一個元胞位置(i,j)計算出其八個最近領居在t時刻的狀態值St的總和M(i,j)。

(2)???? 根據M(i,j)取值的奇偶性來決定下一時刻t+1該點的狀態St+1(i,j)。當M(i,j)為偶數時,St+1(i,j)等于0;當M(i,j)為奇數時,St+1(i,j)等于1。八個點和為偶數,則變為0,為奇數則變為 1

平穩型元胞自動機實現

% 規則,先把中間點置為1,每一時間步對每一點,如果周圍% 八個點和為偶數,則變為0,為奇數則變為 1Map = [1 1 1; 0 0 0];colormap(Map);% 設置網格大小S = 121;L = zeros(S);% 把中間一個數設置為 1 作為元胞種子M = (S+1)/2;L(M, M) = 1;Temp = L;imagesc(L);% 計算層數Layer = (S-1)/2 + 1;for t=2:Layer    for x=M-t+1:M+t-1       if x==M-t+1 || x==M+t-1                     for y=M-t+1:M+t-1            SUM = 0;            for m=-1:1               for n=-1:1                  if x+m>0 && x+m<=S && y+n>0 && y+n<=S                     SUM = SUM + L(x+m, y+n);                   end               end            end            SUM = SUM - L(x, y);            Temp(x, y) = mod(SUM, 2);          end                 else            y = M-t+1;            SUM = 0;            for m=-1:1               for n=-1:1                  if x+m>0 && x+m<=S && y+n>0 && y+n<=S                     SUM = SUM + L(x+m, y+n);                   end               end            end            SUM = SUM - L(x, y);            Temp(x, y) = mod(SUM, 2);                        y = M+t-1;            SUM = 0;            for m=-1:1               for n=-1:1                  if x+m>0 && x+m<=S && y+n>0 && y+n<=S                     SUM = SUM + L(x+m, y+n);                   end               end            end            SUM = SUM - L(x, y);            Temp(x, y) = mod(SUM, 2);       end    end    L = Temp;    imagesc(L);    pause(0.1);end

效果圖