论文部分内容阅读
膜计算(Membrane Computing, MC)作为计算机科学的一个重要研究领域,旨在研究从生命细胞的结构与功能中以及从组织和器官等细胞群的协作中抽象出的计算模型,其计算模型被称为膜系统或P系统。膜系统是一类具有分布式、极大并行性的计算模型,大量研究表明,许多简单膜系统在理论上具有与图灵机同等的计算能力。膜计算是当前非常活跃的一个研究领域,研究者们用数学、形式语言等工具来进行膜计算的理论研究,提出了各种P系统模型并取得很多研究成果。目前已提出的P系统模型都是由研究者们精心设计而成,其设计过程都较为复杂,既需要扎实的专业知识,又需要仔细反复推导论证,费时费力。对于膜系统设计方法研究,目前相关工作还非常少,非常需要进一步研究。本文以细胞型膜系统作为研究对象,探讨采用量子进化算法和P-Lingua软件实现膜系统自动优化设计的方法。论文主要工作及研究成果如下:1、概述膜计算基本理论,简要介绍细胞型膜系统仿真软件,对膜系统仿真软件P-Lingua进行详细介绍,并通过实例说明细胞型膜系统在P-Lingua软件中仿真实现方法。2、详细描述和分析细胞型膜系统设计问题,给出简单细胞型膜系统优化设计方法,具体介绍了其设计思路、采用的量子进化算法、膜系统的编码和评价方式。将此方法应用于计算四平方膜系统的设计,获得比遗传算法更好的实验结果。在此基础上,对此方法进行拓展,用于计算任意自然数平方膜系统设计,并通过实验验证该方法的有效性。3、通过改进评价方法和在量子进化算法中加入局部扰动策略,实现膜系统优化设计方法的改进。运用改进后的设计方法,在同样的给定条件下,只通过改变评价函数,分别实现任意自然数平方P系统、代数式P系统、语言产生P系统的设计。此外,与采用传统的量子进化算法、随机搜索算法的设计方法分别进行对比实验,结果表明改进后的设计方法能获得更好的效果。4、给出细胞型膜系统的踪迹设计法,具体介绍了膜系统踪迹的定义、设计思路、膜系统的编码和评价方式。将此方法应用于计算任意数平方P系统的设计,结果表明膜系统踪迹设计法是可行并且有效的。本文工作得到国家自然科学基金(61170016)和教育部新世纪优秀人才支持计划项目(NCET-11-0715)和教育部留学回国人员科研启动基金项目的共同资助。