膜計算-譚立偉

膜計算android與算法俱樂部譚立偉參考文獻陳海珠.膜計算應(yīng)用研究.重慶大學博士學位論文,2011.4概述膜計算(MembraneComputing，也稱為P系統(tǒng))是自然計算的一個新分支，其目的是從活細胞中以及組織、器官或其他結(jié)構(gòu)的細胞之間相互協(xié)作的方式中獲得新的計算思想、設(shè)計新的計算模型。P系統(tǒng)不僅為計算機科學引入了新的分布式并行信息處理方法和技術(shù)，而且為生物系統(tǒng)的建模和仿真提供了新工具，是當前非常活躍的一個研究領(lǐng)域，預(yù)計在新一代計算系統(tǒng)、信息處理系統(tǒng)的技術(shù)開發(fā)方面將起關(guān)鍵作用。關(guān)于膜計算的研究工作可歸為三類：理論研究、應(yīng)用研究和軟、硬件實現(xiàn)研究。膜計算的理論研究主要集中于各種計算模型的建立及其計算能力(ComputationPower)的分析；膜計算的應(yīng)用研究主要是利用P系統(tǒng)的特點和各種模型求解生物學、計算機科學、語言學、社會學等方面的實際問題；而膜計算的軟硬件實現(xiàn)研究則側(cè)重于在現(xiàn)有計算機上用程序?qū)崿F(xiàn)或開發(fā)新的處理器實現(xiàn)有關(guān)的膜計算模型或求解有關(guān)問題。盡管P系統(tǒng)還處于理論研究階段，但它所具有的一些性質(zhì)如并行性、非確定性等已經(jīng)引起了越來越多學者的研究和關(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)的化學反應(yīng)與膜間的物質(zhì)流動抽象為計算過程：生物膜內(nèi)的化學反應(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í)行{b→d,ff→f,cf→cdδ}，2#膜溶解，多重集被送到1#膜中。(3)在1#膜中，按接收到的多重集分兩種情況：1)收到的f個數(shù)>=1時，f→f將一直執(zhí)行，計算無效；

2)收到的多重集為cd2e或只有規(guī)則e→(e,out)可執(zhí)行，獲得的輸出為對象e的數(shù)量，即(n+1)2。脈沖神經(jīng)P系統(tǒng)脈沖神經(jīng)P系統(tǒng)的生物學基礎(chǔ)SNP系統(tǒng)的定義SNP系統(tǒng)中基本的計算單元稱為神經(jīng)元(neuron)，神經(jīng)元內(nèi)部含有脈沖(spike)和規(guī)則(rule)，不同的神經(jīng)元通過突觸(synapse)連接在一起，脈沖通過突觸單向傳輸，實現(xiàn)神經(jīng)元之間的通信。神經(jīng)元具有打開(open)和封閉(close)兩種狀態(tài)，當神經(jīng)元處于打開狀態(tài)時，神經(jīng)元內(nèi)的規(guī)則若滿足執(zhí)行的條件則被執(zhí)行，神經(jīng)元根據(jù)該規(guī)則做相應(yīng)的動作，如向其他神經(jīng)元發(fā)送脈沖。封閉的神經(jīng)元不接收其他神經(jīng)元送來的任何脈沖，這些不被接受的脈沖因不被接收而消失(即被遺忘)。在SNP系統(tǒng)中有兩種特殊的神經(jīng)元：輸入神經(jīng)元和輸出神經(jīng)元，分別用于輸入脈沖以及輸出計算的結(jié)果或標識計算的終止。SNP系統(tǒng)中所有的脈沖都是一樣的，沒有差別，一個脈沖用一個符號a表示。SNP系統(tǒng)的計算結(jié)果可以用輸出神經(jīng)元輸出的脈沖數(shù)目來表示。此外，還可以通過輸出神經(jīng)元兩次被觸發(fā)的時間間隔表示來計算結(jié)果。一個度為m≥1的脈沖神經(jīng)P系統(tǒng)的形式化定義為：Π=(O,σ1,σ2,...,σm,syn,in,out)其中：O={a}為單字母集合，a表示一個脈沖；σi(1≤i≤m),表示系統(tǒng)Π中的m個神經(jīng)元，σi表示為(ni,Ri),其中：

