求解计算困难问题的膜计算模型和算法研究.doc

:NiuYunyunMajorSupervisor:SystemAnalysisandAssembling:&TechnologyWuhan430074,,2012√独创性声明本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知,除文中已标明引用的内容外,本论文不包含任何其他人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名:日期:年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于保密,在不保密。年解密后适用本授权书。(请在以上方框内打“”)学位论文作者签名:指导教师签名:日期:年月日日期:年月日华中科技大学博士学位论文摘要膜计算是自然计算的一个新的分支。它是由细胞以及由细胞组成的组织或器官的结构和功能得到启发,而抽象出来的一种计算模式。从“膜计算”的概念提出至今十几年的时间里,关于膜计算的计算理论、模型、算法及应用得到了飞速发展。膜计算为计算机科学提供了新的分布式并行信息处理方法和技术,促进了新型高性能计算技术的发展,为求解计算困难问题提供了新的途径。类细胞膜系统和类组织膜系统是膜计算模型的两种基本类型。本文主要研究了在这两种模型框架下求解计算困难问题的膜计算算法。计算有效性描述的是模型求解计算困难问题的能力,是自然计算中的一个关键问题。膜计算模型基于常用的空间换时间的方法(通常使用受生物启发的操作,如膜分裂、膜分割和膜创生),可以在多项式时间内求解计算困难问题。如何构造算法在多项式时间内求解计算困难问题,特别是,NP完全问题,PSPACE完全问题;如何改进已有的结果,构造半统一形式(semi-uniform)的解与统一形式(uniform)的解等都是值得研究的方向。本文对几个经典的NP完全问题—CAP问题、三匹配问题、二次分配问题,给出了不同膜系统框架或不同规则使用模式下的算法,分析了不同膜系统模型在计算中的表现。空间换时间的膜计算算法尽管从理论上来说是正确的,但目前尚无真正意义上的生物或物理实现。从算法实现的现实考虑,膜计算优化算法成为解决计算困难问题的另外一种途径。它是膜系统框架与优化算法结合而成的,可以通过电子计算机仿真实现,得到关于计算困难问题的近似解。本文分别构造了两类膜系统框架下的膜计算优化算法,并将它们应用到路径规划领域,成功地求解了带容量约束的交通路径问题和带时间窗的交通路径问题。膜系统提供的并行分布式计算模型、结构变化方式和信息交流方式可以很好的改进传统优化算法的性能。主要工作如下:首先,研究了带活性膜的膜系统框架下的算法设计。带活性膜的膜系统是类细胞膜系统的一种重要类型。该模型在计算过程中往往包含膜结构的不断进化。早期的带活性膜的膜系统是受电荷(+,?,0)控制的模型。但是,电荷的频繁变化不符合生物实际,从计算的角度看,也浪费了大量的计算资源。对于一个经典的NP完全I华中科技大学博士学位论文问题――CAP问题,本文改进了P′erez-Jim′enez等人的已有结论,设计了不带电荷的情况下,求解该问题的算法,并给出了由半统一形式的解到统一形式的解的改进。另外,本文还研究了在极小并行的规则使用模式下如何求解该问题。特别地,这里首次在极小并行的情况下,给出了无电荷的带活性膜的膜系统求解NP问题的统一形式的解。其次,研究了组织膜系统框架下的算法设计。本文延续类细胞膜系统求解CAP问题的研究,给出了在组织膜系统框架下求解该问题的算法,证明了组织膜系统的有效性。通过与前面的算法比较可以看出,组织膜系统只用两类规则即可实现对该问题的求解。系统的结构和规则简单,易于理解。此外,本文还给出了组织膜系统求解三匹配问题的算法。三匹配问题的算例可以与图论中的超图联系起来。以前的文献构造的求解一般图论问题的算法通常都既与顶点数目有关,又与边的数目有关。当边的数目改变时,通常需要重新构造系统。本文构造的算法只与超图的顶点数目有关,与超边的数目无关。因此,当边的数目改变时,只要点的数目不变,都无需重新构造系统。从这个意义上说,本文的构造技术优于之前的构造技术。本文还特别研究了带二元输入的组织膜系统。以往的膜系统在求解NP困难问题时,通常都是采用一元