第6章　膜计算

6.1　膜计算的提出

膜计算（Membrane Computing，MC）是1998年由欧洲科学院院士、罗马尼亚科学家Pǎun在芬兰图尔库计算机研究中心的研究报告中提出的。有关膜计算的论文Computing with membrane于2000年在Journal of Computer and System Science上发表^[25]。

Pǎun在深入研究DNA分子计算的基础上，受生物细胞的启发，提出了膜计算的概念。膜计算的本质是从活细胞以及由细胞组成的组织或器官的功能和结构中抽象出模型或计算思想。它是一种具有层次结构的分布式并行计算模型。从微观的角度看，细胞中的细胞核、泡囊等被抽象成一个细胞中的细胞膜。这些膜将各个计算单元按区域划分，其中的数据结构具有多重性，可以用字符集或字符串来表示。生物细胞膜内的生化反应或细胞膜之间的物质交流被看作一种计算过程，甚至细胞之间的物质交换也可以看作计算单元之间的信息交流。从某种意义上来说，可以将整个生物体看作一个细胞膜，甚至可以将一个生物系统看作一个膜系统。

6.2　细胞膜的结构、模型及功能

1. 细胞及细胞膜的结构

细胞是构成生命机体的基本单位，其机能主要表现在3方面：一是细胞能够利用能量和转变能量，以维持细胞各种生命活动；二是具有生物合成的能力，能把小分子的简单物质合成大分子的复杂物质；三是具有自我复制和分裂繁殖的能力，能将细胞的特性遗传给下一代细胞。此外，细胞还具有协调细胞机体整体生命的能力等。

一个真核细胞的结构如图6.1所示。细胞内部空间包含细胞核、线粒体、高尔基体和液胞等。细胞核含有细胞生命活动的最主要的遗传物质，包括核膜、核纤层、核基质、染色质和核仁等部分。染色质DNA是含有大量基因的生命遗传物质，因此细胞核是细胞生命活动的控制中心。线粒体是由内膜和外膜包裹着的囊状结构，囊内是液态的基质。在细胞中它不断移动并不时改变着自身的形状。线粒体是细胞进行氧化呼吸，产生能量的地方。高尔基体由扁平的膜囊组成，它将蛋白质和脂质集中起来，向细胞的特殊位置派送。高尔基体完成细胞分泌物的最后加工和包装。

图6.1　真核细胞膜的结构

虽然细胞的形态结构与机能是多种多样的，但是它们在形态结构与机能上又有共同的特征。它的外面被一层薄膜——细胞膜包裹着，如图6.2所示。厚度为7～8nm的细胞膜是细胞的界限，它将具有生命力的活细胞与非生命的环境分隔开来。科学家们对细胞膜的研究发现，凡是可以溶于脂类的物质比不能溶于脂类的物质更容易透过细胞膜进入到细胞中去。化学分析表明，细胞膜的主要成分是磷脂和蛋白质。磷脂是一种由甘油、脂肪酸和磷酸组成的具有双重极性的分子。科学家提出细胞膜是一种磷脂双分子结构。因为只有这种双分子结构才可能稳定于细胞内外均为极性的液体环境中。

图6.2　生物细胞膜的结构

2. 细胞膜的模型

根据实验，并结合脂双层和膜蛋白的特性，科学家提出了细胞膜的“流动镶嵌模型”。该模型的主要特点如下。

（1）磷脂双分子层构成了膜的基本结构，磷脂分子非极性的“尾”向着内侧疏水区，而磷脂分子极性的“头”向着外侧，暴露于两侧的亲水区。这种磷脂双分子主要由亲水的头部和疏水的尾部组成的结构体现了膜结构的有序性。

（2）磷脂双分子层既有分子排列的有序性，又有脂类的流动性。这种流动性使得磷脂和蛋白质在膜的水平方向或者垂直方向都可以流动、反转和变化。同时膜的分子组成也可以发生变化。

