遗传多目标优化算法的研究

论文摘要

多目标优化问题是一门新兴学科,起源于许多实际复杂系统的设计、建模和规划问题。由于遗传算法自身的进化本质,使其非常适合处理多目标优化问题,对Pareto最优前端的形状和连续性也不敏感,比传统方法可求解的复杂问题的数量大得多。遗传算法的基本特点是多方向和全局搜索,操作对象是一组个体,这种从种群到种群的方法,使得遗传多目标优化算法运行一次就能找到多目标优化问题的几个Pareto最优解,而传统优化方法可能需要进行很多次的运算才能达到这样的效果,因此遗传多目标优化算法在寻找有良好的收敛性和分布性的Pareto最优解时十分有效,也是一种行之有效的求解多目标优化问题的方法。1984年Schaffer提出的VEGA,该算法只是在简单遗传算法的基础上加上一个循环机制,针对每个目标函数来进行遗传操作,并产生最终结果。随后在Goldberg提出的Pareto排序思想上产生了MOGA （Fonseca和Fleming,1993）, NPGA（Nafpliotis和Horn,1994）和NSGA （Srinivas和Deb,2000）等算法。MOGA算法依据个体的次序值来进行排序,并分配不同的适应值,相同的次序则有相同的适应值,较好地保存了较优个体。NPGA算法采用了二进制竞争选择机制,使得随机抽出的个体可以跟比较集进行比较来进行优胜劣汰。NSGA算法则是先将种群进行分类,依次分配的适应值。随后引入了精英保留机制（Elitism）,产生了SPEA（Zitzler和Thiele,1999）, SPEA2 （Zitzler et al.2001）,PESA（Corne et al.2000）和NSGA2 （Deb et al.2002）等算法。NSGA2算法就是在NSGA算法的基础上引入了一个外部种群,在实际操作中需确定其次序值,还需计算个体的拥挤距离。SPEA算法其个体的适应值由个体与外部种群间的支配关系决定,再采用二进制竞争选择机制来选择个体,具有较小适应值的个体更优。SPEA2算法改进了SPEA算法的适应值分配机制,引入了一个最小邻居密度估计机制来对搜索过程作更准确的引导,同时引入新的档案截断方法来保证了边缘解的保存。PESA算法最大的特点是采用hyper-box来保持种群的多样性,采用挤压因子来完成选择和EP种群更新机制,有利于保留Pareto最优前端中位于稀疏区域的个体,维持了较好的种群多样性。本文主要从试验的角度出发,针对文中提到的8个不同的算法进行全面的综合比较。选取几个特定的应用比较广泛的测试函数,比较各个算法的收敛速率,种群的多样性等性能,再从中吸取各算法的长处,最终提出一个在性能方面有所改进的遗传多目标优化算法。

论文目录

• 摘要
• Abstract
• 第1章 选题背景和意义
• 1.1 选题背景
• 1.2 选题意义
• 第2章 研究现状
• 第3章 遗传多目标优化算法
• 3.1 多目标优化问题
• 3.2 适应值共享
• 3.3 向量评估遗传算法（VEGA）
• 3.4 遗传多目标优化算法（MOGA）
• 3.5 小生境Pareto遗传算法（NPGA）
• 3.6 非支配排序遗传算法（NSGA）
• 3.7 NSGA2
• 3.8 强度Pareto进化算法（SPEA）
• 3.9 SPEA2
• 3.10 基于封套Pareto选择算法（PESA）
• 第4章 实验分析
• 4.1 测试函数
• 4.2 测试结果及分析
• 4.2.1 收敛性评价方法
• 4.2.2 分布度评价方法
• 4.2.3 运行效率比较
• 4.2.4 测试结果分析
• 第5章 算法改进
• 第6章 结果与展望
• 6.1 论文主要完成的工作
• 6.2 论文有待进一步研究的问题
• 致谢
• 参考文献
• 附录