论文部分内容阅读
高维多目标优化问题指目标数量大于3的多目标优化问题。随着问题中目标数目的增多,多目标优化问题往往变得难以求解。近年来,利用以进化算法为主的智能算法来解决高维多目标优化问题已得到越来越多研究者的关注。针对当前高维多目标优化算法中的若干难题,本文从算法的效率和性能两个角度出发,提出了新型的非支配排序算法与高维多目标进化算法,具体内容包括:首先,本文提出了一种高效的非支配排序算法框架ENS。在ENS中每个待排序的个体仅需要和已排序的个体进行比较,因此可以在非支配排序操作中避免大量不必要的非支配比较。在此框架的基础上,提出了两种采用不同搜索策略的非支配排序算法ENS-SS和ENS-BS。理论分析和实验结果均证实,这两种非支配排序算法能够大幅度地提升多目标优化算法的执行效率。其次,本文提出了一种适用于高维多目标优化问题的非支配排序算法T-ENS。传统的非支配排序算法通常需要对同一前沿面的每两个个体均进行非支配比较,而T-ENS中采用的树形存储结构使得它无需对同一前沿面中的每对个体进行比较。因此,在同一前沿面中个体数量较多的高维多目标优化问题中,T-ENS能够大幅减少非支配比较的次数,从而可以有效地提高高维多目标优化算法的效率。接着,本文提出了一种同样适用于高维多目标问题的非支配近似排序算法A-ENS.与其它非支配排序算法不同的是,A-ENS无需对个体间进行非支配比较,取而代之的是直接估计个体间的支配关系。A-ENS的这种估计策略使得判断两个个体间支配关系的时间复杂度由O(M)降为了O(1),其中M为目标数。理论分析和实验结果均证明,结合了A-ENS的高维多目标优化算法有着更高的执行效率,同时算法的性能也有一定的提升。最后,为了克服高维多目标问题上非支配排序策略的选择压力不足的问题,本文提出了一种基于knee point的高维多目标进化算法KnEA。 Knee points是前沿面上具有更好收敛性的一些个体,本文所提出的KnEA通过一种自适应的方法识别出种群中的knee points,并在交配池选择和环境选择操作中优先考虑它们,从而提升环境选择压力。与多个目前主流的高维多目标进化算法的对比实验证明,KnEA能够更加有效地解决高维多目标优化问题。