论文部分内容阅读
膜计算(又称P系统)是由欧洲科学院院士、罗马尼亚科学院院士Gheorghe Paun教授提出的受生物细胞结构和功能启发的一种分布式并行计算模型。由于膜计算模型具有强大的计算能力,它受到了越来越多研究者的关注。
鉴于P系统生物实现的限制,膜计算模型仿真器成为P系统验证和研究的重要工具。以P-Lingua为代表的P系统仿真工具由于扩展性差、无人维护更新等原因,而不能适应膜计算的快速发展。膜计算领域也不断涌现出新特性、混合型计算模型。本文从仿真器的扩展性、可维护性出发开展了相关研究。在模型的应用研究方面,研究者们提出了包括基本四则运算、求解计算困难问题(SAT问题、0-1背包问题等)、膜算法等应用解决方案。其中,膜算法是受膜计算思想启发的一种启发式算法,但是在以往的研究中,膜算法实际应用时会集成很多其他的启发式算法,如遗传算法、局部搜索算法等,因而其进化能力依赖于其他启发式算法。本文从进化能力的角度研究了膜进化算法并将其应用于求解最小顶点覆盖问题。
本文基于对已有膜计算模型的研究,设计和实现了新的P系统仿真工具UPSimulator,提出和实现了受膜计算思想启发的膜进化算法MEAMVC。主要工作内容如下:
①设计和实现了P系统仿真工具UPSimulator。UPSimulator通过对P系统进化机制的仿真,实现了三类基础P系统以及很多最近提出的P系统进化规则的仿真。并且,UPSimulator支持的概念可以任意组合,随着支持概念的增多,UPSimulator能仿真的P系统的数目会呈指数级增加,这也就一定程度上解决了混合型P系统的仿真困难。
②提出了受膜计算思想启发的膜进化算法框架MEAF。MEAF含有自己独特的进化算子:分裂、合并、选择以及溶解。基于MEAF,本文实现了相应的算子,用于求解最小顶点覆盖问题。通过实验对比,发现实验结果比局部搜索算法更好,且更稳定。此外,本文还进一步优化了用于求解最小顶点覆盖问题的局部搜索算法,使之得到了更好的结果和性能。
本文设计和实现的P系统仿真工具UPSimulator极大地方便了膜计算领域的研究者进行模型的验证,同时也降低了新P系统的研究难度。本文提出的膜进化算法,拥有独特的计算算子,改变了膜算法需要集成其他启发式算法的局面。
鉴于P系统生物实现的限制,膜计算模型仿真器成为P系统验证和研究的重要工具。以P-Lingua为代表的P系统仿真工具由于扩展性差、无人维护更新等原因,而不能适应膜计算的快速发展。膜计算领域也不断涌现出新特性、混合型计算模型。本文从仿真器的扩展性、可维护性出发开展了相关研究。在模型的应用研究方面,研究者们提出了包括基本四则运算、求解计算困难问题(SAT问题、0-1背包问题等)、膜算法等应用解决方案。其中,膜算法是受膜计算思想启发的一种启发式算法,但是在以往的研究中,膜算法实际应用时会集成很多其他的启发式算法,如遗传算法、局部搜索算法等,因而其进化能力依赖于其他启发式算法。本文从进化能力的角度研究了膜进化算法并将其应用于求解最小顶点覆盖问题。
本文基于对已有膜计算模型的研究,设计和实现了新的P系统仿真工具UPSimulator,提出和实现了受膜计算思想启发的膜进化算法MEAMVC。主要工作内容如下:
①设计和实现了P系统仿真工具UPSimulator。UPSimulator通过对P系统进化机制的仿真,实现了三类基础P系统以及很多最近提出的P系统进化规则的仿真。并且,UPSimulator支持的概念可以任意组合,随着支持概念的增多,UPSimulator能仿真的P系统的数目会呈指数级增加,这也就一定程度上解决了混合型P系统的仿真困难。
②提出了受膜计算思想启发的膜进化算法框架MEAF。MEAF含有自己独特的进化算子:分裂、合并、选择以及溶解。基于MEAF,本文实现了相应的算子,用于求解最小顶点覆盖问题。通过实验对比,发现实验结果比局部搜索算法更好,且更稳定。此外,本文还进一步优化了用于求解最小顶点覆盖问题的局部搜索算法,使之得到了更好的结果和性能。
本文设计和实现的P系统仿真工具UPSimulator极大地方便了膜计算领域的研究者进行模型的验证,同时也降低了新P系统的研究难度。本文提出的膜进化算法,拥有独特的计算算子,改变了膜算法需要集成其他启发式算法的局面。