基于分解排序的多目标进化算法的研究

摘要

由于基于种群的进化算法在单次运行中能近似出一个Pareto解集，因此多目标进化算法已成为一种较为普遍且有效的求解多目标优化问题的方法。本文将基于分解和排序的方法融入到多目标进化算法框架中以求解多目标优化问题。本文主要包括如下部分：
　　第一，基于分解的多目标进化算法（如MOEA/D）将一个多目标优化问题分解成一组单目标优化子问题，然后并行地求解它们。为了在进化过程中进一步平衡算法的收敛性和多样性，我们提出了一种新的解选择方法：首先通过解在各个子问题上的收敛性对它们进行整体排序，然后基于解之间的多样性进行二次选择。我们将该方法嵌入到基于分解的算法框架中并将它和三个经典多目标进化算法以及一个目前较好的多目标算法进行比较。实验结果表明所提出的算法非常具有竞争力。
　　第二，在MOEA/D及其变种算法中，每个子问题有且仅有一个解与之关联。隐含的假设为每个子问题对应一个不同的Pareto最优解。这种假设对于一些特殊的多目标优化问题（如具有分段的不完整的Pareto前沿的问题）并不成立。为了进一步拓展基于分解的多目标进化算法，在本文提出的算法（MOEA/D-SAS）中，不同的解可被关联到相同的子问题，一些子问题甚至可以没有解与之关联。同时，不同于其它算法，本文使用了基于分解的排序（DBS）和基于角度的选择（ABS）来平衡算法的收敛性和多样性。为了减少算法的计算复杂度，DBS仅对子问题的局部邻居解进行排序；ABS利用解在目标空间域的角度信息来维持一个更加细化（fine-grained）的多样性。实验表明MOEA/D-SAS能够同时保持良好的收敛性和多样性，特别是对于特殊的多目标优化问题（如具有不连续且不完整的Pareto前沿）更为有效。此外，我们对DBS的计算效率和ABS的作用也进行了详细分析和讨论。

目录

封面

声明

中文摘要

英文摘要

目录

注释表

缩略词

第一章 绪论

1.1 研究背景

1.2 研究进展

1.3 本文主要研究内容

1.4 本文各章节组织安排

第二章 多目标进化算法简述

2.1 多目标优化相关概念

2.2 多目标进化算法分类

2.3 性能度量指标与测试问题

第三章 基于排序选择的多目标进化算法

3.1 引言

3.2 动机

3.3 算法设计

3.4 实验设计与结果分析

3.5 小结

第四章 基于分解排序和角度选择的多目标进化算法

4.1 引言

4.2 动机

4.3 解选择方法

4.4 算法设计

4.5 实验设计与结果分析

4.6 MOEA/D-SBS与MOEA/D-SAS的比较

4.7 小结

第五章 研究工作总结与展望

5.1 研究总结

5.2 研究展望

参考文献

致谢

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