王志剛

(中國神華神東煤炭集團設(shè)備維修中心，內(nèi)蒙古伊金霍洛旗017200)

20世紀30年代，計算機之父阿蘭·麥席森·圖靈提出了“圖靈機”模型，能夠由一定輸入得到一定輸出.之后人們發(fā)現(xiàn)，只要設(shè)置好合適的輸出輸入的格式、內(nèi)部狀態(tài)以及控制程序，幾乎現(xiàn)實中的所有計算，都能用圖靈機來計算.50年代，計算機科學的另一個開創(chuàng)者馮·諾伊曼開始從計算的視角思考生命的本質(zhì)問題，他認為自我復(fù)制乃是有生命的物體的獨一無二的特征，也是被稱之為生命的必要條件.為了構(gòu)造一個能夠自我復(fù)制的機器，馮·諾伊曼提出了元胞自動機的概念.后來劍橋大學數(shù)學家約翰·何頓·康威進一步證明了元胞自動機具有通用圖靈機的計算能力，與圖靈機計算等價.

計算動詞元胞網(wǎng)絡(luò)(CVCN)是一種建立在基于計算動詞局域規(guī)則上的新型的元胞網(wǎng)絡(luò)(T.Yang，2009).與其他元胞網(wǎng)絡(luò)相比，如元胞自動機(Eric Goles and Servet Martinez，1994)和元胞神經(jīng)網(wǎng)絡(luò)(L.O.Chua and L.Yang，1988)，CVCN更為復(fù)雜且類型更多，更能體現(xiàn)語義學的作用，適合于復(fù)雜現(xiàn)象的建模.

二維計算動詞元胞網(wǎng)絡(luò)(2D－CVCN)是CVCNs中的一個重要部分，目前還處于探索階段.Kun Wen and Tao Yang(2010)對二維計算動詞元胞網(wǎng)絡(luò)中形成的常見模式及一些罕見模式作了系統(tǒng)性的研究和分類，給出大量實驗數(shù)據(jù)，說明CVCN很可能擁有模式形成的普遍性.換句話說，CVCN擁有與圖靈機等價的計算能力.Wen Kun，Yang Tao(2010，Wen Kun et al.)提出了一些罕見的模式，比如圖靈班圖、游動的魚、波傳圖、靶波等.

本文通過2D－CVCN的大量仿真實驗，得到仿真結(jié)果，并且系統(tǒng)性地探究了二維計算動詞元胞網(wǎng)絡(luò)空間頻率分布普遍性，證明二維計算動詞元胞網(wǎng)絡(luò)的鄰域規(guī)則尚有可以改進的空間.

1 二維計算動詞元胞網(wǎng)絡(luò)

元胞網(wǎng)絡(luò)可以被看作一種空間、時間、狀態(tài)都離散的動力學系統(tǒng).系統(tǒng)的狀態(tài)變化由模型所定義的非線性特性所決定.這些變化往往極其復(fù)雜，不容易在數(shù)學上被證明.二維計算動詞元胞網(wǎng)絡(luò)以計算動詞規(guī)則為局部規(guī)則，在設(shè)計和應(yīng)用上十分簡單，卻能產(chǎn)生豐富的模式形成表現(xiàn).常見的二維計算動詞元胞網(wǎng)絡(luò)的空間圖譜結(jié)構(gòu)是一張上下、左右相互連接的網(wǎng)絡(luò)，可以被看作三維的圓環(huán)空間拓撲結(jié)構(gòu)，如圖1所示.

圖1 二維計算動詞元胞網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

1.1 計算動詞的定義(楊濤，2011)

可以用以下函數(shù)定義一個連續(xù)時間的計算動詞V，

其中，TR并且ΩRn，T和Ω分別代表時間和狀態(tài)空間.

類似地，可以用以下函數(shù)定義一個離散時間的計算動詞V.

由計算動詞的數(shù)學定義可見其易于操作，并涵蓋了時間、狀態(tài)以及狀態(tài)進化三元素，其執(zhí)行性高.

1.2 計算動詞相似度

