陳弋璽

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

0 引言

歐洲科學(xué)院院士、羅馬尼亞科學(xué)院院士Gheorghe Pǎun于1998年在研究DNA計算與生物細(xì)胞結(jié)構(gòu)之間的關(guān)系時，根據(jù)細(xì)胞處理化學(xué)物質(zhì)的機(jī)理，提出了第一個膜計算模型［1］。該模型通常被稱作膜系統(tǒng)或P系統(tǒng)。一個膜系統(tǒng)可以形式化地描述為:

Π =(O，μ，W，R)

其中，O:預(yù)定義的膜系統(tǒng)對象集;μ:預(yù)定義的膜結(jié)構(gòu)，設(shè)膜結(jié)構(gòu)由m層膜構(gòu)成，則各層膜由有限集合H={1，2，...，m}中的元素標(biāo)定;W:W={w1，w2，...，wm}，其中wi表示膜i中由對象集O中的元素構(gòu)成的初始對象集;R:膜系統(tǒng)的規(guī)則集。

Gheorghe Pǎun在2000年正式發(fā)表了第一篇關(guān)于膜計算的論文［2］。2003年2月，該論文被美國科學(xué)情報研究所(ISI)列為計算機(jī)領(lǐng)域的快速突破文章，同年10月，膜計算在美國ISI公司旗下著名的ESI數(shù)據(jù)庫中被選為計算機(jī)科學(xué)新興研究前沿，這也標(biāo)志著膜計算正式成為一個新興的研究領(lǐng)域。自Gheorghe Pǎun提出了膜計算的概念以來，受到國內(nèi)外眾多學(xué)者廣泛關(guān)注［3］。迄今為止，膜計算作為自然計算的一個重要分支，在其理論研究方面已取得很多重大成果。膜計算的理論研究大多從數(shù)學(xué)和計算機(jī)理論出發(fā)，結(jié)合生命體中具體的細(xì)胞模型，提出了不同結(jié)構(gòu)的多類膜系統(tǒng)(細(xì)胞型膜系統(tǒng)、神經(jīng)性膜系統(tǒng)、組織性膜系統(tǒng)等)［4］，探討各類膜系統(tǒng)的運算機(jī)理與計算能力，進(jìn)而設(shè)計出能夠解決某一特定問題的膜系統(tǒng)［5-6］。但是，膜計算應(yīng)用方面的研究大多還不夠成熟，主要是將膜計算與進(jìn)化算法相結(jié)合，提出了膜算法［7-8］。有學(xué)者提出，正是由于膜系統(tǒng)的可編程性、可模塊化、可擴(kuò)展性與可理解性問題沒有得到很好的解決，才限制了膜計算應(yīng)用發(fā)展［9］。其中可編程性問題就是指如何利用計算機(jī)程序模擬膜計算的過程，包括用算法實現(xiàn)膜系統(tǒng)的自動設(shè)計。具體到膜系統(tǒng)的自動設(shè)計問題，就是指研究者只需給出膜系統(tǒng)需要解決的問題，計算機(jī)就能通過程序設(shè)計出滿足要求的膜系統(tǒng)，這將大大降低膜系統(tǒng)設(shè)計的難度。本文所研究的內(nèi)容主要是利用基本算術(shù)運算膜系統(tǒng)作為模塊，構(gòu)建復(fù)雜的混合算術(shù)運算膜系統(tǒng)的自動設(shè)計算法，為研究膜系統(tǒng)的可編程性問題探索一條新的途徑。

1 設(shè)計方法

本文主要的思想就是利用基本算術(shù)運算膜系統(tǒng)作為基本模塊，構(gòu)建混合算術(shù)運算膜系統(tǒng)。其中對象集和規(guī)則集都取自基本算術(shù)運算膜系統(tǒng)，并輔以一些輔助規(guī)則。但如何構(gòu)建膜系統(tǒng)的膜結(jié)構(gòu)則是本文首先需解決的問題。文獻(xiàn)［10］中提到，任何膜系統(tǒng)的膜結(jié)構(gòu)都可以看作文氏圖，而將該文氏圖用歐拉圖表示則形成了一棵樹(如圖1所示)。所以，如果能用一棵樹來表示一個算術(shù)表達(dá)式，便能生成對應(yīng)的膜結(jié)構(gòu)。

