1. 引言
大数据时代的来临,使得工程系统中的计算模型越来越复杂,如何获得更高计算精度成为一个亟待解决的问题,优化算法则是解决的重要工具。经典优化算法的计算过程复杂,且对目标函数的性质有严格要求,并不适用于解决高维复杂的优化问题。智能优化算法因其操作简单,鲁棒性强,对解要求不高,且仅以目标函数为适应度值的特点,而比经典优化算法应用范围更广。
2005年土耳其学者Karaboga [1] 受蜂群个体之间分工和交流完成采蜜行为的启发提出了人工蜂群算法(Artificial Bee Colony, ABC)。与经典的优化算法相比,ABC算法对目标函数和约束几乎没有要求,操作简单,控制参数少,同时拥有较好的灵活性和鲁棒性,在解决一些优化问题上有得天独厚的优势。然而ABC算法存在局部搜索能力弱,收敛速度慢的缺点 [2],因此,学者们提出了各种不同方式的改进算法。反向学习(Opposition-Based Learning, OBL)策略是其中的一个改进手段,Tizhooshs和Pahnamayan等 [3] [4] [5] 已将反向学习用于遗传算法(Genetic Algorithm, GA),差分进化算法(Differential Evolution, DE)和粒子群算法(Particle Swarm Ootimization, PSO)等多种智能优化算法,并取得较好结果。王等在ABC算法的跟随蜂阶段采用依概率反向学习策略更新种群 [6]。
为进一步提高ABC算法的性能,本文提出了基于折射反向学习的人工蜂群算法。该算法在引领蜂阶段利用差分变异搜索策略生成候选解,在引领蜂阶段后,将扰动向量加入折射反向学习(Refracted Opposition-Based Learning, ROBL)策略 [7] [8] 生成折射反向种群。通过基准测试函数对所提算法的性能进行测试,同时与其他算法进行对比分析,以验证所采用改进策略的可行性和有效性。
2. 人工蜂群算法介绍
在ABC算法中,蜂群分为引领蜂,跟随蜂和侦察蜂3种类型,其中引领蜂和跟随蜂各占蜂群的一半,数量等于蜜源的数量,且每个蜜源同一时间内只有一只引领蜂采蜜 [9] [10] [11],蜜源位置表示候选解,蜜源i的质量用适应度fit表示。
1) 种群初始化。假设维空间D中,蜜源数量SN,蜜源被废弃的条件参数为limit,根据式(1)确定第i个蜜源的位置
。
(1)
其中,
为第i个蜜源的第j维的值,
和
分别表示
的最大值和最小值。每个蜜源位置相当于一个问题的可行解,可行解的适应度值
,可根据式(2)计算,同时,
是人工蜂群算法的目标函数值。
(2)
2) 引领蜂阶段。引领蜂采取“贪婪选择”将新旧蜜源适应度比较,当新蜜源优于旧蜜源时,将旧蜜源替换,否则保持不变。在进行邻域搜索时,根据式(3)由旧蜜源产生新蜜源
。
(3)
其中,
,
是随机选择的维度,
,
是
中是一个随机数,用来控制搜索范围。
3) 跟随蜂阶段。引领蜂通过跳摇摆舞将蜜源信息传递给跟随蜂。此时,跟随蜂通过轮盘赌的方式来选择开采的蜜源。适应度值大越能吸引蜜蜂跟随,跟随蜂开采的蜜源由概率
来确定。
(4)
跟随蜂选择的蜜源也将根据式(3)进行邻域搜索,同样采取贪婪选择。
4) 侦察蜂阶段。在搜索的过程中,如果蜜源经过trial次迭代搜索到达阈值limit后,还没更新为更好的蜜源,该蜜源就会被放弃。引领蜂转为侦察蜂,侦察蜂就会带领找到一个新的蜜源,侦察蜂找到的新的蜜源的位置根据式(1)随机生成。
3. 改进人工蜂群算法
ABC算法在处理单峰问题时,不能充分利用种群等信息来确定最有效的搜索方向;在求解复杂的多峰问题时,也很容易陷入局部最优 [12],这些缺点限制了ABC算法的更广泛应用,因此本文在引领蜂阶段和跟随蜂阶段进行改进,提出了基于折射反向学习的人工蜂群算法。
3.1. 反向学习策略
在智能优化算法中,需要在种群初始化和搜索过程中产生随机数以供使用,反向学习策略考虑随机性的同时,也考虑反向性 [3]。Rahnamayan在文献 [13] 中从理论和实验上证明了反向学习比纯随机产生的解更好,Wang [14] 提出了一种基于广义反向学习的新算法来提高差分进化算法的性能;暴励等 [15] 在改进ABC算法时利用反向学习产生初始解;毕晓君等 [16] 将基于反向学习的变异策略代替侦察蜂;杨小健等 [17] 用反向学习策略来改进引领蜂搜索阶段。其中,反向学习的相关定义如下:
定义1若x是定义在
上的实数,则x的反向解
定义如下:
(5)
定义2若
是定义在n维空间中的一点,且
,则
的反向解
定义如下:
(6)
反向学习机制的主要思想是:对所有解求其反向解,并在其中选取较优解参与到下次迭代。
3.2. 光的折射原理
几何光学将光的传播和成像简化,笛卡尔在《折光学》中首次公布了具有现代形式正弦之比的规律,邵等 [7] 将折射原理用于改进反向学习,并应用于改进粒子群算法,有效地改进了全局搜索能力,其中光的折射相关定义和定律如下:
定义3光从一种介质斜射入另一种介质时,传播方向发生改变,从而使光线在不同介质的交界处发生偏折,这种现象称为光的折射。如图1所示。
Figure 1. The phenomenon of refraction of light
图1. 光的折射现象
定律1折射光线,入射光线和法线在同一平面内;折射光线与入射光线分居法线两侧;当光从空气斜射入其他介质中时,折射角小于入射角;当光从其他介质中斜射入空气时,折射角大于入射角;折射角随着入射角的增大而增大;当光线垂直射向介质表面时,传播方向不改变,这时入射角与折射角均为0˚,称为光的折射定律。
定义4光从真空射入介质发生折射时,入射角
正弦值与折射角
正弦值的比值为一固定数值n,称为该介质的绝对折射率,简称折射率,公式表示如下:
(7)
式(7)又称为斯涅尔公式。
3.3. 折射反向学习策略
反向学习作为一种改进方式,在迭代初期可以提高算法的寻优能力,但在后期易陷入局部最优,导致收敛精度和速度变差。折射反向学习机制 [8] 是在反向学习的基础上引入光的折射原理来寻找最优解。折射反向学习的原理如图2所示。
在一维空间中,x轴上方表示真空,下方表示其他介质,x的搜索空间为
,y为法线。为描述折射反向学习机制做以下假设:在A点(入射点)有一光源,向O点发出入射光线AO,设AO的长度为l,由定义3与定律1可知,光线AO在O处发生折射现象,折射光线为OAr,Ar为折射点,设OAr的长度为
,入射角和折射角分别为
,
,O为区间
的中点。
定义5设入射点A在x轴的投影为x,入射光线发生折射后产生的折射点Ar在x轴的投影为
,称
为x的基于折射原理的反向解。
Figure 2. Refracted opposition-based learning mechanism
图2. 折射反向学习机制
由图2中各线段的几何关系可得:
(8)
(9)
由定义4与上两式可得:
(10)
令
,则上式可化为:
(11)
由(11)可得折射反向学习解的计算公式:
(12)
当
,
时,式(12)可化为式(5),ROBL可以通过调整参数k、n获得动态候选解,而OBL只能得固定解。实际上,由图1可知,入射光线在发生折射的同时,还会出现光的反射现象。当入射光线等于反射光线长度时,反射点在x轴的投影恰好是x的反向解
。由于优化问题都是多维的,折射反向解可按下式计算:
(13)
其中,
表示当前种群中第i个个体在第j维的值,
是求得的折射反向解,
和
表示第j维的最小值和最大值,动态边界更新有利于的到得到更好的解,加速收敛。
3.4. 基于折射原理的反向学习人工蜂群算法
3.4. 1. 差分变异搜索策略
Storn和Price [18] 为求解多项式问题提出了DE算法,它是模拟群体生物进化的一种随机模型,根据“适者生存”的原则,通过迭代得到最优解。DE算法需要进行变异和交叉操作,变异操作计算公式如下:
(14)
其中,V表示变异后的个体,F表示变异算子,
表示随机选择的三个个体。变异操作有不同的变体,不同的变异操作对算法性能产生不同影响。
引领蜂根据(2)进行位置更新时,在邻域中随机选择一个蜜源进行操作产生候选解,此种选择方式具有良好的全局搜索能力,忽略了局部搜索能力。在算法寻优过程中,希望尽可能向最优解靠近,因此引入当前最优解指导的差分变异搜索方程:
(15)
是
中是一个随机数,
是当前种群中最好个体的第j维的值。
3.4.2. 折射反向学习搜索策略
随着迭代的进行,差分变异搜索策略会降低种群多样性,也容易陷入局部最优,因此在引领蜂阶段后进行折射反向学习,产生当前种群的折射反向解,并在当前解和折射反向解中选择较优的作为下次迭代种群,此过程相当于在
个个体中选择出较优的SN个个体,在保证种群多样性的同时,可以提高跳出局部最优的概率,折射反向解计算方式如下:
(16)
其中,
表示当前种群中第i个个体在第j维的值,
表示为当前种群第j维的下限和上限,
表示
上的均匀分布随机数,计算公式如下:
(17)
其中,t表示当前迭代次数,T表示最大迭代次数。由式(16)可知,当k变化时,折射反向解的位置也会发生变化,所以可以通过调整k的值提高算法跳出局部最优解的概率,这里k是随着迭代次数的增加从0到2非线性递减,计算公式如下:
(18)
k随t的变化曲线如图3所示。n表示折射率,根据式(7)可知,实际跟入射角有关,但是在(16)中仅把n看作参数,n的不同取值对算法性能产生不同影响。
以二维空间为例,如图4所示,在式(16)中不考虑扰动向量
,即
,此时是一般的折射反向学习计算公式。当k,n都为1时,根据式(16)产生的反向解
距离最优解
较远,说明此时处于局部最优解区域;当k,n任一参数不为1时,产生的折射反向解
距离最优解
仍然较远,说明此时仍处于局部最优解区域;调整参数k,产生的折射反向解
向最优解靠近,说明调整参数可以帮助跳出局部最优,再对n进行调整,得到折射反向解
,此时距离最优解较近。
Figure 3. Variation curve of parameter k
图3. 参数k的变化曲线
一般的折射反向学习产生的折射反向解不能利用折射反向解所在邻域的信息,因此通过加入扰动向量
扩大搜索邻域,有助于跳出局部最优,这样产生的折射反向解在保证种群多样性的基础上,利用一般折射反向学习信息。在图4中阴影部分表示加入扰动向量
后,反向解或折射反向解所在的区域,通过随机扰动后得到折射反向解
,说明到达全局最优解
所在区域,经历多次迭代后。扰动向量
由h取值决定,在迭代初期,需要保持算法的全局搜索能力,因此h取值较大,随着迭代次数的增加,在全局最优解区域搜索时,需要提高算法精度,因此h取值变小,采用随机扰动的方式可以提高产生的折射反向参与下次迭代的可能性。
Figure 4. Two-dimensional space refraction of the reverse learning process
图4. 二维空间折射反向学习过程
综上所述,折射反向学习搜索策略是通过调整参数h,k,n的值来得到折射反向解,通过比较当前解与折射反向解的适应度值选出较优的个体组成新的种群参与到下一次迭代,在保证种群多样性的同时,使算法跳出局部最优到达全局最优区域。
3.4.3. 所提算法
综合上述策略对基本ABC算法改进后,得到的CRABC算法基本思想是:引领蜂阶段利用差分变异向最优解靠近;引领蜂阶段后进行折射反向学习,参数h和k随迭代次数而变化,随着迭代的增加,折射反向学习搜索范围逐渐变小,提高了算法的收敛速度和精度。CRABC算法实现流程如下:
Step 1设置算法参数:种群规模,最大迭代次数等,随机生成初始种群;
Step 2引领蜂根据式(15)搜索新的蜜源,根据贪婪选择对更好的蜜源进行替代;
Step 3根据式(16)生成折射反向种群,在当前种群与折射反向种群选择优秀的个体组成新种群;
Step 4根据式(3)计算引领蜂被跟随的概率;
Step 5根据轮盘赌规则选择跟随,并搜索一个新的蜜源,如果更好则替代;
Step 6如果一个蜜源在阈值limit内没有找到更好的蜜源,则被遗弃,侦察蜂根据式(1)产生新蜜源,去寻找更好的蜜源;
Step 7判断是否满足终止条件,若满足则停止,否则返回Step 2。
4. 实验与分析
4.1. 基准测试函数
为了验证CRABC算法在求解全局优化问题的性能,本文选择12个基准测试函数进行测试,基准测试维数为30维,表1给出了基准函数的序号,名称,类型,取值范围以及理论最优值。除F7理论最优值为−78.33236外,其他都为0, U, M分别表示单峰函数,多峰函数,S, N分别表示可分函数,不可分函数。
4.2. 参数设置
采用CRABC算法对12个基准测试函数求解,并与ABC算法、仅采用差分变异搜索策略的ABC算法(CABC)、仅加入折射反向学习搜索策略的ABC算法(RABC)进行比较,来验证综合两种策略后的RABC算法改进效果。
为了实验结果的公平性,将4种算法的参数设置一致。函数评价次数为100,000,最大迭代次数为1000,种群规模为100 (
),蜜源迭代阈值为
(dim表示函数维数),这与文献 [19] 设置一样,其中RABC算法与CRABC算法中的参数
,
,
,
。
4.3. 实验结果与分析
4.3.1. 算法精度结果分析
为减少随机性带来的误差,表2给出4种算法在相同环境下独立运行30次后12个基准测试函数的最优值,平均值,方差,最差值以及一次实验的平均时长,其中黑体表示最佳结果。平均值和方差能够反映算法的收敛精度和稳定性。
从表2中可以看出,对于12个30维的单峰基准测试函数(F1~F6)和多峰基准测试函数(F6~F12)除F4和F8外,RABC算法和CRABC算法的平均值和方差都优于ABC算法,且在F10上收敛到最小值,标准差也小于ABC算法。由于F4为Rosenbrock函数,在低维时是单峰函数,高维情形具有多个理论最优解,所以四个算法得到的结果相差不大;而对于F8,虽然CABC算法精度更高也更稳定,但是RABC算法和CRABC算法却可以找到理论最优值。综上所述,提出的两种策略对提升算法性能是有效的,尤其是在F8、F10、F12这三个函数找到了理论最优解。
表3给出了CRABC,RABC与文献 [20] 中提出的GABC (C = 1.5)算法和文献 [19] 提出的ABC/best/1算法在5个基准测试函数上进行比较,Sphere,Rastrigin,Ackley,Griewank这4个函数是在30维上测试,Rosenbrock函数在3维上测试,在Sphere,Griewank,Ackley,Rosenbrock这4个函数上CRABC算法最优,尤其是Griewank函数可以找到理论最优解。
4.3.2. 算法运行时间分析
ABC算法没有加入其他策略,而CABC算法只是在引领蜂阶段变化了搜索方程,所以这两种算法的运行时间差不多且少于RABC算法和CRANC算法;而RABC算法和CRABC算法引入了折射反向学习策略,耗时花费在折射反向学习,当前解与折射反向解比较上,所以在运行时间上要长于另两种算法,这也与表2中所列的30次平均运行时间吻合,由于运行环境影响,实验允许存在误差。
Table 2. Comparison of ABC, CABC, RABC and CRABC experimental results
表2. ABC, CABC, RABC与CRABC实验结果比较
Table 3. Comparison of GABC (C = 1.5), ABC/best/1, RABC and CRABC experimental results
表3. GABC (C = 1.5), ABC/best/1, RABC与CRABC实验结果比较
4.3.3. 相关参数确定和说明
1) 参数h和k的影响
在迭代初期,算法需要较好的全局搜索能力,因此h和k取值较大,相应的搜索范围也大,增加了找到潜在最优解所在区域的可能;随着迭代的进行,h和k取值变小,这样保证在折射反向解附近搜索;当h和k取值足够小时,折射反向解在当前解的足够小邻域内,提高了开发能力。
2) 参数n的影响
n实际表示折射率,跟入射角有关,在算法中仅将其看作一个参数,因此需要找到合适的n值,来保证算法性能。以F1为例,选取不同的n值做30次独立实验,取平均值。从表4可以看出,n取2时取值最优,过小会导致性能下降,因此,参数n取2。
Table 4. The test function value corresponding to the different values of parameter n
表4. 参数n的不同取值对应的测试函数值
4.3.4. 算法收敛分析
为进一步说明算法的收敛性,图5给出了4种算法在12个30维基准测试函数上的收敛曲线。从图中可以看出,RABC算法和CRABC算法在迭代初期就可以保持较高的收敛速度。对于F5这一非连续的单峰函数,RABC算法和CRABC算法可以在不到20次迭代找到最优值。对于F4,F6,F11这三个函数,可以看到RABC算法和CRABC算法的收敛曲线呈阶段式下降,这与参数h有关,h的变化使得搜索区域在最优解潜在区域更小的范围进行。F8,F10,F12在某次迭代后收敛速度迅速提升,这是因为折射反向学习能很快搜索到最优解的潜在区域。
通过分析表2和图5,可以得到结论:引入差分变异搜索策略和折射反向学习搜索策略的CRABC算法在总体上优于ABC算法以及两种单策略改进的ABC算法,能更好地平衡探索和开发能力,提高了算法收敛速度和精度。
Figure 5. Convergence curves of each algorithm
图5. 各算法收敛曲线
5. 结束语
本文将差分变异搜索策略和折射反向学习搜索策略引入ABC算法,提出了基于折射反向学习的人工蜂群算法(CRABC)。在引领蜂阶段,根据当前最优解来指导候选解生成;然后计算当前种群的折射反向解,并根据适应度值在折射反向种群和当前种群选择较好的个体参与下一次迭代。通过对12个基准测试函数以及实验研究,分析了算法的探索和开发能力,同时与GABC (C = 1.5)算法,ABC/best/1算法进行比较实验。结果表明:差分变异搜索策略和折射反向学习搜索策略对提高算法性能是有效的,CRABC算法的求解精度和收敛速度是有优越性的,未来可考虑用于求解实际优化问题。
基金项目
牡丹江师范学院国家级课题培育项目(GP2020003);国家自然科学基金项目(11871097);牡丹江师范学院科技创新项目(kjcx2020-009mdjnu)。
NOTES
*通讯作者。