融合头脑风暴思想的教与学优化算法
2020-09-29李丽荣王培崇
李丽荣,杨 坤,王培崇*
(1.河北地质大学艺术设计学院,石家庄 050031;2.河北地质大学信息工程学院,石家庄 050031;3.河北地质大学人工智能与机器学习研究室,石家庄 050031)
0 引言
教与学优化(Teaching & Learning Based Optimization,TLBO)[1-2]算法是Rao 等于2010 年提出的一种原理简单、高效的启发式算法。TLBO算法通过“教”和“学”两种操作模拟了一个自然教学班中种群学习进化的过程。由于其收敛性能较好且易于实现,已经成为了群智能算法中求解全局优化问题常用的算法之一[2-5]。虽然TLBO 在数字图像处理、背包问题、车间调度、聚类等多个领域得到了成功的应用,并展现了其优势,但也显现出了算法的诸多不足和弱点,如:在求解较高维度问题时,算法容易早熟、收敛速度较慢且解的精度较低等[4]。
为了提高算法的性能,克服TLBO 的弱点,国内外的专家和学者相继提出了多种改进机制。如:该算法的创始人Rao等[6]提出了一种基于精英思想的改进教与学优化(Elite TLBO,ETLBO)算法,应用精英个体适当替换种群内的劣质个体,提高算法的收敛速度,但是该算法往往会使种群的多样性降低较快,容易造成算法陷入局部最优。文献[7]中提出了一种约束教与学优化算法(Improved & Constrained TLBO,ICTLBO),该算法将种群初始划分为多个子种群,并通过种群的平均位置和子种群内最好位置之间的差异引导子种群的收敛方向,且在收敛过程中子种群间互相交换信息;在“学”阶段,还引入了个体的自我学习策略,来抑制算法的过早收敛。文献[8]中在研究对比蝙蝠算法和教与学优化算法的基础上,提出了一种融合局部搜索的混合蝙蝠教与学优化算法(TLBO with local search and BA,TLBO-RLS),该算法将蝙蝠算法的局部搜索机制集成在TLBO的优化过程中,并应用该算法成功解决了“Team workshop problem 25”问题。Zhang等[9]提出应用对数螺旋策略和三角变异策略的思想,来解决TLBO算法容易早熟的问题。算法在“教”算子中,引入对数螺旋策略学习机制,来加快算法的收敛;在“学”算子中,利用三角变异策略进一步提高当前个体的探索和开发能力。该算法被命名为LMTLBO(TLBO with LogarithMic spiral and triangular mutation)。针对ETLBO 算法中种群多样性降低过快的问题,于坤杰等[10]提出了一种基于反馈的精英教与学优化算法(Elitist Teaching-Learning-Based Optimization algorithm based on Feedback,FETLBO),该算法在“学”阶段中增加了劣质个体与教师个体间反馈交流的机制,抑制种群的过早收敛,并通过实验证明了算法的有效性。文献[11]中提出了一种具有自主学习行为的TLBO(Self -Learning TLBO,SLTLBO)算法。在该算法中,种群中的个体首先执行标准的“教”和“学”两个算子;然后,根据自己与种群内的最佳个体、最差个体之间的距离,自主完成多样性学习,并执行基于高斯搜索的反思式学习。
上述的众多改进机制虽然能够较好地改善TLBO的性能,但往往需要引入较多的额外算子或机制。为了改善TLBO算法在求解高维度问题时的能力,通过引入较少的算子克服其弱点,借鉴头脑风暴优化(Brain Storm Optimization,BSO)[12-14]产生新个体的方法,提出了一种融合头脑风暴机制的改进教与学优化(Improved TLBO with Brain Storm Optimization,ITLBOBSO)算法。将该算法在11个无约束标准测试函数和2个有约束工程优化问题上进行仿真实验,验证了算法的有效性。
1 教与学优化算法的改进
1.1 基于头脑风暴的“学”算子
头脑风暴优化算法是近年来热门的一个群智能算法,该算法模拟多人之间通过激烈的思想碰撞,从而产生出新方法或新策略的学习过程。从直观上看,基于人类创新思维过程的模拟一定程度上要优于其他受动物群居行为启发的群智能算法[15]。
教与学优化算法也是一种模拟人类集体学习行为的群智能算法,该算法具有两个算子,分别是最优个体向其余个体执行“教”和学生之间互相“学”。前者引导种群逐渐向最优个体所在空间收敛;后者赋予种群一定的发散能力,避免算法早熟。分析BSO和TLBO两个算法的基本原理并结合生活中的群体学习行为可知,群体内的个体通过思维碰撞提升自身状态的效果要明显优于个体间的相互“学”行为的效果。源于此,基于头脑风暴机制设计“学”算子,并替换标准TLBO算法中的“学”算子。借鉴文献[15]中的相关思想,该算子为式(1):
式(1)中的Xr视问题的性质取min(Xr1,Xr2) 或max(Xr1,Xr2),Xr1和Xr2为在种群内随机选择的个体。其他参数说明如下:
1)α∈[0.5,1)为随机数,β=1-α。当前个体Xi生成的新状态值取决于自身的原状态值,以及自身与Xr的差距。以上转换权重参数的设计是出于这样一种考虑:“在任何学习过程中,个体Xi都有保持自身状态的趋势”,可以较好地抑制算法早熟。
2)Cauch(0,1)为柯西函数。由于“教”算子使算法趋于收敛,所以在这里引入柯西函数,利用其较强的变异能力保证算法具有一定的发散性,以能够搜索更为广阔的空间。
3)δ由式(2)计算得到,其中rand(0,1)为(0,1)内的随机数,logsig(*)为对数sigmoid的传递函数,Tmax是算法的最大迭代次数,t为当前迭代次数,k是改变logsig(*)函数的斜率。多次实验表明,k适合在[0.3,0.6]取值。分析式(2)可知δ的范围为(0,1),且随着迭代次数自适应变化,该参数与柯西变异结合,有利于算法早期的探索和后期的开发。
1.2 算法步骤
算法1 ITLBOBSO。
输入:种群规模,迭代次数等参数;
输出:最佳个体Xt(t)。
步骤1 迭代计数器t=0,在解空间内随机生成种群pop(t)。
步骤2 计算全部个体的适应度,选择最优个体作为教师Xt(t)。
步骤3 执行“教”算子。
步骤4 执行式(1)的“学”算子。
步骤5 算法满足终止条件(精度要求或迭代次数满足),则输出最佳个体Xt(t),终止算法;否则转步骤2。
1.3 算法复杂度分析
设迭代次数为t,种群规模为n,分析ITLBOBSO算法,主要操作在步骤3和步骤4,两个步骤时间复杂度均是O(n),则算法的时间复杂度为O(t*n)。使用数组存储种群,则空间复杂度为O(n)。
2 仿真实验与分析
2.1 无约束函数测试
应用C 语言实现算法ITLBOBSO,选择11 个50 维的Benchmark 函数来测试该算法的性能,可接受解的目标精度为0.000 1。选择近年来较为经典的几个改进算法,如:ETLBO、TLBO-RLS、FETLBO、LMTLBO、DAEDTLBO[16]参与对比。ITLBOBSO 算法的种群规模d设为30,其中f1、f2、f3、f4、f5、f7、f8、f9的迭代次数为3 000,其余函数为5 000 次,斜率k=0.4。其他算法的参数设置参考各自文献。所有算法均独立运行30次,以消除随机性和其他因素的影响。
分析表1,函数f1、f2、f3、f4都是较易优化的函数,ITLBOBSO算法表现出了较好的求解能力,它在f1、f2、f3上的解均是最优的,在f4上的解略低于FETLBO 算法。稳定性的对比方面,ITLBOBSO算法在f4上略逊于FETLBO和LMTLBO,而在其他函数上则最优。函数f5为多峰,ITLBOBSO算法的表现略差,其解的质量和方差均较FETLBO和LMTLBO算法低了0.01个数量级,但仍然优于其他几个算法。f6的解空间非对称,对算法的搜索能力以及克服早熟的能力要求均较高,ITLBOBSO算法表现优异,无论是解精度还是解方差均超越了其他算法。在f7、f8两个测试函数上,ITLBOBSO表现仍然优秀,解的精度是最优的,但是在f8的方差上较FETLBO 和LMTLBO 低。在函数f9上ITLBOBSO、FETLBO、LMTLBO 三个算法的解精度相当,但是ITLBOBSO 算法的解方差要稍差。f10、f11是较难优化的多峰函数,存在多个局部极值点且解空间内存在陷阱,ITLBOBSO算法表现得较为一般,解的精度均较FETLBO和LMTLBO两个算法低,但是该算法的解方差与FETLBO、LMTLBO基本相当。
表1 无约束测试函数上的结果对比(均值/方差)Tab.1 Comparison of results on unconstrained benchmark functions(Mean/Std)
续表
表2列出了算法的成功收敛次数(S)、成功收敛所需迭代次数(I)和运算时间(t)。从表中数据可以看出,ITLBOBSO算法在所有函数上的收敛成功次数均非常高,只是在f6、f10、f11上要逊于FETLBO或LMTLBO算法。在成功收敛所需迭代次数对比方面,本文算法在函数f1、f2、f3、f4、f6、f7、f9、f10上均高于FETLBO和LMTLBO两个算法,在其他的几个函数上,ITLBOBSO的迭代次数均最少。观察对比算法的运算时间,ITLBOBSO和其他的算法均是互有胜负,但是大多数是较少的运行时间,表现比较优秀。取30次运算中最好的1次和最坏1次结果的均值,绘制了其中4个算法在f1、f2、f3、f4、f5、f6这6个函数上的收敛曲线,分别为图1(a)~(f)。从图中的结果可以看出,ITLBOBSO的收敛速度明显要优于另外3个算法,在较少的迭代次数内,适应度值快速下降,使种群快速集中于最优个体周围进行精细搜索。另外,从表1和表2中的数据可以看出ITLBOBSO解的精度以及收敛速度明显优于DAEDTLBO算法。
图1 算法的演化曲线对比Fig.1 Comparison of evolution curves of algorithms
表2 无约束测试函数上的结果对比(成功次数/迭代次数/时间)Tab.2 Comparison of results on unconstrained benchmark functions(successful number/iteration number/time)
续表
续表
在算法ITLBOBSO的早期,当前个体保持向最优个体收敛的趋势,同时由于受“学”算子的影响,个体也在不断搜索更为广阔的区域,避免种群过早地收敛到最优个体所在区域而使算法陷入早熟。在算法的后期,如果种群聚集在全局最优解所在区域,则个体会利用“学”算子保持自身状态,对所在区域进行精细搜索,提高算法的解精度。如果种群被局限于局部最优解所在区域,“学”算子中的柯西函数,也会赋予种群一定的变异能力,使个体逃离约束。综上所述,所提出算法的“教”和“学”算子可以很好地协调,保证种群全局搜索和局部勘探之间的平衡。
2.2 约束函数测试
为了测试算法在约束问题上的求解能力,选择工程中两个常见的优化问题:压力容器设计优化和张力弹簧问题[17]进行实验,两个问题的详细资料请参见文献[17]。
1)压力容器设计优化问题。
这是一个带约束复杂结构优化问题,追求的目标是最小化总成本(含:成型代价、材料代价和焊接代价)。Ts(x1)表示半球形风头厚度,Th(x2)为圆柱形压力容器的溶度,R(x3)是半径,L(x4)代表圆柱段长度。该问题的目标函数为式(3),约束条件为式(4):
其中:1×0.062 5 ≤x1,x2≤99×0.062 5,10 ≤x3,x4≤200。
将TLBO和ITLBOBSO 两个算法的种群规模设为50,独立运行30 次,取结果的平均值,然后与SzAPSO(PSO with Search space zoomed factor and attractor)、SAMGA(Self-Adaptive Migration model Genetic Algorithm)、GSDE(DE with Gaussian random walk and individual Selection strategies)等算法进行对比。结果分别列于表3和表4,表中所列其他算法的数据取自文献[17]。从表3 的数据可以看出,ITLBOBSO 算法求得的Ts(x1)、Th(x2)、R(x3)、L(x4)4 个分量以及在总成本上仅逊于GSDE 算法,明显优于其他参与对比的算法。但是,本算法的评价次数要比GSDE少很多。
表3 压力容器设计问题上的结果对比Tab.3 Result comparison of pressure vessel design
表4 压力容器设计问题中的约束函数值对比Tab.4 Constrained function values comparison in pressure vessel design
2)张力弹簧设计问题。
该问题也是工程上的经典优化问题,目标是在满足挠度、剪应力和振动频率等约束条件下,追求所设计的质量最小。它包含有3 个变量分别是:弹簧的线圈直径w(x1)、弹簧的平均直径d(x2)和弹簧的有效线圈数L(x3)。该问题的目标函数为(5),约束为(6),实验数据列于表5、6。
表5 算法在张力弹簧问题上的结果对比Tab.5 Result comparison of design of tension/compression springs
表6 弹簧设计问题的约束函数值对比Tab.6 Comparison of constrained function values in design of tension/compression springs
其中:0.05 ≤x1≤2,0.25 ≤x2≤1.3,2.0 ≤x3≤15.0。
从表5、6 的结果可以看出,ITLBOBSO 和GSDE 算法的表现要优于其他的算法,虽然在总代价上要稍逊于GSDE 算法,但是本算法所需的评价次数却要比GSDE 算法少很多,说明ITLBOBSO 算法既可以保证求解的精度,收敛速度也比较快。综合以上两个实验的对比结果,可知道在约束函数问题的优化上,ITLBOBSO算法具有较好的稳定性和精度。
3 结语
通过吸收BSO 算法中的优秀思想,将标准TLBO 中的“学”算子修改为基于头脑风暴讨论式的“学”算子,以期通过个体之间的思想碰撞实现种群内的信息交流和互相学习,提升种群的状态。在新的“学”算子中引入柯西变异机制,赋予个体跳出局部最优约束的能力。选择了11 个经典的Benchmark 函数和工程上的两个带有约束的优化问题进行了仿真实验。实验结果表明,改进算法的收敛速度、解精度和鲁棒性均较标准TLBO 有明显提升。TLBO 算法出现时间较短,也存在一些弱点,下一步将会深入研究该算法的演化原理,借鉴传统演化算法的优点实现优势互补。探索TLBO 算法新的应用领域也是主要的研究方向之一。