（3）膜脂与膜蛋白质在膜上的排列具有不对称性，主要表现在内外两层脂类的分子种类和含量有很大的差异。蛋白质分子在膜内外分布的位置和数量也有很大差异。这种差异导致的不对称性对于识别外来的受体或信号起到重要作用。

（4）膜的有序性、流动性和不对称性对于生物膜适应膜内外环境的变化、选择通透性及物质的跨膜运输、电子传递和信号的传导等均具有重要意义。

3. 细胞膜的功能

活细胞新陈代谢的一个重要表现就是与外界环境的物质交换，细胞不断地从外界摄取生命活动所需的各种物质，同时，不停地把新陈代谢废物排到细胞外面。

（1）物质如何进入细胞。细胞膜的构成以脂双层为基本框架，中间镶嵌着各种蛋白质。细胞膜的结构决定了它的选择通透性。一般来说，外界环境中的脂溶性的非极性分子容易透过细胞膜；水溶性的强极性的分子不容易透过细胞膜。水可以进出细胞膜，影响水进出细胞的主要因素是渗透压。溶于水的小分子物质进入细胞主要有4种方式：简单扩散、协助运输、主动运输和基因转移。前两种方式推动物质进入细胞的动力来自物质的浓度差。后两种方式物质逆浓度梯度进入细胞，需要细胞消耗能量才能做到。大分子或颗粒进入细胞不能仅依靠细胞膜上的载体来帮助完成，还要使用局部细胞膜将有关物质包围，形成一个内吞泡，这样的过程称为内吞过程。

（2）物质如何被排出细胞。小分子被排出细胞由渗透压决定。蛋白质等大分子以一些颗粒状物质被排出细胞，主要通过细胞质中的泡液和细胞膜的融合，称为细胞的外排作用。

综上所述，细胞膜对进出入细胞的物质有很强的选择通透性，具有分离和过滤的功能，具有物质转运功能，具有控制细胞与周围环境之间的物质交换，以维持细胞内外的平衡和有序的功能。

6.3　标准膜计算的原理

由于膜计算的许多模型都是由Pǎun提出的，因此标准膜计算的各种模型又称为P系统。膜计算不是对生物膜的功能的简单模拟，而是Pǎun从各种生物膜的分层结构和处理化合物实现物质交流功能的原理中，抽象出一种可以用于计算的通用模型。

由细胞的结构和功能可知，生物膜的一个基本功能就是将自身和外在环境区分开，将细胞划分并构成不同功能的区域，区域中存在对象的多重集，也就是说，对象具有多重性，这是膜计算的基本特征之一。可以用一个字符串表示一个区域中的对象。这些对象通过“反应规则”来进化，而规则的选取具有并行性和非确定性。这些对象还能够穿越膜，进入系统中的另一个区域。膜能够改变其自身的渗透性，甚至可以溶解和分裂。用这些特征来定义系统的一个格局。在每一个时间步内，每个膜及其中的对象根据相应的规则进化，从而使系统产生一个新的格局。这样，一系列格局的转换就称为计算。当所有区域中没有任何规则可以发生作用，即不再发生任何事件时，称这种格局为停机格局。如果计算能达到一个停机的格局，则称为停机的计算或成功的计算。计算的结果是指那些被送到环境或指定膜中的对象。

一个膜系统主要包含3个要素：膜结构、对象、规则。膜结构是由细胞膜或生物膜抽象出来的。对象是由细胞或环境中的物质抽象出来的。规则是由细胞内的化学反应或细胞之间的信息交流方式抽象出来的。膜结构将空间分成若干个不同的区域，区域中的对象按照特定的规则进化。细胞内的化学反应过程和细胞区域之间的物质流动过程可以理解为计算过程。这些过程的时间序列意味着许多基本操作的并行执行，而且从给定的初始状态出发，细胞可以按多种方式演化。因此，膜系统往往具有并行性和非确定性。