圖1 膜結(jié)構(gòu)示例及其樹狀表示

圖2 波蘭式生成算法

1.1 表達(dá)式預(yù)處理

在通常的表達(dá)式中，二元算數(shù)運算符總是置于與之相關(guān)的兩個運算操作數(shù)之間，這種表示法被稱作中綴表示法。中綴表達(dá)式的計值，并非按運算符出現(xiàn)的自然順序來執(zhí)行其中的各個運算，而是根據(jù)運算符間的優(yōu)先關(guān)系來確定運算的次序，此外，還應(yīng)顧及括號規(guī)則。因此，使用機(jī)器通過中綴表達(dá)式求得混合算數(shù)運算表達(dá)式的值會較為復(fù)雜。為此，波蘭邏輯學(xué)家盧卡西維茨(J.Lukasiewicz)在1929年提出了另一種算術(shù)運算表達(dá)式的表達(dá)方法，即后綴表達(dá)式或逆波蘭式［11］。按此方法，每一運算符都置于其運算對象之后，這樣表達(dá)式中各個運算是按運算符出現(xiàn)的順序進(jìn)行的。另外，還有一種表示方法與后綴表示方法相反，即前綴表達(dá)式或波蘭式。輸入的中綴表達(dá)式經(jīng)圖2所示的算法處理后便能得到相應(yīng)的前綴表達(dá)式。

通過波蘭式可以將一個算術(shù)運算表達(dá)式轉(zhuǎn)換為一棵二叉樹［12］，從而可生成對應(yīng)的膜結(jié)構(gòu)。例如算術(shù)運算表達(dá)式“4+3×2－1”經(jīng)過文獻(xiàn)［12］中算法處理后，便能轉(zhuǎn)換成如與表達(dá)式對應(yīng)的二叉樹，由此二叉樹便能進(jìn)一步生成對應(yīng)的膜系統(tǒng)膜結(jié)構(gòu) (如圖3所示)。

圖3 表達(dá)式的樹狀表示與其對應(yīng)的膜結(jié)構(gòu)

1.2 膜系統(tǒng)膜結(jié)構(gòu)生成算法

通過算法處理后，得到了算術(shù)運算表達(dá)式的波蘭式表示法，便能按照圖4中的算法流程圖生成對應(yīng)的混合算術(shù)運算膜系統(tǒng)的膜結(jié)構(gòu)。這里對該算法作較為詳細(xì)的說明。

首先，對圖4算法中的參數(shù)作出說明:

Expr:存儲混合算術(shù)運算表達(dá)式的字符串?dāng)?shù)組;

CurrentParentMembrane:每當(dāng)在構(gòu)建一個新的膜m時，需要指明m的父膜，從而才能確定m在膜系統(tǒng)中的所在區(qū)域，如在圖1中，膜1即為膜2和膜3的父膜。該參數(shù)為即將構(gòu)建膜的父膜;

CurrentMembrane:當(dāng)前正在構(gòu)造的膜;

CurrentParentMembrane.ParentMembrane:為當(dāng)前父膜的父膜。

該算法的執(zhí)行過程如下:

(1)首先利用圖2所示的算法，將一個中綴算術(shù)運算表達(dá)式轉(zhuǎn)成前綴表達(dá)式，并存儲于字符串?dāng)?shù)組Expr中。

(2)構(gòu)建子膜時，根據(jù)Expr［i］的屬性(是否為操作數(shù))構(gòu)建對應(yīng)的子膜，主要完成對各個膜進(jìn)行標(biāo)號，再根據(jù)膜標(biāo)號選擇相應(yīng)的規(guī)則和初始對象放入膜中。此外，為了使各個基本算術(shù)運算膜系統(tǒng)能協(xié)調(diào)工作，還應(yīng)根據(jù)當(dāng)前膜的計算結(jié)果，作為下次運算的操作數(shù)次序加入一些輔助規(guī)則。在定義膜標(biāo)號時，需要判斷當(dāng)前膜的計算結(jié)果作為外層膜操作數(shù)的次序。根據(jù)波蘭式所具備的特點，可以按照圖5所示的方法進(jìn)行判斷。

