指數函數膜計算模型的自動設計方法研究

賴正坤，孫 敏，楊昌東

(西南交通大學電氣工程學院，四川 成都 610031)

指數函數膜計算模型的自動設計方法研究

賴正坤，孫 敏，楊昌東

(西南交通大學電氣工程學院，四川 成都 610031)

膜計算模型設計是當前膜計算方向非常活躍的一個研究方向。研究者們利用數學、形式語言等工具進行膜計算基礎理論研究，已經提出了各種膜計算模型，并取得了許多研究成果。從最開始復雜的手工推導到近期的自動設計研究，在膜計算模型自動設計方法變的日益成熟的過程中，膜計算模型也能解決更多的問題。在前人的基礎上將膜計算自動設計方法用于推廣到指數函數的計算，同時對設計方法進行了改進，采用置換編碼的方法，結合遺傳算法在P-Lingua仿真平臺實現了2n、3n、4n的計算，驗證此方法的有效性和可行性。

膜計算；指數函數；自動設計；置換編碼

0 引 言

膜計算(membrane computing，MC)作為自然計算的一個年輕分支，旨在從生命細胞的結構與功能中以及從組織和器官等細胞群的協作中抽象出計算模型[1-3]，其計算模型被稱為膜系統或P系統。膜計算領域的一個熱門研究方向就是如何根據特定的任務要求，設計出可以完成一定功能的膜系統計算模型。研究者在研究的過程中，采用數學、形式語言等工具來進行膜計算的理論分析，已經提出了許多不同的細胞型計算模型[4-6]、組織型膜計算模型[7-8]、脈沖型膜計算模型[9]等。從最開始復雜的手工推導到近期的自動設計研究。隨著對膜計算研究的不斷深入，研究者們更多地把目光集中于對膜系統設計方法的研究。文獻[10]第一次提出將遺傳算法應用于膜系統的自動設計，在預先設計一個由18條規則組成的冗余規則集基礎上，通過遺傳算法對冗余規則集中的規則進行尋優，實現膜系統的自動設計；文獻[11]將量子進化算法與膜系統的設計結合起來，并首次通過0、1編碼來表示冗余規則集規則的選取，其中“0”表示不選取該條規則，“1”表示選取該條規則。不僅實現了計算42的膜系統設計，更是將問題擴展到了n2(n為自然數)膜系統的自動設計，且成功率要優于文獻[10]；文獻[12]首次提出了一種通過調整膜系統的膜結構、初始化對象集、進化規則集3個要素來實現完成特定計算任務的膜系統自動設計方法，并將該方法應用于42膜系統的自動設計中，實驗表明，該方法能夠成功設計出種類更多的膜系統；文獻[13]在膜系統具有相同的初始化格局下，與量子進化算法相結合，分別實現了能夠完成加、減、乘、除、加權5種算術運算膜系統的自動設計；文獻[14]又提出了用膜系統自動設計來完成多項式的計算，能計算出最高次數為4次，最大項數為4項的多項式，同時改進了規則的設計，規則條數在預設最大數目內可以變化。

雖然上述文獻成功地將進化算法和細胞型膜系統的設計結合起來，但是只能完成一些較為簡單的任務，在計算復雜問題時成功率很低，因此在固定膜結構的前提下初始對象與規則通過自動設計來完成指數函數的計算，在推廣膜計算的同時又能找到一些簡單的P系統，同時最終用多個對象個數來表示結果，提高了試驗的成功率，增加了膜系統的多樣性和靈活性。

1 設計思想和設計方法

1.1 細胞型膜系統簡介

細胞型膜系統是模仿細胞結構和功能的計算模型，一個細胞型膜系統主要由字母表、膜結構、初始化對象集、進化規則集、結果輸出區域5個部分組成，如圖1所示。其中，每一個組成元素均扮演著特定的角色，且能夠與實際生物細胞中的組成要素相對應，對應關系及各自作用描述如下：

1) 字母表：對應實際生物細胞中的物質，是組成初始化對象集和進化規則集的字符集；

2) 膜結構：對應實際生物細胞的細胞膜及內膜之間組成的層次結構，用于劃分不同對象的多重集所組成的區域。最外層膜被稱為表層膜，膜內不包含其他膜的膜被稱為基本膜。每個膜所圍成的部分被稱為區域，每個區域內包含著各自的規則與對象。

圖1 膜系統示意圖

3) 初始化對象集：對應實際生物細胞中的反應物，由字母表中的字符表示；

4) 進化規則集：猶如一個個的化學反應式，對應實際生物細胞膜中的化學反應。一條規則需要有一組輸入物質，然后通過該條規則產生一組輸出物質，每條規則能夠確定被處理的對象以及具體進行的操作。規則間采用極大并行的方式執行，由字母表中的字符組成。

