膜計算-譚立偉

膜計算android與算法俱樂部譚立偉參考文獻陳海珠.膜計算應(yīng)用研究.重慶大學(xué)博士學(xué)位論文,2011.4概述膜計算(MembraneComputing，也稱為P系統(tǒng))是自然計算的一個新分支，其目的是從活細胞中以及組織、器官或其他結(jié)構(gòu)的細胞之間相互協(xié)作的方式中獲得新的計算思想、設(shè)計新的計算模型。P系統(tǒng)不僅為計算機科學(xué)引入了新的分布式并行信息處理方法和技術(shù)，而且為生物系統(tǒng)的建模和仿真提供了新工具，是當前非?；钴S的一個研究領(lǐng)域，預(yù)計在新一代計算系統(tǒng)、信息處理系統(tǒng)的技術(shù)開發(fā)方面將起關(guān)鍵作用。關(guān)于膜計算的研究工作可歸為三類：理論研究、應(yīng)用研究和軟、硬件實現(xiàn)研究。膜計算的理論研究主要集中于各種計算模型的建立及其計算能力(ComputationPower)的分析；膜計算的應(yīng)用研究主要是利用P系統(tǒng)的特點和各種模型求解生物學(xué)、計算機科學(xué)、語言學(xué)、社會學(xué)等方面的實際問題；而膜計算的軟硬件實現(xiàn)研究則側(cè)重于在現(xiàn)有計算機上用程序?qū)崿F(xiàn)或開發(fā)新的處理器實現(xiàn)有關(guān)的膜計算模型或求解有關(guān)問題。盡管P系統(tǒng)還處于理論研究階段，但它所具有的一些性質(zhì)如并行性、非確定性等已經(jīng)引起了越來越多學(xué)者的研究和關(guān)注。隨著研究的深入，由原始模型衍生出了許多不同的膜計算模型，主要有：類細胞P系統(tǒng)(Cell-likePSystems)、類組織P系統(tǒng)(Tissue-likePSystems)類神經(jīng)P系統(tǒng)(Neural-likePSystems)它們分別是從細胞、組織以及神經(jīng)系統(tǒng)中抽象而來的計算模型。形式語言基礎(chǔ)對于字母表V，V*(V的閉包)表示V上所有有限字符串的集合?？兆址忙吮硎尽上的所有非空有限字符串用V+(V的正閉包)表示，即V+=V*?{λ}V*的任意一個子集稱為V上的一個語言如果V={a}（這時稱V為單字母表），則{a}*，{a}+分別簡記為a*，a+字母表V上的正則表達式(正規(guī)式)定義如下：①λ和a∈V都是正則表達式；②如果E1，E2是V上的正則表達式，則E1E2,E1∪E2，E1+都是V上的正則表達式；③除①、②之外，V上不再有其他正則表達式。正則表達式E對應(yīng)于一個語言L(E)，L(E)按如下方式定義：①L(λ)={λ}以及對每個a∈V，有L(a)={a}；②對V上的任意表達式E1，E2，有L(E1∪E2)=L(E1)∪L(E2)L(E1E2)=L(E1)L(E2)L(E1+)=L(E1)+在不引起歧義的前提下，正則表達式中的某些括號可以省略。另外，對于任意正則表達式E，把E+∪{λ}簡記為E*。類細胞P系統(tǒng)類細胞P系統(tǒng)是第一個被提出來的P系統(tǒng)。類細胞P系統(tǒng)將生物膜內(nèi)的化學(xué)反應(yīng)與膜間的物質(zhì)流動抽象為計算過程：生物膜內(nèi)的化學(xué)反應(yīng)就是通常理解的計算過程，而物質(zhì)在不同膜之間的流動則對應(yīng)于通常意義計算系統(tǒng)中的消息傳遞，細胞或細胞器成為計算單元。類細胞P系統(tǒng)結(jié)構(gòu)的示意圖最外邊的膜稱為皮膚膜(skinmembrane)，它將本系統(tǒng)與外在環(huán)境分開。如果一個膜的內(nèi)部不存在其他膜，就稱這個膜為基本膜(elementalmembrane)，否則稱為非基本膜(non-elementalmembrane)。每一個膜定義了一個區(qū)域：對于基本膜，這個區(qū)域就是它所包含的空間；對于非基本膜，區(qū)域是指這個膜和它直接包含的其他膜之間的空間。膜結(jié)構(gòu)的描述通常有兩種方式:樹形結(jié)構(gòu)-膜的層次結(jié)構(gòu)特征適合于用樹結(jié)構(gòu)來描述：皮膚做為根節(jié)點，基本膜做為葉節(jié)點。廣義表用嵌套結(jié)構(gòu)即是用字符串來表示膜結(jié)構(gòu)。當i#膜為基本膜時，表示為：[i]i；當k#膜包含在i#膜內(nèi)部時，表示為[i[k]k]i。一對括號[]表示一個膜，括號的下標為膜的標號。例如，上圖的膜結(jié)構(gòu)可表示為：[1[2]2[3]3[4[5]5[6[8]8[9]9]6

