控制与决策  2019, Vol. 34 Issue (10): 2073-2084  
0

引用本文 [复制中英文]

张新明, 王霞, 康强. 改进的灰狼优化算法及其高维函数和FCM优化[J]. 控制与决策, 2019, 34(10): 2073-2084.
[复制中文]
ZHANG Xin-ming, WANG Xia, KANG Qiang. Improved grey wolf optimizer and its application to high-dimensional function and FCM optimization[J]. Control and Decision, 2019, 34(10): 2073-2084. DOI: 10.13195/j.kzyjc.2018.0146.
[复制英文]

基金项目

河南省高等学校重点科研项目(19A520026)

作者简介

张新明(1963-), 男, 教授, 从事智能优化算法、数字图像处理、模式识别等研究, E-mail: xinmingzhang@126.com;
王霞(1993-), 女, 硕士生, 从事智能优化算法、数字图像处理的研究, E-mail: wangxiagzyx@126.com;
康强(1989-), 男, 硕士生, 从事智能优化算法、数字图像处理的研究, E-mail: 2813985282@qq.com

通讯作者

张新明, E-mail: xinmingzhang@126.com

文章历史

收稿日期:2018-01-29
修回日期:2018-03-22
改进的灰狼优化算法及其高维函数和FCM优化
张新明 1,2, 王霞 1, 康强 1     
1. 河南师范大学 计算机与信息工程学院,河南 新乡 453007;
2. 河南省高校计算智能与数据挖掘工程技术研究中心,河南 新乡 453007
摘要:灰狼优化算法(GWO)具有较强的局部搜索能力和较快的收敛速度, 但在解决高维和复杂的优化问题时存在全局搜索能力不足的问题.对此, 提出一种改进的GWO, 即新型反向学习和差分变异的GWO(ODGWO).首先, 提出一种最优最差反向学习策略和一种动态随机差分变异算子, 并将它们融入GWO中, 以便增强全局搜索能力; 然后, 为了很好地平衡探索与开采能力以提升整体的优化性能, 对算法前、后半搜索阶段分别采用单维操作和全维操作形成ODGWO; 最后, 将ODGWO用于高维函数和模糊C均值(FCM)聚类优化.实验结果表明, 在许多高维Benchmark函数(30维、50维和1 000维)优化上, ODGWO的搜索能力大幅度领先于GWO, 与state-of-the-art优化算法相比, ODGWO具有更好的优化性能.在7个标准数据集的FCM聚类优化上, 与GWO、GWOepd和LGWO相比, ODGWO表现出了更好的聚类优化性能, 可应用在更多的实际优化问题上.
关键词智能优化算法    灰狼优化算法    反向学习    差分变异    模糊C均值(FCM)聚类    高维函数优化    
Improved grey wolf optimizer and its application to high-dimensional function and FCM optimization
ZHANG Xin-ming 1,2, WANG Xia 1, KANG Qiang 1     
1. College of Computer and Information Engineering, Henan Normal University, Xinxiang 453007, China;
2. Engineering Technology Research Center for Computing Intelligence & Data Mining of Henan Province, Xinxiang 453007, China
Abstract: The grey wolf optimizer (GWO) algorithm proposed recently has strong local search ability and fast convergence, but it has some defects, such as poor global search ability in solving high-dimensional functions and complex optimization problems. Therefore, this paper proposes an improved GWO, namely GWO with opposition-learning and differential mutation (ODGWO). Firstly, a max-min opposition learning strategy and a dynamical and random differential mutation operator are proposed, which are integrated with GWO to enhance its global search ability. Then, in order to balance exploration and exploitation well to improve the overall performance, one-dimensional operation and full-dimensional operation are applied to the first half and the latter one of the search phase respectively to form the ODGWO consequently. Finally, the ODGWO is used for the high-dimensional function and fuzzy C-means (FCM) clustering optimization. The experimental results on many high-dimensional (30, 50 and 1 000 dimension) benchmark functions show that the ODGWO has significantly higher global search ability than the GWO does, and the ODGWO outperforms the state-of-the-art algorithms. As for FCM optimization on seven standard datasets, the ODGWO shows better clustering optimization performance compared with the GWO, the GWOepd and the LGWO, and it will be applied to more real-world optimization problems.
Keywords: intelligent optimization algorithm    grey wolf optimization    opposition-learning    differential mutation    fuzzy C-means (FCM) clustering    high-dimensional function optimization    
0 引言

