一种从目标空间反向引导种群进化的进化算法

杨祉祺 姚亦飞 于繁华 李晓宁 苏小丽

摘  要： 目前进化算法大多是通过解从决策空间到目标空间的映射，来判断解的质量。针对约束多目标优化问题，将极限学习机代理模型与不可行解存档方法相结合，提出一种通过目标向量反向预测来引导决策空间种群进化的算法。在CTP和TYPE系列的测试问题上进行了HV度量、IGD度量的性能测试。与几种经典的算法比较，该算法在大多情况下都表现出具有竞争力的性能，且在高难度问题下比其他算法表现更好。

关键词： 引导解； 代理模型； 不可行解； 约束优化问题； 进化算法

中图分类号：TP311.5          文献标识码：A     文章编号：1006-8228（2023）04-58-04

Abstract： Most of the current evolutionary algorithms judge the quality of the solution by mapping the solution from the decision space to the objective space. For the constrained multi-objective optimization problem， combining the extreme learning machine surrogate model with the infeasible solution archiving method，an algorithm to guide the evolution of the decision space according to backward prediction of the objective vector is proposed. The comparison of HV indicators and IGD indicators on CTP and TYPE test series shows that the proposed algorithm performs better than other classical algorithms in most cases， especially in high complexity problems.

Key words： guidance solution; surrogate model; infeasible solution; constraint optimization problem; evolutionary algorithms

0 引言

现实世界中的优化问题往往存在相互冲突的多个目标，这样的问题被称为多目标优化问题（multi-objective optimization problem，MOP）。一个MOP中原则上会产生一组帕累托最优解。所有帕累托最优解组成的集合称为帕累托集（Pareto set，PS），PS在目标空间的映射即帕累托前沿（Pareto front，PF）。优化问题往往还涉及不等式和/或等式约束，约束处理是现实世界问题的关键组成部分。约束多目标优化问题（constrained multi-objective optimization problems，CMOP）根据其种类、约束强度、约束数量等属性，难度通常比普通的MOP更大，应用也更加广泛。一个CMOP可以在数学上表述为

其中，有[m]个目标函数需要同时进行优化，一个解[m]个目标函数上的函数值共同构成这个解在一个[m]维目标空间（objective space，OS）的目标向量（objective director，OD）。每个目标函数[fix]都是在决策空间（decision space，DS）[S?Xd]上定义的。通常，DS是一个在[Xd]上的[d]维超空间。DS的每个维度都有其上界（[xmaxi]）、下界[（xmini）]的限制，每个解也在DS中存在一个对应的[d]维决策向量（decision director，DD）。[gj（x）]是[d]维的不等式约束，[hj（x）]是[d]维的等式约束。总共有[p]个约束，[q]个不等式约束和[p-q]个等式约束。约束的存在将解限制在DS上的一个区域[F?S]中，称作可行域，所有未越界但不属于可行域的区域称为不可行域[1，2]。

目前对于约束多目标优化算法（constrained multi-objective evolutionary algorithms，CMOEAs）的研究深度不及传统的MOEAs。针对CMOEAs高维情况收敛速度慢和陷入局部最优这两个问题，本文中提出了一种在主要循环之外直接生成优秀的OD来引导优化过程的新方法。并将这种方法与另一种不可行解存档方法相结合，对基于差分进化的分解算法进行了改进，形成了一种目标空间反向引导算法（Objective space reverse guiding algorithm，ORGA）。

ORGA能够处理高收敛压力和不规则PF问题，弥补了目前此方向研究的空白。更重要的是，反向引导策略生成解的新思路，对EA研究的意义所在。

1 ORGA框架

1.1 反向引导策略

1.1.1 理论基础

MOP中的解通常对应两个向量。目标向量OD，一般记作[Fi（f1，…，fm）]（[m]为目标数）；决策向量DD，一般记作[Xi（x1，…， xd）]（[d]为决策变量数）。[Fi（f1，…，fm）]与[Xi（x1，…， xd）]之间有函数关系[fj=fj（xj，1，…，xj，d）（j∈1，…，m）]，即某个解OD的各分量可由其DD的各分量经过指定的函数运算得到。为了降低使用复杂真实函数的次数，很多研究者使用了从DS到OS的代理模型，用于替代真实函数[3]。或者是使用代理模型作為分类器，直接进行后代筛选[4]。既然可以使用代理模型来依据DD计算OD，对于本质上存在某种函数映射关系的DD和OD，理论上，也可以通过OD和训练好的代理模型来计算精度有所损失的DD。