5) 結果輸出區域：對應實際生物細胞中的環境，隨著規則的執行，會不斷有物質傳遞到環境中，每一次格局轉換完成后，環境中的物質可當作是計算的“結果”。

1.2 設計思路和方法

設計目標：設計一個確定性的、非終止型的細胞型膜系統∏=(V，μ，W，R，i0)，使之能夠用于求解簡單的指數函數。

需要說明的是：1)由于給定的是確定性的目標，因此要設計的膜系統必須是確定性的膜系統，即在格局的變化中任何時刻每個對象只能觸發執行一種規則；2)由于求解的目標是形如2n的指數函數，這就需要保證設計出的膜系統可以隨著式中變量n取值的變化而計算出相應的結果，因此該膜系統必須是非終止型的，即在仿真過程中不會進入停機狀態的膜系統，隨著格局的變化總有規則被對象觸發執行。

設計目標中要求設計出的膜系統能夠對指數函數進行求解，這里可以將問題轉化為尋找一種膜系統，在格局的變化過程中某一對象或多個對象個數的變化與函數結果隨值的變化一致。這樣可以將膜系統的設計問題當作是一個優化問題來處理，借助遺傳算法，對膜系統的要素進行優化搜索，并通過膜系統仿真軟件P-Lingua來驗證、評價獲得的膜系統個體，最終得到滿意的膜系統。

考慮一個膜系統種群∏，∏={∏i}i?N(N為自然數集合)，則其中任意一個膜系統個體可定義為如下數學模型：

∏i=(V，μ，W，R，i0)

(1)

1)V是預先設計好的字母表，字母表中的元素稱為對象，選自26個字母組成的英文字母表。設計時需根據初始化對象集中對象個數以及進化規則集中規則條數來合理確定字母表中對象的個數；

2)μ是膜結構，一般來講，復雜的膜結構更能夠實現設計難度更大的問題。而這里主要是對膜系統設計方法的研究，因此，用最為簡單的單層膜結構μ=[]1反而更能證明所提方法的有效性；

3) 初始化對象集是W設計的目標，通過遺傳算法對字母表尋優獲得。設計時必須考慮初始化對象集中包含對象的最大個數；

4) 進化規則集R是設計的目標，通過遺傳算法對字母表尋優獲得；設計時必須考慮進化規則集中包含規則的最大條數；

5)io為輸出結果區域，本方法中io=1，即最終結果保存到表層膜中。

1.3 膜系統的評價方法

適應度函數是膜系統設計中的關鍵，適應度函數設計的合理與否將直接關乎膜系統設計的成敗。將多項式轉化為與仿真步數step相關的函數f(step)，例如要設計一個求解2n的細胞型膜系統，則可以首先將其轉化為關于仿真步數的函數f(step)，f(step)=2step；然后，以膜系統每一個格局的表層膜中某些對象的數量NumSomeObj來代表實際的計算結果，則適應度函數fitness可表示為

fitness=|NumSomeObj-f(step)|

(2)

fitness的值用于表征實際結果與期望結果之間的差距，顯然，fitness的值越小越好。這里由于將函數中的變量n與仿真步數step相關聯，因此被求解式中n需為自然數。

1.3 膜系統設計實現算法

這里的膜系統自動設計方法均是基于遺傳算法實現的，因為是著眼于如何提出指數函數膜系統的設計方法，而不是如何設計進化算法，故而選用了現已發展成熟且具備專用算法包JGAP[15]的遺傳算法來實現膜系統的自動設計，設計過程中只需考慮遺傳操作算子的選擇及遺傳參數的設置問題。其中遺傳算子采用精英選擇算子、單點交叉算子、均勻變異算子，參數設置主要考慮以下一組參數。

set={Pm,Pc,Np,IterNum}

(3)

式中，Np是膜系統的種群規模；Pc是交叉概率；Pm是變異概率；Iternum是算法的最大迭代次數。

設計流程如圖2所示。

步驟1：初始化膜系統種群∏={∏1，∏2，…，∏NP-1，∏NP}，其中NP為種群規模；

步驟2：判斷當前仿真是否達到終止條件，“是”，則轉向步驟6；“否”，則轉向步驟3；

步驟3：單步仿真當前膜系統，即對個體解碼后，創建該多項式膜系統的P-Lingua文件，調用內核P-LinguaCore中的函數實現對膜系統的仿真，并讀取仿真結果；

步驟4：單步評價當前膜系統，即評價該多項式膜系統是否滿足確定性、非終止性，是否含有冗余對象、冗余規則，是否能夠用于對求解目標的計算等，若不滿足期望要求，則對適應度函數增加相應的懲罰值；

圖2 多項式膜系統自動設計流程

步驟5：經過評價后，若多項式膜系統最終的適應度函數值為0，則轉向步驟6；若適應度函數值不為0，則轉向步驟7；