群智能优化算法受启发于自然界生物的社会行为等, 相比于传统优化算法, 其结构简单, 易于实现, 从而受到广泛关注. 2014年, Mirjalili等提出了一种新型的群智能优化算法——灰狼优化算法(Grey wolf optimizer, GWO)[1]. GWO模拟了自然界中灰狼的社会等级和狩猎行为.该算法因采用新型的搜索机制, 在解决一些优化问题时表现出良好的性能, 如局部搜索能力较强, 收敛速度较快等等.但GWO在解决一些复杂问题时仍存在全局搜索能力较差等缺陷.因此, 许多学者对其进行了改进研究.文献[2]提出了融合动态进化种群(Evolutionary population dynamics, EPD)的GWO(GWOepd), 提高了GWO的探索能力.文献[3]提出了一种基于Powell局部优化方法的GWO, 并将该算法用于聚类分析.文献[4]将差分进化算法的交叉和变异算子引入GWO中, 提出一种混合GWO, 提高了GWO的优化性能.文献[5]提出了一种基于混沌理论和精英反向学习策略的混合GWO(Hybrid GWO, HGWO), 用于解决高维函数优化问题.文献[6]将Levy flight和贪婪选择策略与改进的狩猎阶段相结合, 提出一种嵌入Levy flight的GWO(Levy-embedded GWO, LGWO), 提高了GWO的种群多样性.文献[7]提出了一种生物地理学优化算法与GWO的混合算法, 以帮助GWO跳出局部最优点.文献[8]以强化学习的方式设置个体行为, 以神经网络的方式学习个体历史经验, 提高了GWO的优化性能, 从而提出一种Experienced GWO.文献[9]将位置更新方程和非线性控制参数策略相结合, 提出了一种提高探索能力的GWO.以上算法很好地解决了GWO存在的一些问题, 但GWO提出时间较短, 有许多改进和应用拓展之处, 尤其在解决一些复杂优化问题时, 仍存在很大的改进空间.

目前, 高维优化问题一直是进化计算领域的一个焦点[5], 因为近年来许多现实世界的问题都涉及多个变量的优化.然而, 维数的增加会导致大多数可用优化算法的性能下降.因此, 传统的智能优化算法已经无法有效地解决该问题.模糊C均值(Fuzzy C-means, FCM)聚类[10]是一种无监督的学习方法, FCM聚类的最终目标是划分到同一组内数据点的相似性最大, 不同组间数据点的相异性最大. FCM聚类使用模糊目标函数来评估聚类结果, 模糊目标函数的值越低表示聚类效果越好. FCM聚类作为一种软聚类算法已被广泛应用于多个领域[10], 但仍存在对初始聚类中心敏感、易陷于局部最优等问题.

本文针对GWO在解决高维和复杂的优化问题时存在的全局搜索能力不足的问题, 提出最优最差反向学习策略与动态随机差分变异策略, 构建一种基于这两种策略的新型灰狼优化算法(GWO with opposition-learning and differential mutation, ODGWO).首先, 为了增加GWO的全局搜索能力, 嵌入最优最差反向学习策略; 其次, 为了进一步增强算法的全局搜索能力, 融入动态随机差分变异策略; 最后, 为了平衡探索与开采能力, 搜索前期采用单维操作, 搜索后期采用全维操作, 实现两种操作的优势互补.为了验证ODGWO处理高维和复杂优化问题的能力, 测试其在30维、50维和1 000维的高维函数优化和FCM聚类优化的性能, 结果表明, 与GWO以及多个state-of-the-art算法相比, ODGWO在高维函数优化问题上取得了较好的结果, 并能更好地处理FCM聚类优化问题.

1 灰狼优化算法

GWO是受灰狼群的社会等级和狩猎行为启发而提出的算法[1, 11].在自然界中, 灰狼群的社会等级分为4个级别, 由上至下依次为α狼、β狼、δ狼和ω狼.狼群的狩猎行为主要分为3个步骤, 分别是跟踪并靠近猎物、追踪包围猎物和攻击猎物.包围行为的数学模型为

(1)
(2)

其中: t为当前迭代标示; AC为系数向量, 其具体取值见文献[1]; XXp分别为灰狼和猎物的位置向量.攻击猎物行为的数学模型为

(3)
(4)
(5)
(6)

其中:式(3)~(5)分别给出了ω狼与α狼、β狼、δ狼之间的距离, XαXβXδ分别表示α狼、β狼和δ狼的位置向量; 式(6)给出了ω狼的位置更新方式, 两个参数AC在灰狼狩猎过程中起着关键作用, 共同决定了GWO的探索与开采阶段[11].当|A|>1时, GWO更强调探索能力, 当|A| < 1时, GWO更强调开采能力, C的取值是为了能随机增加(|C|>1)或减轻(|C| < 1)灰狼靠近猎物的难易程度.

算法1  GWO伪代码.

1) 随机初始化N头灰狼的位置, 初始化参数AC

2) 计算每头灰狼的适应度值

3) 初始化Xα, Xβ, Xδ, 且令t=0

4) while t < MaxDT

5) for i to N do

6) 按照式(3)~(6)更新第i头灰狼的位置

7) end for

8) 计算每头灰狼的适应度值

9) 贪心算法更新Xα, Xβ, Xδ并保存, 更新AC

10) t=t+1

11) end while

12) return Xα

