求解计算困难问题的膜计算模型与算法研究

摘要

膜计算是自然计算的一个新的分支。它是由细胞以及由细胞组成的组织或器官的结构和功能得到启发,而抽象出来的一种计算模式。从“膜计算”的概念提出至今十几年的时间里,关于膜计算的计算理论、模型、算法及应用得到了飞速发展。膜计算为计算机科学提供了新的分布式并行信息处理方法和技术,促进了新型高性能计算技术的发展,为求解计算困难问题提供了新的途径。类细胞膜系统和类组织膜系统是膜计算模型的两种基本类型。本文主要研究了在这两种模型框架下求解计算困难问题的膜计算算法。
　　计算有效性描述的是模型求解计算困难问题的能力,是自然计算中的一个关键问题。膜计算模型基于常用的空间换时间的方法(通常使用受生物启发的操作,如膜分裂、膜分割和膜创生),可以在多项式时间内求解计算困难问题。如何构造算法在多项式时间内求解计算困难问题,特别是,NP完全问题,PSPACE完全问题;如何改进已有的结果,构造半统一形式(semi-uniform)的解与统一形式(uniform)的解等都是值得研究的方向。本文对几个经典的NP完全问题— CAP问题、三匹配问题、二次分配问题,给出了不同膜系统框架或不同规则使用模式下的算法,分析了不同膜系统模型在计算中的表现。
　　空间换时间的膜计算算法尽管从理论上来说是正确的,但目前尚无真正意义上的生物或物理实现。从算法实现的现实考虑,膜计算优化算法成为解决计算困难问题的另外一种途径。它是膜系统框架与优化算法结合而成的,可以通过电子计算机仿真实现,得到关于计算困难问题的近似解。本文分别构造了两类膜系统框架下的膜计算优化算法,并将它们应用到路径规划领域,成功地求解了带容量约束的交通路径问题和带时间窗的交通路径问题。膜系统提供的并行分布式计算模型、结构变化方式和信息交流方式可以很好的改进传统优化算法的性能。主要工作如下:
　　首先,研究了带活性膜的膜系统框架下的算法设计。带活性膜的膜系统是类细胞膜系统的一种重要类型。该模型在计算过程中往往包含膜结构的不断进化。早期的带活性膜的膜系统是受电荷(+,?,0)控制的模型。但是,电荷的频繁变化不符合生物实际,从计算的角度看,也浪费了大量的计算资源。对于一个经典的NP完全问题――CAP问题,本文改进了P′erez-Jim′enez等人的已有结论,设计了不带电荷的情况下,求解该问题的算法,并给出了由半统一形式的解到统一形式的解的改进。另外,本文还研究了在极小并行的规则使用模式下如何求解该问题。特别地,这里首次在极小并行的情况下,给出了无电荷的带活性膜的膜系统求解NP问题的统一形式的解。
　　其次,研究了组织膜系统框架下的算法设计。本文延续类细胞膜系统求解CAP问题的研究,给出了在组织膜系统框架下求解该问题的算法,证明了组织膜系统的有效性。通过与前面的算法比较可以看出,组织膜系统只用两类规则即可实现对该问题的求解。系统的结构和规则简单,易于理解。此外,本文还给出了组织膜系统求解三匹配问题的算法。三匹配问题的算例可以与图论中的超图联系起来。以前的文献构造的求解一般图论问题的算法通常都既与顶点数目有关,又与边的数目有关。当边的数目改变时,通常需要重新构造系统。本文构造的算法只与超图的顶点数目有关,与超边的数目无关。因此,当边的数目改变时,只要点的数目不变,都无需重新构造系统。从这个意义上说,本文的构造技术优于之前的构造技术。
　　本文还特别研究了带二元输入的组织膜系统。以往的膜系统在求解NP困难问题时,通常都是采用一元编码的方式。因此,二进制编码的NP问题通常要先转化成一元编码的形式,再通过膜系统求解。但是,对于NP完全数值问题或牵扯到大量数值计算的NP问题,一元编码机制并不适当(较复杂)。通过膜系统解决这类问题时,二进制编码需要的计算资源更少。本文通过使用带二元输入的组织膜系统求解二次分配问题,证明了二进制编码的NP问题可以直接通过带二元输入的组织膜系统求解,而不需要转化为一元编码的形式。
　　最后,本文设计了两类膜计算优化算法,并分别用于求解带容量约束的交通路径问题和带时间窗的交通路径问题,将膜算法的应用扩展到路径规划领域。带容量约束的交通路径问题是大量路径问题的基本模型。本文设计的膜算法采用类细胞的膜结构,蚁群算法作为其子算法。特别地,将膜计算中“非确定的规则使用模式”引入到算法设计中,改善了蚁群算法的性能,有助于平衡收敛速度与搜索效果之间的矛盾。带时间窗的交通路径问题增加了时间调度这一环节,有更广泛的实际应用背景。为解决这一问题,本文设计了一种基于类组织膜系统的膜算法。该算法融合了“分布式结构”、“同向传输”等膜系统特性,扩展了搜索模型,避免了遗传算法容易过早收敛的问题。通过将仿真实验结果与文献中的当前最好结果作比较,证明了该算法的竞争力。其中两个测例的搜索结果比当前最好结果分别少一辆车。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景及意义

1.2 膜计算模型介绍

1.3 膜计算算法介绍

1.4 研究涉及到的定义和概念

1.5 研究内容与创新点

1.6 本文的内容安排

2 带活性膜的膜系统框架下的算法设计

2.1 极大并行模式下求解CAP问题

2.2 极小并行模式下求解CAP问题

2.3 本章小结

3 组织膜系统框架下的算法设计

3.1 组织膜系统求解CAP问题

3.2 组织膜系统求解三匹配问题

3.3 本章小结

4 带二元输入的组织膜系统求解二次分配问题

4.1 带二元输入的组织膜系统

4.2 二次分配问题

4.3 统一形式的解

4.4 本章小结

5 膜算法求解带容量约束的交通路径问题

5.1 相关定义

5.2 膜算法设计

5.3 仿真实验

5.4 参数分析

5.5 本章小结

6 膜算法求解带时间窗的交通路径问题

6.1 带时间窗的交通路径问题

6.2 膜算法设计

6.3 仿真实验

6.4 本章小结

7 总结与展望

7.1 全文总结

7.2 尚待研究的工作

致谢

参考文献

附录1 攻读学位期间发表的学术论文

附录2 博士学位论文章节内容与博士期间发表论文的关系

附录3 攻读博士学位论文期间参加的科研课题