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

王志剛

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

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

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

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

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

1 二維計算動詞元胞網絡

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

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

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

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

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

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

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

1.2 計算動詞相似度

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

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

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

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

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

1.3 二維計算動詞元胞網絡的動詞規則

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

整體的動力學系統的動詞規則由下式給出:

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

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

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

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

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

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

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

2D－CVCN動詞區域規則可以直觀地由下式給出.

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

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

2 實驗

首先預定義動詞規則矩陣為以下動詞規則矩陣:

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

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

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

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

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

3 結語

綜上所述，我們通過對2D－CVCN的等間隔參數空間遍歷，得到海量的形成模式，并對這些模式的頻譜進行統計.從統計結果可以看出，2D－CVCN得到的模式空間頻率集中分布在最低頻和3個極高頻附近，能量向外圍漸減.由此可以推斷摩爾鄰域很可能是限制2D－CVCN成為通用模式形成工具的一個瓶頸.此外，我們還發現同質模式出現的頻率約為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.