组织P系统的计算能力探究

李燕　王焕庭

关键词：膜计算;组织P系统

基金项目：2019年校级自然科学重点项目——组织P系统在细胞分裂中的计算能力研究（项目编号TCSZ2019KJzd01）

维持人类生存的自然系统，与生俱来的错综复杂的相互作用机制可以看成一个庞大的计算系统。自然环境中蕴藏的一些计算规律经过分析研究，重新演绎，生成新的计算过程，这就是生物计算。如人工神经网络，是利用信息处理技术，对人脑神经元网络进行抽象而建立起来的一种运算模型;进化计算，是受自然界生物进化过程中“优胜劣汰”的自然选择机制影响的智能计算。

细胞作为一个基本的生命系统，其结构复杂而精巧;各组分之间分工协作，结构与功能紧密联系，生命活动得以在变化的环境中自我调控。细胞膜将细胞与外界环境分隔开，防止细胞外物质自由进入细胞，为细胞的生命活动提供了相对稳定的内部环境。生物膜把各种细胞器分隔开，如同一个个小的区室，作为每一个膜内部的反应相对独立的空间，多种化学反应可以同时进行，并且互不干扰，使细胞生命活动高效有序地进行。科学家们对生物膜内物质的各种化学反应和细胞膜间物质的信息交流、能量交换进行抽象和概括，衍生出一种新型的生物计算——膜计算，又称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.