ni≥0表示神經(jīng)元σi包含的脈沖數(shù)目；Ri表示神經(jīng)元σi中的規(guī)則有限集合。（關(guān)于規(guī)則見下頁）syn?{1,2,,m}×{1,2,,m}表示神經(jīng)元之間的連接關(guān)系(對應(yīng)于生物神經(jīng)系統(tǒng)中的突觸)，對每個1≤i≤m，有(i,i)?syn；in,out∈{1,2,,m}分別表示輸入和輸出神經(jīng)元。SNPSystem中神經(jīng)元的規(guī)則兩種類型：激發(fā)規(guī)則：E/ac→ap;d其中E表示字符a上的正則表達式，c≥1，d≥0，p≥1，且c≥p；遺忘規(guī)則：E'/as→λ其中E′表示字符a上的正則表達式，s≥1。對激發(fā)規(guī)則和遺忘規(guī)則總有：L(E)∩L(E')=?；稱E/ac→a;d為標準激發(fā)規(guī)則(即p=1)稱as/as→λ為標準遺忘規(guī)則(即E'=as)。對激發(fā)規(guī)則，若E=ac，則將之簡寫為ac→ap;d；若d=0，則寫成E/ac→ap，若同時滿足，則寫成ac→ap。對遺忘規(guī)則，若E'=as,則簡寫成as→λ。規(guī)則的使用激發(fā)規(guī)則：E/ac→ap;d在某時刻，如果神經(jīng)元σi包含k個脈沖，且有ak∈L(E)及k≥c，則σi此時可以使用激發(fā)規(guī)則E/ac→ap;d。使用此規(guī)則后，σi將消耗c個脈沖(于是σi剩余k?c個脈沖)，同時產(chǎn)生p個新脈沖，延遲d個單位時間后向與它連接的其他所有神經(jīng)元分別發(fā)送p個脈沖。另外，使用這條規(guī)則后的d個時間單位內(nèi)，σi是封閉的，不能接收其他神經(jīng)元發(fā)送過來的任何脈沖。如果σi在第t步使用激發(fā)規(guī)則E/ac→ap;d(d≥1)，則σi在第t，t+1，…，t+d?1步都是封閉的。當一個神經(jīng)元處于封閉狀態(tài)時，它所具有的任何規(guī)則都不能使用；只有當它變?yōu)殚_放狀態(tài)后，才能使用滿足正則表達式的規(guī)則。若某個神經(jīng)元向一個封閉的神經(jīng)元發(fā)送脈沖，則封閉的神經(jīng)元此時不能接收到這些脈沖，這些脈沖被丟棄(即被遺忘)。對于輸出神經(jīng)元來說，它可以向環(huán)境發(fā)送脈沖，而這些脈沖將被檢測到并作為輸出結(jié)果來處理。規(guī)則的使用遺忘規(guī)則：E'/as→λ若神經(jīng)元σi包含k個脈沖，且有ak∈L(E')及k≥s，則此σi此時可以使用遺忘規(guī)則E'/as→λ。注意此時σi中的所有激發(fā)規(guī)則都不能使用。當神經(jīng)元σi使用此規(guī)則后，將消耗s個脈沖，但不會產(chǎn)生任何新脈沖?？赡艽嬖贚(E1)∩L(E2)≠?，因此在一個神經(jīng)元中可能存在多條規(guī)則可以使用的情形。在任何時刻，若神經(jīng)元σi中有多條規(guī)則可以使用，那么此神經(jīng)元能且只能使用一條規(guī)則，并且此規(guī)則的選取是隨機的。將只使用標準激發(fā)規(guī)則和標準遺忘規(guī)則的SNP系統(tǒng)稱為標準SNP系統(tǒng)。標準脈沖神經(jīng)膜系統(tǒng)在并行模式下工作(即系統(tǒng)是同步的)，但在每個神經(jīng)元內(nèi)，每步至多只能使用規(guī)則一次。窮舉使用規(guī)則的SNP系統(tǒng)M.Ioneseu和Gh.P?un對SNP系統(tǒng)的標準定義進行擴展而得到。SNP系統(tǒng)在窮舉使用規(guī)則模式下，每個神經(jīng)元在每步需要盡可能多次的使用一條激發(fā)規(guī)則，使該神經(jīng)元中剩余的脈沖數(shù)最小。例如，假設(shè)神經(jīng)元σi內(nèi)有規(guī)則E/ac→ap(p≥0)，若σi內(nèi)有k=sc+r（ak∈L(E)，r<c）個脈沖，則消耗sc個脈沖，余下r個脈沖，產(chǎn)生sp個脈沖。對于窮舉使用規(guī)則的SNP系統(tǒng)，不僅在所有神經(jīng)元上系統(tǒng)是在并行模式下工作的，在每個神