面向多目标优化的多样性代理辅助进化算法-孙哲人，黄玉划，陈志远.pdf

上善若水

388

15页

0次

2022-05-26

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2021,32(12):3814−3828 [doi: 10.13328/j.cnki.jos.006109] http://www.jos.org.cn

面向多目标优化的多样性代理辅助进化算法

∗

孙哲人

黄玉划

陈志远

(南京航空航天大学计算机科学与技术学院,江苏南京 211106)

通讯作者: 孙哲人, E-mail: szheren2k@163.com

摘要: 代理辅助进化算法(SAEA)是目前解决昂贵优化问题的一种有效途径.提出一种基于多样性的代理辅助

进化算法(DSAEA)来解决昂贵多目标优化问题.DSAEA 采用 Kriging 模型近似每个目标来代替原目标函数进行评

估,加速了进化算法的优化过程.其引入参考向量把问题分解为多个子问题,根据解与参考向量之间的角度大小建立

它们的相关性,然后计算出最小相关解集.在此基础上,候选解生成算子和选择算子会趋向于保留多样性的解.另外,

训练集 A 在每次迭代后会进行更新,根据多样性删除价值不大的样本以减少建模时间.实验部分对 DSAEA 与目前

流行的代理辅助进化算法在大规模 2 目标和 3 目标优化问题上进行对比实验.每个算法在不同的测试问题上分别独

立运行 30 次,并计算和统计反向迭代距离(IGD)、超体积(HV)和运行时间,最后使用秩和检验分析实验结果.结果表

明:DSAEA 在多数实验测试问题上表现更好,因此具有有效性和可行性.

关键词: 代理模型;进化算法;多目标优化;昂贵问题;参考向量;模型管理;Kriging

中图法分类号: TP18

中文引用格式: 孙哲人,黄玉划,陈志远.面向多目标优化的多样性代理辅助进化算法.软件学报,2021,32(12):3814−3828.

http://www.jos.org.cn/1000-9825/6109.htm

英文引用格式: Sun ZR, Huang YH, Chen ZY. Diversity based surrogate-assisted evolutionary algorithm for expensive multi-

objective optimization problem. Ruan Jian Xue Bao/Journal of Software, 2021,32(12):3814−3828 (in Chinese). http://www.jos.

org.cn/1000-9825/6109.htm

Diversity Based Surrogate-assisted Evolutionary Algorithm for Expensive Multi-objective

Optimiza tion Problem

SUN Zhe-Ren, HUANG Yu-Hua, CHEN Zhi-Yuan

(College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China)

Abstra ct : The surrogate-assisted evolutionary algorithm (SAEA) is an effective way to solve expensive problems. This study proposed a

diversity-based surrogate-assisted evolutionary algorithm (DSAEA) to solve the expensive multi-objective optimization problem. DSAEA

approximates each objective with the Kriging model to replace the original objective function evaluation, accelerating the optimization

process of the evolutionary algorithm. It decomposes the problem into several subproblems with the reference vectors. The correlation

between the solution and the reference vector is established according to the angle between them. Then the minimum correlative solution

set is computed. Based on it, the candidate producing operator and the selection operator tend to preserve the solutions of diversity. In

addition, as the training set, Archive A is updated after each iteration, deleting the little value samples according to diversity to reduce the

modeling time. In the experiment section, large scale 2- and 3-objective comparative experiments for DSAEA and several current popular

SAEAs were done. Each algorithm on different test problems ran 30 times independently, and the inverted generational distance (IGD),

hypervolume (HV), and running time were calculated and collected. At last, rank sum test was used to analyze the experimental results.

The results show that DSAEA performs better on the most experimental test problems, therefore, it is effective and feasible.

∗ 基金项目: 江苏省科技支撑计划(BE2013879)

Foundation item: Science & Technology Support Plan of Jiangsu Province (BE2013879)

收稿时间: 2020-02-21; 修改时间: 2020-04-13, 2020-06-07; 采用时间: 2020-06-27

孙哲人等:面向多目标优化的多样性代理辅助进化算法

3815

Key words: surrogate; evolutionary algorithm; multi-objective optimization; expensive problem; reference vector; model management;

Kriging

多目标优化问题(multi-objective optimization problem,简称 MOP)

[1]

是指包含两个或两个以上目标的优化

