混合算术运算膜系统模块化设计方法

陈弋玺

(西南交通大学电气工程学院，四川 成都 610031)

0 引言

欧洲科学院院士、罗马尼亚科学院院士Gheorghe Pǎun于1998年在研究DNA计算与生物细胞结构之间的关系时，根据细胞处理化学物质的机理，提出了第一个膜计算模型［1］。该模型通常被称作膜系统或P系统。一个膜系统可以形式化地描述为:

Π =(O，μ，W，R)

其中，O:预定义的膜系统对象集;μ:预定义的膜结构，设膜结构由m层膜构成，则各层膜由有限集合H={1，2，...，m}中的元素标定;W:W={w1，w2，...，wm}，其中wi表示膜i中由对象集O中的元素构成的初始对象集;R:膜系统的规则集。

Gheorghe Pǎun在2000年正式发表了第一篇关于膜计算的论文［2］。2003年2月，该论文被美国科学情报研究所(ISI)列为计算机领域的快速突破文章，同年10月，膜计算在美国ISI公司旗下著名的ESI数据库中被选为计算机科学新兴研究前沿，这也标志着膜计算正式成为一个新兴的研究领域。自Gheorghe Pǎun提出了膜计算的概念以来，受到国内外众多学者广泛关注［3］。迄今为止，膜计算作为自然计算的一个重要分支，在其理论研究方面已取得很多重大成果。膜计算的理论研究大多从数学和计算机理论出发，结合生命体中具体的细胞模型，提出了不同结构的多类膜系统(细胞型膜系统、神经性膜系统、组织性膜系统等)［4］，探讨各类膜系统的运算机理与计算能力，进而设计出能够解决某一特定问题的膜系统［5-6］。但是，膜计算应用方面的研究大多还不够成熟，主要是将膜计算与进化算法相结合，提出了膜算法［7-8］。有学者提出，正是由于膜系统的可编程性、可模块化、可扩展性与可理解性问题没有得到很好的解决，才限制了膜计算应用发展［9］。其中可编程性问题就是指如何利用计算机程序模拟膜计算的过程，包括用算法实现膜系统的自动设计。具体到膜系统的自动设计问题，就是指研究者只需给出膜系统需要解决的问题，计算机就能通过程序设计出满足要求的膜系统，这将大大降低膜系统设计的难度。本文所研究的内容主要是利用基本算术运算膜系统作为模块，构建复杂的混合算术运算膜系统的自动设计算法，为研究膜系统的可编程性问题探索一条新的途径。

1 设计方法

本文主要的思想就是利用基本算术运算膜系统作为基本模块，构建混合算术运算膜系统。其中对象集和规则集都取自基本算术运算膜系统，并辅以一些辅助规则。但如何构建膜系统的膜结构则是本文首先需解决的问题。文献［10］中提到，任何膜系统的膜结构都可以看作文氏图，而将该文氏图用欧拉图表示则形成了一棵树(如图1所示)。所以，如果能用一棵树来表示一个算术表达式，便能生成对应的膜结构。

图1 膜结构示例及其树状表示

图2 波兰式生成算法

1.1 表达式预处理

在通常的表达式中，二元算数运算符总是置于与之相关的两个运算操作数之间，这种表示法被称作中缀表示法。中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是根据运算符间的优先关系来确定运算的次序，此外，还应顾及括号规则。因此，使用机器通过中缀表达式求得混合算数运算表达式的值会较为复杂。为此，波兰逻辑学家卢卡西维茨(J.Lukasiewicz)在1929年提出了另一种算术运算表达式的表达方法，即后缀表达式或逆波兰式［11］。按此方法，每一运算符都置于其运算对象之后，这样表达式中各个运算是按运算符出现的顺序进行的。另外，还有一种表示方法与后缀表示方法相反，即前缀表达式或波兰式。输入的中缀表达式经图2所示的算法处理后便能得到相应的前缀表达式。

通过波兰式可以将一个算术运算表达式转换为一棵二叉树［12］，从而可生成对应的膜结构。例如算术运算表达式“4+3×2－1”经过文献［12］中算法处理后，便能转换成如与表达式对应的二叉树，由此二叉树便能进一步生成对应的膜系统膜结构 (如图3所示)。

图3 表达式的树状表示与其对应的膜结构

1.2 膜系统膜结构生成算法

通过算法处理后，得到了算术运算表达式的波兰式表示法，便能按照图4中的算法流程图生成对应的混合算术运算膜系统的膜结构。这里对该算法作较为详细的说明。

首先，对图4算法中的参数作出说明:

Expr:存储混合算术运算表达式的字符串数组;

