膜计算-谭立伟

膜计算android与算法俱乐部谭立伟参考文献陈海珠.膜计算应用研究.重庆大学博士学位论文,2011.4概述膜计算(MembraneComputing，也称为P系统)是自然计算的一个新分支，其目的是从活细胞中以及组织、器官或其他结构的细胞之间相互协作的方式中获得新的计算思想、设计新的计算模型。P系统不仅为计算机科学引入了新的分布式并行信息处理方法和技术，而且为生物系统的建模和仿真提供了新工具，是当前非常活跃的一个研究领域，预计在新一代计算系统、信息处理系统的技术开发方面将起关键作用。关于膜计算的研究工作可归为三类：理论研究、应用研究和软、硬件实现研究。膜计算的理论研究主要集中于各种计算模型的建立及其计算能力(ComputationPower)的分析；膜计算的应用研究主要是利用P系统的特点和各种模型求解生物学、计算机科学、语言学、社会学等方面的实际问题；而膜计算的软硬件实现研究则侧重于在现有计算机上用程序实现或开发新的处理器实现有关的膜计算模型或求解有关问题。尽管P系统还处于理论研究阶段，但它所具有的一些性质如并行性、非确定性等已经引起了越来越多学者的研究和关注。随着研究的深入，由原始模型衍生出了许多不同的膜计算模型，主要有：类细胞P系统(Cell-likePSystems)、类组织P系统(Tissue-likePSystems)类神经P系统(Neural-likePSystems)它们分别是从细胞、组织以及神经系统中抽象而来的计算模型。形式语言基础对于字母表V，V*(V的闭包)表示V上所有有限字符串的集合。空字符串用λ表示。V上的所有非空有限字符串用V+(V的正闭包)表示，即V+=V*−{λ}V*的任意一个子集称为V上的一个语言如果V={a}（这时称V为单字母表），则{a}*，{a}+分别简记为a*，a+字母表V上的正则表达式(正规式)定义如下：①λ和a∈V都是正则表达式；②如果E1，E2是V上的正则表达式，则E1E2,E1∪E2，E1+都是V上的正则表达式；③除①、②之外，V上不再有其他正则表达式。正则表达式E对应于一个语言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系统类细胞P系统是第一个被提出来的P系统。类细胞P系统将生物膜内的化学反应与膜间的物质流动抽象为计算过程：生物膜内的化学反应就是通常理解的计算过程，而物质在不同膜之间的流动则对应于通常意义计算系统中的消息传递，细胞或细胞器成为计算单元。类细胞P系统结构的示意图最外边的膜称为皮肤膜(skinmembrane)，它将本系统与外在环境分开。如果一个膜的内部不存在其他膜，就称这个膜为基本膜(elementalmembrane)，否则称为非基本膜(non-elementalmembrane)。每一个膜定义了一个区域：对于基本膜，这个区域就是它所包含的空间；对于非基本膜，区域是指这个膜和它直接包含的其他膜之间的空间。膜结构的描述通常有两种方式:树形结构-膜的层次结构特征适合于用树结构来描述：皮肤做为根节点，基本膜做为叶节点。广义表用嵌套结构即是用字符串来表示膜结构。当i#膜为基本膜时，表示为：[i]i；当k#膜包含在i#膜内部时，表示为[i[k]k]i。一对括号[]表示一个膜，括号的下标为膜的标号。例如，上图的膜结构可表示为：[1[2]2[3]3[4[5]5[6[8]8[9]9]6

[7]7]4]1。在膜结构的描述中，同一层次的膜的排列顺序是任意的。故对同一个P系统，其描述形式不是唯一的。在生物膜内存在多种物质，如离子、小分子、微分子等。每种物质通常不止一个，并且是无序的。在P系统中使用小写字母来表示这些物质，这样膜中含有的物质就可以用多重集表示。所谓多重集是指允许有相同元素的集合。例如，A={a,a,b,c,c,c}是多重集，记为{a2,b,c3}或a2bc3。多重集表示是无序的，即a2bc3与bc3a2是同一个多重集。膜作为细胞的边界，细胞内包含的物质是膜计算的对象，物质的反应以及膜之间物质的流动是膜计算的过程，这一过程中膜内物质及其数量发生改变，不同的改变过程对应着不同的进化规则。P系统中，往往存在多种对象和多个进化规则，规则执行的原则是:不确定性

