多目标进化算法中解集分布性能的研究

论文摘要

进化算法是基于模拟生物进化机制而发展起来的一类新的优化算法,因其具有简单、易操作、需求低、并行和全局性等特点,已经在非常广泛的领域中取得了成功应用。多目标进化算法擅长于求解高度复杂的非线性多目标优化问题,它能通过一次运行而得到优化问题的多个非支配解（解集）,再由决策者进行权衡选择。一个好的解集对于决策者作出正确有效的决策至关重要,因此,获得一个高质量的解集成为多目标进化算法设计者们追求的重要目标。解集的分布性能是解集质量的一个重要方面,理想的情况是,算法所得解集应该尽可能地靠近问题的真实Pareto最优边界,又要尽可能覆盖整个Pareto最优边界并且保持均匀的分布情况。本文针对多目标进化算法解集的分布性能开展研究,主要工作包括:第一,针对多目标进化算法中出现重复个体的现象进行研究,探讨了重复个体产生的原因。研究发现,输出解集中是否存在重复个体取决于算法所采用的个体适应度赋值方法和构造非支配集（归档集）时所使用的个体保存策略。通过实验得知,对于同一测试问题,采用二进制编码比采用实数编码实现的算法所产生的重复个体数目少很多;对于不同测试问题,决策变量维数是影响重复个体数目的主要因素,而目标维数的相应影响不大。另外,去除重复个体使得NSGA-II的稳定性更好,且所得解集的分布性较之原NSGA-II有较大改进。第二,指出ε-MOEA存在固有缺陷,即当优化问题的PFtrue对某一维的变化率在该维不同区域的差异较大时,解集中边界个体或代表性个体丢失,这对解集的分布性能有较大的影响。为了克服ε-MOEA的不足,本文定义了一种新的δ支配概念,并提出和使用虚拟“最优点”概念,设计了一种新的网格存优策略（δ-GS）。δ-GS允许“ε被支配”网格单元内符合一定条件的个体保存进入归档集;它保留了ε支配概念的优点,但是能避免ε-MOEA在PFtrue的边界附近和部分区域丢失重要个体的现象。“虚拟‘最优点’”集合了网格内以往优秀个体的信息,其使用保证了归档集种群不会发生退化。第三,我们将新的支配概念和δ-GS运用于多目标进化归档算法（δ-MOEA）。在δ-MOEA中,用基于δ支配概念的新网格存优策略δ-GS更新算法的归档种群,以使解集具有好的分布性能。通过一系列测试实验说明:δ-MOEA能克服NSGA-II和ε-MOEA的不足,获得的解集具有良好的分布性能。

论文目录

• 摘要
• Abstract
• 符号说明表
• 第1章 绪论
• 1.1 多目标进化算法概述
• 1.1.1 多目标优化的相关定义
• 1.1.2 Pareto 最优解集
• 1.1.3 多目标进化算法的基本框架
• 1.2 多目标进化算法的编码和算子
• 1.2.1 多目标优化的编码问题
• 1.2.2 多目标进化算法的算子
• 1.3 多目标进化算法的性能评价
• 1.3.1 概述
• 1.3.2 MOEA 性能评价方法
• 1.4 本文的工作
• 1.5 论文的组织结构
• 第2章 多目标进化算法中的重复个体研究
• 2.1 NSGA-II 算法
• 2.1.1 NSGA-II 概述
• 2.1.2 算法描述
• 2.1.3 算法流程分析
• 2.2 NSGA-II 中重复个体的研究
• 2.2.1 NSGA-II 中重复个体数目与编码方式的关系
• 2.2.2 NSGA-II 中重复个体产生原因分析
• 2.2.3 NSGA-II 中重复个体数目与优化问题的关系
• 2.2.4 重复个体对于算法搜索效率和解集分布性的影响
• 2.2.5 本节小结
• 2.3 其它多目标进化算法中的重复个体
• 第3章 δ支配概念和新的网格存优策略（δ-GS）
• 3.1 ε-MOEA 算法
• 3.1.1 ε-MOEA 算法概述
• 3.1.2 ε支配的相关概念
• 3.1.3 ε-MOEA 算法实现及流程分析
• 3.2 ε-MOEA 的不足
• 3.3 新的δ支配概念
• 3.4 虚拟“最优点”和新的网格存优策略（δ-GS）
• 第4章 基于δ-GS 的多目标进化算法δ-MOEA
• 4.1 δ-MOEA
• 4.2 实验及结果
• 4.2.1 实验环境及评价方法
• 4.2.2 测试函数及实验结果
• 4.3 小结与分析
• 第5章 总结与展望
• 5.1 本文的主要贡献
• 5.2 将来的工作
• 参考文献
• 致谢
• 附录A （攻读硕士学位期间公开发表的论文）