目前，膜计算模型主要有3种类型：类细胞（Cell-like）膜计算模型、类组织（Tissue-like）膜计算模型和类神经（Neural-like）膜计算模型。这3类模型分别是基于单细胞的结构和功能、组织中的细胞群及神经元细胞而建立起来的分布式并行计算模型，在膜结构上分别可以抽象为树、无向图和有向图。这3类模型已被证明具有不弱于图灵机的计算能力。

6.4　标准膜计算的描述

Pǎun院士提出的P系统是从活细胞体新陈代谢的适应过程中抽象出来的，用字母之间的传输变换来描述细胞内物质交流行为的一种迭代计算模型。

细胞膜系统一般由膜的层次结构、物质对象表示、进化规则3部分构成。给定一个细胞膜系统的基本结构，并且确定各个膜所包含的物质与进化规则，在初始化格局状态下，膜系统就会以非确定和最大并行的方式执行各个进化规则，直至细胞膜系统内的资源耗尽、规则不能再被执行为止，此时计算结束，系统陷入停机格局。

从生命细胞分层结构处理化合物的方式中抽象出膜计算的方法，借助于生物进化规则，用字母之间的传输变换来描述细胞内物质交流行为。一般地，一个度为m的膜系统可表示的多元组为

∏=（V，T，C，μ，w₁，w₂，…，w_m，（R₁，ρ₁）（R₂，ρ₂），…，（R_m，ρ_m））（6.1）

其中，V为输入字母表，其元素称为对象；T⊆V为输出字母表；C⊆V-T为催化剂，其元素在生物进化过程中不发生变化，用于控制特定进化反应；μ为包含m个膜的膜结构，用于描述膜系统的包含层次关系。各个膜及所围的区域用标号集H表示，H=｛1，2，…，m｝，其中m称为模系统的度；w_i∈V^∗（1≤i≤m）表示膜结构μ中的区域i中含有对象的多重集，V^∗为字母表V中字符组成的任意字符串的集合。

进化规则是二元组（u，v），通常写成u→v，u是V^∗中的字符串，v是T中输出的字符。v=v′，或者v=v′δ，其中v′是集合｛a_here，a_out，a_in|a∈V，1≤j≤m｝中的字符串，δ是不属于V的特殊字符。当某规则包含δ时，执行该规则后膜就被溶解了。u的长度称为规则u→v的半径。R_i（1≤i≤m）是进化规则的有限集，每一个R_i是与膜结构μ中的区域i相关联的，ρ_i是R_i中的偏序关系，称为规则R_i执行的优先关系。

例如，对于进化规则

ca→cb_ind_outδ（6.2）

其中，物质c在进化前后没有发生变化，称为生物催化剂；下角标out表示物质元素传输到细胞膜外区域；下角标in表示物质运输到子细胞膜区域内；δ表示执行该规则后当前膜就被溶解消失。

给每个膜贴上标签（图6.3中为正整数）作为地址，并用这个标签来标识这个膜所确定的区域。每一个区域中有一个对象的多重集和一个进化规则集。这些对象由特定的字母表中的符号来表示。每个区域都有一个独特的属于自身的规则优先次序关系。也就是，一个规则只有当本区域没有比它具有更高优先级的规则时，才有可能起作用，处理字符对象。

每一个膜都有可能被溶解。当一个膜被溶解之后，其中所包含的对象将进入包含这个膜的区域，而原来区域中的规则随之消失。当然，膜也有可能变得不具有渗透性。

膜计算系统的结构具有层次性、区域性；计算的基本要素——对象，具有多重性；对象和规则的选取具有最大的并行性和不确定性。从复杂适应系统理论的观点看，活细胞对物质的新陈代谢的动态过程符合复杂适应系统的特性。实质上，细胞新陈代谢的过程是一个内外环境、新旧物质不断适应地转化、进化、优化的过程。

6.5　膜计算的过程及实现步骤