GWO伪代码如算法1所示, 其中t表示当前迭代次数, N表示种群大小, MaxDT表示最大迭代次数.

用GWO与粒子群优化算法(PSO)进行对比, GWO具有以下优势: 1)搜索方式独特, 所有灰狼均依赖3头不同位置的最优灰狼更新其位置, 即所有灰狼朝着3个最优点趋近, 而PSO中所有粒子向着两个最优位置趋近, 故在解决一些简单优化问题时, GWO比PSO具有更好的全局搜索能力. 2)探索与开采平衡方式不同, GWO采用AC两个参数向量进行平衡, 故能够获得更快的收敛速度和更强的局部搜索能力[1]. 3)每次迭代只保留更新后的α狼、β狼和δ狼, 而PSO保留N个历史最优位置向量和速度向量, GWO具有更低的空间复杂度. 4) PSO采用迭代贪心算法进行更新, 迭代贪心算法指的是每次得到一个新解之后, 对其计算适应度值, 将新解与原解进行对比, 新解优于原解则替换原解, 加快了收敛速度, 一般更适用于单峰优化问题, 但对于多峰优化问题, 会使算法易陷于局部最优. GWO更新所有灰狼位置之后才计算其适应度值, 然后采用贪心算法更新α狼、β狼和δ狼的位置.与迭代贪心算法相比, GWO的贪心算法使得适应度值的计算可采用并行计算方式以便提高运行速度. 5) GWO原理简单, 参数少, 易于操作和实现.另外, 与采用单维操作的人工蜂群算法[12]相比, GWO采用全维操作更新灰狼位置等, 具有较高的搜索效率.

2 改进的灰狼优化算法(ODGWO) 2.1 GWO存在的问题及改进的动机

主要问题:由式(6)可知, ω狼在α狼、β狼和δ狼的带领下更新自身位置, 当α狼、β狼和δ狼均处于局部最优时, 狼群中的每一头狼因受这3头狼的影响, 有可能趋近于局部最优, 种群多样性降低; 因此, GWO在解决复杂优化问题时, 易陷于局部最优, 全局搜索能力不足.

为解决该问题, ODGWO在GWO上进行了一系列改进: 1)为避免算法陷入局部最优和增加全局搜索能力, 引入新型的反向学习策略. 2)为进一步增加全局搜索能力, 动态融合随机差分变异策略, 借助差分变异增加种群的多样性. 3)依据现代智能优化理论, 在处理优化问题时, 需追求探索和开采的平衡.因此, 在算法搜索前半阶段采用有助于探索的单维操作, 后半阶段采用有助于开采的全维操作, 以平衡探索和开采, 且能够做到单维和全维操作的优势互补, 从而从整体上提升算法的优化性能.

2.2 最优最差反向学习策略

Tizhoosh[13]在2005年提出反向学习的概念, 其目的在于避免算法陷入局部最优.许多改进的优化算法引入了反向学习策略, 如文献[5]将精英反向学习策略融入到GWO中.本文提出了一种最优最差反向学习策略, 并嵌入到GWO中.

最优最差反向学习策略是将一般反向学习机制与随机反向学习机制相融合.主要思想是寻找狼群中的某一可行解的反向解[14], 从而更好地引导狼群寻找到全局最优解.当GWO陷入局部最优时, 当前种群中的最优灰狼得不到有效的更新, 因此对其采用一般反向学习机制, 即

(7)

其中: Xbest表示当前全局最优灰狼位置向量, ab分别表示灰狼位置下边界向量和上边界向量.

为增加最差灰狼的全局搜索能力, 采用随机反向学习机制, 即

(8)

其中: Xworst表示当前全局最差灰狼位置向量, rand表示在区间[0, 1]中的均匀分布随机数.

与文献[5]中精英反向学习策略相比, 最优最差反向学习策略主要有如下特点:

1) 执行对象不同.精英反向学习策略的执行对象是当前种群中前m个精英个体, 而本文中一般反向学习策略和随机反向学习策略的执行对象分别是当前种群中的最优灰狼和最差灰狼(两个个体).原因在于最优灰狼若陷入局部最优, 则可能引导其他灰狼陷入局部最优, 因此采用一般反向学习策略使其有机会跳出局部最优; 而最差灰狼处于最差的位置, 因此采用随机反向学习得到一个反向最差灰狼的随机位置, 更加提高了种群的多样性, 增加了获得全局最优解的概率.采用两个个体进行反向学习既有利于避免算法陷于局部最优, 又不至于影响收敛速度, 因为过多的个体采用反向学习虽然能增加种群的多样性, 但会影响局部搜索能力.

2) 参数含义不同.精英反向学习策略中的ab值分别表示m个精英个体位置每一维上的最小值和最大值, 每次迭代需要计算它们, 如此增加了计算复杂度.而本文反向学习策略中的ab值分别表示灰狼种群位置的下边界和上边界, 每次迭代不变, 无需计算.

