分子优化算法及其应用模型的研究

《分子优化算法及其应用模型的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆大学硕士学位论文中文摘要摘要近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉、相互渗透和相互促进。随着计算机技术和分子生物技术的迅速发展，DNA计算作为一种新兴的交叉学科已经成为当今研究的热点。DNA计算是一种以生物分子DNA作为计算介质，以生物化学反应作为计算工具的一种新型计算方法。DNA计算的优点主要在于DNA分子具有高度的并行性，其次是DNA计算有很高的能量效率和存贮容量。因此，DNA计算在求解自然界大量存在的需用穷举搜索方法求解的复杂问题上具有经典数字计算机所无法比拟的天然优势，在解决大规模并行计算问题上，特别是在解决NP．完全问题上有着不可估

2、量的优势。本文首先介绍了DNA计算产生的生物背景、发展现状、DNA计算的数学理论、生物学基础以及DNA计算的机理，介绍了DNA分子的一些基本操作，对近年来有关DNA计算的研究成果进行了综述。同时作为一种生物计算技术，DNA计算与遗传算法有着许多共同之处，在探索了各种进化算法和DNA计算之间的关系后，发现遗传算法尤其适合于采用DNA分子来实现，分析了关于DNA计算与遗传算法相结合的构想与具体实现，同时详细介绍了DNA遗传算法的结构、遗传操作算子及其求解优化问题的实现步骤。最后建立了2个基于DNA-GA的应用实例。M．TSP问题的DNA遗传算法模型：多人旅行商问题是一个实

3、际应用背景很强的数学模型，该问题已被证明属于NP．完全问题，以前对于多人旅行商问题的研究多采用近似算法、遗传算法、蚁群算法等，都取得了一定的研究成果。本文在前人工作基础上提出了该问题的DNA-GA模型。对图的顶点用长度为20的寡聚核苷酸片段表示，同时将边的权值也转换成长度为20的寡聚核苷酸片段，然后模拟生物化学反应操作，经过DNA计算超大的并行计算找到闯题的解。结果证实，该算法是一种求解M．TSP问题的有效算法，具有较好的性能，还可以保证一定的实时性。三维空间路径规划问题的应用模型：提出了一种求解空间机器人路径规划的DNA-GA算法。该算法首先将机器人当前所在的位置与

4、将要到达的位置之间的空间划分成立体网格，同时定义了源点与目的点之间的有效路径。对每个小立方体网格的顶点以及可连接的点与点之问的距离采用DNA编码，然后在这种编码方法的基础上进行遗传操作来得到问题的解。实验结果表明，该算法不仅有效，而且具有极快的速度。在该算法中，网格的稠密程度决定了算法解的精度，即网格越重庆大学硕士学位论文中文摘要稠密，算法的精度越高，但编码更困难，所需时间也越长；反之则精度越低，所花时间越短。最后对全文的研究工作进行了总结，并展望了DNA遗传算法在理论和应用方面进一步研究的课题。关键词：DNA算法遗传算法DNA编码多人旅行商问题机器人路径规划Ⅱ重庆大

5、学硕士学位论文英文摘要ABS7rRACTAnoverlapbetweenlifesciencesandengl+neeringisvividcharacteristicofdevelopmentofmodernscienceandtechnology．Withthefastdevelopmentofcomputerandbiotcchaology,DNAcomputing,asanovelCI"OSSsubject，developsveryquicklyintheorytheseyears．DNAcomputingisanewcalculationmethodthat

6、usedbiolcIgicalmoleculeDNAascalculationmediumandbiochemicalreactionascalculationt001．Theadvantagesalethemassiveparallelism，high-densitystorageandenergyefficiency．Generallyconsidering,althoughtheabilityoftheclassicaldigitalcomputerisunassailablewhenitexecutesserialtask,DNAcomputingshowsn

7、aturaladvantagecomparedwiththeclassicaldigitalcomputerinsolvingtheproblenlsthatallpossiblesolutionshouldbeverifiedwhichexisteverywhere．Whenusedtosolvetheparallelprocessinginlarge-sizecomputing,itisoftremendousadvantages．Initially,thispaperintroducedthebiologicalbackgroundofDNAc