张凤月[1]2004年在《0-1规划和排课表问题的DNA计算模型研究》文中研究指明Adleman1994 年在Science 上发表的文章“Molecular Computation of Solutions to Combinatorial Problems”,成功地用DNA 计算方法求解有向图的Hamilton有向路问题,标志着一个全新的研究领域——DNA计算的随之产生。由于DNA计算机具有的巨并行性、海量存储以及低能耗等特点,该领域的研究引起了众多学者的关注。本文结合生物学的研究方法和实验技术,对DNA 计算及其模型生物实现过程中的编码问题做了初步地探讨,并就DNA计算中的简单0-1 规划问题和排课表问题进行了初步研究。在DNA 计算中,信息是以DNA 序列为载体并通过DNA 分子间的特异性杂交来完成信息的处理的,因此,DNA 计算首要的问题就是DNA编码问题。由于DNA计算编码问题实质上属于NP 问题,目前的编码方法还无法很好地满足特定DNA计算模型的实际要求。本文在对DNA 计算中编码问题的产生背景和主要研究进展做了简单介绍,并进一步综合分子生物学实验涉及到DNA 设计基本原则的基础上,提出利用计算机辅助生物软件来对DNA编码链进行验证。结合对一DNA计算模型的DNA编码链的理论及实验结果验证,表明该方法对DNA编码验证是可行的。DNA 计算离不开生物反应,并且在很大程度上依赖于生物技术的发展,而代表生物技术前沿技术的生物芯片技术,其在对信息的处理和DNA 计算上有诸多相似之处。本文用DNA计算解决规划问题的研究中,对0-1 规划问题分别给出了基于溶液计算、表面计算和溶液表面结合计算的叁类DNA 计算模型,分别强调了溶液计算的高度并行和高存储性,表面计算的高自动化程度等优点,并进一步利用溶液与表面计算相结合的方法来避免各自的缺点,突出其优点,生物实验对溶液与表面计算相结合的模型进行了验证。另外,我们指出生物芯片技术可以被用于构建DNA计算的芯片,而可能解决更复杂的规划问题的DNA 计算模型,将是溶液与表面计算、常规和先进生物技术结合的产物。对于DNA计算而言,其关注的焦点在于能否解决现实中的难计算问题。目前研究者逐渐意识到,除非可以获得极大的反应规模,否则理论上仅仅通过增加反应规模来增强计算能力并无助于DNA 计算的进一步发展。基于此原因,我们利用两项生物技术:Acrydite~TM 凝胶技术和缩微实验室技术(Lab-on-chip),首次在理论上构建了解决简单排课表问题的DNA 计算模型,尽管其在运算规模上还无法达到大容积溶液计算的高并行性和高存储量,但两类模型都具有自动化,微型和高通量分析的特征。我们认为通过将前沿的生物技术和计算的新形式的相互结合,在一定程度上对并行性和可行性进行取舍,探索构建杂交型的微型DNA计算机将有助于DNA
单静怡, 殷志祥[2]2014年在《基于表面的DNA计算模型解决排课表问题》文中研究表明考虑到教师、班级以及课时等的不同要求,复杂的排课表问题就属于NP问题。为了使排课表问题更加简捷,方便,提出了基于微量点样技术的表面DNA计算模型。在实验中,通过对每次结果进行记录和比较,得到了满足问题要求的可行解。不需要改变问题的初始点列,适于研究规模较大的问题。
陈敏[3]2013年在《基于DNA计算模型的图顶点着色问题及其应用》文中指出DNA计算是一门新兴学科,是生物计算中最受关注的一种智能计算,自1994年,图论中的哈密顿路径问题被Adleman利用DNA计算成功解决并进行了实验,DNA计算就成为国内外专家学者关注的重要领域。DNA计算的基本思想是：利用DNA分子特殊的自我复制等性能,产生相应的编程,然后生成DNA分子链,在各种生物酶的催化下,生成所需的数据池(data pool),然后进行生物反应。最后,利用PCR、分子纯化、凝胶电泳、磁珠分离等生物技术,对产生的结果进行检测。首先,本文介绍了DNA计算的产生背景,研究状况,生物学操作。指出DNA计算机的优点与缺点、实际应用与存在的问题。其次通过对DNA计算的几种模型的研究,试图找到DNA计算模型来解决图顶点着色问题,并对几种模型进行比较。最后,利用图顶点着色的DNA计算模型,解决了课表安排问题及机场停机位问题。排课表是一个典型的NP-完全问题。本文利用AcryditeTM凝胶技术,把课时作为图顶点着色信息映射成DNA分子链,构建凝胶柱,通过生物反应将DNA链重新排列,排列所需要的最少循环数即为排课表所需要的最少课时数。AcryditeTM凝胶技术作为较新的一种核酸分离技术,在DNA计算中得到了成功应用。停机位分配(ASA)是一种关于优化组合的问题,分配的合理性对机场的生产调度非常关键。本文通过对ASA问题的分析,把ASA问题转化为基于DNA计算的图顶点着色模型并设计了一种生物算法。经过多次实验证明：这种算法非常的简单,在实验室中很容易操作,与遗传算法,贪婪算法相比,更具有优势。
李艳梅[4]2016年在《DNA计算模型的理论设计与应用研究》文中研究说明DNA分子计算是以DNA分子作为“数据”,以DNA的生化反应作为“信息处理工具”的计算模式。自1994年Aldeman成功利用DNA分子求解了七个结点的哈密尔顿路径问题后,DNA分子计算以其海量的存储能力和高度并行计算能力等优势,为求解NP难题提供了一种新的解决方法。DNA计算的发展依赖于当前生物技术的发展水平。目前各种DNA计算模型都是针对特定问题而建立的特定计算模型,很难不做修改或少量修改应用于其他问题,即不似电子计算机般具有通用性;随着问题规模的增加,DNA的并行计算能力受生化反应的影响而大大降低,失去了其计算优势;目前解的检测基本上采用电泳技术、PCR扩增等常规的生物检测方法,错误率高。以上多种局限性成为制约生物DNA计算自动化发展的重要障碍。本文借鉴生物DNA计算并行处理信息的原理,提出了一种新的基于硅的仿生物并行计算模型-DNA电子计算模型(DNA electronic computing model,DEM)。本文主要包括基础理论的提出、硬件实现和在求解图论和军事弹药配送路径优化问题等NP难题的应用研究叁方面,本文的具体工作如下:(1)DNA电子计算模型的理论基础及仿真实现DNA计算中典型模型之一的粘贴模型采用单双链混合对DNA分子进行编码:单链用来表示2-进制数中的0,双链来表示2-进制数中的1,编码形式与电子计算机类似,具有一定的通用性。且粘贴模型是一种典型的同时对信息位垂直处理的计算模型,其信息并行处理原理适合在硅硬件上实现。借鉴粘贴模型的信息表达和并行计算原理详细介绍了DEM的基础理论模型-一种基于分子计算的广义图灵模型(Generalized Turing Machine,GTM)。GTM通过特殊的拓扑映射和并行的同时读、写算子,实现对信息的并行处理。通过求解可满足性问题的仿真试验详细说明的GTM的并行计算原理。对GTM结构不变的情况下进行改进,通过增加指令可以在多项式时间内求解集合覆盖问题的最优解。仿真试验说明GTM在求解NP难题时具有一定的通用性。(2)DEM模型的硬件实现本部分工作为本文的重点,将GTM在SOPC平台进行软硬件实现,提出了基于硅的DEM模型。DEM根据功能划分为指令系统、地址译码器、数据生成器、处理单元、结果分析器等功能模块。首先根据DEM各功能模块实现的复杂度和规模进行软硬件划分,进行软硬件设计。对于不同的问题,指令系统和结果分析器因问题不同而异,故用软核实现;地址译码器、数据生成器等生成具有自主知识产权(Intellectual property core,IP核)的硬件电路图。(3)DEM在图论问题中的应用研究通过图的最大团问题详细了DEM的硬件实现方法。针对图的最大团的指令系统和结果分析器进行软核设计,该部分在NiosII集成开发环境下用C语言编写软件代码;基于多值逻辑的地址译码器、数据译码器等在SOPC内部搭建硬件电路;最后将软硬核下载固化到目标电路板上。Ramsey数问题是组合数学甚至整个数据界最困难的数据问题之一,本文在求解图的最大团算法基础上,提出了通过逐个添加顶点,删除非解的求解Ramsey数的DEM_(RAM)模型。在一定程度上缓解了解空间的指数增长速度。(4)DEM在军事弹药配送路径优化问题中的应用研究可满足性问题、图的最大团问题、集合覆盖问题、旅行商问题以及军事弹药配送路径优化等问题都可以转换为0-1规划问题,故对0-1规划问题的算法研究在实践中有着广泛的应用价值。介绍以上问题的0-1规划形式的数学模型,并设计求解0-1规划问题的DEM求解方法。军事弹药配送路径优化问题是旅行商问题的扩增,如何实时、精准、安全地将弹药运送到需求部队手中关系着整个战斗的胜负。分析弹药配送路径的特殊性要求,利用DEM进行计算,并对算法进行复杂度分析,验证了该计算模型在计算军事弹药供给线路优化问题中的优越性。
强小利[5]2008年在《图顶点着色DNA计算模型及实验研究》文中研究说明DNA计算是以DNA分子作为“数据”,以生化反应作为“信息处理工具”的一种新颖计算模式。由于其高度并行性、海量存储能力、低能耗等优点,DNA计算成为众多学者关注的焦点。近年来,许多研究成果已经提高了它的性能并增加了它的可行性。但是,DNA计算尚未成熟。关于DNA计算理论和技术上的进一步研究都具有重要的科学意义。图顶点着色问题存在于丰富的科学和工程应用中,如工序问题、排课表问题、物资储存问题等等,但它却是众所周知的NP-完全问题。本文针对这一具体问题,结合分子生物学的研究方法和实验技术,旨在建立自动化程度较高的,可用于求解较大规模问题的DNA计算模型,研究探讨了四种解决图顶点着色的DNA计算模型的可行性及优缺点,对每个DNA计算模型给出了具体的编码条件及相应的编码,及实现DNA计算模型的生化操作的实验步骤,并对一些模型给出了详细的实验验证。主要工作如下:文章首先基于杂交反应提出一种枚举型的DNA计算模型。在该模型中,提出了具体编码方案,并利用DNA自动合成仪合成初始解空间,然后利用杂交反应和聚合酶链式反应来求解问题。文章以具有5个顶点图为例对该模型进行了生化实验验证。实验结果表明,该模型能有效求解图顶点着色问题。为了减少DNA计算中编码的数量,不降低生化实验操作的可靠性,文章提出一种改进的枚举型DNA计算模型。在该模型中,利用双编码法对图顶点着色这一问题进行编码,利用酶切反应和聚合酶链式反应对问题进行求解。实例分析表明,该模型具有编码量少、求解过程简单的优点,尤其是因为该模型的解的检测方法类似于DNA测序技术,使得该模型更容易实现自动化操作。解空间指数爆炸问题是阻碍DNA计算发展的最大瓶颈。针对这一问题,文章提出一种非枚举型DNA计算模型。在模型中,首先对编码方案和初始解空间构建进行了优化,构建了非枚举型的初始解空间,删除了大量非解,提高计算效率;然后利用聚合酶链式反应实现非解删除的操作,并使用DNA测序技术读取最终解;文章以一个含有12个顶点的图为例对该模型进行了实验验证。实验结果表明,该模型有效可靠,可以较好的克服DNA计算中的解空间指数爆炸问题。为建立可用于求解大规模图顶点着色问题的DNA计算模型,文章在非枚举型DNA计算模型的基础上,引入并行处理的思想,建立了一种并行型DNA计算模型。在模型中,给出了一种子图划分的方法和原则,通过对给定图进行分解和合并处理,使得该DNA计算模型能够求解更大规模的图顶点着色问题。文章以一个含有61个顶点的图为例,对该模型进行了实验验证。实验结果表明,该模型不但延续了非枚举型DNA计算的优势,而且具有解决大规模的图顶点着色问题的能力。同传统的DNA计算模型相比,该模型可以大大提高计算效率,降低成本,能有效处理更大规模的图顶点着色问题,具有较强的应用价值。为了满足不同DNA计算模型的编码需求,文章也考虑了不同编码条件及参数,设计了大量DNA编码。实验结果表明,这些编码能满足DNA计算中的数量和质量要求。由此所构成的编码数据库,能方便DNA计算技术的设计与利用,为后续超大规模DNA计算模型奠定了基础,具有较高的理论意义和应用价值。
陈远[6]2009年在《基于遗传算法的排课系统的设计》文中研究表明课程表是学校教学工作的基本文件,排课表是教学管理的重要环节。随着高校招生规模扩大,课程数目繁多,如何高效的编排出科学合理的课表,已经成为学校教学管理中较为复杂、最为棘手的难题之一。排课问题是一种复杂的排程问题,不仅影响因素众多,而且各因素互相制约,环节复杂。排课问题要解决的是找出教师、班级、课程、上课时间等因素的最佳对应关系,并尽量满足诸多的限制条件,因此排课问题是一个多目标的优化问题。遗传算法借鉴生物界自然选择和自然遗传机制,使用群体搜索技术,尤其适用于处理传统搜索方法难以解决的复杂的非线性问题。它通过对当前群体施加复制、交叉、变异等一系列遗传操作,从而产生新一代的群体,并逐步使群体进化到包含或接近最优解的态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受,并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领域得到了广泛的应用。遗传算法给我们呈现出的是一种通用的算法框架,该框架不依赖于问题的种类。遗传算法是一类具有较强鲁棒性的优化算法,特别是对于一些大型、复杂非线性系统,它更表现出了比其他传统优化方法更加独特和优越的性能。本文以高校排课问题为研究范围,以遗传算法建构求解模式,产生满足硬条件的初始解,并以软条件为适应度依据,进行最佳解的搜索。求解利用Matlab编写运行程序,最后以一所职业技术学院课表系统为实例,执行程序,结果证明这种方法切实可行。系统经时间性能和排课性能测试,结果表明,系统降低了排课的复杂程度,提高了排课的效率。该排课算法的实现很好地满足了学校的排课需求,同时对其他高校排课系统的开发也具有参考价值。
卢雅晴[7]2015年在《基于选课满意度的学期课表问题研究》文中提出选课和排课是教务工作中不可或缺的组成部分,对于维护良好的教学秩序具有重要的指导作用。其中排课问题作为一项常见的组合优化问题,涉及因素较多,规模较大,实际操作相当复杂。本文从高校选课排课中的实际案例出发,研究基于选课满意度的学期课表问题,文章所做的主要工作如下:首先,描述了该排课问题的特点,在排课模式上,将选课与排课过程结合考虑,同时引入了选课偏好表、选课满意度等概念,使得排课过程更尊重学生的选课意愿,且有利于多样化人才的培养;在时间元素上,考虑周次、节次的结合,贴近高校实际排课情形,同时能够更加有效地利用教学资源;在教师因素方面,考虑一人教授多门课程的情况,对资源进行合理的优化。其次,构建了新的排课模型,同时考虑多个约束,该模型将学期课表与自选课程相结合,不仅拓展了排课问题的研究内容,也丰富了排课问题的理论范畴。最后,在求解阶段,通过叁阶段式算法来进行求解,第一阶段进行数据的预处理,存储课程冲突矩阵等关键信息,第二阶段通过基于优先级的构建法,较快速的得到满意的初始可行解,最后采用局部搜索算法对初始课表进行优化,并通过算例对基于自选课程的学期课表问题和基于课程集的学期课表问题进行对比分析,验证了该模型和算法在同样满足各约束的基础上对于保证学生选课满意度上的有效性,为高校“先选课后排课”模式提供了理论依据和技术支撑。
许进, 强小利, 方刚, 周康[8]2006年在《一种图顶点着色DNA计算机模型》文中指出设计了一种专门用于求解图顶点着色的DNA计算机.该计算机的主体是由一个可变温度的聚丙烯酰胺凝胶电泳构成.可变温度的电泳由3部分组成,分别为“解链区”、“非解区”和“解区”.它们对应的可控温度分别为Tm1,Tm2和Tm3.本文介绍了该计算机的基本结构与基本原理,给出了存储库的构建方法,特别讨论了编码问题,并成功地对5个顶点的图给出了系统的生物操作与生化实验.
汪晓飞[9]2008年在《基于多维编码方案的遗传算法在高校排课系统中的应用》文中提出排课问题是典型的多重约束和组合优化问题,并且早在70年代已经被证明是一个NP完全问题。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的自适应随机搜索算法。它具有良好的并行性、通用性、稳定性,是一种非常有效的解决NP完全问题的方法。本文将遗传算法应用于求解排课问题,主要进行了以下几个方面研究工作:首先,系统分析了排课问题的各要素及多重约束条件,提出了排课问题的求解难点和优化目标,并完整设计了排课问题的数学模型。其次,着重分析比较常用的遗传算法编码方案并研究其在排课系统中的应用,在综合各种编码方案优缺点基础上,设计了一种更适合解决排课问题的多维编码方案。较之传统编码方案,该编码方案更简单、更高效、更易于理解。并且,根据设计的编码方案,重新设计了与之对应的交叉算子和变异算子。再次,结合排课问题具体数学模型,以Visual C++ 6.0为主要开发工具,将多维编码方案以及与之对应的改进遗传算子应用到排课系统中,设计并实现了基于上述改进型遗传算法的自动排课系统。最后,以实际排课数据测试了本论文设计的多维编码方案及对应的遗传算子在实际排课问题中的应用,并对测试结果从时间复杂度和排课结果两方面进行了性能分析,效果令人满意。
刘敏[10]2013年在《基于病毒进化遗传算法排课系统的研究与实现》文中研究说明1976年S.Even和Cooper证明了排课问题是一个NP完全问题,不存在精确求解排课问题的多项式时间算法,需借助智能算法寻找其较合理和满意的近似最优解。遗传算法通过模拟自然界生物遗传中的“优胜劣汰、适者生存”原则,避免陷入局部最优解,从而实现对最优解或次优解的快速搜索,被广泛应用于函数优化、组合优化等领域,是当今影响深远的进化计算方法之一,但其存在着局部早熟收敛和进化后期搜索速度下降等问题。病毒进化遗传算法通过引入病毒种群的感染、复制和删减操作在实现了种群的生物多样性的同时,又保持了遗传算法原有的同代间基因信息传递,有效的实现了上下代种群之间的纵向遗传信息传递和同代种群的横向进化信息传递,获得了较为满意的算法收敛性能,有效的克服了传统遗传算法固有早熟和收敛性能不佳的缺点。本文借鉴病毒进化遗传算法的思想对排课问题进行了研究与应用,其主要工作如下：1.系统研究了排课问题,并根据课题的实际需要,分析了排课问题的基本要素、各类软、硬约束条件和求解目标,建立了排课系统的数学优化模型。2.在总结了遗传算法在排课问题中的应用研究后,针对排课问题本身的特点,提出一个适宜解决该问题的改进病毒进化遗传算法(Improved Virus Evolutionary Genetic Algorithm,IVEGA),其主要改进在于：(1)改进传统病毒种群的随机生成方式,有效的利用了排课历史数据和约束条件,加快了病毒种群的收敛。(2)针对排课问题设计了一种有效的基因编码方式,使得原有算法更有针对性。使用典型测试函数对该算法的性能进行测试并与其它算法进行比较,表明了该算法的有效性。3.根据IVEGA算法,以Visual Studio2008为工具,使用C#语言实现了一个排课算法原型,并用实际数据进行了测试,测试结果表明,该原型系统能较好的完成排课任务的分派工作。
参考文献：
[1]. 0-1规划和排课表问题的DNA计算模型研究[D]. 张凤月. 华中科技大学. 2004
[2]. 基于表面的DNA计算模型解决排课表问题[J]. 单静怡, 殷志祥. 安徽理工大学学报(自然科学版). 2014
[3]. 基于DNA计算模型的图顶点着色问题及其应用[D]. 陈敏. 安徽理工大学. 2013
[4]. DNA计算模型的理论设计与应用研究[D]. 李艳梅. 北京理工大学. 2016
[5]. 图顶点着色DNA计算模型及实验研究[D]. 强小利. 华中科技大学. 2008
[6]. 基于遗传算法的排课系统的设计[D]. 陈远. 苏州大学. 2009
[7]. 基于选课满意度的学期课表问题研究[D]. 卢雅晴. 华中科技大学. 2015
[8]. 一种图顶点着色DNA计算机模型[J]. 许进, 强小利, 方刚, 周康. 科学通报. 2006
[9]. 基于多维编码方案的遗传算法在高校排课系统中的应用[D]. 汪晓飞. 四川师范大学. 2008
[10]. 基于病毒进化遗传算法排课系统的研究与实现[D]. 刘敏. 湖南大学. 2013