3) 无参数调整.精英反向学习需要确定精英个数m, 需要在实验中多次调整, 而本文的新型反向学习策略无需设置参数.

2.3 动态随机差分变异策略

为进一步解决GWO在解决复杂优化问题时全局搜索能力不足的问题, 在2.2节的基础上又融入一种新型的差分变异策略, 即动态随机差分变异策略.这种策略来自于差分进化算法的典型差分变异思想[4], 先随机选择不同的3个个体, 然后缩放2个个体的差分向量, 随后将缩放的差分向量与第3个个体结合以实现差分扰动, 以便增强全局搜索能力.本文首先采用如下所示的差分变异策略:

(9)

其中: Xr1Xr2Xr3是从狼群中随机选择的3头灰狼的位置向量, 满足r1r2r3∈[1, N], 且r1r2r3i.为进一步增强全局搜索能力, 采用随机缩放参数, 形成随机差分变异策略, 即设置缩放因子为随机值F=0.5+0.5 rand.

将随机差分变异策略与GWO搜索方式交替执行, 实现了动态随机差分变异策略.

算法2  随机差分变异策略与GWO的动态融合.

1) if rand < Pd

2) 按照式(9)执行随机差分变异策略

3) else

4) 按照式(3)~(6)执行GWO的更新策略

5) end

其中: Pd是随机差分变异策略的选择概率, 其值采用从1到0的线性动态递减方式, 即

(10)

由式(10)可知, 搜索前期Pd的值较大, 主要采用随机差分变异策略, 有利于提高探索能力; 在搜索后期Pd的值较小, 主要采用GWO的搜索方式, 有利于提高开采能力.由算法2可知, 与GWO更新方式(式(3)~(6))相比, 随机差分变异策略仅使用式(9)进行位置更新, 其更新表达式简单, 计算量较小, 故计算复杂度较小.算法2是两种策略的动态融合, 故与GWO相比, 从整体上算法2降低了计算复杂度.

动态随机差分变异策略有如下主要特点: 1)其执行对象是当前种群中除最优灰狼和最差灰狼之外的所有灰狼, 而不是当前种群中的全部个体. 2)随机差分变异策略与GWO搜索方式以概率Pd随机选择形式交替进行, 有利于提高优化性能. 3)差分变异策略采用随机缩放参数F, 无需人为的调整, 可操作性增强; 且由于F的随机性, 从而整体上增加了种群多样性, 进一步增强了算法的全局搜索能力.

2.4 单维和全维分段操作

为了平衡算法的探索与开采能力, 根据算法的迭代次数将搜索过程分为两个阶段, 前半搜索阶段(即迭代次数的取值范围为[1, MaxDT/2])采用单维操作, 后半搜索阶段采用全维操作.文献[12]对单维和全维操作的优化性能进行了对比实验, 结果表明单维操作的优势在于:具有较高的种群多样性, 有助于提高算法的全局搜索能力, 且单维操作是解决不可分优化问题的一种有效操作.但是, 单维操作具有以下缺陷:1)因只选择一维进行更新, 故搜索效率相对较低; 2)因随机性较强, 收敛速度较慢.全维操作的优势在于:对全部维度进行更新, 搜索效率较高, 收敛速度较快.因此, 本文提出了单维与全维分段操作的方式.算法的前半搜索阶段更强调全局搜索能力, 因此采用单维操作.单维操作即在当前灰狼的位置向量上随机选择一维执行更新操作.为了弥补单维操作的缺陷, 在后半搜索阶段更需强调开采能力, 即采用全维操作进行优势互补.全维操作即对当前灰狼的位置向量的每一维都进行更新操作.

将最优最差反向学习策略和动态随机差分变异策略融合到GWO中, 并在算法前半搜索阶段采用单维操作, 后半搜索阶段采用全维操作, 如此构建ODGWO, 其算法流程如图 1所示.

图 1可以看出: 1)在算法中嵌入最优最差反向学习策略和动态随机差分变异策略, 增加了种群多样性, 有利于避免算法陷入局部最优, 从而提高全局搜索能力; 2)采用单维全维分段操作, 有助于更好地平衡探索与开采能力和两种操作的优势互补; 3)保留了GWO的优势, 即收敛速度快和所有个体更新过后再计算适应度值, 这种方式有助于并行计算目标函数值以提高运行速度.

图 1 ODGWO流程
3 函数优化仿真实验及结果分析

为了验证ODGWO的性能, 本节采用两组实验:实验1是ODGWO在24个30维和50维Benchmark函数上的优化实验; 实验2是其在10个1 000维Benchmark函数上的优化实验.实验环境采用Windows 7操作系统, 3.10 GHz CPU和4 GB内存的PC, 编程语言为Matlab R2014a.

3.1 在30维和50维函数上优化性能比较 3.1.1 测试函数及对比算法

