演化算法因在优化过程中能够找到一组非支配解、能够处理具有多个局部和非凸Pareto前沿的问题、能够处理不同类型的变量(如二元、实数、整数或混合)、不需要关于目标和约束的凸性和可微性的假设等优点,被广泛用于求解多目标优化问题。然而,演化算法也因优化过程中大量适应值评估导致的计算时间开销增加而受到制约。特别的,当待处理问题的适应值评估代价高时,解决这一瓶颈显得至关重要。因此,需要对演化算法进行适应性调整,以便在不降低解质量的情况下以更少的计算时间获得最优/满意解。本期AAEO我们将与大家分享使用演化算法求解高代价多目标优化问题的综述文章,由于笔者能力有限,如果分享过程中疏漏了重要工作,还请大家不吝赐教与指正。

发表在Soft Computing 2017来自Tinkle Chugh,Karthik Sindhya,Jussi Hakanen,Kaisa Miettinen的综述文章:A survey on handling computationally expensive multiobjective optimization problems with evolutionary algorithms(原文链接),对2008至2016年期间提出的45个用以解决高代价多目标优化问题的算法进行了综述。与以前的综述文章相比,本综述文章具有以下7个特点:

1.侧重被广泛使用的基于函数逼近或代理模型的算法;

2.将基于函数逼近的算法进一步分类为基于Kriging和非Kriging的算法,表明Kriging具有广泛的适用性;

3.算法参考一个通用函数逼近框架来描述,从而为读者能够更好地使用演化算法中的任何函数逼近;

4.强调不同算法在降低计算代价或适应值评估次数方面的效率;

5.观察和讨论算法中的各种缺点,例如处理约束条件、解决问题的维数(在决策和目标空间两方面)、训练时间等;

6.确定了一些有助于克服几个问题的局限性的因素,例如有效管理函数逼近方法以处理三个以上目标;

7.对根据待解决问题的特点、目标和决策空间的维度以及可用的预算等选择特定的算法,提供了一些指导意见。

文章主要从以下三个方面进行了综述:

(一)概念术语

这部分对降低计算代价时经常使用的一些方法:元模型(meta-model)、元模型集成(ensemble of meta-models)、进化控制或模型管理(evolution control or model management)、适应值继承(fitness inheritance)、适应值模仿(fitness imitation)等的概念进行了综述,并给出了相关方法提出、应用的文献。

(二)近似算法

在近似算法中,问题中计算代价高的元素被计算代价低的近似值替换。基于近似的方法可分为问题近似、函数近似、适应值近似三种。本部分从函数近似、元模型使用中存在的挑战、基于单元模型的算法、基于多元模型的算法、基于元模型集成的算法、基于函数近似的算法对比、问题近似和适应值近似等七部分分别进行综述。

1、函数近似

文章首先综述了常用的进行函数近似的方法;其次,将基于函数近似方法的演化算法框架总结为两部分共十个步骤,并分别对每步的相关算法进行了综述。


Stage 1

1. Initialize the population either randomly or using a sampling method.
2. Evaluate the individuals of the population using the original functions and add them to an archive.
3. If a prefixed number of generations is completed, go to stage 2.
4. Use EA operators (selection, crossover and mutation) to create a new population and go to step 2.
Stage 2
5. Build or update a meta-model for each computationally expensive objective and constraint function using the individuals from the archive.
6. Use EA operators (selection, crossover and mutation) to create a new population.
7. For each objective and constraint function, evaluate the individuals of the new population either using the meta-model or the original function (fixed or adaptive evolution control strategy).
8. If a stopping criterion is met, select the non-dominated individuals from step 7 as the final population and stop. Otherwise, continue.
9. Select individuals from step 7 for re-evaluation using the original functions if needed.
10. Add the individuals from step 9 to the archive and go to step 5.


2、元模型使用中存在的挑战

首先,本部分总结了在多目标优化中使用函数近似方法主要存在的挑战,结合总结的算法框架分别从元模型的使用、元模型的更新、元模型的训练时间等进行了综述。其次,总结了在单目标优化和多目标优化中使用函数近似方法时均存在的挑战,分别从元模型的选择、元模型的更新时机、约束控制等进行了综述。

3、基于单元模型的算法

本部分对单元模型在算法中的应用进行了综述,分别从基于Kriging模型的算法、非基于Kriging模型的算法两部分进行综述。

4、基于多元模型的算法

本部分对使用多元模型的算法进行了讨论,这些元模型被独立使用来预测目标或约束函数。

5、基于元模型集成的算法

本部分对基于元模型集成的算法进行了总结,并分析了在每个算法中,模型集成实际的工作过程。

6、基于函数近似的算法对比

本部分对基于函数近似的算法进行了对比,文章分别总结了关于元模型、多目标演化算法、演化控制策略的相关文献。

7、问题近似和适应值近似

除了函数近似外,很多文献也使用问题和适应值近似来降低多目标优化问题中的计算时间。问题近似的主要目的是降低问题的计算复杂度,适应值近似是使用元模型来近似某些元素而不是目标函数。本部分分别对问题近似和适应值近似两部分的算法进行了总结、分析。

(三)讨论

本部分首先总结了文献中提到的算法找到的有希望的元素;其次,讨论了可用于设计增强型演化算法的方法,以处理高代理多目标优化问题;最后,讨论了文献中算法运行过程中观察到的主要问题,即关于在演化算法中实验近似值和用于测试其效率的参数设置。

文章最后对在综述中总结对比的算法中观察到的问题进行了归纳总结,并给出了未来可能的研究方向。

更多相关文献请见:

AAEO第18期:基于代理模型的演化算法论文分享

AAEO第40期:基于演化算法求解高代价多目标优化问题论文分享

AAEO第86期:演化算法在大规模高代价优化问题中的论文分享

AAEO第88期:不确定环境中的演化优化方法综述文章分享

张 晋媛

张 晋媛

华东师范大学-计算机科学与软件工程学院计算机科学技术系-博士生

© 2019 ECOLE