一种基于分解和协同的高维多目标进化算法-谢承旺 , 余伟伟 , 闭应洲 , 汪慎文 , 胡玉荣.pdf

上善若水

250

18页

0次

2022-05-24

免费下载

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

Journal of Software,2020,31(2):356−373[doi: 10.13328/j.cnki.jos.005617] http://www.jos.org.cn

一种基于分解和协同的高维多目标进化算法

∗

谢承旺

余伟伟

闭应洲

汪慎文

胡玉荣

(南宁师范大学计算机与信息工程学院,广西南宁 530299)

(北京工业大学软件学院,北京 100124)

(河北地质大学信息工程学院,河北石家庄 050031)

(荆楚理工学院科技处,湖北荆门 448000)

通讯作者: 谢承旺, E-mail:

chengwangxie@163.com; 闭应洲, E-mail: byzhou@163.com

摘要: 现实中大量存在的高维多目标优化问题对以往高效的多目标进化算法提出了严峻的挑战.通过将分解策

略和协同策略相结合提出一种高维多目标进化算法 MaOEA/DCE.该算法利用混合水平正交实验方法在聚合系数

空间产生一组均匀分布的权重向量以改善初始种群的分布性;其次,算法将差分进化算子和自适应 SBX 算子进行协

同进化,以产生高质量的子代个体,并改善算法的收敛性.该算法与另外 5 种高性能的多目标进化算法在基准测试函

数集 DTLZ{1,2,4,5}上进行对比实验,利用改进的反转世代距离指标 IGD+评估各算法的性能.实验结果表明,

MaOEA/DCE 算法与其他对比算法相比,在总体上具有较为显著的收敛性和分布性优势.

关键词: 高维多目标优化;分解策略;混合水平正交实验设计;高维多目标进化算法

中图法分类号: TP181

中文引用格式: 谢承旺,余伟伟,闭应洲,汪慎文,胡玉荣.一种基于分解和协同的高维多目标进化算法.软件学报,2020,31(2):

356−373. http://www.jos.org.cn/1000-9825/5617.htm

英文引用格式: Xie CW, Yu WW, Bi YZ, Wang SW, Hu YR. Many-objective evolutionary algorithm based on decomposition

and coevolution. Ruan Jian Xue Bao/Journal of Software, 2020,31(2):356−373 (in Chinese). http://www.jos.org.cn/1000-9825/

5617.htm

Many-objective Evolutionary Algorithm Based on Decomposi tion a nd Coev olutio n

XIE Cheng-Wang

, YU Wei-Wei

, BI Ying-Zhou

, WANG Shen-Wen

, HU Yu-Rong

(School of Computer and Information Engineering, Nanning Normal University, Nanning 530299, China)

(School of Software Engineering, Beijing University of Technology, Beijing 100124, China)

(School of Information Engineering, Hebei Geo University, Shijiazhuang 050031, China)

(Department of Science and Technology, Jingchu University of Technology, Jingmen 448000, China)

Abstra ct : In real-world, there exist lots of many-objective optimization problems (MaOPs), which severely challenge well-known

multi-objective evolutioanry algorithms (MOEAs). A many-obective evolutioanry algorithm combining decomposition and coevolution

∗ 基金项目: 国家自然科学基金(61763010, 61402481, 61165004); 广西八桂学者项目; 河北青年拔尖人才支持计划(冀字[2013]

17); 河北省自然科学基金(F2015403046); 河北省教育厅科技重点项目(ZD2018083); 湖北省教育厅科研项目(B2015240);荆楚理工

学院科学研究重点基金(ZR201402); 荆楚理工学院科学研究引进人才科研启动金(QDB201605)

Foundation item: National Natural Science Foundation of China (61763010, 61402481, 61165004); “BAGUI Scholar” Program

of Guangxi Zhuang Autonomous Region of China; Hebei Youth Top Talent Support Program (冀字[2013]17); Natural Science Foundation

of Hebei Province(F2015403046); Major Scientific Research Program of Education Bureau of Hebei Province (DZ2018083); Science and

Technology Project of Education Bureau of Hubei Province (B2015240); Major Scientific Research Fund of Jingchu University of

Technology (ZR201402); Startup Fund for Talents of Jingchu University of Technology (QDB201605)

收稿时间: 2018-04-01; 修改时间: 2018-05-25; 采用时间: 2018-06-18; jos 在线出版时间: 2019-01-21

CNKI 网络优先出版: 2019-01-22 13:49:08, http://kns.cnki.net/kcms/detail/11.2560.TP.20190122.1348.012.html

谢承旺等:一种基于分解和协同的高维多目标进化算法

357

(MaOEA/DCE) is presented in this paper. MaOEA/DCE adopts mix-level orthogonal experimental design to produce a set of weight

vectors evenly distributed in weight coefficient space, so as to improve the diversity of initial population. In addition, the MaOEA/DCE

