膜计算应用研究

发布时间：2020-10-16 17:36

　　 根据摩尔定律,传统计算机中的晶体管电路逐渐接近性能极限,再加上电子计算机在计算能力等方面存在的局限性,科学家期待并开始在自然界寻找新的计算介质来代替传统的电子计算机,其中利用生物硬件的分子计算机因其极高的并行性与极低的能耗量而受到科学界的极大青睐。生物系统是个复杂的“计算系统”,是产生新的计算思想的重要源泉。从各种各样的生物系统及其进化过程中获得灵感,可为求解传统计算方法难于解决的各种复杂问题提供新的计算思想或模型。膜计算(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算法的设计思想可推广到求解其他的离散优化问题。 作为自然计算的新分枝,目前对膜计算的研究还处于数学模型建立、理论研究阶段。将膜计算与其他领域相结合、从理论上来指导解决各自领域中的问题以及实现技术的研究还比较薄弱。本论文的研究工作即是在这样的背景上展开的,论文取得的成果不仅促进膜计算的理论与应用研究,也为相关领域的研究提供新的思路和途径。
【学位单位】：重庆大学
【学位级别】：博士
【学位年份】：2011
【中图分类】：TP38
【部分图文】：

学界的极大青睐。生物体的信息获取、存储与处理方人脑凭借众多的神经元构成的复杂网络实现对各种信生命的核心，其复杂结构构造了复杂计算——生命既细胞间信息的交换与处理发生在各种生命体中，以此强大功能。是个复杂的“计算系统”，是产生新的计算思想的重要领域的一门新兴学科，它主要包括进化计算、神经计名的研究方向。如图 1.1 所示，自然计算从生物体的结出各种各样的计算模型或计算思想[1]。膜计算(Memb一个新分支，其目的是从活细胞中以及组织、器官或作的方式中获得新的计算思想、设计新的计算模型。统，也称为 P 系统。1998 年，欧洲科学院院士、罗马在研究生物细胞结构和功能时，根据细胞处理化学物质算模型[2]，从而拉开了膜计算研究的序幕。该理论不仅

把 E {λ }+∪ 简记为*E 。 系统P 系统的生物学基础胞是生命的基础也是最小的生命载体。作为生命结构，细胞内部空间包含细胞核、线粒体、高尔某些病毒外，都具有生物膜。真核细胞除质膜(又器的内膜系统，包括核膜、线粒体膜、内质网膜体膜、过氧化酶体膜等。如图 2.1 所示，生物细胞而其内部的细胞器被内部膜包裹着，这些内部膜域，每个区域内存在着独立的、不同的生物化学整个生命体划分为一个个细胞所占据的区域，每活动。细胞膜和内部膜可统称为生物膜[106]。生物分离和过滤的功能。

图 2.4 转移 P 系统计算示例[3]ure 2.4 Example for calculation of the transition P syst的规则能被执行，显然，在同一时刻，有其中一组能被执行。现假设{a → ab, f →→ ff}。因 a → bδ的执行，使 3#膜被溶解，多，分两种情况：重集为2bcf 。{b → d , ff → f}或{b → d , cf →{b → d , ff → f}，然后只有{d → de, cf → cd多重集2cd e 被送到#1 膜中。{b → d , cf → cdδ}，#2 膜被溶解，多重集cd重集为112++nbcfn。 {b → d , ff → f}，得到多重集ncdfn +12。
【参考文献】

相关期刊论文 前10条

1 莫海芳;康立山;;求解TSP的混合遗传算法[J];计算机工程与应用;2007年18期

2 张煜东;吴乐南;韦耿;;智能算法求解TSP问题的比较[J];计算机工程与应用;2009年11期

3 王轩;李元香;;一种结合局部搜索策略的求解TSP的演化算法[J];计算机工程;2006年09期

4 张兴义;曾湘祥;潘林强;罗斌;;脉冲神经膜系统求解任意两个自然数的乘积[J];计算机学报;2009年12期

5 张葛祥;潘林强;;自然计算的新分支——膜计算[J];计算机学报;2010年02期

6 占志刚;张求明;张盛意;王康;;一种改进的自适应蚁群算法求解TSP问题[J];计算机与数字工程;2010年02期

7 江瑞,罗予频,胡东成,司徒国业;一种基于种群熵估计的自适应遗传算法[J];清华大学学报(自然科学版);2002年03期

8 王勇;蔡自兴;周育人;肖赤心;;约束优化进化算法[J];软件学报;2009年01期

9 罗若愚;李亦学;;系统生物学中建模方法的研究现状及展望[J];生命科学;2007年03期

10 ;P systems based multi-objective optimization algorithm[J];Progress in Natural Science;2007年04期

相关博士学位论文 前2条

1 黄亮;膜计算优化方法研究[D];浙江大学;2007年

2 张兴义;脉冲神经膜系统的计算能力研究[D];华中科技大学;2009年

本文编号：2843561