-当有n个规则需要执行m个，具体是哪m个是随机的最大并行性-每次执行所有可执行的规则都必须执行且同时执行。给定一个P系统，即给定了一个膜结构，并且各个膜里都包含有相应的字符串和进化规则，这个称为P系统的初始格局。从初始格局开始，P系统的各个膜不确定、最大并行地使用规则，系统每运行一步(也称为一个计算步)，当前格局就会做相应的改变进入一个新格局。经过若干计算步，形成一系列的格局。当没有规则可以执行，系统进入停机状态。整个格局序列被称为P系统的一次计算，被送到环境或指定膜中的对象即是计算的结果。若P系统的规则一直执行，无法进入停机状态，则计算无效，也就没有计算结果。转移P系统、协同P系统、活性膜P系统是类细胞P系统的三种基本模型，它们从不同角度模拟了细胞内物质对象的变化过程，故采用不同的规则。其中，转移P系统是膜计算应用中最常使用的一种计算模型，其形式化定义为：O是非空有限的字符集，每个符号表示膜结构中的一种对象(也即物质)μ是膜结构，度为m，每个膜都有相应的标号，H={1,2,,m}为∏的标号集合；wi

(i=1...m)为i#膜中对象的集合，用多重集表示，wi=λ表示i#膜内没有任何对象；Ri为i#膜内的进化规则(定义见下页)i0是膜结构的输出区域，该区域最后保存计算结果。进化规则形式为u→v或u→vδ，u∈O+，v∈(O×Tar)*,Tar={here,in,out}，Tar表示生成物v的去向：here表示v留在i#膜内；inj表示v被送至j#膜内，j#膜是i#膜的子膜；out表示v被送至i#膜外成为其父膜中的对象。δ是溶解操作，它溶解对象u所在的i#膜，其所在膜内所有的对象都被释放到其父膜内，并且定义在i#膜内的规则也会跟着消失，δ操作不能应用于皮肤膜。在细胞的进化中，除了细胞内物质种类、数量变化外，还会发生细胞分裂等细胞繁殖活动。活性膜P系统即是抽象这一细胞活动而得到的计算模型。此类P系统将膜也作为规则处理对象，其规则包括膜的溶解、膜分裂、膜创建、膜分离和膜合并等。采用活性膜P系统进行计算时，膜结构随着膜操作规则的执行而发生着变化。活性膜P系统的一般形式与转移P系统的相同，区别在于规则不同。活性膜P系统使用的规则为：对象进化规则：当h#膜所带电荷为e时(当e为0时表示h#膜没有极性，此时可不必写出，下同)，其中的对象a可进化为v(v为对象集合)。通信规则：当h#膜所带电荷为e1时，膜外对象a可进入h#膜且进化为对象b；当h#膜所带电荷为e2时，膜内对象a可移出h#膜之外(进入h#膜的上一层膜)且进化为对象b。(注意，原文有误)Π中规则的执行仍然采用不确定、最大并行原则。对②～④类型的规则，在同一时刻每个膜中只能使用一种，而规则①可与②～④同时使用。举例以下图的转移P系统为例来解释P系统的计算过程。该系统描述为：计算过程为：（1）仅有3#膜的规则能被执行，显然，在同一时刻，{a→ab,f→ff}与{a→bδ,f→ff}仅有其中一组能被执行。现假设{a→ab,f→ff}执行n次后再执行一次{a→bδ,f→ff}。因a→bδ的执行，使3#膜被溶解，多重集(n≥0)被带到2#膜中。(注意，原文有误)(2)在2#膜中，分两种情况：1)n=0，多重集为bcf2。{b→d,ff→f}或{b→d,cf→cdδ}能先执行。a.先执行{b→d,ff→f}，然后只有{d→de,cf→cdδ}能被执行。此时，2#膜被溶解，多重集cd2e被送到1#膜中。b.先执行{b→d,cf→cdδ}，2#膜被溶解，多重集cd2f被送到1#膜中。2)n>0，多重集为。a.先执行{b→d,ff→f}，得到多重集。这时再执行规则集{d→de,ff→f}，得到，重复执行此规则集k(k<n)次后，得到：当k=n时，得多重集，这时可执行的规则集为{d→de,cf→cdδ}，执行之，2#膜溶解，多重集被送到1#膜中；当k≠n时，执行规则集{d→de,ff→f,cf→cdδ}，2#膜溶解，被送到1#膜中。b.先执行{b→d,ff→f,cf→cdδ}，2#膜溶解，多重集被送到1#膜中。(3)在1#膜中，按接收到的多重集分两种情况：1)收到的f个数>=1时，f→f将一直执行，计算无效；