步驟6：輸出仿真結果，并轉向步驟8；

步驟7：對種群進行選擇、交叉、變異等更新操作，并轉向步驟2；

步驟8：結束本次仿真。

2 膜系統三要素的置換編碼

采用置換編碼來編碼膜系統。所謂置換編碼就是采用字母表中每一個對象對應的實際位置來表示其編碼。如字母表為V={s，a，b，c，x}，采用置換編碼方案，則有下面給出的對應關系：s→1，a→2，b→3，x→4，c→5，且一個字母表中只需插入一個空字符λ，其對應的置換編碼為0，即λ→0。那么選中字母表中每一個對象的概率為P(λ)=P(s)=P(a)=P(b)=P(x)=P(c)=1/6。而如果采用二進制編碼方案，則需對字母表進行23-5=3位補空操作，即V′={λ，λ，λ，s，a，b，c，x}，那么選中對象s，a，b，c，x的概率為P(s)=P(a)=P(b)=P(x)=P(c)=1/8，而選中空字符λ的概率為P(λ)=3/8。

可以看出，相比于傳統二進制編碼，置換編碼的優勢在于在遺傳算法對字母表進行尋優的過程中保證了每一個對象都是被等概率選取的，而等概率選取的好處最終體現在遺傳優化的過程中不會產生過多無效的基因變化，如λ→λ。

由于已預先固定膜結構為單層膜結構μ=[]1，因此只需對膜系統的其余兩要素初始化對象集W和進化規則集R進行編碼，而W和R皆選自字母表V。

2.1 初始對象集W的置換編碼

初始對象集表示為W={w1}，若已知w1中對象的最大個數為n，則初始化對象集可以用n位置換編碼來表示。如w1中包含對象的最大個數為4，當w1=scax時，對應的4位置換編碼為1524；當w1=ab時，對應的4位置換編碼為0023。

2.2 進化規則集R的置換編碼

進化規則集表示為R={R1}，進化規則采用重寫規則，規則形式如下：

[leftobj→rightobj]1

(4)

假設每一條規則的左側leftObjSet和右側rightObjSet中包含對象的最大個數分別為nleft和nright，則可相應的采用nleft和nright位置換編碼來分別表示leftObjSet和rightObjSet。那么R1中任何一條規則的置換編碼位數可用公式(5)來計算。

Lr=nleft+nright

(5)

假設規則左側最多包含1個對象，規則右側最多包含5個對象，則每一條規則可以用6位置換編碼來表示。如一條規則為r1=[s→assbc]1，則對應的置換編碼為121135；若一條規則為r2=[x→abc]1，則對應的置換編碼為400235。

設計過程中，還需知道R中包含的規則條數nR，即可用公式(6)來計算整個進化規則集的置換編碼位數。

LR=nRLr

(6)

膜系統∏的置換編碼：因為沒有對膜結構進行編碼，因此膜系統的編碼只有初始化對象集和進化規則集兩部分，編碼的位數即為兩部分編碼位數之和，計算公式如下：

L∏=n+LR

(7)

3 仿真實驗及結果分析

3.1 仿真實驗

實驗目標：設計一個能夠用于求解2n的膜系統，其中n為自然數。這里將2n中變量n轉化為仿真步數(step)，即隨著仿真步數的增加就能計算出n依次增加的一系列2n的值。

實驗條件：實驗所用計算機為MD2.3GHZ，2GMB，仿真平臺是Eclipse 3.5.0，JDK 版本為1.7.1，仿真膜系統的軟件為P-Lingua 2.1.0。

參數設置：字母表V={s，a，b，x，c}；膜結構μ=[]1；初始對象集W={w1}，nw1=4；進化nR1=3nrleft=1nrright=4規則集R={R1}，規則均采用重寫規則，計算結果以對象c的個數來表示；懲罰因子η=10 000，最大仿真步數MaxSteps=25。

遺傳算法參數設置：根據文獻[14]中可以看出：變異概率Pm=0.1時，成功率達到最高，平均進化代數最少；交叉概率Pc=0.75時，成功率和平均進化代數最為理想；當種群規模大于等于30時，成功率達到最大值，最大迭代次數Iternum=300時成功率最高，且平均運行時間最少。綜上，可以得到一組最優的參數組合setBest={0.1，0.75，30，300}。

評價函數為fitness=|Numofc-2step|,即當c的個數滿足2stetp(2n)時輸出符合要求的膜系統。

3.2 仿真結果

在上述最優遺傳參數組合的條件下，獨立運行100次，其中有49次找到了成功的膜系統，將49個膜系統用膜系統分析軟件[14]進行統計排除相同的膜系統，共得出14種不同的膜系統，由于其他要素都相同，所以下面只列出初始對象集和進化規則集，如表1所示。