圖4 混合算術(shù)運算膜系統(tǒng)膜結(jié)構(gòu)生成算法

(3)根據(jù)Expr［0］完成對表層膜(skin)的構(gòu)建，同時確定表層膜的標(biāo)號，并將CurrentParentMembrane參數(shù)設(shè)為skin，以便將其作為內(nèi)層膜的父膜。

(4)依次掃描 Expr數(shù)組，并判斷 Expr［i］是否為操作數(shù)，隨后以CurrentParentMembrane為父膜構(gòu)建當(dāng)前膜，同時定義其膜標(biāo)號。

(5)若 Expr［i］為操作符，則需要與 Current-ParentMembrane的操作符比較優(yōu)先級，若Expr［i］的優(yōu)先級更大，則需要將CurrentParentMembrane更新為當(dāng)前正在構(gòu)建的膜，即CurrentMembrane。需要說明的是，由文獻(xiàn)［12］中的算法生成的運算表達(dá)式二叉樹中的葉子節(jié)點一定是操作數(shù)，而葉子節(jié)點對應(yīng)膜結(jié)構(gòu)中的基本膜，且CurrentParentMembrane的值域是所有非基本膜，因此，CurrentParentMembrane一定對應(yīng)一個操作符。

(6)若Expr［i］為第一操作數(shù)，且不滿足程序結(jié)束條件時，需將CurrentParentMembrane更新為其父膜，即 CurrentParentMembrane.ParentMembr-ane。

(7)當(dāng)對Expr數(shù)組中每個元素都掃描完畢并構(gòu)建了相應(yīng)的子膜后，混合算術(shù)運算膜系統(tǒng)膜結(jié)構(gòu)建立完成，程序退出。

圖5 判斷Expr［i］的結(jié)果作為操作數(shù)的次序算法

2 混合算術(shù)運算膜系統(tǒng)

受電子計算機(jī)對數(shù)字計算規(guī)則的啟發(fā)［13］，本文提出一系列二進(jìn)制基本算術(shù)運算膜系統(tǒng)，并在此基礎(chǔ)上實現(xiàn)二進(jìn)制混合算術(shù)運算膜系統(tǒng)。

2.1 算術(shù)運算膜系統(tǒng)模塊設(shè)計

為了設(shè)計二進(jìn)制算術(shù)運算膜系統(tǒng)，首先對膜系統(tǒng)中的對象的二進(jìn)制數(shù)編碼規(guī)則進(jìn)行說明。本節(jié)中，主要用 ai、bi、ci對二進(jìn)制數(shù)進(jìn)行編碼，其中 ai對應(yīng)第一操作數(shù)，bi對應(yīng)第二操作數(shù)，ci對應(yīng)計算結(jié)果。若系統(tǒng)中含有對象ci，則表示第一操作數(shù)的第i位為1，否則為0。下面將在上述編碼規(guī)則的基礎(chǔ)上給出二進(jìn)制混合算術(shù)運算膜系統(tǒng)要用到的基本模塊。

(1)十進(jìn)制-二進(jìn)制膜系統(tǒng)(Πcode)。

為了方便起見，本文的膜系統(tǒng)輸入采用十進(jìn)制算術(shù)運算膜系統(tǒng)的編碼方式。因此，對于每個輸入數(shù)據(jù)，都將經(jīng)過一個十進(jìn)制-二進(jìn)制膜系統(tǒng)完成編碼的轉(zhuǎn)換。這里，根據(jù)編碼轉(zhuǎn)換膜系統(tǒng)規(guī)則的特點，設(shè)計出十進(jìn)制-二進(jìn)制編碼轉(zhuǎn)換單膜系統(tǒng)Πcode，可以得到Πcode的規(guī)則集如下:

在構(gòu)建混合算術(shù)運算膜系統(tǒng)時，根據(jù)各層膜中的輸入對象，將編碼轉(zhuǎn)化膜系統(tǒng)的規(guī)則集加入其中。在實驗中，如果輸入為第一操作數(shù)，則需將Rcode中的s與si改成a和ai，并修改規(guī)則中的膜標(biāo)號;相應(yīng)地，如果是第二操作數(shù)，則需改成b和bi。

(2)二進(jìn)制加法膜系統(tǒng)(Π2－add)。

從這一步開始，設(shè)計得到的3種基本算術(shù)運算膜系統(tǒng)都是在二進(jìn)制條件下實現(xiàn)的，使用的規(guī)則都是借鑒于計算機(jī)中實現(xiàn)二進(jìn)制算術(shù)運算時所用到的計算法則，直接給出3種二進(jìn)制基本算術(shù)運算膜系統(tǒng)。

其中:

需指出ai和bi是作為輸入傳入膜系統(tǒng)的，并不能作為膜系統(tǒng)的初始對象，因此才有w1=λ。

(3)二進(jìn)制減法膜系統(tǒng)(Π2－sub)。

其中:

與 Π2－add類似，ai和 bi將作為輸入傳入膜系統(tǒng)。

(4)二進(jìn)制乘法膜系統(tǒng)(Π2－mul)。

其中:

可以看出，實現(xiàn)二進(jìn)制乘法要比實現(xiàn)加減法更為復(fù)雜，并且引入了一系列的輔助對象。對這些對象進(jìn)行簡要的說明:a1，i和 a0，i分別表示被乘數(shù)第 i位為 1或0，在Π2－mul中，僅僅用ai對被乘數(shù)進(jìn)行編碼很難實現(xiàn)乘法，因此引入這兩個對象;bj，i表示乘數(shù)第j位為1，bj，i與被乘數(shù)第 i位(a1，i或 a0，i)相乘時，引入 bj，i后能用膜系統(tǒng)實現(xiàn)交叉相乘。此外，兩個4位數(shù)的乘法可能會產(chǎn)生8位數(shù)的積，因此有ck(0≤k≤7)。

2.2 混合算術(shù)運算膜系統(tǒng)設(shè)計

由基本算術(shù)運算膜系統(tǒng)模塊構(gòu)建混合算術(shù)運算膜系統(tǒng)還需解決兩個問題。首先，二進(jìn)制混合算術(shù)運算膜系統(tǒng)需要將每層膜中的結(jié)果對象c轉(zhuǎn)換為外層膜操作數(shù)對象a(對應(yīng)第一操作數(shù))或b(對應(yīng)第二操作數(shù))。為了解決這一問題，引入一組優(yōu)先級規(guī)則，使得所有的轉(zhuǎn)運規(guī)則優(yōu)先級都低于其它規(guī)則。設(shè)2.1中所有膜系統(tǒng)模塊中的規(guī)則集合為Rcac，轉(zhuǎn)運規(guī)則集合為 Rtra，則有 ρRcac＞ ρRtra，其中 Rtra定義為:

為方便起見，實驗時的算術(shù)運算表達(dá)式最多含有一次乘法，結(jié)果為16位的二進(jìn)制數(shù)。

此處需要通過膜標(biāo)號來確定每一層膜的功能，因此本文采用3位字符串?dāng)?shù)組進(jìn)行膜標(biāo)號編碼，分別表示該層膜在運算表達(dá)式中的次序、對應(yīng)操作符以及其結(jié)果作為下一操作符的操作數(shù)次序。這里給出二進(jìn)制混合算術(shù)運算膜系統(tǒng)解析膜標(biāo)號添加規(guī)則的算法(如圖6所示)。

圖6 二進(jìn)制混合算術(shù)運算膜系統(tǒng)規(guī)則添加算法

3 實驗結(jié)果與分析