2)收到的多重集为cd2e或只有规则e→(e,out)可执行，获得的输出为对象e的数量，即(n+1)2。脉冲神经P系统脉冲神经P系统的生物学基础SNP系统的定义SNP系统中基本的计算单元称为神经元(neuron)，神经元内部含有脉冲(spike)和规则(rule)，不同的神经元通过突触(synapse)连接在一起，脉冲通过突触单向传输，实现神经元之间的通信。神经元具有打开(open)和封闭(close)两种状态，当神经元处于打开状态时，神经元内的规则若满足执行的条件则被执行，神经元根据该规则做相应的动作，如向其他神经元发送脉冲。封闭的神经元不接收其他神经元送来的任何脉冲，这些不被接受的脉冲因不被接收而消失(即被遗忘)。在SNP系统中有两种特殊的神经元：输入神经元和输出神经元，分别用于输入脉冲以及输出计算的结果或标识计算的终止。SNP系统中所有的脉冲都是一样的，没有差别，一个脉冲用一个符号a表示。SNP系统的计算结果可以用输出神经元输出的脉冲数目来表示。此外，还可以通过输出神经元两次被触发的时间间隔表示来计算结果。一个度为m≥1的脉冲神经P系统的形式化定义为：Π=(O,σ1,σ2,...,σm,syn,in,out)其中：O={a}为单字母集合，a表示一个脉冲；σi(1≤i≤m),表示系统Π中的m个神经元，σi表示为(ni,Ri),其中：

ni≥0表示神经元σi包含的脉冲数目；Ri表示神经元σi中的规则有限集合。（关于规则见下页）syn⊆{1,2,,m}×{1,2,,m}表示神经元之间的连接关系(对应于生物神经系统中的突触)，对每个1≤i≤m，有(i,i)∉syn；in,out∈{1,2,,m}分别表示输入和输出神经元。SNPSystem中神经元的规则两种类型：激发规则：E/ac→ap;d其中E表示字符a上的正则表达式，c≥1，d≥0，p≥1，且c≥p；遗忘规则：E'/as→λ其中E′表示字符a上的正则表达式，s≥1。对激发规则和遗忘规则总有：L(E)∩L(E')=∅；称E/ac→a;d为标准激发规则(即p=1)称as/as→λ为标准遗忘规则(即E'=as)。对激发规则，若E=ac，则将之简写为ac→ap;d；若d=0，则写成E/ac→ap，若同时满足，则写成ac→ap。对遗忘规则，若E'=as,则简写成as→λ。规则的使用激发规则：E/ac→ap;d在某时刻，如果神经元σi包含k个脉冲，且有ak∈L(E)及k≥c，则σi此时可以使用激发规则E/ac→ap;d。使用此规则后，σi将消耗c个脉冲(于是σi剩余k−c个脉冲)，同时产生p个新脉冲，延迟d个单位时间后向与它连接的其他所有神经元分别发送p个脉冲。另外，使用这条规则后的d个时间单位内，σi是封闭的，不能接收其他神经元发送过来的任何脉冲。如果σi在第t步使用激发规则E/ac→ap;d(d≥1)，则σi在第t，t+1，…，t+d−1步都是封闭的。当一个神经元处于封闭状态时，它所具有的任何规则都不能使用；只有当它变为开放状态后，才能使用满足正则表达式的规则。若某个神经元向一个封闭的神经元发送脉冲，则封闭的神经元此时不能接收到这些脉冲，这些脉冲被丢弃(即被遗忘)。对于输出神经元来说，它可以向环境发送脉冲，而这些脉冲将被检测到并作为输出结果来处理。规则的使用遗忘规则：E'/as→λ若神经元σi包含k个脉冲，且有ak∈L(E')及k≥s，则此σi此时可以使用遗忘规则E'/as→λ。注意此时σi中的所有激发规则都不能使用。当神经元σi使用此规则后，将消耗s个脉冲，但不会产生任何新脉冲。可能存在L(E1)∩L(E2)≠∅，因此在一个神经元中可能存在多条规则可以使用的情形。在任何时刻，若神经元σi中有多条规则可以使用，那么此神经元能且只能使用一条规则，并且此规则的选取是随机的。将只使用标准激发规则和标准遗忘规则的SNP系统称为标准SNP系统。标准脉冲神经膜系统在并行模式下工作(即系统是同步的)，但在每个神经元内，每步至多只能使用规则一次。穷举使用规则的SNP系统M.Ioneseu和Gh.Păun对SNP系统的标准定义进行扩展而得到。SNP系统在穷举使用规则模式下，每个神经元在每步需要尽可能多次的使用一条激发规则，使该神经元中剩余的脉冲数最小。例如，假设神经元σi内有规则E/ac→ap(p≥0)，若σi内有k=sc+r（ak∈L(E)，r<c）个脉冲，则消耗sc个脉冲，余下r个脉冲，产生sp个脉冲。对于穷举使用规则的SNP系统，不仅在所有神经元上系统是在并行模式下工作的，在每个神