[7]7]4]1。在膜結(jié)構(gòu)的描述中，同一層次的膜的排列順序是任意的。故對同一個P系統(tǒng)，其描述形式不是唯一的。在生物膜內(nèi)存在多種物質(zhì)，如離子、小分子、微分子等。每種物質(zhì)通常不止一個，并且是無序的。在P系統(tǒng)中使用小寫字母來表示這些物質(zhì)，這樣膜中含有的物質(zhì)就可以用多重集表示。所謂多重集是指允許有相同元素的集合。例如，A={a,a,b,c,c,c}是多重集，記為{a2,b,c3}或a2bc3。多重集表示是無序的，即a2bc3與bc3a2是同一個多重集。膜作為細胞的邊界，細胞內(nèi)包含的物質(zhì)是膜計算的對象，物質(zhì)的反應(yīng)以及膜之間物質(zhì)的流動是膜計算的過程，這一過程中膜內(nèi)物質(zhì)及其數(shù)量發(fā)生改變，不同的改變過程對應(yīng)著不同的進化規(guī)則。P系統(tǒng)中，往往存在多種對象和多個進化規(guī)則，規(guī)則執(zhí)行的原則是:不確定性

-當有n個規(guī)則需要執(zhí)行m個，具體是哪m個是隨機的最大并行性-每次執(zhí)行所有可執(zhí)行的規(guī)則都必須執(zhí)行且同時執(zhí)行。給定一個P系統(tǒng)，即給定了一個膜結(jié)構(gòu)，并且各個膜里都包含有相應(yīng)的字符串和進化規(guī)則，這個稱為P系統(tǒng)的初始格局。從初始格局開始，P系統(tǒng)的各個膜不確定、最大并行地使用規(guī)則，系統(tǒng)每運行一步(也稱為一個計算步)，當前格局就會做相應(yīng)的改變進入一個新格局。經(jīng)過若干計算步，形成一系列的格局。當沒有規(guī)則可以執(zhí)行，系統(tǒng)進入停機狀態(tài)。整個格局序列被稱為P系統(tǒng)的一次計算，被送到環(huán)境或指定膜中的對象即是計算的結(jié)果。若P系統(tǒng)的規(guī)則一直執(zhí)行，無法進入停機狀態(tài)，則計算無效，也就沒有計算結(jié)果。轉(zhuǎn)移P系統(tǒng)、協(xié)同P系統(tǒng)、活性膜P系統(tǒng)是類細胞P系統(tǒng)的三種基本模型，它們從不同角度模擬了細胞內(nèi)物質(zhì)對象的變化過程，故采用不同的規(guī)則。其中，轉(zhuǎn)移P系統(tǒng)是膜計算應(yīng)用中最常使用的一種計算模型，其形式化定義為：O是非空有限的字符集，每個符號表示膜結(jié)構(gòu)中的一種對象(也即物質(zhì))μ是膜結(jié)構(gòu)，度為m，每個膜都有相應(yīng)的標號，H={1,2,,m}為∏的標號集合；wi

