HMOFA_一种混合型多目标萤火虫算法-谢承旺 , 肖驰 , 丁立新 , 夏学文 , 朱建勇 , 张飞龙.pdf

上善若水

159

20页

0次

2022-05-19

免费下载

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

Journal of Software,2018,29(4):11431162 [doi: 10.13328/j.cnki.jos.005275] http://www.jos.org.cn

HMOFA:一种混合型多目标萤火虫算法



谢承旺

肖

驰

丁立新

夏学文

朱建勇

张飞龙

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

(华东交通大学软件学院,江西南昌 330013)

(武汉大学计算机学院,湖北武汉 430072)

(华东交通大学电气与自动化工程学院,江西南昌 330013)

通讯作者: 谢承旺, E-mail: chengwangxie@163.com

摘要: 现实中不断涌现出数目众多且日益复杂的多目标优化问题,迫切需要发展新型多目标优化算法以应对挑

战.将基本萤火虫算法拓展至多目标优化领域,提出一种混合型多目标萤火虫算法 HMOFA(hybrid multi-objective

firefly algorithm).该算法提出使用混合水平正交实验设计和连续决策空间量化的方法生成接近于用户指定规模且

均匀分布于搜索空间的初始种群,为后续的进化提供良好的起始点;利用外部档案中的精英解个体引导萤火虫移动,

促使算法较快收敛;运用 3 点最短路径方法维持外部档案的多样性.HMOFA 算法与另外 5 种代表性多目标进化算法

一同在 17 个基准多目标测试题上进行性能比较,实验结果表明,HMOFA 算法在收敛性、多样性和鲁棒性方面总体

上具有较显著的性能优势.

关键词: 萤火虫算法;多目标进化算法;混合水平正交实验设计

中图法分类号: TP18

中文引用格式: 谢承旺,肖驰,丁立新,夏学文,朱建勇,张飞龙.HMOFA:一种混合型多目标萤火虫算法.软件学报,2018,

29(4):11431162. h ttp://www.jos.o rg.cn/1000-9825/5275.ht m

英文引用格式: Xie CW, Xiao C, Ding LX, Xia XW, Zhu JY, Zhang FL. HMOFA: A hybrid multi-objective firefly algorithm.

Ruan Jian Xue Bao/Journal of Software, 2018,29(4):11431162 (in Chinese). http://www.jos.org.cn/1000-9825/5275.htm

HMOFA: A Hybrid Multi-Objective Firefly Algorithm

XIE Cheng-Wang

, XIAO Chi

, DING Li-Xin

, XIA Xue-Wen

, ZHU Jian-Yong

, ZHANG Fei-Long

(School of Computer and Information Engineering, Guangxi Teachers Education University, Nanning 530299, China)

(School of Software, East China Ji aotong University, Nanchang 330013, China)

(Computer School, Wuhan Univ ersity, Wuh an 430072, China)

(School of Electrical and Electronic Engineering, East China Jiaotong University, Nanchang 330013, China)

 基金项目: 国家自然科学基金(61763010, 61563015, 61663009, 61602174); 广西八桂学者项目; 广西壮族自治区自然科学基金

(2016GXNSFAA380209); 江西省自然科学基金(20114BAB201025, 20161BAB 212052, 20161BAB202064); 教育部人文社科青年基

金(14YJCZH172); 江西省科技支撑项目(20151BBG70055); 江西省博士后基金(2015KY18); 江西省教育厅科技项目( GJJ12307,

GJJ14373, GJJ14374, GJJ160469, GJJ150496); 科学计算与智能信息处理广西高校重点实验室开放课题(GXSCIIP201604)

Foundation item: National Natural Science Foundation of China (61763010, 61563015, 61663009, 61602174); Guangxi “BAGUI

Scholar” Program; Natural Science Foundation of Guangxi Zhuang Autonomous Region, China (2016GXNSFAA380209); Natural Science

Foundation of Jiangxi Province, China (20114BAB201025, 20161BAB212052, 20161BAB202064); Ministry of Education Humanities

and Social Sciences Youth Fund (14YJCZH172); Jiangxi Science and Technology Support Project (20151BBG70055); Jiangxi

Postdoctoral Fund (2015KY18); Science and Technology Project of Jiangxi Provincial Department of Education (GJJ12307, GJJ14373,

GJJ14374, GJJ160469, GJJ150496); Science Computing and Intelligent Information Processing of Guangxi Higher Education Key

Laboratory (GXSCIIP201604)

收稿时间: 2016-11-09; 修改时间: 20 17-01-26; 采用时间: 2017-03-02; jo s 在线出版时间: 2 017-03-17

CNKI 网络优先出版: 2017-03-17 14:37:42, http://kns.cnki.net/kcms/d etail/11.2560.TP.20170317.1437.007.html

1144

Journal of Software 软件学报 Vol.29, No.4, April 2018

Abstra ct : It is necessary to develop some novel multi-objective optimization algorithms to cope with the complicated multi-objective

optimization problems which are emerging and increasingly hard in reality. The basic firefly algorithm is extended to the realm of

multi-objective optimization, and a hybrid multi-objective firefly algorithm (HMOFA) is proposed in this paper. Firstly, an initia lization

approach of mix-level orthogonal experimental design with the quantification of the continuous search space is used to generate an

