組織P系統的計算能力探究

李燕　王煥庭

關鍵詞：膜計算;組織P系統

基金項目：2019年校級自然科學重點項目——組織P系統在細胞分裂中的計算能力研究（項目編號TCSZ2019KJzd01）

維持人類生存的自然系統，與生俱來的錯綜復雜的相互作用機制可以看成一個龐大的計算系統。自然環境中蘊藏的一些計算規律經過分析研究，重新演繹，生成新的計算過程，這就是生物計算。如人工神經網絡，是利用信息處理技術，對人腦神經元網絡進行抽象而建立起來的一種運算模型;進化計算，是受自然界生物進化過程中“優勝劣汰”的自然選擇機制影響的智能計算。

細胞作為一個基本的生命系統，其結構復雜而精巧;各組分之間分工協作，結構與功能緊密聯系，生命活動得以在變化的環境中自我調控。細胞膜將細胞與外界環境分隔開，防止細胞外物質自由進入細胞，為細胞的生命活動提供了相對穩定的內部環境。生物膜把各種細胞器分隔開，如同一個個小的區室，作為每一個膜內部的反應相對獨立的空間，多種化學反應可以同時進行，并且互不干擾，使細胞生命活動高效有序地進行?？茖W家們對生物膜內物質的各種化學反應和細胞膜間物質的信息交流、能量交換進行抽象和概括，衍生出一種新型的生物計算——膜計算，又稱P系統，它是一種新穎的分布式并行計算模型。

P系統是膜計算的基本模型，主要通過細胞膜中對象的進化而實現信息的計算和處理。膜將整個系統劃分成不同的區域，每個區域中放置各自的進化對象及進化規則。字母表中的字符或字符串相當于計算變量，是計算直接作用的對象。進化規則類似于運算符，對象按所處區域中的規則進行演化。按照膜結構，P系統可分為三大類型：細胞型P系統、組織型P系統和神經型P系統。

組織型P系統由多個單膜細胞組成，它們依賴指定的通道進行交流。通過處理字符串和研究同一環境中多個細胞間的相互作用，組織型P系統實現計算機制。其基本膜結構如圖1所示，每個細胞中包含了不同的對象集，單個細胞與細胞之間以及細胞與環境之間采用轉運規則進行通信。組織型P系統的轉運規則可以發生在細胞1和細胞2之間，也可以發生在細胞1和細胞3之間，或者細胞1和細胞m之間，具體取決于通信通道的建立。

圖1 組織型P系統的膜結構示意圖

給出的組織P系統實例形式為：

Π=（ V，u，ε，φ1，…，φd，R，iin，，iout）

其中：

（1）V= {a，b，c，d，e};是字母表中的5個字母;

（2）u=[[]1[]2[]1]0 ，將環境看作是系統最外層的膜;

（3）ε= {a，b}，是環境中的字母表;

（4）φ1=ab4c，φ2=ab2d，φ3=c4d，分別是膜1、膜2、膜3中的初始對象，

（5）R={r1= （1，b /d ，3），r2= （2，a / c，3），r3 =（1，a / b，2），

r4 =（3， e/d2 ，0），r5= （1，d /λ，0）}，是系統的轉運規則集;

（6）iin= 1，iout= 0，前者表示輸入膜是膜1，后者表示輸出膜是環境。

圖2 組織型P系統實例示意圖

從（a）圖中，我們看見了P系統的結構以及膜1、膜2、膜3中包含的不同對象。（b）圖讓我們看到，通過規則集的運用，三個膜中的對象都發生了變化。實例中，R包含了r1、r2、r3、r4、r5五種轉運規則。當膜1中包含一個對象b、膜3中包含一個對象d時，膜1輸送一個b給膜3、膜3轉運一個d給膜1。當膜2中包含一個對象a、膜3中包含一個對象c時，膜2輸送一個a給膜3、膜3轉運一個c給膜2。當膜1中包含一個對象a并且膜2中包含一個對象b時，膜1和膜2中就會發生物質交換，稱作一次交流。規則四發生在膜3與環境之間，膜3輸送給環境一個對象e，又從環境中獲得兩個對象d。規則五表示膜1輸送給環境一個對象d，而環境不需要輸送任何對象給膜1。

在組織P系統的每一步運行中，所有可執行的對象都要求同時被執行規則，并且所有規則都以一種高度并行的方式運行。細胞被生物膜分成多個區域，各區域能夠實現同步的數據處理，多個計算單元可以合作并行的進行計算，相比傳統的獨個單元的計算，計算能力也有了顯著的提高。

參考文獻

[1] 張弘.基于膜計算的算術運算系統研究[D].重慶大學，2014.

[2] 陳海珠.膜計算應用研究[D].重慶大學，2011.

[3] 張葛祥，潘林強.自然計算的新分支——膜計算[ J].計算機學報，2010.