(i=1...m)為i#膜中對象的集合，用多重集表示，wi=λ表示i#膜內(nèi)沒有任何對象；Ri為i#膜內(nèi)的進化規(guī)則(定義見下頁)i0是膜結(jié)構(gòu)的輸出區(qū)域，該區(qū)域最后保存計算結(jié)果。進化規(guī)則形式為u→v或u→vδ，u∈O+，v∈(O×Tar)*,Tar={here,in,out}，Tar表示生成物v的去向：here表示v留在i#膜內(nèi)；inj表示v被送至j#膜內(nèi)，j#膜是i#膜的子膜；out表示v被送至i#膜外成為其父膜中的對象。δ是溶解操作，它溶解對象u所在的i#膜，其所在膜內(nèi)所有的對象都被釋放到其父膜內(nèi)，并且定義在i#膜內(nèi)的規(guī)則也會跟著消失，δ操作不能應(yīng)用于皮膚膜。在細胞的進化中，除了細胞內(nèi)物質(zhì)種類、數(shù)量變化外，還會發(fā)生細胞分裂等細胞繁殖活動?；钚阅系統(tǒng)即是抽象這一細胞活動而得到的計算模型。此類P系統(tǒng)將膜也作為規(guī)則處理對象，其規(guī)則包括膜的溶解、膜分裂、膜創(chuàng)建、膜分離和膜合并等。采用活性膜P系統(tǒng)進行計算時，膜結(jié)構(gòu)隨著膜操作規(guī)則的執(zhí)行而發(fā)生著變化。活性膜P系統(tǒng)的一般形式與轉(zhuǎn)移P系統(tǒng)的相同，區(qū)別在于規(guī)則不同?；钚阅系統(tǒng)使用的規(guī)則為：對象進化規(guī)則：當h#膜所帶電荷為e時(當e為0時表示h#膜沒有極性，此時可不必寫出，下同)，其中的對象a可進化為v(v為對象集合)。通信規(guī)則：當h#膜所帶電荷為e1時，膜外對象a可進入h#膜且進化為對象b；當h#膜所帶電荷為e2時，膜內(nèi)對象a可移出h#膜之外(進入h#膜的上一層膜)且進化為對象b。(注意，原文有誤)Π中規(guī)則的執(zhí)行仍然采用不確定、最大并行原則。對②～④類型的規(guī)則，在同一時刻每個膜中只能使用一種，而規(guī)則①可與②～④同時使用。舉例以下圖的轉(zhuǎn)移P系統(tǒng)為例來解釋P系統(tǒng)的計算過程。該系統(tǒng)描述為：計算過程為：（1）僅有3#膜的規(guī)則能被執(zhí)行，顯然，在同一時刻，{a→ab,f→ff}與{a→bδ,f→ff}僅有其中一組能被執(zhí)行?，F(xiàn)假設(shè){a→ab,f→ff}執(zhí)行n次后再執(zhí)行一次{a→bδ,f→ff}。因a→bδ的執(zhí)行，使3#膜被溶解，多重集(n≥0)被帶到2#膜中。(注意，原文有誤)(2)在2#膜中，分兩種情況：1)n=0，多重集為bcf2。{b→d,ff→f}或{b→d,cf→cdδ}能先執(zhí)行。a.先執(zhí)行{b→d,ff→f}，然后只有{d→de,cf→cdδ}能被執(zhí)行。此時，2#膜被溶解，多重集cd2e被送到1#膜中。b.先執(zhí)行{b→d,cf→cdδ}，2#膜被溶解，多重集cd2f被送到1#膜中。2)n>0，多重集為。a.先執(zhí)行{b→d,ff→f}，得到多重集。這時再執(zhí)行規(guī)則集{d→de,ff→f}，得到，重復(fù)執(zhí)行此規(guī)則集k(k<n)次后，得到：當k=n時，得多重集，這時可執(zhí)行的規(guī)則集為{d→de,cf→cdδ}，執(zhí)行之，2#膜溶解，多重集被送到1#膜中；當k≠n時，執(zhí)行規(guī)則集{d→de,ff→f,cf→cdδ}，2#膜溶解，被送到1#膜中。b.先執(zhí)