（计算机软件与理论专业论文）模糊p系统的建模和模拟.pdf

一一一 生出太空亟主垃窑 摸期丕蕴曲建堪型搓赵 硕士生： 指导教师： 模糊p 系统的建模和模拟 曾召军 张治国 计算机软件与理论 摘要 膜计算属于生物分子计算，它将计算理论的思想建立在细胞、组织或更高级 生物结构之上，其实质是并行与分布式计算。p 系统是理想化的膜计算模型，它 用膜内规则的应用表示生物化学过程。模糊p 系统是特殊的p 系统，在p 系统之上 引入了模糊集理论来描述细胞内物质的差异性，更真实的描述了膜计算过程。 目前生物上还没有任何p 系统的实现，故对p 系统计算过程的观察必须借助于 模拟系统，研制模拟系统是膜计算研究的一个应用领域，本文属于此领域。 本文选择p r i s m 作为模拟工具，是因为p r s i m 模型能准确描述膜计算过程， p r i s m 语言简单实用，而且p r i s m 模拟器支持三种概率模型，即马尔可夫决策过程、 离散时间马尔可夫链和连续时间马尔可夫链，可以模拟模糊p 系统计算过程中的 不确定性和最大并行性。 建立模糊p 系统的数学模型并把数学模型映射到对等的p r i s m 模型是本文的 创新所在，我开发了一小型系统自动转换器，可以实现转换的自动化。p r i s m 模型中的命令( c o m m a n d ) 、变量( v a r i a b l e ) 以及模块( m o d u l e ) 分别对应模糊p 系统中的规则( r u l e ) 、对象( o b j e c t ) 、膜结构( m e m b r a n es t r u c t u r e ) ，命令行的 条件部分可以表示模糊p 系统的模糊性，并列的命令行组中有的条件具有重复部 分，这可以模拟模糊p 系统的不确定性，p r i s m 可以同时运行多条命令。这可以模 拟模糊p 系统的最大并行性，这是本文的成果。我还对大量例子进行测试并对一 个例子进行了详细的分析，测试表明，模拟既体现了模糊性，也体现了膜计算的 不确定性和最大并行性，准确的演示了计算过程，可以作为研究模糊p 系统的模 拟器。 主山盔茎亟j 金塞 搓描垂统鲍建搓塑搓拟 本文在建模过程中忽略了膜融解符，催化剂，没有规定输出膜，终止字符等； 只利用了p r i s m 概率模型验证器进行p r i s m 模型的模拟，没有进行模型属性的验 证。这些都是今后可以研究改进的地方。 关键词：膜计算，模糊p 系统、不确定性、最大并行性、建模、模拟、p r i s m l l 生出太堂亟监室搓担歪统曲建搓塑搓翅 m o d e l i n ga n ds i m u l a t i n gp r o b a b i l i s t i c p s y s t e m s s o f t w a r ea n dt h e o r e t i c a lc o m p u t e rs c i e n c 镕 n a m e ：z e u gz b a o j u n s u p e r v i s o r ：z h a n gz h i g n o a b s t r a c t m e m b r a n ec o m p u t i n gi sab r a n c ho fb i o l o g ym o l e c u l ec o m p u t i n g , i td e r i v e s f r o mb i o l o g yc h e m i c a lr e a c t i o n , a n di nf a c ti sa p a r a l l e la n dd i s t r i b u t e dc o m p u t i n g m o d e l i nt h i st h e s i sir e s e a r c hp r o b a b i l i s t i eps y s t e mt h a tt a k e si n t oa c c o u n tt h e i m p e r f e c t i o no f t h er e a c t i v e si n v o l v e di nc o m p u t a t i o n s u pt on o w , t h e r ei s n ta n yr e a l i z a t i o no fps y s t e mi nb i o l o g y , 8 0o b s e r v i n gi t s c o m p u t i n gp r o c e s sm u s t u s es i m u l a t o r , t h i st h e s i si sa b o u th o wt os i m u l a t e p r o b a b i l i s t i eps y s t e m is e l e c tp r i s ma sas i m u l a t o r , b e c a u s ep r i s ml a n g u a g es i m p l ea n dc l e a r , f i l r t h e r n l o r e ，p r i s ms u p p o r tt h r e ep r o b a b i l i s t i em o d e l ：m a r k o vd e c i s i o np r o c e s s ， d i s c r e t e - t i m em a r k o vc h a i na n dc o n t i n u o u s - t i m em a r k o vc h a i nw h i c hc a ns i m u l a t e p a r a l l e l i s ma n du n c e r t a i n t yo f p r o b a b i l i s t i cps y s t e m b u i l d i n gam a t h e m a t i c a lm o d e la n dm a p p i n gi tt op r i s mm o d e li sm yc r e a t i v e p a r t i no r d e rt ot a k et h et r a n s i t i o na u t o m a t i c a l l y , id e v e l o p e dat r a n s i t i o nm a c h i n e w h i c hw i l lb ei n t r o d u c e di nc h a p t e r6 c o m m a n d ，v a r i a b l ea n dm o d u l ec a nm a pt o r u l ea p p l i c a t i o n , o b j e c ta n dm e m h r a n es t r u c t u r er e s p e c t i v e l yi np r o b a b i l i s t i cp s y s t e m c o o r d i n a t ec o m m a n d sw h i c hh a v es a m ec o n d i t i o nc a l ld e s c r i b eu n c e r t a i n t yw h i l e p r i s mc a nr u nm a n yc o m m a n d so n c ei na c y c l ec a nd e s c r i b ep a r a l l e l i s m t oc o n f i r m c o l t e c t n e s s ，id i ds o m et e s t sa n da n a l y s i so n eo f e x a m p l e si nd e t m li nc h a p t e r8 t h e r e s u l t si n d i c a t et h ew h o l es i m u l a t i o ns y s t e mc a n1 1 1 1 1w e l la n dg i v ec l e a rr e s u l t sw h i c h e x p r e s sp a r a l l e l i s ma n du n c e r t a i n t y h 1 生鱼太堂亟圭论奎 搓擞基缝妇建搓塑搓拟 i nf u t u r er e s e a f c l ：i w ec a r tm o d e l i n gm o r ec o m p r e h e n s i v e l y , c o n s i d e r i n g t e r m i n a t ea n dd i s s o l v es i g n , 0 1 w ec a nd o s o m ea t t r i b u t ec h e c k i n go np r i s m k e ) rw o r d s ：m e m b r a n ec o m p u t i n g ，p r o b a b i l i s t i cps y s t e m , u n c e r t a i n t y , p r i s m 生出太生亟i 幺室撞攒丞蕴酸建摸塑搓抠 1 1 研究背景 第1 章综述 1 1 1 p 系统计算原理 膜计算的思想是罗马尼亚科学家g h e o r g h ep a u n 于1 9 9 8 年提出的，属于 生物分子计算，它将计算理论的思想建立在生物细胞的结构及将细胞组成生物 组织或者更高级生物结构的体系结构上，其实质上是一种并行与分布式计算模 型。 膜计算的设备是膜系统，又称为p 系统。p 系统是由膜结构、膜内物质和规 则组成。整个细胞可以划分为若干区域，区域内部又可以划分成若干子区域， 如此嵌套，膜结构就是区域、子区域的集合及它们之间的包含关系，各个区域 的边界称为膜。膜没有细胞膜那样繁杂的组成物质，但具备细胞膜在细胞活动 中的功能，如选择性传输，对膜内化学反应起催化作用，接受外界的信息，支 持物质跨膜传输等。由膜围绕而成的区域中包含若干物质和规则，规则是类似 化学反应方程式的表达式，表示细胞内的某种物质或某些物质在条件( 主要指 反应物质或催化剂足量，不考虑温度等因素) 具备的情况下能够生成另一种或 另一些物质，它是p 系统计算的依据。单个区域及其中的物质、规则构成一个 反应单元，各个反应单元不是孤立存在的，它们之间存在物质的转移、渗透关 系。在各个反应单元内，物质依照规则发生化学反应，某些物质消失，某些物 质生成，整个膜结构所有反应单元内的化学反应进程之和即为p 计算过程。当 所有膜内都无法再应用任何规则时，p 计算结束，此时，在指定的输出膜内的 物质就是计算结果，这就是p 系统的计算原理。 1 1 2 p 系统与图灵机 p 系统能够模拟图灵机的每一个基本操作，由于图灵机是电子计算机的理 论模型，所以电子计算机能够进行的计算，p 系统也能够进行【1 4 】。因此，p 系 统是计算完整的1 1 5 】，这个结论意味着p 系统与图灵机的计算能力是等价的，从 生出太堂亟论塞搓期丕统鲍建毽麴搓担 一个万能的图灵机可以得到等价的万能p 系统，并且该p 系统膜结构度数是收 敛的，即只需要度数较小( 如2 度、3 度) 的膜结构的p 系统足以描述万能图 灵机的计算能力【4 1 。可以将小小的“细胞”看成计算能力强大的“计算机”。p 系统特有的操作膜分裂，膜创建，以及字符串复制操作使得其可以在多项 式时间内解决某些目前电子计算机( 或者确定图灵机) 尚无高效解决方案的n p 完全问题【1 3 】。 与电子计算机相比，p 系统的优越性在于可以在一个时间单元内执行多个操 作，这是由p 系统最大并行性的特点所决定的： 1 ) 不同区域内的规则同时应用； 2 1 区域问的多个通信过程同时开始： 3 ) 区域内的规则应用在所有的物质上； 们在一次通信过程中，同时运输多个物质： 也就是说，p 系统能够进行并行计算，而电子计算机不能。 另外，p 系统的另外一大特性是不确定性：当某个区域内的物质可以满足多 个规则时，即规则之间存在竞争关系时，p 系统对规则的选择具有不确定性， 这也导致最后的计算结果不是唯一的。 1 1 3 模糊p 系统 p 系统有多种类型，主要分为转移p 系统( t r a n s i t i o nps y s t e m ) 、通讯一 进化p 系统( c o 舳u n i c a t i o n - e v o l u t i o nps y s t e m ) 以及带激活膜的p 系统( p s y s t e mw i t ha c t i v em e m b r a n e s ) 。这三种类型中，转移p 系统是用的最多的p 系统。 在转移p 系统基础之上，j a u m ec a s a s n o v a s ，m a n u e lm o y a ，j o em i r0 ， f r a n c e s cr o s s e l l 在论文ap r o b a b i l i s t i ca p p r o a c ht om e m b r a n ec o m p u t i n g w i t ha p p r o x i m a t ec o p i e s ( 模糊法研究带近似拷贝的膜计算) 中引入模糊集 理论研究p 系统，这主要是考虑到p 系统实际的计算过程中的物质与规则表达 式中的物质有一定的差别，前者是后者的近似拷贝，而不是精确拷贝，后者是 前者的模糊集，前者以 o ，1 区问内的值( 相似度) 近似于后者，所有考虑到这 2 种差别的p 系统又成为模糊p 系统。 本文研究就是模糊p 系统，模糊p 系统规则的应用更加严格，它不仅需要 一定数量的物质，还需要这些物质达到一定的近似程度( 相似度) ，达不到所规 定的相似度的物质不能应用规则，另外，不同相似度的作为反应物的物质组合 会生成不同相似度的作为生成物的物质。模糊p 系统延伸了转移p 系统的概念， 更加真实的反应了膜计算过程。 1 2 问题陈述 p 系统的提出在多个学科内都引起了极大的反响，尤其是生物科学，从而 引发了一系列全新的研究领域，但是，目前生物上还没有任何p 系统的实现， 对p 系统计算( 生物学成为进化) 过程的观察必须借助模拟器。有关p 系统的 模拟器很多，从实现的方式而言分为硬件模拟系统和软件模拟系统。各种模拟 器都是针对某一特定类型的p 系统，不同类型的p 系统需要不同的模拟器，本 文是针对模糊p 系统的软件模拟系统。 模拟p 系统的关键是要模拟出其计算特点。模糊p 系统具备三大特性：模 糊性、不确定性和最大并行性。如何模拟出这三大特性，采用何种模拟工具是 需要解决的主要问题。本文选择了p r i s m 概率模型验证器模拟三大特性。 模糊性是指模糊p 系统中细胞内的物质不完全等同于规则表达式中的物 质，而是规则表达式物质的模糊集，每一条规则都规定发生反应的最小相似度， 只有达到最小相似度的细胞内的物质才能应用规则，达不到最小相似度的细胞 内物质不能应用规则。模糊性可以用p r i s m 语言中模块内命令行中的条件部分 描述，满足条件则可以触发命令，引起更新，即发生反应，不能满足条件则不 能触发命令，反应也不会发生。 不确定性是指每一条规则存在多种应用方式，当某个状态下满足多种应用 方式的条件时，需要从中选出一种方式应用，这种选择是不确定的。不确定性 可以p r i s m 所支持的概率模型来表示，p r i s m 支持的三种基本概率模型，即离 散时间马尔可夫链( d i s c r e t e t i m em a r k o vc h a i n s ) ，连续时间马尔可夫链 ( c o n t i n u o u s t i m ei 帐a r k o vc h a i n s ) 和马尔可夫决策过程( m a r k o vd e c i s i o n p r o c e s s e s ) ，它们分别以不同的策略进行选择，从而模拟不确定性 生出太茔亟监塞搓搁丕统鲍建搓塑搓拟 最大并行性是指规则与规则之间可以并行应用，只要他们相互之间不存在 竞争关系。p r i s m 模拟器可以模拟最大并行性，它通过设置进化步长，可以一 次执行p r i s m 模块中的多条命令，其实质是用串行的方式模拟并行的计算过程。 在确定了用p r i s m 模拟上述三大特性后，余下的主要工作便是建立p r i s m 的数学模型，并采取适当的策略把数学模型转换为p r i s m 模型。 1 3 主要工作 本文对模糊p 系统进行建模和模拟，共分四部分阐述，第一部分是介绍生 物分子计算中的膜计算系统模糊p 系统的结构和计算原理；第二部分是通 过与转移p 系统的比较，在转移p 系统数学模型之上给出了模糊p 系统的数学 模型及计算步骤；第三部分是通过开发自动转换器把数学模型转换成p r i s m 模 型，并用p r i s m 概率模型验证器模拟模糊p 系统计算过程；第四部分是通过一 个具体的例子演示模拟的整个流程。 建模和模拟是重点，模拟是建模的目的，建模是模拟的前提，两者次序清 晰，功能分明，模拟的流程如下图所示： 建模是给出模糊p 系统的数学模型，形式化描述模糊p 系统中的要素：膜 结构、规则、对象、作用物等。我在转移p 系统的数学模型之上，通过添加相 似度的概念以区分作用物和对象，从而给出了模糊p 系统的数学模型及其计算 步骤。第四章中详细阐述。 模拟是在p r i s m 上进行的，所以首先要把模糊p 系统的数学模型转换为对 等的p r i s m 模型，分别把膜结构，对象，规则映射为p r i s m 语言中的模块，变 量，命令。我采用j d k l 4 和e c l i p s e 平台开发了自动转换器，可使转换过程自 4 生出盍望亟j 金窑搓塑丕蕴的建攫麴搓拯 动化，并在自动转换器之上制定了一套描述规则，用户只要按照此描述规则表 述所要模拟的模糊p 系统并把描述式作为自动转换器的输入，运行自动转换器， 便可得出相应的p r i s m 模型。 在p r i s m 上运行p r i s m 模型可以得到模拟结果。p r i s m 模拟结果是一张表格， 表格的第一行表示初始状态，表格的最后一行表示终止状态，从第一行到最后 一行就是整个计算过程。 为了验证模拟和建模策略的正确性，本文随后做了一些测试，并在第八章 讨论了一个实例，给出了从最初的输入到得到最终计算结果的过程，并分析了 模拟结果。 1 4 论文组织结构 本文共分为九章。 第一章为综述部分，介绍了研究背景，对问题进行了阐述并列举了主要的 工作和论文的组织结构。 第二章阐述膜计算的基本理论，从多集合引出了膜内作用物，规则的概念 并阐述了膜计算的两大特性，不确定性和最大并行性。 第三章阐述模糊p 系统。分析了转移p 系统与模糊p 系统的区别尤其解释 了“模糊”的概念。 第四章讲建模。给了除了模糊p 系统的数学模型和计算步骤，分析了不确 定性和最大并行性在模糊p 系统中的表现，并给出建模过程中所做的假设和模 型可能引发的计算膨胀问题。 第五章介绍p r s i m 。阐述p r i s m 的三种概率模型和p r i s m 语法以及p r i s m 模拟器的使用。 第六章介绍自动转换器。从功能，概要设计、详细设计及系统的输入输出 方面介绍。 第七章是模拟部分。给出了模拟的策略，不确定性和最大并行性在模拟中 的体现以及模拟的结果。 第八章给出了一个具体的例子，介绍了模拟的整个流程。 第九章是总结和展望部分。 生出太堂亟土监窑撼搠丕统曲建篮狃摸越 2 1 膜计算 第2 章膜计算基本理论 计算可以分为图灵计算和自然计算，前者是由一个控制器，一条可无限延 伸的带子和一个可在带子上面左右移动的读写头组成。冯诺伊曼体系结构则是 图灵机的一种实现，所以目前的电子计算机是图灵计算，而后者采用如细胞结 构、d n a 、细胞内物质等定义计算的核心要素，将生命体内发生的活动，如遗传 操作、d n a 的断链、细胞内物质跨膜传输等等，看成是计算过程。两种计算的 核心概念是一致的，不同的是概念的具体表示方式。 自然计算分为四种：进化计算、神经计算、量子计算和生物分子计算。其 中生物分子计算分为d n a 计算和我们将研究到的膜计算。 膜计算的思想是罗马尼亚科学家g h e o r g h ep a u n 于1 9 9 8 年提出的，它将 计算理论的思想建立在生物细胞的结构及由细胞组成生物组织或者更高级生物 结构的体系结构上，其实质上是一种并行与分布式计算模型。 下图展示了膜计算和本文研究对象模糊p 系统在计算模型中的位置。 rd n a 计算 【膜计算 转移p 系统通讯一进化p 系统带激活膜的p 系统其他 j 遥眵 6 算 算 算 算 计 计 计 计 化 经 子 子 进 神 量 分 厂j、l 算 算 计 计 灵 然 图 自 厂lj一、|l 型模算汁 图1 ：膜计算在计算模型中的位置 与电子计算机相比，膜计算系统的优越性在于可以在一个时间单元内执行 多个操作，具有最大并行性。 最大并行性极大的提高了计算能力和计算效率，使得用膜计算的思想去解 决现在的电子计算机不能解决的问题成为了可能。 例如：许多著名的难解计算问题可以通过穷尽所有可能解来解决，然而， 这样的搜索规模过于庞大，利用当前的技术是无法完成的，但由于单个细胞体 积很小，生物体内细胞数目巨大，多个细胞内同时可以发生化学反应，这也许 可以使穷尽搜索成为可能。膜计算打开了解决难计算问题的另一扇门，具有非 常重要的研究价值。 下面介绍膜计算中的关键概念：多集合、膜结构和规则。 2 2 多集合 在细胞质中游离着大量物质，如小分子，大分子，铁离子等，我们把这些 物质称为作用物，换句话说，作用物是细胞质中的物质种类。作用物是无序的， 对化学反应而言，只有浓度才起着作用。作用物的浓度，就是作用物的数量， 例如铁离子有2 3 摩尔等。显然，这样存在重复物质的集合不能由传统的集合表 示的问题。为传统的集合( s e t ) 由相互不同的元素组成，即集合元素不允许重复， 必须借助于多集合表示。多集合( m u l t i s e t ) 是允许集合内元素重复多次( 有限 次) 出现的集合，是传统集合的泛化。其形式化定义如下： 定义2 2 1 ( 多集合定义) 令d 为集合，在d 上的多集合z d ，f ， 其中，d 是集合，是一个函数：d 寸n ( n 为正整数集合) 。 实际上，集合是多集合的特殊情况，集合a = ，u 是全集，乜 是特征函数。多集合的子集，并，差的概念是膜计算中由于规则应用改变物质 的基础。 定义2 2 2 ( 子集定义) 设a ： 与b = 是多集合，则b 是彳 的子集，标记为b a 当且仅当v a e a ，f ( a ) g ( 口) 。 7 生出太堂亟：| 幺奎 搓搠丕蕴殴建搓塑摸担 例如，a = 口，a , a ，b ，b ，d