得到上述結果后，采用P-Lingua軟件中的膜系統仿真工具來展示膜系統每一步的格局變化，以驗證所得的膜系統是否滿足設計要求。這里以表1中的第5種膜系統的設計結果為例。仿真過程如圖3和表2所示，圖中則直觀的展示了每一步規則執行完后各個對象的個數，表中所示為每一步由對象觸發的規則，從膜系統的初始化格局開始，隨著仿真的進行，規則被對象觸發執行，膜系統的格局不斷發生著變化。下面只展示了前幾步中每一格局對象個數的變化，代表計算結果的對象c的個數也發生著變化，其值依次為2，4，8，16，32，64。不難看出，對象c的個數隨仿真步數的變化規律與實驗中所求的函數2n隨變量n值的變化(n=1、n=2、n=3、n=4、n=5、n=6)的取值一致，也就證明了所設計的膜系統滿足設計要求。

用同樣的設計方法可以找到實現3n、4n的膜系統，驗證了所提出的指數函數的膜系統自動設計方法的正確性和有效性。

表1 指數函數膜系統的設計結果

圖3 膜系統格局轉換示意圖

執行的規則各對象的個數初始格局x,s第一步r1≡s→xcr2≡x→scas,c*2,a,x第二步r1≡s→xcr2≡s→scar3≡a→axss*2,c*4,x*2,a*2第三步r1≡s→xcr2≡s→scar3≡a→axss*4,c*8,x*4,a*4第四步r1≡s→xcr2≡s→scar3≡a→axss*8,c*16,x*8,a*8┆┆┆

[1] Paun Gh. Computing with Membranes[J]. Journal of Computer and System Sciences，2000, 61(1): 108-143 (frist circulated at TUCS Research Report No 208, November 1998).

[2] Paun Gh. Membrane Computing:An Introduction[M]. Berlin: Springer， 2002.

[3] 張葛祥, 潘林強. 自然計算的新分支——膜計算[J]. 計算機學報，2010, 2(33):208-214.

[4] Obtulowicz A, Paun Gh. (in search of)Probabilistic P Systems[J]. BioSystems, 2003, 70(2):107-121.

[5] Ferrettia C, Mauria G, Paun Gh, et al. On Three Variants of Rewriting P Systems[J]. Theoretical Computer Science, 2003, 301(1-3):201-215.

[6] Mutyam M. Rewriting P Systems:Improved Hierarchies[J].Theoretical Computer Science, 2005, 334(1-3):161-175.

[7] Freund R, Paun Gh. Tissue P Systems With Channel States[J]. Theoretical Computer Science, 2003, 296(2): 295-326.

[8] Martin-Vide C, Paun Gh, Pazos J. Tissue P system[J]. Theoretical Computer Science, 2003, 296(2):295-326.

[9] 潘林強，張興義，曾湘祥，等. 脈沖神經膜計算系統的研究進展及展望[J]. 計算機學報, 2008,31(12):2090-2096.

[10] Escuela G, Gutiérrez M. An Application of Genetic Algorithms to Membrane Computing[C].Proc. of. the Eighth Brainstorming Week on Membrane Computing, Esvilla. 2010：101-108.

[11] Huang X, Zhang G, Rong H. Evolutionary Design of a Simple Membrane System[C].Lecture Notes in Computer Science. Berlin: Springer. 2012: 203-214.

[12] Ou Z, Zhang G, Wang T. Automatic Design of Cell-like P Systems through Tuning Membrane Structures, Initial Objects and Evolution Rules[J]. International Journal of Unconventional Computing, 2013.

[13] Chen Y, Zhang G, Wang T. Automatic Design of P Systems for Five Basic Arithmetic Operations within One Framework[J].Chinese Journal of Electronics, 23(CJE-2): 302-304.

[14] 孟琪.多項式膜計算模型的遺傳優化設計方法[D].成都：西南交通大學,2014.

[15] Meffert K, Rotstan N, Knowles C, et al. Jgap-java Genetic Algorithms and Genetic Programming Package. URL:http://jgap. sf. net, 2008.

The design of membrane computing model is the current research direction of membrane computing. Researchers use math, formal language and other tools to form the basis for the theory of membrane computing, they have proposed a variety of membrane computing models and have achieved many research results. From the complex manual automatic derivation to the recent research of automatic design in membrane computing model, the automatic design methods becomes increasingly sophisticated, and the membrane computing model also can solve more problems. On the basis of the former researches, the automatic design methods of membrane computing are applied to the calculation of exponential function, while the design method is improved. Using replacement encoding method and combined with genetic algorithm in P-Lingua simulation platform to achieve 2n, 3n, 4ncalculations, the validity and feasibility of the proposed method are verified.

membrane computing; exponential function; automatic design; replacement encoding

TM769

A

1003-6954(2015)03-0050-05

2015-01-15)

賴正坤(1989)，碩士，研究方向為自然計算分支膜計算。