MOPs中需要被优化的是DD，但是解的质量直接取决于OD。这就导致了现在MOEAs的复杂流程——通过遗传和变异增殖DD，使用真实函数计算OD，再将其用于DD的环境选择。而如果能用代理模型来反向由OD计算出DD，就可以采取一种新的产生解的模式，即根据现有的OD，直接产生一个在OS可能更加优秀的后代解的OD，之后再依据代理模型来计算它的DD。传统方法使用现有解中的优秀解引导种群进化，而这种新的产生解的模式可以使用现有解的优化解来引导进化。

1.1.2 目标空间引导解的生成方法

受基于分解的评估方法启发，本文提出了一种在OS产生引导解的方法。具体步骤如下：

第一步 在OS产生一组均匀分布的参考向量，并初始化一组和向量数量相同大小的零数组[Dmin]；

第二步 在父代中寻找模长最长的OD，然后取它的模记为[Dmax]；

第三步 以式（5）求出[Dmid]

其中，[k]为收敛系数（[k>1]，本文中[k]设置为2），控制引导解的收缩速度;

第四步 以[Dmid]确定长度，以参考向量确定方向，生成一组引导解；

第五步 用极限学习机[5]来预测引导解的DD；

第六步 将越界的引导解舍去，并以其[Dmid]更新其[Dmin]，对未越界的引导解再评估之后环境选择。

1.1.3 反向引导策略

如图1所示，假设用于预测DD的代理模型误差足够小，则[X']落在[X]的附近区域内。而OD由DD通过连续函数计算得出，则[F']应当也落于[F]在OS的附近区域内。换言之，通过预测得到[X']，再通过函数计算得到的[F']，在代理模型的误差足够小时，应当落在生成的引导解[F]的附近区域内。

本方法预测得到的一组解[X']和[F']，其PF能够基本保持两点优秀特质：