表 1给出了24个Benchmark函数的信息, 包含6个单峰函数(f1~f6)、6个多峰函数(f7~f12)、6个平移函数(f13~f18)和6个旋转函数(f19~f24), 其中Range表示函数定义域, Fmin表示函数的理论最优值.单峰函数用于评估算法的开采能力, 多峰函数用于评估算法的探索能力, 平移和旋转函数用于评估算法解决复杂优化问题的能力.本节选取GWO[1]和6种state-of-the-art算法(GWOepd[2]、MEABC[15]、CSPSO[16]、SinDE[17]、RLPSO[18]和DELLU[19])作对比. MEABC(Multi-strategy ensemble ABC)是一种多策略集成的人工蜂群算法. CSPSO(PSO using crisscross search)是一种改进粒子群算法:交叉搜索的粒子群优化算法. SinDE (Sinusoidal differential evolution)是正弦差分进化算法, 该算法使用新的正弦表达式来自动调整差分进化算法主要参数(缩放因子和交叉概率)的值, 从而促进算法探索能力与开采能力之间的平衡. RLPSO (Reverse-learning and local-learning PSO)是一种具备反向学习和局部学习能力的粒子群优化算法. DELLU (Differential evolution algorithm based on local lipschitz underestimate supporting hyperplanes)是在差分进化算法的框架下, 结合Lipschitz估计理论提出的一种基于局部Lipschitz下界估计支撑面的差分进化算法.

表 1 Benchmark测试函数信息表
3.1.2 与GWO、GWOepd、MEABC、CSPSO和SinDE性能对比

为了公平起见, 对GWO、GWOepd、MEABC、CSPSO、SinDE和ODGWO设置相同的基本参数:种群大小N=20, 独立运行次数Num=30, 当维度D =30时最大迭代次数MaxDT=2 500, 当D=50时MaxDT=3 500, 其他参数设置同其相应的参考文献.同时, 为更好地显示ODGWO与5种对比算法之间的差异性, 本文采用Wilcoxon符号秩和检验法[20]进行差异性检验. Wilcoxon符号秩和检验法主要采用成对检验, 目的在于检验两个算法之间的显著性差异. 表 2表 3分别给出了6种算法在24个Benchmark函数上30维和50维的结果对比以及ODGWO与5种对比算法之间的Wilcoxon符号秩和检验结果.其中包含均值(Mean)、标准差(Std)及排名(Rank), 排名依据为:均值越小, 排名越高, 如果均值相同, 则标准差越小排名越高; 如果二者相同, 则排名相同.最优者用下划线标注. “n/w/t/l”分别表示测试的函数个数、ODGWO优于(win)对比算法的函数个数、ODGWO等于(tie)对比算法的函数个数和ODGWO劣于(lose)对比算法的函数个数.置信水平α=0.05.

表 2 6种算法在30维函数上的优化结果
表 3 6种算法在50维函数上的优化结果

表 2的实验结果可知, 与GWO相比, ODGWO在10个Benchmark单峰和多峰函数上的优化结果均优于GWO, 且在函数f7f11上ODGWO与GWO获得相同的结果.从均值和标准差来看, 在单峰函数上, GWO在5个函数上的均值仅次于ODGWO, 并且优于其余4种对比算法, 说明GWO的局部搜索能力强于4种对比算法, 即开采能力较强.但在多峰函数上, GWO仅在函数f7f11上与ODGWO同时取得排名第1, 其他多峰函数上的均值劣于ODGWO, 说明GWO的全局搜索能力有待提高.在平移和旋转函数上, ODGWO的优化性能大幅度领先, 尤其在f16f17f19~f23上, ODGWO的结果优势明显, 这也说明GWO解决复杂优化问题的能力较差, 表明了在GWO中引入新型搜索策略是必要的.由Wilcoxon符号秩和检验结果可知, ODGWO优于、等于和劣于GWO的个数分别是22、2和0, 说明ODGWO在24个函数上表现出的优化性能明显优于GWO.与GWOepd、MEABC、CSPSO和SinDE相比, 从排名来看, ODGWO获得了19次第1名, GWOepd、MEABC、CSPSO和SinDE分别获得3次、3次、2次和0次第1名, 表明ODGWO在30维的Benchmark函数上具有较好的优化性能.由Wilcoxon符号秩和检验结果可知, ODGWO优于GWOepd、MEABC、CSPSO和SinDE的个数分别为21、21、22和22, 说明ODGWO在24个函数上明显优于这4种对比算法.