目前，膜计算算法可分为两类：一类是基于空间换时间的算法；另一类是膜计算优化算法。膜计算模型往往具有自我增加计算空间的能力，通过使用受生物启发的操作（膜分裂、膜分割、膜创生等）可以在线性时间内产生指数计算空间来求解问题的算法实现起来比较困难。Nishida提出了膜计算优化算法（膜算法）是将膜系统框架与优化算法结合起来的一类分布式演化算法，他利用膜算法很好地解决了旅行商问题。

图6.3给出一个包含4个膜的P系统，P系统置于环境中，系统中的4个膜按层次结构组织，分别标号为1、2、3、4，最外层的膜称为表层膜，膜3因不含有其他膜而被称为基本膜，每个膜所包围的部分称为区域，区域内包含着对象a、b、c、e和相应的进化规则。图6.3所示的P系统从初始状态开始，运用膜结构中进化规则编码的程序完成计算的过程如下。

（1）在初始状态时，在表层膜定义的区域1中，包含一个对象b和一个对象c，在区域4中有一个对象e，其他区域均为空。

（2）区域1中存在催化剂c，进化规则b→bb₂|_c在每一步计算中将一个对象b送入区域2中，并同时保留一份在区域1中，同时规则c→ca₃在催化剂c的作用下将对象a不断送入到区域3中，直到对象不可用为止。

（3）在区域1中，如果规则c→c₂被使用，则一个对象c被送入区域2中。这样，区域1中不再有催化剂c，规则b→bb₂|_c将不再向区域2发送对象b。

（4）当对象c到达区域2后，将会根据其中的规则c→c₄继续到达区域4中。

（5）当对象c到达区域4后，其中对象e的产生将停止，因为c是规则e→ee┐_c中的抑制剂。

在P系统中，使用规则的通常方式是极大并行，即凡是能使用的所有规则都必须使用；一个对象只能被一个规则使用，该规则按优先关系选择（如果优先关系ρ_i为空集，则非确定性选择规则）；需要强调的是，任何能被规则使用的对象必须选择一个规则，按该规则进化。在本例中，经过计算操作后的结果为区域3中将产生n个a，区域2中将产生n+1个b，区域4中将产生n+3个c。

图6.3　含有4个膜的膜系统结构示意图

针对无约束函数优化问题，文献［28］提出一种细胞膜优化算法（Cell Membrane Optimization，CMO），根据细胞膜转运物质的过程，把物质分为3种：脂溶性物质、高浓度非脂溶性物质和低浓度非脂溶性物质。在解决优化问题时，一个物质对应优化问题的一个解，上述3种不同类型的物质对应3种不同特性的解。若干个物质组成一个物质群，它是细胞膜优化算法进行优化计算的一个种群。在CMO算法中，把一个物质群划分为3种小物质群。在最小（大）化问题时，把结果数值小（大）的物质划分为脂溶性物质群，结果数值大（小）的物质划分为非脂溶性物质群，并把非脂溶性物质群进一步划分为两个子物质群。用物质某一邻域范围内包含的物质数占总物质数的百分比作为浓度的定义。根据非脂溶性物质所处的浓度，对非脂溶性物质群进一步划分为低浓度非脂溶性物质群和高浓度非脂溶性物质群。

CMO算法的实现步骤包括参数设定和物质初始化、物质类型划分、高浓度脂溶性物质自由扩散、高浓度非脂溶性物质运动、低浓度物质运动、当前最优物质循环运动和物质的更新。具体步骤如下。

（1）参数设定和物质初始化。

（2）物质类型划分。

（3）高浓度脂溶性物质自由扩散。

（4）高浓度非脂溶性物质运动。

（5）低浓度物质运动。

（6）当前最优物质循环运动。

（7）更新物质。

     iteration ← iteration + 1
     end while

细胞膜优化算法的流程如图6.4所示。

图6.4　细胞膜优化算法的流程图