陳弋璽

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

0 引言

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

Π =(O，μ，W，R)

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

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

1 設(shè)計(jì)方法

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

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

圖2 波蘭式生成算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中:

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

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

其中:

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

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

其中:

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

其中:

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

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

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

4 結(jié)束語

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

［1］張葛祥，潘林強(qiáng).自然計(jì)算的新分支——膜計(jì)算［J］.計(jì)算機(jī)學(xué)報(bào)，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è)計(jì)方法研究［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］黃亮.膜計(jì)算優(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í)與技術(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.