表 3的数据可知, 与GWO相比, 从均值和标准差来看, ODGWO得到与30维类似的结果.由Wilcoxon符号秩和检验结果可知, ODGWO优于、等于和劣于GWO的个数分别是21、1和2, 同样说明ODGWO在50维函数上明显优于GWO.与GWOepd、MEABC、CSPSO和SinDE相比, 在单峰和多峰函数上, ODGWO在函数f1~f5f11f12上表现出了最好的优化性能, 得到了理论最优值0.在平移和旋转函数上, ODGWO在函数f19f22上表现出了最优的性能, 取得了理论最优值0.在函数f16f17f20f23上, ODGWO虽然没有取得最优值0, 但是其优化性能远远优于其他4种算法.从排名来看, ODGWO共获得15次第1名, GWOepd、MEABC、CSPSO和SinDE分别获得3次、3次、4次和0次第1名, 说明ODGWO在50维Benchmark函数上同样具有较好的优化性能.由Wilcoxon符号秩和检验结果可知, ODGWO优于GWOepd、MEABC、CSPSO和SinDE的个数分别为21、21、18和23, 也说明ODGWO在24个函数上明显优于这4种优秀的对比算法.

另外, 由表 2表 3可以看出, 因f6是不可分函数, 只有采用单维处理的MEABC和ODGWO获得了较好的结果, 足以证明单维操作在此类优化问题上的优势所在.由Wilcoxon符号秩和检验结果可知, 无论是在30维还是在50维, P-value值均小于0.05, 说明ODGWO与5种对比算法之间存在显著性差异.

总的来说, ODGWO在不同维度的4种类型Benchmark函数上获得了较为满意的结果, 验证了ODGWO能很好地解决GWO存在的问题, 同时表明了本文提出的最优最差反向学习策略、动态随机差分变异策略以及单维全维分段操作是有效的.

3.1.3 运行时间对比及时间复杂度分析

为了考查ODGWO的运行速度, 对GWO、SinDE、GWOepd、MEABC、CSPSO和ODGWO的运行时间进行了测试, 图 2给出了这6种算法在30维和50维上的平均运行时间结果(单位s).

图 2可以看出, 在30维和50维两种情况下ODGWO的耗时最少, 运行速度最快, 其在30维函数上的平均耗时分别是GWO、GWOepd、MEABC、CSPSO和SinDE的52 %、48 %、26 %、48 %和27 %, 在50维函数上的平均耗时是其他算法的1/3至1/2.

图 2 30维和50维平均运行时间对比

对ODGWO的计算复杂度进行分析.一般而言, 算法的计算复杂度主要体现在两个方面:目标函数的计算复杂度和算法本身的计算复杂度.以一次迭代为例, ODGWO的运行速度快的原因主要有两个: 1)虽然6种算法的最大函数评价次数(maxFEs)相同, 但SinDE和MEABC采用了串行目标函数评价方式, 在每得到一个新种群位置之后就对其进行目标函数评价, 这样串行的评价方式较为耗时; 而ODGWO使用了并行目标函数评价方式, 对N个新解同时进行目标函数评价, 从而提高了运行速度, 节省了运行时间; 2) GWO、GWOepd和CSPSO虽然也采用了并行的函数评价方式, 但算法的整个搜索阶段采用了全维操作, 当对某一候选解向量进行更新时, 需要通过循环更新其中的每一维, 其时间复杂度为O(D), 运行时间相对稍长.另外, ODGWO采用算法2的搜索方式, 正如2.3节所述, 算法2的计算复杂度少于GWO和GWOepd.而ODGWO在前半搜索阶段采用单维操作, 当对某一灰狼的位置向量进行更新时, 只更新其中的一维, 其时间复杂度为O(1). MEABC虽然也采用了单维操作, 但正如原因1)所知, MEABC采用了串行的目标函数评价方式, 且采用多种策略协同处理, 所以MEABC的运行时间较长.虽然ODGWO的更新方式融入了随机差分变异策略, 增加了一些判断和计算步骤, 但没有额外增加循环步骤, 而对算法的一半搜索阶段使用单维操作和目标函数并行计算使计算复杂度大幅度降低, 从而整体上节省了算法的运行时间.上述分析也验证了图 2平均运行时间的对比结果.

3.1.4 与RLPSO和DELLU性能对比

为了进一步验证ODGWO的性能, 将其分别与RLPSO[18]和DELLU[19]进行对比. RLPSO与ODGWO均使用了反向学习策略, DELLU与ODGWO均采用了差分变异方式更新种群, 选用这两种算法进行对比是因为它们具有较强的可比性. RLPSO和DELLU的实验数据分别取自于文献[18]和文献[19], 由于不同文献使用的函数测试集不同, 只取ODGWO与这两种算法共同的测试函数上的结果进行对比.为使结果对比可靠, 保证ODGWO的maxFEs总是小于两种对比算法, 即ODGWO优化条件更苛刻.它们在30维函数上的结果对比如表 4所示, 其中表 4的第1行括号中的数据是对应的maxFEs, NA表示相应的参考文献没有提供该数据.

表 4 ODGWO与RLPSO、DELLU的结果对比

表 4可以看出, 与RLPSO相比, 在ODGWO的maxFEs更少的前提下, 其在所有函数上的优化性能大幅度优于RLPSO.与DELLU相比, 在maxFEs更少的前提下, 除了在f9上ODGWO的结果稍差于DELLU, 在其他9个函数上, ODGWO的结果明显优于DELLU.这说明将动态随机差分进化策略和最优最差反向学习方案等有机融合到GWO中是有效的, 既发挥了差分变异和反向学习增强全局搜索能力的优点, 又承袭了GWO较强的局部搜索能力的优势.

