基于遗传算法的优化研究

论文摘要

自1960年以来,人们对于模拟生物进化行为以及由此开发的针对复杂优化问题的有效算法产生了浓厚的兴趣。遗传算法作为一种强有力的随机搜索和优化方法,广泛应用于工业工程优化领域并产生了深远影响。旅行商问题(TSP)是一个典型的组合优化问题,求解起来非常困难,常被作为遗传算法的应用测试实例。然而以往研究很少考虑到它的动态属性,一旦将它置于一个动态环境,现存的算法将不再适用。近年来,动态旅行商问题(DTSP)越来越吸引广大研究者的注意力,DTSP的研究也有着非常重要的实际意义。优化领域还存在一类更加复杂的优化问题,这类问题需要处理多个目标并且这些目标常常是相互冲突的。简单地将多个目标通过加权处理转换为单目标问题远不能满足决策者的要求,因此设计求解多目标优化问题的有效算法是非常有现实意义的。遗传算法在多目标优化方面也体现着它的魅力并获得了广泛应用。本文主要针对基于遗传算法的优化问题进行研究,具体说来,包括TSP求解和多目标优化两个方面。对于TSP求解,本文主要做了下面的研究工作:1、对反序杂交算子进行改进。考虑到反序操作的高度随机性,重组过程最终并不一定能得到比上一代更有优势的个体。为此我们将最优保留机制应用到反序杂交算子中,称为记忆机制,用于保留当次反序过程中出现的最好的基因序列,进而一步一步逼近最优解。实验表明我们的改进算子能在加快收敛速度的同时和提高解的质量。2、对于一类动态环境下的旅行商问题建模和求解。对生活中出现的上下班高峰期交通阻塞的城市交通情况进行高斯建模,使得随机被阻塞的边的数目在遗传算法进化中期达到最大。进而设计了该环境下的响应算法,该算法能利用已有最优路径中未被破坏的短边对动态变化情况做出快速反应。同时为了使算法更有效,我们将改进的反序杂交算子用于优化中。实验表明算法对解这一类动态旅行商问题很有效。本文在多目标优化方面的主要研究工作有两点:1、提出用庄家法则来构造非支配集。在多目标遗传算法中,构造非支配集的时间耗费是非常大的,而这种耗费主要用于个体比较。庄家法则不同于已有构造非支配集的方法,它做为一种非回朔方法可以有效减少个体比较次数,从而提高算法效率。2、提出了基于密度的多目标遗传算法(DMOGA)。对多种算法进行分析发现,密度是维护种群分布性的一个非常重要的因素。DMOGA考虑整个种群个体之间的影响,用于计算个体密度,准确反映外部集的分布情况,得到一个时间复杂度为O(n2)的优秀的分布性保持方法。并且为了提高算法效率,DMOGA采用庄家法则来构造非支配集。实验表明DMOGA能得到很好的分布性的同时拥有较高的运行效率。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 遗传优化概述
• 1.1.1 组合优化问题概述
• 1.1.2 多目标优化问题概述
• 1.2 遗传算法概述
• 1.3 多目标遗传算法概述
• 1.4 本文的工作
• 1.5 本文的组织结构
• 第二章 遗传算法求解旅行商问题
• 2.1 TSP 问题的数学定义
• 2.2 TSP 求解算法的研究概况
• 2.3 反序杂交算子的改进算法
• 2.3.1 反序杂交算子介绍
• 2.3.2 改进的反序杂交算子
• 2.4 实验结果
• 第三章 基于遗传算法的动态TSP 模型及其求解
• 3.1 动态TSP 概述
• 3.2 一种新的动态TSP 模型及其求解
• 3.2.1 添加高斯扰动的DTSP 模型
• 3.2.2 针对新模型的求解
• 3.3 实验结果
• 3.3.1 扰动模型模拟
• 3.3.2 变化前后最优解差值比对
• 第四章 基于密度的多目标遗传算法
• 4.1 多目标遗传算法的研究概况
• 4.2 几种典型的多目标遗传算法
• 4.2.1 NSGA-II 算法
• 4.2.2 SPEA2 算法
• 4.2.3 PESA-II 算法
• 4.3 基于密度的多目标遗传算法基本流程
• 4.4 庄家法则构造非支配集
• 4.4.1 用庄家法则构造非支配集的方法
• 4.4.2 正确性论证
• 4.4.3 时间复杂度分析
• 4.5 个体适应度计算
• 4.6 繁殖选择
• 4.7 实验结果
• 4.7.1 在测试函数 DTLZ1 上的实验结果
• 4.7.2 在测试函数 DTLZ2 上的实验结果
• 总结与展望
• 参考文献
• 致谢
• 附录A （攻读硕士学位期间已公开发表的论文）