二維計算動詞元胞網絡形成模式的整體空間頻率分布

王志剛

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

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

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

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

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

1 二維計算動詞元胞網絡

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

圖1 二維計算動詞元胞網絡的拓撲結構

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).

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

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

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

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

1.3 二維計算動詞元胞網絡的動詞規(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)

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

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

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

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

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

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

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

2 實驗

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

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

圖2 二維計算動詞元胞網絡生成的多種多樣的模式

觀察實驗結果，我們發(fā)現(xiàn)1000000實驗有642308次得到同質模式(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).由于篇幅有限，這里不作太多解釋.

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

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

3 結語

綜上所述，我們通過對2D－CVCN的等間隔參數(shù)空間遍歷，得到海量的形成模式，并對這些模式的頻譜進行統(tǒng)計.從統(tǒng)計結果可以看出，2D－CVCN得到的模式空間頻率集中分布在最低頻和3個極高頻附近，能量向外圍漸減.由此可以推斷摩爾鄰域很可能是限制2D－CVCN成為通用模式形成工具的一個瓶頸.此外，我們還發(fā)現(xiàn)同質模式出現(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］楊濤.計算動詞理論及應用［M］.廈門:廈門大學出版社，2011.