欢迎来到天天文库
浏览记录
ID:34809453
大小:1.21 MB
页数:42页
时间:2019-03-11
《试论dna计算及其算法优化》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、太原理工大学硕士学位论文DNA计算及其算法优化姓名:王斌田申请学位级别:硕士专业:计算机应用技术指导教师:余雪丽;欧阳钟灿20060501太原理工大学硕士研究生学位论文DNA计算及其算法优化摘要在计算机中,利用有机分子的信息处理能力来代替数字开关部件,这就是DNA计算的基本思想。以当前的计算机技术要实现微型化存在明显的局限性,所以要进行大的革新,很早以前就有人提出现代计算机的基本部件应逐步过渡到分子水平,这样一来,它将会比我们利用当前技术制造出的任何东西都要小得多,量子计算和DNA计算是当前这种思想的两种不同表现,本论文主要介
2、绍DNA计算。DNA计算主要基于以下两点:(1)DNA链的巨大并行性;(2)Watson—Crick的互补结构。传统理论上的计算机科学植根于重复写操作,这对于大部分自动机械装置和语言理论模型是正确的,然而,在计算行为中,自然界操作DNA分子利用的是完全不同的操作类型:剪切、粘贴、连接、插入、删除等。可以证明,利用这些操作可以建立计算模型,并且在功能上等价于图灵机。以前DNA计算的研究主要集中在一些组合问题上,像Hamiltonian路径问题、旅行商问题、3-SAT问题,甚至破解DES密码等等,但提出的上述所有问题的DNA算法基
3、本上都是蛮力搜索,初始化时生成问题的所有可能的解决方案,然后根据条件消除掉不正确的答案,最后剩下的方案即是问题的正确答案。但值得注意的是,实际问题的正确答案也许会在计算过程中被破坏掉,最后得到的答案也许是一个错误的答案。为了避免这种错误,我们提出了将启发式优化算法和DNA计算结合,采用新的手段来设计算法。在这篇论文中,我们将蚁群优化算法和DNA计算结合,来解决旅行商问题。即使正确的答案在处理的过程中被破坏掉,该正确答案在以后的处理过程总还会被构造,在过滤掉不合适的答案以后,我们利用控制变性I太原理工大学硕士研究生学位论文温度的
4、方法按比例放大经过过滤剩下的序列,并把放大的结果作为下次迭代的输入,相应的代表正确答案的DNA序列的浓度就会增加。在经过多次迭代之后,若结果趋于稳定,则认为剩下的序列即为问题的答案。论文的前两部分主要介绍生物学的基础知识、DNA计算的基本概念、基本模型和相关的著名实验,接下来介绍了启发式优化算法:蚁群优化算法;然后提出蚁群优化算法和DNA计算结合的构想与具体实现,同时详细介绍了算法处理过程;在文章的最后对提出的算法进行了总结,并对DNA计算的前景进行了展望。关键词:DNA计算,启发式优化方法,NP完全问题,序列抽取II太原理工
5、大学硕士研究生学位论文DNACOM口UTINGANDOPTI~ⅡZATIONOFTHEALGORITHMABSTRACTInformation-processingcapabilitiesoforganicmoleculescallbeusedincomputerstoreplacedigitalswitches;thisisthebasicideainDNAcomputing.Thereareobviouslimitstominiaturizationwithcurrentcomputertechnologies.Forad
6、rasticinnovation,itwassuggestedalreadyalongtimeagothatthebasiccomponentsshouldgotothemolecularlevel.Theresultwouldbemuchsmallerthananythingwecanmakewithpresenttechnology.QuantumcomputingandDNAcomputingaretworecentmanifestationsofthissuggestion.Thisworkis*boutthelatt
7、er.DNAcomputingarebasedontwofundamentalfeatures:(1)ThemassiveparallelismofDNAstrands;(2)Watson-Crickcomplementarity.Classictheoreticalcomputerscienceisgroundedonrewritingoperations;thisistmeformostautomataandlanguagetheorymodels.Asweshallsee,naturemanipulatestheDNAm
8、oleculesinacomputingmannerbyusingoperationsofaquitedifferenttype:cutandpaste,adjoining,insertion,deletion,etc.Ithasbeenprovedthatbyusingsu
此文档下载收益归作者所有