问题,其目标之间往往相互冲突且难以相互比较.由于能够较好地权衡多目标优化问题中的多个目标,进化算法

逐渐成为了很多领域中解决多目标优化问题的一种较为流行的工具

[2]

,如经济、金融、工程

[3−5]

在过去的 30 多年里,专家学者对多目标进化算法进行了大量的研究,提出了许多先进的算法,大体可以分

成基于支配、基于分解和基于指标这 3 种

[6]

:基于支配的算法主要有 Zitzler 等人提出的 SPEA2

[7]

和 Deb 等人提

出的 NSGA-II

[8]

,基于分解的算法主要有 Deb 等人提出的 NSGA-III

[9]

和 Zhang 等人提出的 MOEA/D

[10]

,基于指

标的算法主要有 Zitzler 等人提出的 IBEA

[11]

和 Beume 等人提出的 SMS-EMOA

[12]

.进化算法在解决多目标优化

问题时,需要对解进行大量的真实评估,即,使用原始的目标函数评估解.然而,现实中存在很多问题需要计算机

仿真、真实实验或数据驱动的方式来评估,因此其评估过程往往需要花费大量时间、人力、物力和财力,这类

问题被称为昂贵问题

[13]

,如创伤系统优化

[14]

等.对于昂贵问题,由于受到评估时间的限制,进化算法难以在短时

间内给出较好的结果.而代理辅助进化算法可以通过廉价的模型评估代替昂贵的真实评估来加速进化算法,大

大减少评估过程的代价,同时能够保证较好的优化结果.

目前,常用的代理模型主要有多项式响应模型、Kriging 模型、神经网络模型、径向基函数网络模型和支

持向量回归模型,但在选择代理模型方面缺乏理论指导

[2]

.一般来说,在使用插值法的模型中,首选的是 Kriging

模型,因为 Kriging 模型在评估解的目标值的同时,可以给出解的不确定性,而不需要额外使用其他方法来计算

不确定性.因为有此特性,Kriging 模型是代理辅助进化算法一个较为流行的选择,如 Knowles 提出的 ParEGO

[15]

Ponweiser 等人提出的 SMS-EGO

[16]

,Zhang 等人提出的 MOEA/D-EGO

[17]

和 Chugh 等人提出的 K-RVEA

[18]

都使

用了 Kriging 模型.

以上提到的算法是此领域较为流行且具有代表性的算法,它们选择解的时候更多关注解在模型评估下的

收敛性.但很多情况下,在模型评估下的好解是伪好解,即在真实评估下并不是好解.对于 Kriging 模型来说,训练

样本的分布对模型评估的准确度有很大的影响,训练样本在需要评估的解四周分布越广泛,则模型评估会相对

越准确

[19]

.对于多目标优化问题,广泛分布在帕累托前沿(Pareto front,简称 PF)上的解,也会较为广泛分布在帕累

托最优集合(Pareto set,简称 PS)上

[20]

.因此,如果能够在真实 PF 附近得到分布较为广泛的样本,Kriging 模型就可

以较好地近似真实 PF 附近的局部空间,从而增加找到在真实 PF 附近的解的可能.这就需要更多地考虑多样性,

而不只是收敛性.因此,本文提出了基于多样性的代理辅助进化算法(DSAEA)来解决昂贵多目标优化问题.

1 背景知识

1.1 多目标优化问题

多目标优化问题的一般形式如下:

min ( ) { ( ),..., ( )}

subject to ,

∈

xx x

其中,F(x)={f

(x),...,f

(x)}

为 m 个目标组成的目标向量,x={x

,...,x

}

为 d 个决策变量组成的决策向量,R

为 d

维决策空间,R

为 m 维目标空间,F 表示从决策空间映射到目标空间.当且仅当∀i={1,...,m},f

)≤f

)和

∃j={1,...,m},f

)<f

),则称 x

支配 x

.如果一个解在解集中没有解能够支配它,则称为非支配解;反之,则称为支

配解.所有非支配解的决策向量构成的集合叫做帕累托最优集合 PS,对应的目标向量构成的集合叫做帕累托前

沿 PF.

1.2 代理辅助进化算法

代理辅助进化算法中的评估方式分为两种.

of 15

免费下载

软件学报计算机技术

关注

评论