3.2 在1 000维函数上优化性能比较

为了验证ODGWO在更高维函数优化上的性能, 本节给出了ODGWO在1 000维Benchmark函数上的优化测试结果.选取文献[5]中的GWO、HGWO、GSA、PSO的实验数据直接作为对比数据, 为公平起见, 设置ODGWO与文献[5]中的maxFEs相同, 均为5e+04, 独立运行次数相同Num=30, 10个相同的Benchmark函数.在这4种对比算法中, HGWO和ODGWO中均嵌入了反向学习策略, 同为GWO的改进算法, 更具有可比性.

表 5给出了ODGWO与GWO、HGWO、GSA和PSO在1 000维的优化结果对比.由表 5可知:与GWO相比, ODGWO在10个1 000维函数上的优化结果更优; 与最先进的GWO改进算法HGWO相比, 在除f10外的9个函数上, ODGWO取得了更好的结果, ODGWO也大幅度优于经典的GSA和PSO.综上所述, ODGWO适用于求解高维函数的优化问题, 也说明本文对GWO的改进是可行的.

表 5 5种算法在1 000维函数上的优化结果
4 在FCM聚类优化上的应用

FCM聚类采用模糊目标函数的值来评估聚类结果[10].当模糊目标函数值达到最小值时, 聚类中心和隶属度最优, 即模糊目标函数的值越低表示聚类效果越好.模糊目标函数表达式如下:

(11)

其中: U表示模糊隶属度矩阵, uij表示第i个数据点属于第j个聚类的隶属度, vi表示第i个聚类中心, “C”和“N”表示将N个点划分为C个簇, m表示加权指数, ||xj-vi||表示第i个聚类中心与第j个数据点之间的欧几里德距离.将ODGWO用于FCM聚类优化, 就是将式(11)作为目标函数.

FCM通过不断迭代求解模糊目标函数的最小值, 每次迭代中使用下式计算隶属度和聚类中心:

(12)
(13)