對于給定的模板計算動詞V和一個觀察所得的時間序列{x(t)}，用計算動詞相似度(簡稱動詞相似度)S(V;{x(t)})的方法來度量觀察到的時間序列與模板計算動詞的進化函數(shù)有多相似.如果取得了計算動詞V1進化函數(shù)的一個實現(xiàn)的時間序列，那么S(V;{x(t)})可以被改寫為S(V;V1).

盡管動詞相似度有許多計算方法，但目前還沒找到一個有關(guān)動詞相似度的定義能夠符合對計算動詞之間相似度的所有直觀感受.因此，動詞相似度中存在著各種不確定性.例如，分別計算兩個計算動詞對于第三個動詞的相似度，當同時使用一種計算方法時，可能得到相同的相似度，而同時使用另一種相似度計算方法時，它們的相似度卻不同了.下面構(gòu)造一種理想函數(shù)來表示計算動詞相似度.已知的模板計算動詞的生命周期有兩個關(guān)鍵點:始點和終點.模板動詞的進化函數(shù)表示如下

對于開始觀察的動詞 V=(0，Δx)，選取標準動詞為 V={increase，decrease，stay}.

定義如下的計算動詞相似度:

其中 Δ ＞0，κ ＞0，Δx=x(k)－x(k－1).

1.3 二維計算動詞元胞網(wǎng)絡(luò)的動詞規(guī)則

2D－CVCN中元胞的初始狀態(tài)通常是以隨機的方式給定的，可以將此處于初始狀態(tài)時的元胞稱為第0代元胞.任意元胞與其相鄰的元胞之間互相影響，影響的效果由計算動詞規(guī)則及相鄰元胞的動態(tài)變化規(guī)律共同確定.常見的二維計算動詞采用3×3的摩爾鄰域作為局部區(qū)域.

整體的動力學系統(tǒng)的動詞規(guī)則由下式給出:

其中，由 S(xkl，Vk－i，l－j)計算動詞的相似度函數(shù)，用來計算時間狀態(tài)序列{xkl}與計算動詞 Vk－i，l－j之間的相似程度.具體的相似度計算由動詞規(guī)則確定.

在式(7)中，fk－i，l－j(xij(k))表示鄰域元胞Ckl對中心元胞 Cij的作用或影響函數(shù)，定義

fk－i，l－j(xij(k))=gp·f(xij(k)).(8)

其中g(shù)p是模擬動詞影響的參數(shù)，來衡量每個動詞的影響程度，因為有3個標準動詞，所以gp有3個值，定義如下式

其中，pi∈ R，ps∈ R，pd∈ R.

在式(8)中，f(xij(k))是非線性飽和輸出函數(shù).

由式(8)，(9)和(10)可知，每個元胞的第k+1代的狀態(tài)，直接相關(guān)的是該元胞的前一代，即第k代的狀態(tài)值的函數(shù).而周圍鄰域元胞的影響，是在這個函數(shù)上乘以一個表示影響程度的系數(shù)因子.

2D－CVCN動詞區(qū)域規(guī)則可以直觀地由下式給出.

每個中心元胞的狀態(tài)與它所在鄰域所選取的動詞規(guī)則有關(guān)，動詞規(guī)則的設(shè)定很大程度上決定了將會形成的模式，定義矩陣A為動詞規(guī)則矩陣，即

由于我們選取了3個標準動詞，所以總共將有39=19683種可能的規(guī)則，考慮到對稱性，可能性空間會有所減小，但仍然是一個很大的數(shù)字.我們將取其中最常見的一組動詞規(guī)則進行系統(tǒng)分析.而在每組規(guī)則下，不同的pi，pd，ps以及相似度函數(shù)中Δ，κ的參數(shù)值的選取不同，也可能得到完全不同的實驗結(jié)果.

2 實驗

首先預(yù)定義動詞規(guī)則矩陣為以下動詞規(guī)則矩陣:

設(shè)置網(wǎng)絡(luò)大小為160×160，相似度計算參數(shù)Δ=0.5和κ=1.我們采用遍歷參數(shù)空間的方式，對這個規(guī)則矩陣下的模式進行系統(tǒng)性的探究.動詞影響參數(shù)的取值通過均勻等距離取點的方式遍歷給定參數(shù)空間，pi，pd，ps∈(－10:0.2:10).每一次改變參數(shù)就進行一次實驗，一共進行1003次實驗.每次實驗對網(wǎng)絡(luò)中所有元胞的初始狀態(tài)值取［0，1］區(qū)間內(nèi)的隨機值，根據(jù)局域動詞規(guī)則進行全網(wǎng)同步跟新.讓其自由進化到1000代，記錄此時的網(wǎng)絡(luò)狀態(tài)作為實驗數(shù)據(jù)保存.將實驗結(jié)果用HSV顏色空間表示，可視化后效果如圖2所示.

圖2 二維計算動詞元胞網(wǎng)絡(luò)生成的多種多樣的模式

觀察實驗結(jié)果，我們發(fā)現(xiàn)1000000實驗有642308次得到同質(zhì)模式(homogenous pattern)，出現(xiàn)的概率為64.23%.用符號＆(y，x)代表圖2中第y行第x個.我們發(fā)現(xiàn)高頻模式(例如條紋圖形、棋盤格圖形)常常伴隨著線條 ＆(1，4).在單向高頻下，方塊被擠壓，可以對比 ＆(1，2)、＆(6，2)、＆(7，5).線條可能隔離兩種不同的模式＆(6，1)、＆(7，2).由于篇幅有限，這里不作太多解釋.

通過將實驗遍歷和迭代形成的模式進行傅立葉變換，并將除了同質(zhì)模式以外的357692個網(wǎng)絡(luò)狀態(tài)的頻譜累加，得到圖3中的頻譜統(tǒng)計.可以看出，整體的空間頻率分布集中在中心最低頻及水平方向(上下端的中間)、垂直方向(左右端的中間)和雙向最高頻率(四角)附近.這說明2D－CVCN在方形的摩爾鄰域下傾向于最低頻模式和最高頻模式的形成.

圖3 對二維計算動詞元胞網(wǎng)絡(luò)357692次實驗結(jié)果的網(wǎng)絡(luò)頻譜能量分布統(tǒng)計

3 結(jié)語

綜上所述，我們通過對2D－CVCN的等間隔參數(shù)空間遍歷，得到海量的形成模式，并對這些模式的頻譜進行統(tǒng)計.從統(tǒng)計結(jié)果可以看出，2D－CVCN得到的模式空間頻率集中分布在最低頻和3個極高頻附近，能量向外圍漸減.由此可以推斷摩爾鄰域很可能是限制2D－CVCN成為通用模式形成工具的一個瓶頸.此外，我們還發(fā)現(xiàn)同質(zhì)模式出現(xiàn)的頻率約為64.23%.

［1］T.Yang.Computational verb cellular networks:Part I－ A new paradigm of human social pattern formation［J］.International Journal of Computational Cognition，2009，7(1):1 －34.

［2］T.Yang.Computational verb cellular networks:Part II－ One－dimensional computational verb local rules［J］.International Journal of Computational Cognition，2009，7(1):35 －51.

［3］T.Yang.Computational verb cellular networks:Part III－ Solutions of one－dimensional Computational verb cellular networks［J］.International Journal of Computational Cognition，2009，7(2):1 －11.

［4］Eric Goles and Servet Martinez.Cellular automata，dynamical systems，and neural networks［M］.Kluwer Academic Publishers，1994.

［5］L.O.Chua and L.Yang.Cellular neural networks:Applications［J］.IEEE Transactions on Circuits and Systems，1988，35(10):1273－1290.

［6］Kun Wen and Tao Yang.Classification of Patterns Formed in Two－Dimensional Computational verb Cellular Networks［J］.International Journal of Computational Cognition，2010，8(4):1 －37.

［7］Kun Wen，Tao Yang.New patterns in two－dimensional computational verb cellular networks［C］.International Conference on Anti－Counterfeiting，Security and Identification(ASID)，2010:219 －222.

［8］Kun Wen，Xuezhi Wu，Tao Yang.Diffusion and wave propagation patterns in computational verb cellular networks［C］.Proceedings of the International Conference on Anti－Counterfeiting，Security and Identification(ASID)，2012:24 －26.

［9］楊濤.計算動詞理論及應(yīng)用［M］.廈門:廈門大學出版社，2011.