超多目标优化问题的高效算法研究

论文摘要

很多领域的实际应用问题都可建模成四个甚至更多目标的优化问题,这类问题称为超多目标优化问题,而两个和三个目标的优化问题称为多目标优化问题。与多目标优化问题相比,超多目标优化问题的求解更加困难。主要原因在于:1)随着目标个数的不断增加,Pareto最优解的数量呈指数级增长,而现有的支配方法选择压力往往不够,无法从大量的Pareto最优解集中高效地筛选出真正有潜力的代表解集;2)由于目标个数的增多,导致目标空间呈指数级增大,如何设计出高效的算法使其在庞大的目标空间中找出收敛性好、分布均匀且宽广的有限个代表解的集合是一个巨大挑战。本论文围绕这两个难点,研究和设计高效的超多目标进化算法来解决这两个难点问题。本文的主要工作和创新点如下:1.针对算法SPEA/R的适应度评价机制中局部收敛强度干扰全局收敛强度且其多样性度量无法区分具有相同参考向量方向角的解对多样性贡献大小的缺点,提出了一种适应于超多目标优化问题新的适应度评价机制。首先,设计了一种基于全局收敛强度的解的收敛性新度量,该度量可有效避免解的局部收敛强度对解的全局收敛强度的干扰,度量的收敛性更加合理客观。同时,设计了一种基于角度-距离的多样性度量新方法,该方法除能准确度量出具有不同方向角的解对多样性的贡献,而且还可以区分具有相同方向角的解对多样性的贡献。进一步,为了平衡收敛性度量和多样性度量在适应度评价机制里所占的比重,将收敛性度量和多样性度量归一化到同一数量级上。最后,结合归一化的收敛性度量和多样性度量设计了一个新的适应度评价机制。将SPEA/R采用了新的适应度评价机制的算法（记为ISPEA/R）与其他五个表现好的超多目标进化算法进行实验对比,结果表明ISPEA/R算法不仅克服了 SPEA/R的缺陷、降低其计算复杂度一个数量级,而且所求解集收敛性与多样性均较好。2.针对已有的支配方法在求解超多目标优化问题时选择压力不足、无法兼顾解的多样性的缺点,设计了一种基于扩展支配区域的新支配方法——Cα-支配方法。与已有扩大支配区域的支配方法利用线性函数变换不同,该支配方法将目标函数进行非线性变换,不仅使每个解的支配区域扩大来增加选择压力,还可去掉阻碍收敛的解,从而提高筛选出来的解集的收敛性并保持多样性。进一步,从理论上证明了Cα-支配方法比已有支配方法的优势。最后,将Cα-支配方法与四种已有效果好的支配方法分别用于NSGA-Ⅲ,在DTLZ测试集上进行了实验比较。结果表明,Cα-支配方法比对比的四种支配方法所得的解集具有更好的收敛性和多样性。3.为了提高超多目标优化算法的求解性能,首先设计了一种双向关联策略,与现有的关联方法不同,该关联策略在将种群和各个子空间进行关联后,进一步对空子空间进行了关联操作,将与空子空间最接近的解关联给这个空子空间,增加了搜索到空子空间解的概率。然后,提出了参数自适应调整的Cα-支配方法。该方法可根据目标数及进化代数对参数自适应调整。在此基础上,设计了一种同时评价收敛性和多样性的适应度评价机制。结合上述策略,设计了一种新的环境选择策略,它可选出兼具收敛性和多样性的新种群。最后,在这些技术基础上,提出了一种新的超多目标进化算法DSEA。大量的仿真实验表明,DSEA与对比的五种超多目标进化算法在收敛性和多样性方面有更大的优势。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 超多目标优化问题面临的困难
•   1.3 国内外的研究现状
•   1.4 论文的主要工作和组织结构
•   1.5 本章小结
• 第二章 基础知识
•   2.1 （超）多目标优化问题相关概念
•   2.2 性能指标
•   2.3 测试问题
•   2.4 参考向量的产生方法
•   2.5 本章小结
• 第三章 基于新的适应度评价机制的超多目标优化算法:ISPEA/R
•   3.1 引言
•   3.2 ISPEA/R算法描述
•     3.2.1 ISPEA/R算法的基本框架
•     3.2.2 解的关联操作
•     3.2.3 新的适应度评价机制
•     3.2.4 ISPEA/R和SPEA/R具体步骤的进一步讨论
•     3.2.5 ISPEA/R和SPEA/R的复杂度分析
•   3.3 实验研究
•     3.3.1 测试问题
•     3.3.2 对比算法简介
•     3.3.3 实验参数设置
•     3.3.4 在DTLZ测试集上的性能比较
•     3.3.5 在MaF测试集上的性能比较
•     3.3.6 在WFG测试集上的性能比较
•   3.4 本章小结
• 第四章 基于扩展支配区域的新支配方法
•   4.1 引言
•   4.2 扩展支配区域的新支配方法（Cα-支配）
•     4.2.1 α-支配方法简介
•     4.2.2 新支配方法:Cα-支配方法
•     4.2.3 Cα-支配方法的性质
•     4.2.4 Cα-支配方法与α-支配方法的对比分析
•   4.3 实验研究
•     4.3.1 测试问题
•     4.3.2 实验参数设置
•     4.3.3 实验结果与分析
•   4.4 本章小结
• 第五章 基于新支配方法的超多目标优化进化算法:DSEA
•   5.1 引言
•   5.2 DSEA算法描述
•     5.2.1 DSEA算法的基本框架
•     5.2.2 双向关联策略
•     5.2.3 自适应调整支配区域的支配方法
•     5.2.4 适应度评价机制
•     5.2.5 环境选择策略
•   5.3 算法DSEA的计算复杂度
•   5.4 实验设计
•     5.4.1 测试问题
•     5.4.2 对比算法简介
•     5.4.3 实验参数设置
•   5.5 不同策略和参数对性能的影响
•     5.5.1 三种不同的关联机制对算法性能的影响
•     5.5.2 采用Cα-支配方法度量解的收敛强度的有效性
•     5.5.3 Cα-支配方法中参数α的作用
•   5.6 六种算法在三个测试集上的性能比较
•     5.6.1 在DTLZ测试集上的性能比较
•     5.6.2 在WFG测试集上的性能比较
•     5.6.3 在MaF测试集上的性能比较
•   5.7 本章小结
• 第六章 总结和展望
•   6.1 工作总结
•   6.2 未来展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 博士论文

作者: 刘俊华

导师: 王宇平

关键词: 超多目标优化,适应度评价机制,扩展支配区域的支配方法,双向关联,环境选择策略

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安电子科技大学

分类号: O224

DOI: 10.27389/d.cnki.gxadu.2019.003199

总页数: 130

文件大小: 3431K

下载量: 96