本文采用7组标准数据集进行聚类优化测试, 选取GWO[1]、GWOepd[2]和LGWO[6]作为对比算法. 7组数据集直接来自于UCI机器学习数据库(http://archive.ics.uci.edu/ml). 4种算法的参数设置相同:种群大小N=20, 独立运行次数Num=30, 最大迭代次数MaxDT=100. 表 6给出了数据集的相关说明以及4种算法在不同数据集上的聚类优化结果.其中: Mean表示一种算法独立运行Num次获取最小目标函数值的平均值, Std表示标准差, Time表示平均时间, 首列数据集名称下面括号中的数据分别表示样本数、属性数和类数.

表 6 FCM聚类优化的结果对比

表 6可知, ODGWO在7个数据集上均获得了最优的Mean值和Std值, 虽然在Newthyroid和Iris上ODGWO的运行时间比GWO略长, 但ODGWO在其他5个数据集上的运行时间总是最少.综合而言, ODGWO的聚类优化效果优于3种对比算法, 且运行速度较快.

综合高维函数和聚类优化的结果, ODGWO的性能优于各组的对比算法, 说明本文提出的ODGWO是有效的, 在高维函数优化上取得了较好的结果, 能够有效地处理FCM聚类优化问题.

5 结论

针对GWO在解决高维和复杂优化问题时存在的全局搜索能力不足的问题, 提出了一种新型反向学习和差分变异的GWO(ODGWO).首先, 引入最优最差反向学习策略增加种群的多样性, 通过对最优灰狼使用一般反向学习机制, 对最差灰狼使用随机反向学习机制, 提升了算法的全局搜索能力; 然后, 引入动态随机差分变异策略, 进一步增强了全局搜索能力; 最后, 在算法前半搜索阶段使用单维操作, 后半搜索阶段使用全维操作, 很好地平衡了算法的探索与开采能力和使两种操作优势互补, 从而整体上提升了算法性能.在30维、50维和1 000维Benchmark函数及7个数据集聚类上的优化结果表明, 本文对GWO的改进是有效的, 其性能大幅度优于GWO, 与state-of-the-art算法相比, 在整体上具有更好的优化性能, 不仅适用于高维函数优化, 而且能够有效处理FCM聚类优化问题, 可望用于其他实际的优化问题.另外, 本文提出的最优最差反向学习与动态随机差分变异两种策略和单维与全维分段操作方式可推广到其他优化算法的改进中.

参考文献
[1]
Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61. DOI:10.1016/j.advengsoft.2013.12.007
[2]
Saremi S, Mirjalili S Z, Mirjalili S M. Evolutionary population dynamics and grey wolf optimizer[J]. Neural Computing and Applications, 2015, 26(5): 1257-1263. DOI:10.1007/s00521-014-1806-7
[3]
Zhang S, Zhou Y. Grey wolf optimizer based on powell local optimization method for clustering analysis[J]. Discrete Dynamics in Nature & Society, 2015, 2015: 1-17.
[4]
Jayabarathi T, Raghunathan T, Adarsh B R, et al. Economic dispatch using hybrid grey wolf optimizer[J]. Energy, 2016, 111: 630-641. DOI:10.1016/j.energy.2016.05.105
[5]
龙文, 蔡绍洪, 焦建军, 等. 求解高维优化问题的混合灰狼优化算法[J]. 控制与决策, 2016, 31(11): 1991-1997.
(Long W, Cai S H, Jiao J J, et al. Hybrid grey wolf optimization algorithm for high-dimensional optimization[J]. Control and Decision, 2016, 31(11): 1991-1997.)
[6]
Heidari A A, Pahlavani P. An efficient modified grey wolf optimizer with lévy flight for optimization tasks[J]. Applied Soft Computing, 2017, 60: 115-134. DOI:10.1016/j.asoc.2017.06.044
[7]
Zhang X M, Kang Q, Cheng J F, et al. A novel hybrid algorithm based on biogeography-based optimization and grey wolf optimizer[J]. Applied Soft Computing, 2018, 67: 197-214. DOI:10.1016/j.asoc.2018.02.049
[8]
Emary E, Zawbaa H M, Grosan C. Experienced gray wolf optimization through reinforcement learning and neural networks[J]. IEEE Trans on Neural Networks and Learning Systems, 2018, 29(3): 681-694. DOI:10.1109/TNNLS.2016.2634548
[9]
Long W, Jiao J J, Liang X M, et al. An exploration-enhanced grey wolf optimizer to solve high-dimensional numerical optimization[J]. Engineering Applications of Artificial Intelligence, 2018, 68: 63-80. DOI:10.1016/j.engappai.2017.10.024
[10]
Nayak J, Naik B, Behera H S, et al. Hybrid chemical reaction based metaheuristic with fuzzy c-means algorithm for optimal cluster analysis[J]. Expert Systems with Applications, 2017, 79: 282-295. DOI:10.1016/j.eswa.2017.02.037
[11]
张新明, 涂强, 康强, 等. 双模狩猎的灰狼优化算法在多阈值图像分割中应用[J]. 山西大学学报:自然科学版, 2016, 39(3): 378-385.
(Zhang X M, Tu Q, Kang Q, et al. Grey wolf optimization algorithm with double-hunting modes and its application to multi-threshold image segmentation[J]. J of Shanxi University: Natural Science Edition, 2016, 39(3): 378-385.)
[12]
Shi Y, Pun C M, Hu H, et al. An improved artificial bee colony and its application[J]. Knowledge-Based Systems, 2016, 107: 14-31. DOI:10.1016/j.knosys.2016.05.052
[13]
Ouyang H B, Gao L Q, Li S, et al. Improved global-best-guided particle swarm optimization with learning operation for global optimization problems[J]. Applied Soft Computing, 2017, 52: 987-1008. DOI:10.1016/j.asoc.2016.09.030
[14]
Wang H, Wu Z, Rahnamayan S, et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181(20): 4699-4714. DOI:10.1016/j.ins.2011.03.016
[15]
Wang H, Wu Z, Rahnamayan S, et al. Multi-strategy ensemble artificial bee colony algorithm[J]. Information Sciences, 2014, 279: 587-603. DOI:10.1016/j.ins.2014.04.013
[16]
Meng A, Li Z, Yin H, et al. Accelerating particle swarm optimization using crisscross search[J]. Information Sciences, 2016, 329(SI): 52-72.
[17]
Draa A, Bouzoubia S, Boukhalfa I. A sinusoidal differential evolution algorithm for numerical optimization[J]. Applied Soft Computing, 2015, 27: 99-126. DOI:10.1016/j.asoc.2014.11.003
[18]
夏学文, 刘经南, 高柯夫, 等. 具备反向学习和局部学习能力的粒子群算法[J]. 计算机学报, 2015, 38(7): 1397-1407.
(Xia X W, Liu J N, Gao K F, et al. Particle swarm optimization algorithm with reverse-learning and local-learning behavior[J]. Chinese J of Computers, 2015, 38(7): 1397-1407.)
[19]
周晓根, 张贵军, 郝小虎, 等. 一种基于局部Lipschitz下界估计支撑面的差分进化算法[J]. 计算机学报, 2016, 39(12): 2631-2650.
(Zhou X G, Zhang G J, Hao X H, et al. Differential evolution algorithm based on local Lipschitz underestimate supporting hyperplanes[J]. Chinese J of Computers, 2016, 39(12): 2631-2650. DOI:10.11897/SP.J.1016.2016.02631)
[20]
Derrac J, García S, Molina D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm & Evolutionary Computation, 2011, 1(1): 3-18.