CurrentParentMembrane:每当在构建一个新的膜m时，需要指明m的父膜，从而才能确定m在膜系统中的所在区域，如在图1中，膜1即为膜2和膜3的父膜。该参数为即将构建膜的父膜;

CurrentMembrane:当前正在构造的膜;

CurrentParentMembrane.ParentMembrane:为当前父膜的父膜。

该算法的执行过程如下:

(1)首先利用图2所示的算法，将一个中缀算术运算表达式转成前缀表达式，并存储于字符串数组Expr中。

(2)构建子膜时，根据Expr［i］的属性(是否为操作数)构建对应的子膜，主要完成对各个膜进行标号，再根据膜标号选择相应的规则和初始对象放入膜中。此外，为了使各个基本算术运算膜系统能协调工作，还应根据当前膜的计算结果，作为下次运算的操作数次序加入一些辅助规则。在定义膜标号时，需要判断当前膜的计算结果作为外层膜操作数的次序。根据波兰式所具备的特点，可以按照图5所示的方法进行判断。

图4 混合算术运算膜系统膜结构生成算法

(3)根据Expr［0］完成对表层膜(skin)的构建，同时确定表层膜的标号，并将CurrentParentMembrane参数设为skin，以便将其作为内层膜的父膜。

(4)依次扫描 Expr数组，并判断 Expr［i］是否为操作数，随后以CurrentParentMembrane为父膜构建当前膜，同时定义其膜标号。

(5)若 Expr［i］为操作符，则需要与 Current-ParentMembrane的操作符比较优先级，若Expr［i］的优先级更大，则需要将CurrentParentMembrane更新为当前正在构建的膜，即CurrentMembrane。需要说明的是，由文献［12］中的算法生成的运算表达式二叉树中的叶子节点一定是操作数，而叶子节点对应膜结构中的基本膜，且CurrentParentMembrane的值域是所有非基本膜，因此，CurrentParentMembrane一定对应一个操作符。

(6)若Expr［i］为第一操作数，且不满足程序结束条件时，需将CurrentParentMembrane更新为其父膜，即 CurrentParentMembrane.ParentMembr-ane。

(7)当对Expr数组中每个元素都扫描完毕并构建了相应的子膜后，混合算术运算膜系统膜结构建立完成，程序退出。

图5 判断Expr［i］的结果作为操作数的次序算法

2 混合算术运算膜系统

受电子计算机对数字计算规则的启发［13］，本文提出一系列二进制基本算术运算膜系统，并在此基础上实现二进制混合算术运算膜系统。

2.1 算术运算膜系统模块设计

为了设计二进制算术运算膜系统，首先对膜系统中的对象的二进制数编码规则进行说明。本节中，主要用 ai、bi、ci对二进制数进行编码，其中 ai对应第一操作数，bi对应第二操作数，ci对应计算结果。若系统中含有对象ci，则表示第一操作数的第i位为1，否则为0。下面将在上述编码规则的基础上给出二进制混合算术运算膜系统要用到的基本模块。

(1)十进制-二进制膜系统(Πcode)。

为了方便起见，本文的膜系统输入采用十进制算术运算膜系统的编码方式。因此，对于每个输入数据，都将经过一个十进制-二进制膜系统完成编码的转换。这里，根据编码转换膜系统规则的特点，设计出十进制-二进制编码转换单膜系统Πcode，可以得到Πcode的规则集如下:

在构建混合算术运算膜系统时，根据各层膜中的输入对象，将编码转化膜系统的规则集加入其中。在实验中，如果输入为第一操作数，则需将Rcode中的s与si改成a和ai，并修改规则中的膜标号;相应地，如果是第二操作数，则需改成b和bi。

(2)二进制加法膜系统(Π2－add)。

从这一步开始，设计得到的3种基本算术运算膜系统都是在二进制条件下实现的，使用的规则都是借鉴于计算机中实现二进制算术运算时所用到的计算法则，直接给出3种二进制基本算术运算膜系统。

其中:

需指出ai和bi是作为输入传入膜系统的，并不能作为膜系统的初始对象，因此才有w1=λ。

(3)二进制减法膜系统(Π2－sub)。

其中:

与 Π2－add类似，ai和 bi将作为输入传入膜系统。

(4)二进制乘法膜系统(Π2－mul)。

其中:

