基于拐点和区域划分的高维多目标进化算法

杨景明，郝佳佳，孙 浩，魏之慧，李霞霞

（燕山大学 电气工程学院，河北 秦皇岛 066004）

1 引言

在科学研究和实际问题中常常需要同时优化多个相互冲突的目标，这类问题被称为多目标优化问题（multi-objective optimization problems，MOPs）［1］。而常规方法在求解目标个数大于3的问题（即MaOPs）时，种群的非支配解随目标数呈指数级增加，选择压力急剧下降，算法处于停滞状态［2］；同时目标空间增大，Pareto前沿更加复杂，算法的收敛性和分布性难以同时保持。

目前，研究人员已经提出许多解决MaOPs的算法，大致可以分为3类：1）基于Pareto支配。这种方法需要引入新的机制来增强选择压力。例如，网格支配［3］通过自适应网格结构增加了选择压力，模糊支配［4］在Pareto支配的基础上引入了模糊的概念来选解，此外还有ε-MOEA［5］、KnEA［6］等。这类算法的收敛性一般比较好，缺点是常常需要引入一些参数，参数的确定比较困难。2）基于分解。该方法将多目标问题分解为若干个单目标子问题，然后对这些子问题进行同步优化和协同优化。经典的有MOEA／DD［7］、参考向量引导的进化算法RVEA［8］等。这类算法的收敛和分布效果受权重分布影响，因而面对退化、不连续或真实PF面不规则的问题时效果不佳。3）基于性能指标。算法在环境选择过程中采用个体的性能指标值选择个体。例如超体积算法Hype［9］、基于R2指标的高维多目标进化算法MOMBI-II［10］等。这类算法的主要缺点是需要大量的计算。针对上述问题，本文提出一种基于拐点和区域划分的高维多目标进化算法（KnSP算法）。

2 背景描述

2.1 高维多目标问题描述

不失一般性，考虑如下MaOPs：