基于CPU+GPU异构计算的高维多目标支配方法

摘要

针对高维多目标优化问题，基于帕累托支配的算法随着优化目标数的增多，解集中绝大部分解都会成为非支配解，进而导致选择压力的损失的问题。前期工作中提出一种线性权重支配关系LWM可以解决传统帕累托支配关系在处理高维多目标优化中的选择压力问题，但由于求解LWM支配关系中的非支配解过程是一个线性规划问题，需要额外的时间开销，计算时间长、效率低。并行化是一种通用提高算法效率的方式，而GPU并行相较于CPU有低成本、高功效特点，被本课题所采用。
　　本课题分析了LWM支配算法在求解高维多目标优化问题中的时间耗费情况，结合GPU并行计算优势，提出了一种CPU+GPU异构计算的LWM支配关系，有效地改进了LWM支配关系的实用性。针对求解LWM非支配解过程中存在的误差累积问题，在GPU端采用高精度浮点数运算，确保串行算法和并行算法结果一致。通过一组基于随机分布均匀数据实验验证，结果表明两者最终结果差异不显著。本课题进一步分析了算法在各个目标中加速效率，显示随着目标数的增多，并行算法加速比增大。在算法应用范围的研究中，通过两个优化目标基准程序实验，在一些基准程序中LWM收敛过窄缺少解的均匀分布，所以LWM支配算法并不完全适用于求解两目标优化问题。课题进一步通过DTLZ多目标基准程序实验表明，LWM支配算法适合于求解5-15个优化目标的多目标优化问题，并且随着目标数的增大，并行算法优化效率越高。
　　在研究删与多目标演化算法的结合方式中，本课题提出两种结合方式，LWM-GA是使用删支配关系更换现有NSGA-Ⅱ中的Pareto支配实现对高维多目标优化问题求解中。另一种是NSGA-Ⅲ+LWM，即使用NSGA-Ⅲ求解高维多目标优化问题，再使用LWM支配关系对解集优化。
　　为比较LWM-GA和NSGA-Ⅲ+LWM方法性能，本课题以HyperVolume作为多目标演化方法评价指标。实验结果表明NSGA-Ⅲ和LWM-GA方法所得到的解集分布和收敛是一致的。同时在NSGA-Ⅲ与NSGA-Ⅲ+LWM方式对比中，实验结果表明LWM支配关系可以在保持解集分布的前提下，进一步约减NSGA-Ⅲ所生成的非支配解，NSGA-Ⅲ+LWM方式更能快捷地帮助决策者选取最优解。

目录

声明

摘要

第一章 绪论

1．1 课题研究背景及意义

1．2 研究现状

1．2．1 高维多目标支配算法

1．2．2 基于CPU+GPU异构计算多目标演化算法

1．3 课题主要研究内容

1．4 本文组织结构

第二章 GPU并行计算与高维多目标优化

2．1 高维多目标优化问题

2．2 GPU并行计算

2．3 高维多目标演化算法

2．4 本章小结

第三章 基于CPU+GPU异构计算LWM支配关系

3．1 LWM支配关系

3．2 并行LWM支配关系

3．2．1 任务划分

3．2．2 算法耗时步骤分析

3．3 本章小结

第四章 并行LWM支配关系应用

4．1 LWM-GA方法

4．2 NSGA-Ⅲ+LWM方法

4．3 MOEA性能评价

4．4 本章小结

第五章 实验设计与结果分析

5．1 实验验证方法

5．2 研究问题

5．3 实验设置

5．4 实验结果及分析

5．4．1 基于随机分布均匀数据实验结果及分析

5．4．2 蹑优化目标基准程序实验结果及分析

5．4．3 DTLZ系列基准程序实验结果及分析

5．4．4 两种结合方式性能评价实验结果及分析

5．5 本章小结

第六章 结论与展望

6．1 结论

6．2 展望

参考文献

致谢

作者与导师简介