混合DNA遗传算法及其在组合优化中的应用

作     者：闻玉刚 

作者单位：辽宁科技大学 

学位级别：硕士

导师姓名：王莉

授予年度：2013年

学科分类：0710[理学-生物学] 12[管理学] 071010[理学-生物化学与分子生物学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081704[工学-应用化学] 07[理学] 081104[工学-模式识别与智能系统] 08[工学] 0817[工学-化学工程与技术] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：遗传算法 DNA计算 新型交叉变异算子 混合DNA遗传算法 组合优化 

摘      要：DNA计算是以DNA分子结构为基础，应用现代的生物实验技术，以遗传物质DNA和各种酶为主要的计算工具，应用生物手段来解决实际问题，但是该技术目前仍处于实验研究阶段，还有很多问题需要解决。遗传算法是模拟生物进化而提出的一种全新的全局优化搜索算法，并具有不受空间限制和不依赖与问题的具体领域，对问题具有很强的鲁棒特性，还具有并行性等特性，这些特性决定了其能在许多领域广泛应用。但是其仍具有局部搜索能力弱和容易早熟收敛等缺点。近年来，随着DNA计算的发展，人们发现DNA计算和遗传算法之间的相似性，将其进行结合更加有利于克服了遗传算法的诸多缺点并将其优点更加的突出增强和发展功能更加强大、能解决更加复杂问题的智能方法。本文受生物的DNA分子结构和遗传信息遗传过程的影响，提出了基于DNA编码方法的DNA遗传算法，并将其用于解决优化设计的问题进行了研究。主要的研究工作如下： （1）受DNA分子操作中染色体基因交叉突变和DNA遗传信息的表达过程的影响，本文提出了移位、对换和抽换三种新型的交叉算子，并基于碱基的编码方式提出了反密码子最大最小变异算子。通过交叉和变异操作，得到适应度值更高的个体。测试函数表明新的算子可以改善种群的多样性、减少寻优代数并且增强了算法的收敛速度、增强了算法克服问题欺骗造成早熟的能力，进一步提高了算法的性能。 （2）将具有新型算子的DNA计算与遗传算法相混合，提出了一种混合的DNA遗传算法，并将其应用在近年来频发的地质灾害中紧急救援物资发放的组合优化问题中典型的MTSP问题中。结果表明，该种新的混合DNA遗传算法对解决紧急救援物资发放的MTSP问题具有优异的结果。