基于多样性保持的多目标优化算法的研究

摘要

不同于单目标优化算法最终优化的结果只有一个最优解，多目标优化算法存在着表示目标间权衡信息的解的集合(在目标域上一般称为Pareto前沿)。多目标优化一般从两个方面评价获取的解集的优劣。第一是收敛性，即解集离真实的Pareto前沿的距离，距离越小表明得到的解集越能更好地近似Pareto前沿。第二是多样性，是指解集的多样化程度。多样性越高表明这组解所携带的信息量越大，越有利于最优决策。 本文围绕着解集的多样性问题，主要研究工作包含以下两个部分： 1.基于现有的多样性度量指标的优缺点，对于超多目标优化问题提出了一种基于参考向量的多样性指标（DIR）。具体过程如下：首先生成一组分布均匀且广泛的参考向量，然后计算每个解占有的参考向量的数目，用这些数目的方差值来表示多样性，方差越小多样性越好，否则越差。将该指标应用于人工生成的解集和算法运行得到的解集上，均能较为准确地反映解集的多样性性能。基于DIR，本文进一步提出了一种超多目标优化算法（d-NSGA-Ⅱ）。在主流的测试问题集上与其他算法的实验比较，表明d-NSGA-Ⅱ总体性能优于其他算法。同时，d-NSGA-Ⅱ被应用于车辆碰撞可靠性设计和汽车侧面碰撞安全性设计两个实际工程优化问题上，也表现出了优异的性能。 2.组合多目标优化问题面临更大的多样性保持的困难。为此，本文提出了一种基于格子加权支配（gws-dominance）的多样性保持策略来保持种群多样性。在格子系统中，每个格子最多只能保持一个解。格子之间的解通过格子强支配关系来选择，同一格子内的解使用格子加权值来选择。格子加权支配被嵌入到一个经典的Pareto局部搜索算法（PLS）。与原始的PLS的实验对比显示，GWS-PLS能够极大地提高PLS的搜索效率，改善PLS算法的时间和空间复杂度；同时多样性和收敛性也优于PLS。在多目标旅行商问题（MOTSP）和多目标背包问题（MOKP）问题上，将其与三种基于分解的Pareto局部搜索算法（MOEA/D-LS（WS，TCH，PBI）），一种基于格子的Pareto局部搜索算法（?-MOEA），和一种最新的混合算法（MOMAD）进行了对比，实验结果表明GWS-PLS在目标个数的可拓展性，收敛性和多样性上均优于其它算法。

目录

中文封面

英文封面

承诺书

摘要

Abstract

目 录

图表目录

注释表

缩略词

第 1 章 绪论

1.1 引言

1.2 研究动机

1.3 本文主要贡献

1.4 论文结构

第 2 章 背景介绍

2.1 多目标优化问题

2.1.1 问题定义

2.1.2 相关概念

2.1.3 收敛性和多样性

2.2 性能评价指标

2.3 多目标优化算法

2.3.1 传统算法

2.3.2 演化多目标优化算法

2.3.3 局部搜索技术

2.4 测试问题

2.4.1 DTLZ 测试集

2.4.2 WFG 测试集

2.4.3 MOTSP 测试集

2.4.4 MOKP 测试集

2.5 本章小结

第 3 章 基于参考线的多样性度量指标

3.1 引言

3.2 多样性指标综述和 DIR 设计的动机

3.3 基于参考向量的多样性度量指标

3.3.1 整体框架

3.3.2 初始化参考线

3.3.3 计算每个解的覆盖度

3.3.4 计算 DIR

3.3.5 一个使用 DIR 的例子

3.3.6 DIR 的精确度讨论

3.3.7 DIR 的时间复杂度

3.4 实验分析

3.4.1 度量人工设置的 PF 近似解集

3.4.2 度量真实的 PF 近似解集

3.4.3 度量不规则 PF

3.4.4 参考线数量对 DIR 精确度的影响

3.5 基于 DIR 的演化多目标优化算法（d-NSGA-II）

3.5.1 将 DIR 嵌入 NSGA-II

3.5.2 实验设置

3.5.3 与 NSGA-II 和 NSGA-III 实验结果的对比

3.5.4 时间复杂度分析

3.5.5 d-NSGA-II 处理真实工程问题

3.6 本章小结

第 4 章 基于格子加权支配的局部搜索算法

4.1 引言

4.2 格子系统

4.3 格子加权支配

4.4 基于格子加权法的帕里托局部搜索算法

4.4.1 算法框架

4.4.2 初始化

4.4.3 局部搜索

4.4.4 更新

4.4.5 与 -MOEA 的对比

4.5 实验分析

4.5.1 实验设置

4.5.2 与 MOEA/D-LS (WS, TCH, PBI) 及 -MOEA 的实验结果的对比

4.5.3 与 PLS 和 MOMAD 实验结果的对比

4.5.4 格子加权法对算法结果的影响

4.6 本章小结

第 5 章 研究工作总结和展望

5.1 本文总结

5.2 研究展望

参考文献

致 谢

在学期间的研究成果及发表的学术论文