integrates differential evolution (DE) with the adaptive SBX operator to generate high-quality offspring for enhancing the convergence of

evolutionary population. Some comparative experiments are conducted among MaOEA/DCE and other five representative MOEAs to

examine their IGD+ performance on four MaOPs of DTLZ{1,2,4,5}. The experimental results show that the proposed MaOEA/DCE has

overall performance advantage over the other peering MOEAs in terms of convergence, diversity, and robustness.

Key words: many-objective optimization; decomposition strategy; mix-level orthogonal experimental design; many-objective evolutionary

algorithm

现实中很多优化问题需要同时优化多个目标,这类问题通常被称为多目标优化问题(multi-objective

optimization problem,简称 MOP).MOP 问题的特征在于多个目标函数之间相互冲突,而且一般不存在唯一的解

能够同时满足多个最优化的目标函数.因此,MOP 问题的求解结果通常是一组折中的解,即 Pareto 解集

[1]

.鉴于

MOP 问题的复杂性,使得传统的数学解析方法难以处理,而进化算法(evolutionary algorithm,简称 EA)是一类通

过模拟生物进化机制发展而来的基于群体的随机优化方法.EA 算法具有适于求解 MOP 问题的若干良好特性,

因而在多目标优化领域受到广泛关注.迄今为止,研究者基于不同的研究背景和视角发展出了多种多目标进化

算法(multi-objective evolutionary algorithm,简称 MOEA),其中,基于 Pareto 最优性的 NSGA-II

[2]

和 SPEA2

[3]

算法

即是其中的经典算法.近年来,一些新型的进化模型陆续引入到多目标优化和高维多目标优化中,包括多目标粒

子群算法 MOPSO

[4]

、改进速度更新的 SMPSO 算法

[5]

、基于分布估计的 RM-MEDA 算法

[6]

和多目标烟花爆炸

算法等

[7]

.近几年来,混合型 MOEA 算法相继产生,其中代表性的工作包括 Molina

[8]

、Nebro

[9]

和 Solima

[10]

等人的

工作.基于混合策略的 MOEA 算法根据算法或算子的优劣,通过取长补短的做法发展出高效的 MOEA 算法.实

践证明,混合型方法是一种很有效的策略.

随着经济与社会的发展,更多个优化目标的优化问题大量涌现,研究者通常把目标数大于等于 4 的优化问

题称为高维多目标优化问题(many-objective optimization problem,简称 MaOP).一般而言,MaOP 问题与 MOP 问

题相比,具有更加难以求解的特征,主要表现在:1) Pareto 支配关系在高维目标空间者难以区分解个体的优劣,从

而严重削弱了种群的进化压力;2) 为了表征 MaOP 问题的 Pareto 前沿,所需使用的非支配解数量依目标数呈指

数增加(例如,对于 m 个目标的 MaOP 问题,按每个目标上分布 k 个解来计算,则需要 mk

m−1

个解来表示 Pareto 前

沿);3) 难以可视化 Pareto 前沿,因为按照人类的认识水平,对 4 维及以上空间其图形特征无法准确地刻画.此外,

一旦多样性保持机制在群体进化中占据主导,则有很大可能迟滞种群逼近真实的 Pareto 前沿,从而对进化过程

带来较大的负面影响

[11−13]

.近期的一些研究也表明,当优化问题的目标数目增至 10 个或更多时,基于 Pareto 支

配的 MOEA 算法甚至比随机搜索算法表现得更差

[14]

为了应对高维多目标问题带来的挑战,研究者从不同方面开展了研究,概括起来可以将其分成如下几种

类型.

1) 引入数学分析中的降维思想,将高维多目标问题降为低维目标问题.这类方法假定 MaOP 问题的目标

集合中存在冗余目标,通过分析目标之间的关系,在尽可能保持解集支配结构的前提下,消除与其他

目标不冲突的冗余目标或者组合彼此不冲突的目标.但是这种方法并非适合所有的 MaOP 问题,某些

问题并不能很好地保证降维的有效性.

2) 基于评估指标的方法. 这类方法通过直接优化 Pareto 近似解集的评估指标(例如超体积指标

Hypervolume 等)来优化待解问题.其实质是将 MaOP 问题转化成一个优化指标函数的单目标优化问

题.然而,基于指标的方法也存在指标,尤其是超体积指标计算复杂度很高的缺点.

3) 利用偏好的方法.在多目标优化中,偏好意味着决策者给目标赋予了不同的值来表示其重要程度或者

优先处理的顺序.它使得搜索过程或者优化结果可以处于决策者感兴趣的区域.这一类方法需要用户

预先指定偏好或要求与搜索进程进行交互,因而增大了用户使用算法的难度.

4) 使用新的支配关系.新的支配关系主要利用目标优劣的计数或者目标之间的差距来区分非劣解,通过

of 18

免费下载

软件学报计算机技术

关注

评论