膜计算应用研究

论文摘要

根据摩尔定律,传统计算机中的晶体管电路逐渐接近性能极限,再加上电子计算机在计算能力等方面存在的局限性,科学家期待并开始在自然界寻找新的计算介质来代替传统的电子计算机,其中利用生物硬件的分子计算机因其极高的并行性与极低的能耗量而受到科学界的极大青睐。生物系统是个复杂的“计算系统”,是产生新的计算思想的重要源泉。从各种各样的生物系统及其进化过程中获得灵感,可为求解传统计算方法难于解决的各种复杂问题提供新的计算思想或模型。膜计算（Membrane Computing,也称为P系统）是自然计算的一个新分支,其目的是从活细胞中以及组织、器官或其他结构的细胞之间相互协作的方式中获得新的计算思想、设计新的计算模型。P系统不仅为计算机科学引入了新的分布式并行信息处理方法和技术,而且为生物系统的建模和仿真提供了新工具,是当前非常活跃的一个研究领域,预计在新一代计算系统、信息处理系统的技术开发方面将起关键作用。关于膜计算的研究工作可归为三类:理论研究、应用研究和软、硬件实现研究。膜计算的理论研究主要集中于各种计算模型的建立及其计算能力（Computation Power）的分析;膜计算的应用研究主要是利用P系统的特点和各种模型求解生物学、计算机科学、语言学、社会学等方面的实际问题;而膜计算的软硬件实现研究则侧重于在现有计算机上用程序实现或开发新的处理器实现有关的膜计算模型或求解有关问题。本论文以膜计算在计算机学科领域的应用为研究对象,本论文的主要工作包括:①构建算术运算P系统算术运算是加法、减法、乘法和除法四种运算的统称,是数学中最古老,最基础和最初等的部分。作为一种基本的运算,实现算术运算是未来生物计算机必须具备的基本功能之一,本论文构建一套基于脉冲神经P系统求解带符号数的算术运算系统,实现了操作数的进制转换以及加减乘除等运算。此工作为实现基于P系统的数值计算系统设计提供了理论依据。②设计求解HPP问题的P系统有向图G的Hamilton路径问题（Hamilton Path Problem,简称HPP问题）是图论中一个典型的NP完全问题。基于活性膜P系统,本论文构建与问题规模有关的P系统,来求解HPP问题,并从理论上证明该系统的求解方式是完备的,即使用一个这样的P系统可以以统一方式来判定有向图中任意两点间的是否存在Hamilton路径。此研究工作进一步扩展了前人对P系统求解计算困难问题的研究成果,为使用P系统以统一方式解决NP完全问题提供了一种新的途径。③提出基于P系统的约束函数优化算法约束优化问题与实际工程问题密切相关,对其进行研究具有十分重要的理论和实际意义。此类优化问题的难点在于约束条件的处理,引入P系统的并行特征以及膜间通信机制来处理约束,有利于增加进化种群的多样性,避免过早地陷入局部最优。为此,本论文提出了一种基于P系统的约束函数优化算法（Constrained Optimization Evolutionary Algorithms based on Membrane Computing,简称为MCCOP算法）,设计了与优化操作相对应的规则以及规则执行的策略。MCCOP算法充分利用了P系统中的膜间通信机制,使得个体可以通过不同的评估来指导进化。实验测试表明,MCCOP算法在解的效率和有效性之间取得了较好的折衷,为求解约束优化问题提供了一种新的思路。④提出基于P系统的求解TSP问题的近似算法旅行商问题（Traveling Salesman Problem,简称为TSP问题）是离散优化问题中的一个典型问题,其应用极为广泛。将局部搜索算子2-Opt和遗传算子相结合,本论文提出一种基于P系统的求解TSP问题的近似算法（Approximate Algorithm based on Membrane Computing for Traveling Salesman Problems,简称MCTSP算法）。基于P系统中皮肤膜与子膜之间的交流规则,在MCTSP算法中设计了全局进化与局部搜索相结合的控制机制。对TSP公共测试库TSPLIB中的实例进行测试并与其他求解TSP问题的混合优化算法（包括已提出的基于P系统的优化算法）进行对比分析,结果表明:MCTSP算法在保持群体的多样性的同时具有较快的收敛速度,在求解问题的精度上优于所对比的算法。MCTSP算法的设计思想可推广到求解其他的离散优化问题。作为自然计算的新分枝,目前对膜计算的研究还处于数学模型建立、理论研究阶段。将膜计算与其他领域相结合、从理论上来指导解决各自领域中的问题以及实现技术的研究还比较薄弱。本论文的研究工作即是在这样的背景上展开的,论文取得的成果不仅促进膜计算的理论与应用研究,也为相关领域的研究提供新的思路和途径。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 研究背景和意义
• 1.2 研究现状
• 1.3 主要研究内容
• 1.4 论文组织结构
• 2 膜计算概述
• 2.1 引言
• 2.2 形式语言基础
• 2.3 类细胞P 系统
• 2.3.1 类细胞P 系统的生物学基础
• 2.3.2 类细胞P 系统的定义
• 2.3.3 实例
• 2.4 脉冲神经P 系统
• 2.4.1 脉冲神经P 系统的生物学基础
• 2.4.2 SN P 系统的定义
• 2.4.3 实例
• 2.5 本章小结
• 3 算术运算 P 系统
• 3.1 引言
• 3.2 进制转换SN P 系统的设计
• 3.2.1 十进制转换为二进制
• 3.2.2 二进制转换为十进制
• 3.3 原-补码转换SN P 系统的设计
• 3.4 算术运算SN P 系统的设计
• 3.4.1 加减法运算
• 3.4.2 乘法运算
• 3.4.3 除法运算
• 3.5 本章小结
• 4 求解 HPP 问题的 P 系统
• 4.1 引言
• 4.2 活性膜P 系统
• 4.3 求解HPP 问题的P 系统设计
• 4.4 求解示例
• 4.5 系统分析
• 4.6 本章小结
• 5 基于 P 系统的约束函数优化算法
• 5.1 引言
• 5.2 MCCOP 算法的设计
• 5.2.1 约束条件的处理
• 5.2.2 对象以及膜结构
• 5.2.3 规则
• 5.2.4 算法步骤
• 5.3 实验结果与分析
• 5.4 本章小结
• 6 基于 P 系统的求解 TSP 问题的近似算法
• 6.1 引言
• 6.2 MCTSP 算法的设计
• 6.2.1 对象
• 6.2.2 膜结构
• 6.2.3 规则
• 6.2.4 算法步骤
• 6.3 实验及结果分析
• 6.3.1 实验参数的选择
• 6.3.2 与其他算法的比较
• 6.3.3 进一步讨论
• 6.4 本章小结
• 7 总结与展望
• 7.1 工作总结
• 7.2 后续研究工作的展望
• 致谢
• 参考文献
• 附录
• A 作者在攻读学位期间发表的论文
• B 作者在攻读学位期间取得的科研成果