高维多目标动力学演化算法及在GPU上的实现

论文摘要

在实际工程优化问题中,大多数多目标优化问题的目标个数往往多于3个,通常这样的问题称为高维多目标优化问题。高维多目标优化问题的难点在于经典的Pareto占优策略在目标数目增加时个体间相互不支配的概率增加,使得种群的选择压力被严重弱化,从而导致算法的收敛过程缓慢甚至停滞。于是,多目标演化算法就退化成一个完全随机的搜索算法了。同时由于Pareto占优没有考虑到决策者的偏好,算法的收敛方向无法获得决策者的指导,进而得到的非劣解集对于决策者的决策支持能力降低,使得算法的性能急剧下降。因此求解高维多目标优化问题已成为多目标演化算法研究领域的前沿和热点。在传统动力学演化算法中,种群的个体被理解为相空间中的粒子,每一代的种群被理解为一个粒子系统。模拟粒子相空间的粒子系统原理进行种群的交叉、变异等演化操作,使得该粒子系统从非平衡状态达到平衡状态。传统算法采用计算粒子Rank函数值的排序方法,以保持相空间（种群）中粒子（个体）分布的多样性和均匀性以及达到粒子与粒子之间可进行比较的唯一性。此类算法对于2-3维多目标优化问题能够较好地收敛到Pareto前沿,但对于4维以上的高维多目标优化问题,却很难收敛到Pareto前沿,甚至出现早熟现象,多样性也较差。原因在于：（1）随着目标维数的增加个体间相互不支配的概率增加,这使得算法的收敛过程缓慢。（2）搜索效率不高,特别是在求解高维函数优化问题时收敛速度明显较慢。（3）动力学多目标演化优化算法中,个体选择时,往往要么采用精英选择策略,要么采用随机选择策略。此将使算法要么出现过早收敛;要么使收敛速度变慢。（4）在动力学演化算法中,个体Rank值的计算量随着种群规模的增大而增大；同时在按Rank值对种群进行排序时,所用时间也在增加。基于以上分析,本论文进行了占优机制、变异策略和选择策略等方面的深入研究及针对以上不足做了进一步的改进,并将改进的算法在GPU平台上并行实现,以期更好地适应高维多目标优化问题的求解。同时,针对高维多目标优化问题中,近似Pareto前沿的可视化问题进行了研究,尝试将决策图法应用于本文算法求得的近似Pareto前沿的可视化中。本文主要研究内容和创新点如下：（1）针对传统的动力学多目标演化算法中Pareto占优策略在目标维度增加时个体间相互不支配的概率增加、算法收敛过程缓慢的缺点,提出了EDAGEA算法。该算法采用了一种宽松的Pareto占优机制,即E-占优策略,在一定程度上使得多目标演化算法在高维多目标优化问题的求解过程中,种群中的个体拥有足够的选择压力,且在计算Rank值时,E占优方法与自由能和熵的计算融合,有效地提高了算法的收敛效率。同时自适应网格的方法在一定程度上保证了演化群体的分布性。实验结果表明,对于3至8个目标的DTLZ1、DTLZ2、DTLZ4、DTLZ6和DTLZ7测试问题,该算法相比HN和MOPSO算法很好地保持了所得最优解在Pareto前沿上分布的宽广性、均匀性以及较好的收敛性。（2）针对传统的动力学多目标演化算法搜索效率不高的缺点,提出了MODDEA算法。该算法采用了搜索效率更高的差分变异算子,以适应高维多目标优化问题,同时为了避免在求解全局优化问题时出现局部收敛或很难求解出全局最优解的问题,对传统差分变异算子进行改进,保证在演化过程中,前期进行全局搜索,后期进行局部搜索,从而保证算法既有较强的全局搜索能力又有较快的收敛速度和搜索精度。同时传统动力学多目标演化优化算法中在计算Rank值时通过粒子自由能和熵的计算保持了种群的多样性。实验结果表明,对于3至8个目标的DTLZ2、DTLZ3、 DTLZ5和DTLZ7测试问题,MODDEA算法相比HN、MOPSO算法在保持分布的均匀性的同时,又具有较强的收敛能力和保持多样性的能力。（3）针对传统动力学多目标演化优化算法中,在对个体进行选择时,往往采用精英选择策略,或者采用随机选择策略,使得算法过早收敛,或者收敛速度过缓的缺点,提出了CTSDEA算法。该算法采用类锦标赛选择策略以使群体保持足够的多样性,同时进行M个个体的选择时,M取值选取采用从大到小变化的策略以提高算法的搜索效率,另外计算粒子Rank函数值的排序方法保持了种群中粒子分布的均匀性。实验结果表明,对于DTLZ1、DTLZ2、DTLZ4、DTLZ5和DTLZ7测试问题,CTSDEA算法相比HN、MOPSO算法在保持最优解在Pareto前沿上分布多样性的同时,又具有了较强的全局搜索能力、保持分布均匀性的能力以及良好的收敛能力。（4）对于高维多目标演化算法来说,算法的计算时间复杂度与所求解的问题的相关的。它随着问题规模的增大而显著增长,解决此问题的主要方案之一是并行化,GPU的高速度、并行计算和可编程功能为通用计算提供了良好的并行计算平台。以探索GPU大规模并行通用计算的运用模式为目标,提出了GPU-EDAGEA、 GPU-MODDEA和GPU-CTSDEA三种算法。针对高维多目标优化中的DTLZ1-7测试函数进行了性能和加速比对比实验。实验结果表明,基于GPU的三种改进算法在尽可能的保持收敛性、均匀性和多样性前提下,大大加快了算法的运行速度。在最大化使用GPU硬件资源的情况下,对于DTLZ2、DTLZ4和DTLZ6测试问题,GPU-EDAGEA算法的优化结果达到了14-22倍的加速比,对于DTLZ3和DTLZ5测试问题,GPU-MODDEA算法的优化结果达到了18-27倍的加速比。对于DTLZ1和DTLZ7测试问题,GPU-CTSDEA算法的优化结果达到了16-24倍的加速比。且目标维数越大,算法的加速比相对就越大。（5）采用决策图法实现了高维多目标优化问题中对近似Pareto前沿的可视化,以色彩鲜艳的图形和滚动条的移动滑块控制直观地展示了所求得的近似Pareto前沿。从图形上也更直观地了解了改进的高维多目标动力学演化算法的性能。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.2.1 演化多目标优化算法研究现状
• 1.2.2 GPU高性能计算的研究现状
• 1.3 主要研究内容
• 1.4 本文的组织结构
• 第二章 传统高维多目标演化优化算法与可编程图形处理器
• 2.1 传统高维多目标演化优化算法
• 2.1.1 混合NSGA-Ⅱ算法
• 2.1.2 多目标粒子群优化算法
• 2.1.3 粒子动力学多目标演化优化算法
• 2.2 可编程图形处理器GPU
• 2.2.1 CPU与GPU结构比较
• 2.2.2 基于GPU的通用计算
• 2.2.3 CUDA编程模型
• 2.2.4 CUDA存储器模型
• 2.3 本章小结
• 第三章 改进的高维多目标动力学演化优化算法
• 3.1 传统多目标动力学演化优化算法的不足分析
• 3.2 高维多目标演化优化算法的性能度量
• 3.2.1 高维多目标演化优化算法测试函数
• 3.2.2 高维多目标演化优化算法性能评价指标
• 3.2.3 近似Pareto前沿的可视化
• 3.3 高维多目标自适应网格E占优动力学演化算法
• 3.3.1 新型占优机制研究
• 3.3.2 E-占优机制
• 3.3.3 自适应网格技术
• 3.3.4 高维多目标自适应网格E占优动力学演化算法
• 3.3.5 实验结果
• 3.3.6 近似Pareto前沿的可视化
• 3.4 高维多目标动力学差分演化算法
• 3.4.1 差分演化变异算子
• 3.4.2 高维多目标动力学差分演化算法
• 3.4.3 实验结果
• 3.4.4 近似Pareto前沿的可视化
• 3.5 高维多目标类锦标赛选择动力学演化算法
• 3.5.1 基于类锦标赛选择的高维多目标动力学演化算法
• 3.5.2 实验结果
• 3.5.3 近似Pareto前沿的可视化
• 3.6 本章小结
• 第四章 改进的高维多目标动力学演化算法在GPU上的并行实现
• 4.1 引言
• 4.2 基于GPU的高维多目标自适应网格E占优动力学演化算法
• 4.2.1 数据的存储
• 4.2.2 算法描述
• 4.2.3 数值实验
• 4.3 基于GPU的高维多目标动力学差分演化算法
• 4.3.1 数据的存储
• 4.3.2 算法描述
• 4.3.3 数值实验
• 4.4 基于GPU的高维多目标类锦标赛选择动力学演化算法
• 4.4.1 算法描述
• 4.4.2 数值实验
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 主要研究成果及创新
• 5.2 研究工作展望
• 参考文献
• 作者在攻读博士学位期间发表的有关学术论文
• 致谢