多目标算法解决高维问题

2023-11-26 理论教育版权反馈

【摘要】：为有效求解高维多目标优化问题，研究者从不同的方面开展研究，概括起来可分成如下几类。使用改进的支配关系为提升Pareto支配关系在高维多目标优化问题上的选择压力，一些改进的支配关系陆续提了出来。Yuan等[54]将高维多目标降维问题视为一个3-目标的优化问题，并从维持解群的支配结构和目标相关性出发定义了目标函数。

MOEA算法在解决目标数目较少的问题(比如具有2个或3个目标)时通常具有较好的性能，但如果将这些MOEA算法用于求解目标数较大的高维多目标优化问题(Many-objective Optimization Problem，MaOP)时，比如目标数大于等于4，这些算法的性能会出现不同程度的下降，算法的开销也会快速增长[41]。MaOP问题对主流的MOEA算法提出了巨大挑战，其原因在于[42]以下几方面:1)优化目标数目的增加使得种群中非支配解个体数目呈指数级增长，这就严重削弱了基于Pareto排序进行选择与搜索的能力，最终使得MOEA算法退化成随机搜索方法。另外，高维目标空间中存在许多支配抵触解(Dominance Resistant Solution，DRS)，这些解是一些远离真实Pareto前沿的非支配解，它们对提升算法的性能亦构成了挑战。2)传统杂交和变异算子面临失效的境地。高维目标空间中的解个体存在更大可能彼此相距较远，而由相距较远的父代产生的子代一般与其父代具有较大的差异，在这种情况下，重组算子的作用将被严重削弱。3)Pareto前沿表示的困难。对于具有M个目标的MaOP问题，如果按每个目标上分布k个解来计，则需要MkM-1个解来表示其Pareto前沿。而实际使用算法时，很少会按这个数目来设置档案集的容量，其原因在于，设置过大规模的档案集将不利于决策者的选择。但由此带来的问题却是，档案集规模的缩减将使得控制MaOP问题非支配解的分布变得更加困难。4)度量多样性的计算代价更高。一方面，为了计算高维目标空间中解个体的拥挤度需要确定解个体的邻域，而这个过程的计算代价通常是很高的；另一方面，那些使用近似方法来估计个体密度的做法亦可能导致所获解集的多样性无法接受。5)难以可视化Pareto前沿。按人类的认识水平，对4维及以上的空间其图形特征无法准确地刻画。

为有效求解高维多目标优化问题，研究者从不同的方面开展研究，概括起来可分成如下几类。

(1)使用改进的支配关系

为提升Pareto支配关系在高维多目标优化问题上的选择压力，一些改进的支配关系陆续提了出来。例如，有的通过扩展解的支配区域来提升每个解支配其他解的概率，例如GPO支配[43]等；有的通过对目标空间划分超网格来增加支配概率，例如grid支配[44]等；有的利用模糊逻辑来定义新的强支配关系，例如自适应模糊支配[45]等；有的利用基于目标分解算法中所使用的权值向量来定义新的支配关系，例如θ支配[46]和RP支配[47]等；以及基于目标向量角度的增强支配关系SDR[48]等。

(2)修改密度估计策略

传统的密度估计策略倾向于保留解集中远离Pareto前沿的非支配解，这样虽然保证了解集在目标空间分布的均匀性，但也导致解集的收敛性降低。Adra等[49]利用多样性管理算子(Diversity Management Operator，DMO)控制选择阶段对多样性的需求，以平衡解集的分布性和收敛性。Li等[50]利用基于变换的密度估计方法(Shift-based Density Estimation，SDE)变换稀疏个体在目标空间中的位置，使其具有较大的密度值。Zhang等[51]提出一种基于拐点的进化算法KnEA，该算法通过优先选择非支配解中的局部拐点来提高解集的收敛性和分布性。

(3)目标降维的方法

这类方法假定问题的目标集中存在冗余的目标，通过分析目标之间的关系，在尽可能保持解集支配结构的前提下消除与其他目标不相冲突的冗余目标或者组合彼此不冲突的目标。Sinha等[52]将最大方差展开方法与PCA结合，提出了一种非线性目标降维方法。Jaimes等[53]将所有正相关的目标划分至同一组，并在每一组内选出一个目标函数作为最终的优化目标。Yuan等[54]将高维多目标降维问题视为一个3-目标的优化问题，并从维持解群的支配结构和目标相关性出发定义了目标函数。Cheung等[55]将冗余的目标加权成一个新的目标予以优化。

(4)基于聚合的方法(www.chuimin.cn)

多重单目标Pareto采样方法[56](Multiple Single Objective Pareto Sampling，MSOPS)预先设定一系列均匀分布的参考向量，这些参考向量表明了算法在目标空间中的搜索方向。由于每一个个体都可获得一组不同的适应值，以代表其在各个参考向量下的优劣，取最优者为该个体的最终适应值，因此，MSOPS总能保持足够多的优劣等级，以保证Pareto最优解的选择压力。基于分解的MOEA算法，即MOEA/D算法，也是基于聚合函数的方法，但不同于MSOPS中每一个体对应多个参考向量，MOEA/D中的每一个体对应一个参考向量。必须指出，在高维目标空间中，通过均匀分布的参考向量并不一定能获得均匀分布的解集。为了解决这一问题，带约束的总体适应度排序算法[57](Ensemble Fitness Ranking with a Ranking Restriction Scheme，EFR-RR)通过限制个体与参考向量的垂直距离来提高解集的分布性。Gu等[58]利用自组织映射的方法产生权重向量以获得均匀分布的解群。Wang等[59]对常用的加权和标量化方法进行局部化，以克服传统的加权和方法不能有效求解非凸问题的缺陷。此外，Cheng等[60]针对MOEA/D算法提出了一些自适应生成参考向量的方法。

