试论dna计算及其算法优化

试论dna计算及其算法优化

ID:34809453

大小:1.21 MB

页数:42页

时间:2019-03-11

试论dna计算及其算法优化_第1页
试论dna计算及其算法优化_第2页
试论dna计算及其算法优化_第3页
试论dna计算及其算法优化_第4页
试论dna计算及其算法优化_第5页
资源描述:

《试论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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。