本文采用一個混合算術(shù)運算表達(dá)式作為測試用例，實驗中作為測試用例的四則運算表達(dá)式為:eq≡4+3×2－1。首先，按照圖2所示的算法將表達(dá)式轉(zhuǎn)為前綴表達(dá)式，處理后的表達(dá)式為:eq'≡－1+×234，再按照圖4所示的算法構(gòu)建膜系統(tǒng)的膜結(jié)構(gòu);然后將基本算術(shù)運算膜系統(tǒng)視作模塊，構(gòu)建混合算術(shù)運算膜系統(tǒng)。實驗結(jié)果是在P-Lingua膜計算仿真平臺［14］下得到的。下面給出混合算術(shù)運算膜系統(tǒng)的設(shè)計結(jié)果。

設(shè)二進(jìn)制混合算術(shù)運算膜系統(tǒng)為 Π2－com，則Π2－com可形式化地描述為:

其中:

O為所有二進(jìn)制基本算術(shù)運算膜系統(tǒng)對象集的并集;

這里，規(guī)則集較為復(fù)雜，將其分為3個子集，分別表示編碼轉(zhuǎn)換規(guī)則(Rcode)、算數(shù)運算規(guī)則(Rcac)和對象轉(zhuǎn)運規(guī)則(Rtra)?，F(xiàn)分別給出這3個規(guī)則子集的詳細(xì)描述:

Π2－com的計算結(jié)果同樣也是二進(jìn)制編碼，即用對象ci表示。

4 結(jié)束語

從實驗結(jié)果中可以看到，利用本文的算法得到的膜系統(tǒng)能實現(xiàn)計算給定的混合算術(shù)運算表達(dá)式，但從測試結(jié)果可以看到，該膜系統(tǒng)的規(guī)則集較為復(fù)雜，且含有較多的對象。在以后的研究中，可針對此問題做出改進(jìn)，簡化基本算術(shù)運算膜系統(tǒng)模塊，對算法進(jìn)行進(jìn)一步的改進(jìn)，使獲得的膜系統(tǒng)具有更為簡單的結(jié)構(gòu)和對象集。

［1］張葛祥，潘林強(qiáng).自然計算的新分支——膜計算［J］.計算機(jī)學(xué)報，2010，33(2):208-214.

［2］Pǎun G.Computing with membranes［J］.Journal of Computer and System Sciences，2000，61(1):108-143.

［3］黃小麗.細(xì)胞型膜系統(tǒng)設(shè)計方法研究［D］.成都:西南交通大學(xué)，2012.

［4］Pǎun G.A quick introduction to membrane computing［J］.The Journal of Logic and Algebraic Programming，2010，79(6):291-294.

［5］Pérez-Jiménez M，Jiménez á，Caparrini F.Complexity classes in models of cellular computing with membranes［J］.Natural Computing，2003，2(3):265-285.

［6］Pǎun G，Suzuki Y，Tanaka H.On the power of membrane division in P systems［J］.Theoretical Computer Science，2004，324(1):61-85.

［7］Nishida T Y.Membrane algorithms［J］.Lecture Notes in Computer Science，2006，3850:55-66.

［8］黃亮.膜計算優(yōu)化方法研究［D］.杭州:浙江大學(xué)，2007.

［9］Pǎun G，Perez-Jimenez M.Membrane computing:Brief introduction，recent results and applications［J］.Biosystems，2006，85(1):11-22.

［10］Pǎun G.From cells to computers:Computing with membranes(P systems)［J］.Biosystems，2001，59(3):139-158.

［11］毛紅梅，嚴(yán)云洋.編譯原理［M］.北京:清華大學(xué)出版社，2011:144-147.

［12］何志宏，毛志軍.表達(dá)式與二叉樹的相互轉(zhuǎn)換［J］.電腦知識與技術(shù)，2010，6(5):1201-1203.

［13］雷麗文，朱曉華，蔡征宇，等.微機(jī)原理與接口技術(shù)［M］.北京:電子工業(yè)出版社，2005:34-42.

［14］García-Quismondo M，Gutiérrez-Escudero R，Pérez-Hurtado I，et al.An overview of P-Lingua 2.0［J］.Lecture Notes in Computer Science，2010，5957:264-288.