(5)基于性能评估指标的方法

这类方法通过计算解相对于种群在某些性能指标上的贡献度来判断解的质量。换言之，基于性能指标的多目标和(或)高维多目标进化算法利用贪心策略选出种群中具有最好性能指标值的那一部分解。比如，HypE[61]、GDE-MOEA[62]、MOMBI-Ⅱ[63]和MaOEA/IGD[64]就分别利用了HV、GD、R2和IGD指标作为解个体的选择标准，SRA算法[65]则同时用到了SDE指标和Iε＋指标。由于超体积指标HV与Pareto支配关系具有一致性，使得HV指标获得广泛使用。上述性能指标大都能同时评价一个种群的收敛性和分布性，故基于性能指标的MOEA算法最终能获得一个收敛性与分布性均衡较优的种群。但必须指出，超体积指标偏好于Pareto前沿中的关节点和边界点，这就使得算法难以获得均匀分布于整个Pareto前沿的解集；另外，超体积指标的计算复杂度随着目标数目的增多而呈指数量级增长，这也制约了HV指标在更高维目标空间中的使用。

(6)基于参考集的方法

这一类方法利用一组参考点来评估解个体的质量，并通过参考点来引导算法搜索。文献[66]提出一种参考点集与种群协同进化的策略，但该算法仍采用传统的Pareto占优准则评价个体。文献[67]提出一种基于双档案的进化算法TAA，Wang等[68]在TAA的基础上提出一种改进的Two-Arch2算法。TAA和Two-Arch2均从历史群体和当前种群中选择解点构造参考点集合，它们属于实参考集方法。与此相对的是，NSGA-Ⅲ[69]、TC-SEA[70]和REF-I-MOPSO[71]等算法都是基于预设参考点的，它们属于虚拟参考集方法。由于许多优化问题的Pareto前沿往往是未知的，如果给定的参考点与真实的Pareto前沿不一致，将会显著降低算法的搜索性能。为克服预设参考点这类做法的弊端，一些自适应生成参考点的算法也相继出现，例如Liu等[72]提出的RPEA算法和Xiang等[73]提出的PaRP/EA算法等。利用自适应方式产生参考点有效地利用了进化过程中的一些信息，将有可能显著地提高所获解集的性能。

(7)基于偏好的方法

对于MaOP问题而言，将大量分布在Pareto前沿上的最优解提供给决策者(Decision Maker，DM)进行选择，既浪费计算资源又无必要性。因为DM更希望获得Pareto前沿上少量的满足其偏好的解。偏好多目标进化算法通过引入DM的偏好信息(Preference)而将算法的搜索集中在DM感兴趣的区域(Region of Interest，ROI)，这样既可以有效地利用算法的计算资源，提高算法的求解效率，降低计算复杂度，同时又有利于DM进行高效地决策。Said等[74]提出一种r-占优方法，该方法通过在Pareto非支配解上建立严格的偏序集，引导算法朝ROI区域搜索。但是r-占优关系只能保证弱Pareto最优性，特别是在具有不连续Pareto前沿的问题上会产生大量弱Pareto最优解，因而严重影响了算法的收敛性。章恩泽等[75]改进了r-占优关系，并将其用在高维多目标粒子群算法中，也取得了不错的效果。邱飞岳等[76]同时考虑DM的正、负偏好信息，提出了双极偏好占优机制，并将其融入NSGA-Ⅱ算法。Jaimes等[77]利用切比雪夫支配关系比较解个体，将DM的ROI区域定义成目标点(Goal Point)的邻域，实验表明了这种新型支配关系的优越性。文献[78]基于偏好多面体理论提出一种交互式进化算法，决策者在算法搜索过程中可以周期性地获得一个非支配解集，并从中选取一个最偏好的解。张兴义等[79]提出一种基于权重向量偏好的MOEA算法，该算法首先将均匀分布的权重向量映射到偏好点附近，随后根据映射后的权重向量搜索偏好点附近的Pareto最优解。王丽萍等[80]提出一种基于角度惩罚距离及精英选择策略的偏好高维多目标优化算法G-RVEA，该算法利用等比缩放的偏好向量生成策略产生目标空间中均匀分布的偏好向量，避免了参考点位置对算法性能的影响，有效地利用了计算资源，提高了算法求解效率。考虑到DM通常以不同的方式表达其偏好信息，Wang等[81]提出了基于偏好集的混合交互式协同进化算法iPICEA-g，该算法能够同时处理多种偏好类型(例如权重、期望等)。

当前，多目标进化算法呈现出蓬勃发展之势，一些性能很好的算法相继出现，但同时人们对多目标优化问题的认识仍具历史局限性。随着社会的进步和经济的发展，多目标以及高维多目标优化问题将会不断涌现，如何利用新型群体智能优化模型高效求解这些问题，是当前多目标优化领域的热点问题，同时也是本书的中心内容。

多目标算法解决高维问题

相关推荐