⑴ 由于生成的向量集[F]落于参考向量上，所以与[F]接近的[F']在OS大致分布均匀，即PF在多样性上表现优秀；

⑵ 由于[Dmax]是种群中距离原点最远的解距离原点的距离，而生成的解[F]相对最远解以指数级度量收敛，所以与[F]接近的[F']在收敛性上亦保持优秀。

1.2 不可行解存档

不可行解不满足约束条件，但在某些测试问题中，优秀的不可行解反而是进化过程中的先进个体。因此适当地保留优秀的不可行解，可能有助于种群进化。为此研究者提出了由不可行算子引导差分进化的方法[6]。此方法在种群之外独立建立了一个优秀不可行解的存档[z]，存档[z]与种群[x]和参考向量[ω]一一对应。

1.3 不可行解引导方法

差分进化算法[7]的子代产生，使用式⑹

将式中的[xj]替换为不可行存档解[zj]即可得到需要的不可行算子引导进化公式⑺。

2 实验部分

2.1 实验设置

对ORGA及有名的几种算法SP-NSGA-II [8]， CDP-NSGA-II[1]，CMOEAD-DE-CDP和CMOEAD-DE-SR [9]分别在经典的CTP1-7问题[10]和Fan等人提出的TYPE1-3问题[11]上进行了测试。ORGA在反向引导时收敛系数[k]设置为2。对于CTP1-7约束问题，使用ZDT4作为测试问题。对于TYPE问题，使用其原测试约束问题。对于TYPE问题的参数设置。TYPE1问题，[η=0.5]。TYPE2问题，[ζ=0.01]。TYPE3问题，[γ=0.5]。在此设置下，TYPE系列的问题的PF和不可行域分布如图2所示。

2.2 实验结果

2.2.1 收敛情况

各算法在CTP6和TYPE系列问题上的最终迭代结果如图3所示。对于CTP经典测试用例的1-5、7问题和TYPE1问题，各算法在这些问题上都表现较好。在TYPE2问题上，ORGA依然能完成收敛，而SP-NSGA-II和CDP-NSGA-II的表现均不佳，MOEAD-DE-CDP要优于前二者，而MOEAD-DE-SR表现较好。在TYPE3问题上，SP-NSGA-II和CDP-NSGA-II表现不佳，MOEAD-DE-CDP和MOEAD-DE-SR并未跨过不可行域达到下半段PF，而ORGA能够均匀地收敛到整个PF附近。在CTP6问题上，ORGA、SP-NSGA-II和CDP-NSGA-II三种算法均收敛到了PF附近，而MOEAD-DE-CDP和MOEAD-DE-SR未能完成收敛，没有越过PF上方的一个可行域。

2.2.2 可靠性实验

最后我们对TYPE和CTP两系列的测试问题进行50次独立重复实验并记录其进化结束后种群的IGD值和HV值。结果表明，在TYPE1、CTP1-5和CTP7问题上五种算法均表现良好；在TYPE2问题上MOEAD-DE-SR表现较好，ORGA仅在可靠性上略逊于它；在TYPE3问题上，ORGA、MOEAD-DE-CDP和MOEAD-DE-SR都可能达到较理想的IGD和HV值，但ORGA可靠性要更高；在CTP6问题上五种参与测试的算法均可能达到IGD值和HV值的较理想值，其中ORGA可靠性最高。

2.2.3 小结

从以上实验结果可以看出，ORGA在所有问题上的表现都较为理想，两种NSGA-Ⅱ在高维决策变量的TYPE系列问题上表现不佳。而MOEAD-DE-CDP和MOEAD-DE-SR在TYPE2、3问题上表现一般，在CTP6测试问题上表现较差。

3 结论

針对CMOPs，提出了一种通过目标向量反向预测来引导决策空间种群进化的方法。将极限学习机代理模型与不可行解存档方法相结合，使得算法能够高效地跨越不可行区域，在保持多样性的同时迅速收敛。

ORGA的核心在于其使用的反向引导策略，该策略将EA原本面临的DS寻解问题转化为了一个OS寻解问题和一个代理模型的精确度问题。OS寻解的优势在于，其天然受到帕累托支配压力的引导，而DS寻解并不直接受到收敛性指标上的引导。而该策略的OS寻解方法和代理模型选择都仍有改进的空间。

参考文献（References）：

[1] K. Deb. An efficient constraint handling method for genetic algorithms. Computer methods in applied mechanics and engineering 186.2-4 （2000）：311-338

[2] K. Deb， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II. IEEE transactions on evolutionary computation 6.2 （2002）：182-197

[3] B. Abbasi， T. Babaei， Z. Hosseinifard， K. Smith-Miles， M.Dehghani. Predicting solutions of large-scale optimization problems via machine learning： A case study in blood supply chain management. Computers & Operations Research 119（2020）：104941

[4] J.C. Xavier-Júnior， et al. An Evolutionary Algorithm for Automated Machine Learning Focusing on Classifier Ensembles： an improved algorithm and extended results， Theoret. Comput. Sci. （2020）

[5] G.B. Huang， Q.Y. Zhu， C.K. Siew，Extreme learning machine： a new learning scheme of feedforward neural networks. 2004 IEEE international joint conference on neural networks （IEEE Cat. No. 04CH37541）. Vol. 2. Ieee，2004

[6] B. Xu， W. Duan， H. Zhang， Z. Li， Differential evolution with infeasible-guiding mutation operators for constrained multi-objective optimization. Applied Intelligence 50.12 （2020）：4459-4481

[7] H. Li， Q. Zhang，Multiobjective optimization problems with complicated Pareto sets， MOEA/D and NSGA-II. IEEE transactions on evolutionary computation 13.2 （2008）：284-302

[8] Y.G. Woldesenbet， G.G.Yen， B.G. Tessema，Constraint handling in multiobjective evolutionary optimization. IEEE Transactions on Evolutionary Computation 13.3 （2009）：514-525

[9] M.A. Jan， R.A. Khanum，A study of two penalty-parameterless constraint handling techniques in the framework of MOEA/D. Applied Soft Computing 13.1 （2013）：128-148

[10] K. Deb， A. Pratap， T. Meyarivan，Constrained test problems for multi-objective evolutionary optimization. International conference on evolutionary multi-criterion optimization. Springer， Berlin， Heidelberg，2001

[11] Z. Fan， W. Li， X. Cai， H. Li， C. Wei， Q. Zhang， E.Goodman，Difficulty adjustable and scalable constrained multiobjective test problem toolkit. Evolutionary computation 28.3（2020）：339-378

*基金項目：本研究由中国自然科学基金（Grant No.42105144）； 吉林省教育厅（Grant No.JJKH20220840-KJ）； 辽宁省科技厅和国家机器人重点实验室联合基金（Grant No.2020-KF-22-08）

作者简介：杨祉祺（1997-），男，湖南长沙人，硕士研究生，主要研究方向：多目标优化、元启发算法。

通讯作者：姚亦飞（1981-），女，吉林长春人，博士，讲师，主要研究方向：安全多方计算，私有信息保护。