【文章內(nèi)容簡介】 位于 內(nèi)部 的 元胞 它的鄰居并不相同 ， 所以我們根據(jù)這些不同分為 周期型邊界、固定邊界、絕熱邊界和映射邊界 等 幾種邊界處理方式 [10]。 元胞自動機仿真與實現(xiàn) 7 (4)規(guī)則 ： 所謂的規(guī)則， 首先 應該做的是確認這個 元胞 現(xiàn)在的 狀態(tài) 以及鄰居的狀態(tài) ， 然后由 仿真要求 可得出 下一 時間點這個 元胞 可能的 狀態(tài) ， 進而確定其 狀態(tài)轉(zhuǎn)移函數(shù) ， 這個過程即被稱作是 演化規(guī)則 ， 演化規(guī)則它 是整個 CA 模型 中的 精髓 部分 。演化規(guī)則 是否 合理 直接 決定 著 仿真 的 結果 是否 可靠 以及是否可信 ， 而其靈活性 與否也直接的 決定 了 CA模型的 適用的 范圍 [11]。 元胞自動機的特征和分類 通常 來說 ， CA 有 下列的 幾種特性 ： (1)空間和時間離散：空間 的 離散 具有兩方面的含義，它既指 元胞空間 自身結構 的 離散， 又指 元胞在 元胞空間里面分布的 離散； 而在 時間 上的 離散 則 是指 系統(tǒng)按照等時步長 來 演化， 和 微分方程 里 的連續(xù)時間 不一樣的是 ， 它的 時間 的 取值是 與 t、 t+ t+2等的 這些 時刻點 相類似的時間點 。 (2)齊性和同質(zhì)性： 所謂 齊性 指的是 元胞的大小 相同 、形狀 相同以及分布方式都完全相同 ； 所謂 同質(zhì)性 則 指的是在 元胞空間 范圍中 所有 的 元胞都 會遵守一樣的 演化規(guī)則。 (3)時空局域性 ： 所謂 時空局域性 它說的是一個 元胞在 t+1 時刻 時 的狀態(tài) 是由 鄰居半徑 r 范圍里 的 所有的 元胞在 t 時刻 時 的狀態(tài) 所決定出來的 ， 但是 在 t時刻 時 的元胞 的元胞 狀態(tài)只 會給 t+1時刻 時 的狀態(tài)產(chǎn)生影響 ， 所以 會 在 時間 與 空間上有 一些 局限。 (4)并行性： 并行性 的定義是在 元胞空間 內(nèi) 的每一個元胞 的元胞 狀態(tài) 的 更新是 時時 同步進行的。 (5)狀態(tài)離散有限： 這 里的狀態(tài)離散有限是 指元胞 本身 的狀態(tài)量只能 在 有限元胞自動機仿真與實現(xiàn) 8 的 而且 離散的狀態(tài)集合 里面進行 取值。 (6)高維數(shù) ： 維數(shù)是 CA里面 研究變量 的數(shù)目 。在 應用的具體實例 中 ， 計算機模擬 會 根據(jù)變量 的 個數(shù) 來 處理 大數(shù)目 、 高維度 的系統(tǒng) [12]。 由 元胞空間的維數(shù) 可把 CA劃為 三類 ， 如圖 。 (1)一維 ： 一維元胞自動機指的是 元胞等 距離的 分布在直線上 ， 其 狀態(tài) 與 規(guī)則 都很 簡單 ， 它的 動態(tài)演化 過程比較容易觀察 。 (2)二維 ： 二維 CA有三角形、正方形和正六邊形 這幾種 空間 的 劃分 方式 。 (3)高維 ： 顧名思義，指的是 三維 和 三維以上的元胞自動機 ， 這中自動機在 實際的 模擬 過程 中應用 的很少 。 元胞自動機理論 自動機是一種 自動的設備，它并 不需要 由 人 來一 步 一 步 的 操作， 自動機 根據(jù)其 存儲帶的 是否 有限性， 可 分 無限帶自動機 與 有限帶自動機 這兩種 。 如圖靈機之類的這種 無限帶自動機 的 主要 用途是來 描述算法 以及算法的 繁衍 的 過程。 有限自動機 它 是一種 具有 離散 的 輸入 與 輸出的 自動機，例如元胞自動機 [13]。 元胞自動機仿真與實現(xiàn) 9 第三章 初等 元胞自動機的實現(xiàn) 初等元胞自動機 (Elementary Cellular Automata, 又稱 ECA)是指 狀態(tài)集 S只存在 2個元素 {0,1},鄰居半徑 r為 1的一維元胞自動機 ,初等元胞自動機 是 所有元胞自動機里面最簡單的模型 。 ECA的 局部映射 f :S3→ S可以表示成 為 : Si(t+1)=f(Si1(t),Si(t),Si+1(t)) 根據(jù) 局部映射規(guī)則 所有的不同的情況一 共 有 28即為 256種 ,因此在 對不同種局部規(guī)則的做了進一步的研究之后 ,他發(fā)現(xiàn) 雖然 ECA模型非常 簡單 , 但是其可以表現(xiàn)出來異常繁雜的 空間 性 形態(tài)。 形式 : (1)趨向 于 與時間無關穩(wěn)定狀態(tài) 。(2)趨向 于 一種 周期 性的 結構 形式 。(3)會有 混沌行為 發(fā)生的可能性 。(4)可以衍變成為更加繁雜的構象 。 S. Wolfram 對 ECA的 探索為后來 CA的研究掃除了障礙 , 此外，他還 對 CA的 理論 性 發(fā)展 和后面的 人工生命 以及最近幾年新興的 復雜性科學 的探究奠定了 卓越 基礎 [14]。 設計 CA的時候通常會利用 一個二維數(shù)組 m(n,t)來對數(shù)據(jù)進行儲存 ,在Matlab軟件中將 一個 axis分成 n t個 格子 , 每一個方格都會與 m 中的一個元素相對應 , 我們用 t來表示時刻 ,用 n表示一個元胞空間；這樣 m(i,t)就代表第i個元胞在 t這個 時刻 的時候它的 狀態(tài) ,我們定義 0代表該元胞“死” ,1代表“活”；我們還 用 黑 色 代表“活的” 元胞 ,用白色 代表“死的” 元胞 ；它的 邊界條件 用 周期型 來進行表示； 鄰居長度 表示成 1； 對于 定編號 ECA來說，它的轉(zhuǎn)變規(guī)則 是 已知的 [15]。算法 可以用下面來表示 ： ① 初始化元胞狀態(tài) 隨機； ② 鍵入 轉(zhuǎn)換規(guī)則 (0 255)； ③ 將 轉(zhuǎn)換規(guī)則號 處理 把其變成 個算法子程序 ； 具體 的 算法 如下 :在 t 時刻 的時候 讀 取 初值 ： m(1:n,t)；根據(jù) 規(guī)則 進行 判斷并且 生成 t+1時刻 的時候各個 元胞 的 狀態(tài) ： m(1:n,t+1)； ④ 從 1t的 循環(huán) 進行這個 子程序 的調(diào)用 ； ⑤ 輸出結果； 基于上述步驟，我們對 ECA做了設計 , 下面是經(jīng)典的 ECA在時間上進行運算的情況。 元胞自動機仿真與實現(xiàn) 10 圖 31 ECA的 運算 (a)編碼為 22的一維基本元胞自動機 (b)編碼為 40時 , 元胞趨向于消失 (c)編碼為 60時的周期型 (d)編碼為 78時的靜態(tài)型 元胞自動機仿真與實現(xiàn) 11 第 四 章 仿真實現(xiàn) 仿真工具簡介 用于 CA的 仿真的軟件 有 很多 種 ， 比如 Mathworks 公司開發(fā)的 MatLab、 圣塔菲研究所開發(fā)的 Swarm等。 Matlab是一個很知名的仿真軟件，它 由美國 Mathworks公司推出并 在 數(shù)值計算 方面 和圖形處理 方面有著很廣泛應用的一個軟件 。它 給用戶建立 了 一套 人機 可以 交互的數(shù)學系統(tǒng)環(huán)境， 同時 還 設計出 了 一個直觀的 可視化界面 來當作 編程 的 環(huán)境 , Matlab 系統(tǒng)的基本 的 數(shù)據(jù)結構是矩陣 , 它 具有 定義 比較 簡單，編程 比較 容易 , 它還給出 了 一些完整 的函數(shù)， 這使得很多 的 基本的 數(shù)學運算 都 能用其特有的 功能函數(shù) 得以完成 ， 此外， Matlab 也給出 了 一些 外部數(shù)據(jù)接口， 用戶可以用 這些接口 調(diào)用 Java語言 這些類似的外部 子程序。 基于 Matlab的 這些 優(yōu)點， 用它來對 CA程序的編寫是很適合的 。 以下我們用 Matlab 來進行模型的仿真實現(xiàn)