even-distributed initial population in the decision space. Secondly, the elites in the external archive are randomly selected to guide the

movement of the fireflies in the evolutionary process. Finally, the archive pruning strategy based on three-point shortest path is used to

maintain the diversity of the external archive. The proposed HMOFA is compared with other five peer algorithms in the performance of

hypervolume based on seventeen benchmark multi-objective test instances, and the experimental results show that the HMOFA employs

the overall performance advantages in convergence, diversity and robus tn ess over oth er peer algorithms.

Key words: firefly algorithm; multi-objective evolutionary algorithm; mix-level orthogonal experimental desig n

科学研究与工程应用中存在大量需要同时优化多个目标的问题, 它们通常被称为多目标优化问题

(multi-objective optimization problem,简称 MOP).一般地,MOP 问题中各目标之间通过决策变量发生联系并相

互冲突,因此,MOP 问题一般并不存在单个的最优解使得各目标同时取得最优值,而往往是一组由折中解组成

的集合,即 Pare t o 解集

[1]

.由于 MOP 模型高度复杂使得一般的解析方法难以凑效,研究者通常利用计算机算法来

获得其 Pareto 解集的一个逼近.进化算法(evolutionary algorithm,简称 EA)是一种模拟自然界中生物进化的随机

优化方法,由于 EA 算法隐含的并行性,运行一次可产生一组解,而且它对待解问题的数学性质不敏感,因此适用

于处理一些不连续、非凸、多模态等优化问题.鉴于 EA 算法在求解 MOP 问题中诸多的优势,使得多目标进化

算法(multi-objective e voluti onary algorith m,简称 MOEA)的研究获得了长足的发展.

纵观 MOEA 算法近十多年的发展历程,可根据其特征将算法大致分成如下几种类型.

(1) 基于 Pa ret o 占优的 MOEA 算法.这类算法以 Pareto 存档进化策略(PAES)

[2]

、非支配排序遗传算法

(NSGA)

[3]

及其改进版本 NSGA-II

[4]

、强度 Pareto 进化算法(SPEA)

[5]

和改进的 SPEA2

[6]

等方法为代表,这类

MOEA 算法一般具有原理简单、易于理解和参数较少等优点,但是由于 Pareto 最优性固有的局限使得这一类算

法并不能较好地求解具有复杂 Pareto 前沿的 MOP 问题和高维多目标优化问题等;

(2) 基于性能评估指标的 MOEA 算法.这类算法通过直接优化 Pareto 近似集合的评估指标来间接优化原

MOP 问题,其本质是将 MOP 问题转化成单目标问题求解.这类算法以 IBEA

[7]

和 HypE

[8]

等算法为代表,但在某

些情形下,由于性能指标值的计算较为耗时,需要采用抽样的方法提高计算速度

[8]

.另外,超体积指标偏好于

Pareto 前沿中的关节点和边界点,使得算法难以获得均匀分布于整个 Par eto 前沿的解集

[9]

;

(3) 基于分解方法的 MOEA 算法.这类算法将 MOP 问题分解成一系列子问题,然后利用子问题邻域信息协

同地求解

[10]

.代表性的工作包括 Zhou 等人

[11]

基于混合高斯模型的 MOE A/ D( MOE A/ D- G M) 和 Wang 等人

[12]

自

适应调整约束子问题的 MOEA/ D( M OE A/ D-AC D ) 算法等.需要指出的是,基于分解技术的 MOEA 算法在获得均

匀分布的解集方面尚存在挑战,其原因在于:一组均匀分布的加权向量并不能保证算法也能获得一组均匀分布

于 Pa ret o 前沿上的交叉点,特别是对于那些具有高度不规则 Pareto 前沿的问题更是如此

[9]

;

(4) 新型进化机制的 MOEA 算法.这类算法将一些新的进化机制和启发式算法引入到多目标优化领域,代

表性的算法包括基于粒子群优化(particle swarm optimization,简称 PSO)的 MOPSO 算法

[13]

以及改进的限制粒子

速度的 SMPSO 算法

[14]

;基于分布估计算法(est imatio n of di stributi on algorit hm, 简称 EDA)的 RM-MEDA 算法

[15]

;

基于烟花爆炸优化(fireworks explosion optimization,简称 FEO)的多目标烟花爆炸算法

[16]

等.新型进化范例的引

入拓宽了解决复杂 MOP 问题的思路,并已成为多目标优化领域新的研究热点之一;

(5) 不同机制相混合的 MOEA 算法.这类算法代表性的工作包括 Molina 等人

[17]

将分散搜索(scatter search)

和禁忌搜索(tabu search)相结合以解决非线性多目标优化问题,Nebro 等人

[18]

提出一种基于档案的混合分散搜

索算法 Ab Y SS, Sol i ma 等人

[19]

将协同进化与局部搜索的思想融入到多目标差分进化算法中,以指导搜索向

Pareto 最优解逼近等.混合型 MOEA 算法利用了每个 MOEA 或元启发式方法的长处,并进行优势互补,从而克服

单个 MOEA 或元启发式方法所固有的局限,可进一步增强算法在解空间中搜索的效率和效果.

2008 年,Yang

[20]

通过对萤火虫群体行为的模拟和简化,提出一种高级启发式算法——萤火虫算法(firefly

of 20

免费下载

软件学报计算机技术

关注

评论