可以看出，实现二进制乘法要比实现加减法更为复杂，并且引入了一系列的辅助对象。对这些对象进行简要的说明:a1，i和 a0，i分别表示被乘数第 i位为 1或0，在Π2－mul中，仅仅用ai对被乘数进行编码很难实现乘法，因此引入这两个对象;bj，i表示乘数第j位为1，bj，i与被乘数第 i位(a1，i或 a0，i)相乘时，引入 bj，i后能用膜系统实现交叉相乘。此外，两个4位数的乘法可能会产生8位数的积，因此有ck(0≤k≤7)。

2.2 混合算术运算膜系统设计

由基本算术运算膜系统模块构建混合算术运算膜系统还需解决两个问题。首先，二进制混合算术运算膜系统需要将每层膜中的结果对象c转换为外层膜操作数对象a(对应第一操作数)或b(对应第二操作数)。为了解决这一问题，引入一组优先级规则，使得所有的转运规则优先级都低于其它规则。设2.1中所有膜系统模块中的规则集合为Rcac，转运规则集合为 Rtra，则有 ρRcac＞ ρRtra，其中 Rtra定义为:

为方便起见，实验时的算术运算表达式最多含有一次乘法，结果为16位的二进制数。

此处需要通过膜标号来确定每一层膜的功能，因此本文采用3位字符串数组进行膜标号编码，分别表示该层膜在运算表达式中的次序、对应操作符以及其结果作为下一操作符的操作数次序。这里给出二进制混合算术运算膜系统解析膜标号添加规则的算法(如图6所示)。

图6 二进制混合算术运算膜系统规则添加算法

3 实验结果与分析

本文采用一个混合算术运算表达式作为测试用例，实验中作为测试用例的四则运算表达式为:eq≡4+3×2－1。首先，按照图2所示的算法将表达式转为前缀表达式，处理后的表达式为:eq'≡－1+×234，再按照图4所示的算法构建膜系统的膜结构;然后将基本算术运算膜系统视作模块，构建混合算术运算膜系统。实验结果是在P-Lingua膜计算仿真平台［14］下得到的。下面给出混合算术运算膜系统的设计结果。

设二进制混合算术运算膜系统为 Π2－com，则Π2－com可形式化地描述为:

其中:

O为所有二进制基本算术运算膜系统对象集的并集;

这里，规则集较为复杂，将其分为3个子集，分别表示编码转换规则(Rcode)、算数运算规则(Rcac)和对象转运规则(Rtra)。现分别给出这3个规则子集的详细描述:

Π2－com的计算结果同样也是二进制编码，即用对象ci表示。

4 结束语

从实验结果中可以看到，利用本文的算法得到的膜系统能实现计算给定的混合算术运算表达式，但从测试结果可以看到，该膜系统的规则集较为复杂，且含有较多的对象。在以后的研究中，可针对此问题做出改进，简化基本算术运算膜系统模块，对算法进行进一步的改进，使获得的膜系统具有更为简单的结构和对象集。

［1］张葛祥，潘林强.自然计算的新分支——膜计算［J］.计算机学报，2010，33(2):208-214.

［2］Pǎun G.Computing with membranes［J］.Journal of Computer and System Sciences，2000，61(1):108-143.

［3］黄小丽.细胞型膜系统设计方法研究［D］.成都:西南交通大学，2012.

［4］Pǎun G.A quick introduction to membrane computing［J］.The Journal of Logic and Algebraic Programming，2010，79(6):291-294.

［5］Pérez-Jiménez M，Jiménez Á，Caparrini F.Complexity classes in models of cellular computing with membranes［J］.Natural Computing，2003，2(3):265-285.

［6］Pǎun G，Suzuki Y，Tanaka H.On the power of membrane division in P systems［J］.Theoretical Computer Science，2004，324(1):61-85.

［7］Nishida T Y.Membrane algorithms［J］.Lecture Notes in Computer Science，2006，3850:55-66.

［8］黄亮.膜计算优化方法研究［D］.杭州:浙江大学，2007.

［9］Pǎun G，Perez-Jimenez M.Membrane computing:Brief introduction，recent results and applications［J］.Biosystems，2006，85(1):11-22.

［10］Pǎun G.From cells to computers:Computing with membranes(P systems)［J］.Biosystems，2001，59(3):139-158.

［11］毛红梅，严云洋.编译原理［M］.北京:清华大学出版社，2011:144-147.

［12］何志宏，毛志军.表达式与二叉树的相互转换［J］.电脑知识与技术，2010，6(5):1201-1203.

［13］雷丽文，朱晓华，蔡征宇，等.微机原理与接口技术［M］.北京:电子工业出版社，2005:34-42.

［14］García-Quismondo M，Gutiérrez-Escudero R，Pérez-Hurtado I，et al.An overview of P-Lingua 2.0［J］.Lecture Notes in Computer Science，2010，5957:264-288.