改进萤火虫算法(精选9篇)
改进萤火虫算法 篇1
0 引言
多模函数又称多峰函数,指有多个峰值点的函数,这些峰值点可能相同,也可能不同。多模函数优化属于复杂优化问题,由于其广泛的应用技术背景,一直受到人们的关注。实际工作中,决策者需要对多模函数优化得到所有峰值,对这些峰值做出筛选,得到满意解[1,2]。萤火虫算法GSO是由印度学者Krishnanand和Ghose提出的一种群智能随机优化算法,该算法从仿生学角度出发,模拟自然界中的萤火虫发光特性,通过荧光素值大小相互吸引对方,达到彼此交流信息的目的[3]。GSO易于实现,操作简单,到目前为止,已经成功应用在多模函数优化[4,5]、机器人协同学习[6,7]、多信号源定位[8]等邻域。但是GSO存在峰值发现率低、收敛速度慢和求解精度不高的缺点[9],本文针对该算法存在的问题提出了改进萤火虫算法IGSO,实验结果表明IGSO一定程度上提高了峰值发现率、收敛速度和求解精度。
1 GSO算法
1.1 GSO算法描述
GSO在问题求解域中随机分布N萤火虫个体,每个个体带有定量的荧光素值,荧光素值和个体所在的位置相关,即荧光素值与函数值大小联系。首先,计算每个个体的荧光素值;然后,每个个体在感知范围内选择比自己荧光素值高的个体组成邻域集合,依概率选择邻域集合中的某个体,并且向该个体移动,其中个体的感知范围大小由感知半径确定;最后,更新感知半径,如果邻域集合较大,则感知半径减小,否则感知半径增大。重复这一过程,直到达到一定的迭代次数,这时所有的萤火虫个体都聚集在问题求解域一定的位置,也就是问题求解域中峰值的位置。概括起来,GSO算法可分为荧光素值更新、位置移动和感知半径更新三个步骤。
1.2 GSO算法存在的问题
GSO虽然实现简单,但是存在峰值发现率低、收敛速度慢和求解精度不高的缺点。在GSO中,每个个体有不同的搜索范围,这个范围称为感知范围,个体向峰值位置的移动依赖于感知范围内存在优秀个体,如果感知范围内不存在优秀个体,则个体位置不移动,这种搜索策略不能保证个体充分发挥自身的搜索能力,充分发掘潜在信息,对优秀个体的依赖程度太高,从而降低了收敛速度和峰值发现率,影响了算法的整体搜索性能,极端条件下,当所有个体的荧光素值大小相等时,GSO无法收敛到峰值。
而且,随着迭代次数的增加,个体聚集在峰值附近趋向收敛,此时个体与峰值之间的距离非常小,当这个距离小于步长时,个体的移动就会在峰值附近产生震荡,降低算法的收敛速度和求解精度。
2 IGSO算法
2.1 IGSO算法描述
下面列出所有公式:
IGSO在GSO基础上做了改进,旨在提高峰值发现率、收敛速度和求解精度。文献[10]提出在未找到优秀个体的前提下可以随机移动一个步长,若移动后的位置更优,则接受移动,否则不移动。受此启发,IGSO为了充分发挥个体的搜索能力,允许个体在没有找到优秀个体的条件下,根据式(3)在感知范围内尝试移动,若移动后的位置优于移动前的位置,则保存移动后的位置,否则保持原来位置不变。式(3)确保了随机移动发生在个体i的感知范围内,不会影响其他个体的邻域集合。
同时,为了减小峰值附近的震荡现象,IGSO不采用GSO步长固定的策略,而是把步长和个体邻域平均距离联系在一起,邻域平均距离表示邻域集合中该个体到其他个体的平均距离,当个体逐渐接近峰值时,邻域平均距离将逐渐减小。文献[5]提出随着迭代次数的增加减小步长,这种方法把步长和迭代次数联系起来,没有考虑个体邻域集合的差异,而是对所有个体相同对待,假设个体距离优秀个体较远,则步长应较大,反之应较小,但是,GSO的步长随着迭代次数的增加一直减小。IGSO的每个个体拥有各自的步长,个体i在向目标移动前按照式(5)计算邻域平均距离,如果邻域平均距离小于初始步长,则根据式(6)更新步长,然后向目标个体移动。
根据上述思想,本文提出的IGSO算法具体步骤如下:
1)设置所有个体的初始步长为s_init,迭代次数t=1,初始化感知半径和其他常量参数,并在问题求解域中随机分布N个萤火虫个体;
2)根据式(1)更新每个萤火虫个体的荧光素值,其中J表示多模函数表达式,ρ为荧光素挥发系数,γ为荧光素更新率(0<ρ<1,0<γ<1);
3)对个体i(i=1,2,…,N)执行:
3.1)根据式(2)计算个体i的邻域集合;
3.2)判断邻域集合是否为空,不为空转向3.3),否则根据式(3)更新个体i的位置,若更新后的个体荧光素值小于移动前,则取消更新,然后转向3.6);
3.3)根据式(4)计算个体j被选择的概率,以概率最大的个体作为移动目标;
3.4)根据式(5)计算个体i的邻域平均距离,若邻域平均距离小于初始步长s_init,则根据式(6)更新个体i的移动步长,否则移动步长不更新。
3.5)根据式(7)更新个体i的位置,j为式(4)计算的概率最大的个体;
3.6)根据式(8)更新个体i的感知半径;
4)t=t+1;
5)如果未达到指定的迭代次数,转向2),否则停止,输出结果。
2.2 IGSO算法特点
IGSO在感知范围内不存在优秀个体的条件下,仍然可以搜索峰值,从而降低对优秀个体的依赖程度,即个体可以在邻域集合为空的情况下做自适应搜索,发掘感知范围内潜在的信息,提高搜索峰值能力;同时,IGSO考虑了每个个体邻域集合分布的不同,个体以自身邻域平均距离与初始步长的比较结果为依据,选择适当步长,因此,IGSO萤火虫个体更加智能,适应性更强。
3 实验结果
程序运行环境为:Windows7 32位操作系统,Intel Core i3530 CPU处理器,主频2.93 GHZ,内存2 GB,集成环境Matlab R2007b。GSO和IGSO公共参数设置见表1所示,IGSO参数s_init=0.03,q=0.96,GSO步长s=0.03。IGSO和GSO的最大感知半径和初始感知半径都置为2。
3.1 实验用例
本文选取3个典型的多模测试函数分别对GSO和IGSO进行实验,实验用例及种群规模设置见表2所示。
Peaks函数:
Himmelblau函数:
Rastrigin's函数:
3.2 实验结果
(1)Peaks和Himmelblau测试函数进行20次独立实验,Peaks和Himmelblau分别有3和4个理论峰值。表3和表4分别列出各自其中一个峰值每100次迭代后的平均优化结果,峰值坐标分别为(0,1.58)、(3,2),其他峰值有相同的优化结果。由表3可见,GSO优化结果的精度并未随着迭代次数的增加而逐渐提高,而是在峰值附近出现了震荡;IGSO的优化结果随着迭代次数的增加,精度逐渐提高,300次迭代后,IGSO趋向收敛。表4的优化结果同样证明IGSO收敛速度和求解精度均优于GSO。
图1和图2表示GSO与IGSO的峰值发现率随迭代次数的变化,峰值发现率表示20次独立实验平均发现峰值数与理论峰值数的比值。由图1和图2可见IGSO的峰值发现率均高于GSO。
(2)Rastrigin's测试函数有100个理论峰值,本次实验参数设置同文献[5]。500次迭代后,IGSO发现了94个峰值,GSO发现了91个峰值。表5列出IGSO和GSO共同发现的10个峰值的优化结果,10个峰值的纵坐标关于x轴对称,对称坐标的峰值相等。由表5可见,GSO的优化结果不是对称相等的,还未完全达到收敛,IGSO的优化结果对称相等,达到收敛,且优化结果的精度均高于GSO。实验结果表明IGSO峰值发现率、收敛速度和求解精度均优于GSO。
3.3 IGSO和其他算法的比较
为了便于与其他算法进行比较,采用文献[2]Himmelblau函数为标准测试函数,范围[-6,6],Himmelblau函数有4个函数值相等的理论峰值点,分别标记为N1(3.0,2.0)、N2(3.58,-1.848)、N3(-2.805,3.131)和N4(-3.779,-3.283),独立进行20次实验,分别对IGSO、文献[2]和文献[11]提出的算法进行测试。IGSO迭代次数为500次,其他参数设置见表1和表2所示,文献参数设置不变。
表6列出了各个算法的优化结果,每个算法都发现所有峰值,但IGSO的迭代次数只有500次,萤火虫个数为50个,文献[11]的迭代次数达到了650次,萤火虫个数为200个。由表6可见,IGSO的每个优化结果相等,满足Himmelblau有4个相等理论峰值点的结论,而且,相比文献[2]和文献[11]的优化结果,IGSO的求解精度更高。实验结果表明IGSO的优化性能优于文献算法。
Himmelblau函数:
4 结语
本文针对GSO峰值发现率低,收敛速度慢和求解精度不高的缺点,提出了改进算法IGSO。IGSO个体比GSO自适应性更强,更加智能,寻找峰值不再高度依赖其他优秀个体,每个个体拥有不同的步长,并可根据实际的邻域分布情况调整步长,降低了GSO的震荡现象。经过多模函数测试,IGSO峰值发现率、收敛速度和求解精度均优于GSO和文献算法。接下来的工作主要是研究IGSO对高维多模函数的优化以及改进。
参考文献
[1]谭俊,康立山,陈毓屏.一种新的求解多峰函数优化问题的动态演化算法[J].计算机科学,2004,31(3):134 136.
[2]王湘中,俞寿益.多模态函数优化的多种群进化策略[J].控制与决策,2006,21(3):285 288.
[3]刘长平,叶春明.一种新颖的仿生群智能优化算法:萤火虫算法[J].计算机应用研究,2011,28(9):3295 3297.
[4]Krishnanand K N,Ghose D.Glowworm Swarm Optimization:A New method for Optimizing Multi-modalfunctions[J].International Journal of Computational Intelligence Studies,2009,1(1):93 119.
[5]Krishnanand K N,Ghose D.Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions[J].Swarm Intelligence,2009,3(2):87 124.
[6]Krishnanand K N,Ghose D.A Glowworm Swarm Optimization Based Multi-robot System for Signal Source Localization[M].Berlin,Germany:[s.n.],2009.
[7]Krishnanand K N,Ghose D.Chasing Multiple Mobile Signal Sources:A Glowworm Swarm Optimization Approach[C]//Proc of the 3rd Indian International Conference on Artificial Intelligence.IEEE Press,2007.
[8]Krishnanand K N.Glowworm Swarm Optimization:A Multimodal Function Optimization Paradigm with Applications to Multiple Signal Source Localization Tasks[D].Indian Institute of Science,2007.
[9]刘佳昆,周永权.一种最大最小荧光素值人工萤火虫算法[J].计算机应用研究,2011,28(10):3662 3664.
[10]Piotr Oramus.Improvements To Glowworm Swarm Optimization Algorithm[J].Computer Science,2010,11:7 20.
[11]黄正新,周永权.自适应步长萤火虫群多模态函数优化算法[J].计算机科学,2011,31(7):1084 1087.
改进萤火虫算法 篇2
给出不定二次规划的.一个改进算法,通过仿射尺度技术,把二次规划问题转化为球约束的二次规划问题,进而转化为球约束的凸二次规划问题来求解.讨论了该算法的收敛性.
作 者:杨春艳 雍龙泉 YANG Chun-Yan YONG Long-Quan 作者单位:杨春艳,YANG Chun-Yan(银川大学,数学系,银川,750105)
雍龙泉,YONG Long-Quan(陕西理工学院,数学系,陕西,汉中,723001)
改进萤火虫算法 篇3
背包问题最早由Dantzing于20世纪50年代提出,它是一种组合优化的NP完全问题。可以描述为:给定N种物品和一个背包,该背包的最大承受重量为W,每种物品均包含重量、数量、价值3个属性,如何取舍这些物品,使得背包中物品的总价值最高。如果每一种物品只有一件,可以选择放或不放,则转为0-1背包问题。
目前,求解背包问题的方法主要分为精确算法和近似算法两类。精确算法包括回溯法、分支定界法和动态规划法等[1];近似算法有蚁群算法、粒子群算法、蜂群优化算法等。随着智能优化算法的不断发展,智能算法在求解复杂问题方面的优势日益凸显,本文将改进的萤火虫算法(Firefly algorithm,FA)应用在0-1 背包问题中,取得了较好的效果。
1 0-1背包问题
将0-1背包问题描述为:已知有n件物品和一个最大承受重量为V的背包,每件物品的重量为wi(i=1,2,…,n),价值为pi,如何选取这些物品,使得总重量在背包承受范围内,且总价值最大。定义一个变量xi,当物品i被放入背包时,xi=1,否则xi=0;则0-1背包问题的数学模型可以表示为:
2 萤火虫算法
萤火虫算法是由剑桥大学Yang Xin-she于2008年提出的一种模拟自然界萤火虫发光行为的仿生算法。尽管人们对于萤火虫发光行为的意义还存有争议,但是有两点是确定的,即吸引配偶和吸引潜在猎物。
为了将萤火虫的生物行为抽象为算法,Yang Xin-she在文献[2]中作了如下约束:(1)萤火虫个体之间不存在性别之分,每只萤火虫个体都可以吸引其它的萤火虫,也可以被其它萤火虫吸引;(2)萤火虫的吸引力和它所发出光的亮度成正比。因此,对于任意两只萤火虫来说,亮度较弱的萤火虫个体会朝着亮度较强的萤火虫飞行;如果当前可见光内,没有发现比自己更亮的萤火虫,则该萤火虫实行随机飞行策略;(3)光的亮度一般由求解问题的目标函数决定[3]。
在萤火虫算法中,每只萤火虫个体包含位置、亮度和吸引力3个属性。萤火虫个体在某个固定位置的亮度I是确定的,该变量一般取决于问题的目标函数。其它个体看到该个体的亮度随着它们之间距离的增大而减小,此外,还要考虑传播介质对光线的吸收作用。因此,个体在距离当前位置r处的亮度可以表示为:
式(3)中,I0为个体在当前位置的亮度,γ为介质的吸收率。
每个个体对其它个体的吸引力β也是相对的,随着两个个体之间距离的增大而减小。此外,吸引力还和介质吸收率有关[2]。因此,个体在距离该个体r位置时对其它个体的吸引力定义为:
式(4)中,β0表示两个个体距离为0时,当前个体对另一个体的吸引力,γ为介质吸收率。
在该算法中,距离采用欧式距离公式计算。个体i朝着比它更亮的个体j飞行的距离为:
式(5)中,xi和xj分别表示个体i和个体j的位置,β0e-γri2j表示个体i和个体j的距离为r时,个体j对个体i的吸引力。α是一个随机参数,rand是一个随机数产生函数,它产生的数字均匀分布于[0,1]区间。
萤火虫算法步骤为:(1) 初始化种群及各参数;(2)计算种群中所有个体的亮度值;(3)根据公式(5)更新种群中的所有个体;(4)对所有个体按照亮度值进行排序,找出最优个体;(5)如果达到最大迭代次数或找到最优解,算法结束;否则,转步骤(3)继续执行。
3 改进萤火虫算法应用于0-1背包问题求解
在用萤火虫算法求解0-1背包问题时,算法可行解采用离散的0、1 序列表示;然而,每个萤火虫个体均用[0,1]区间内随机生成的n维向量X(x1,x2,…,xn)实数编码表示。因此,在每次计算萤火虫个体的亮度值之前,需要将个体的实数编码离散化,本文采用四舍五入的方法将实数编码转换成离散的0、1序列。
在0-1背包问题的数学模型中,还存在一个约束条件:物品的总重量不能超过背包的容量。由于萤火虫算法的个体实数编码全部随机生成,因此,可能存在不满足这一约束的个体。对于那些不满足约束的个体,本文采用一种贪心策略:按照价值密度(价值和重量的比值)从小到大的顺序,依次将物品取出背包,直至满足问题的约束条件为止。这种方法保证了所有个体都能满足问题的约束条件。
为了增加种群的多样性,本文设计了一种变异策略,使得算法随迭代次数的增加依然可以保持种群个体的差异性。在每次迭代后,对于种群中除最优解之外的所有个体,从中随机选择一个个体,随机选择该个体的某一位进行变异操作,即由0变1或者由1变0。这种方法有效增加了种群个体的差异性,避免随迭代次数增加,种群陷入局部收敛。
本文将背包中物品的总价值作为萤火虫个体的亮度值,利用改进萤火虫算法(Improved Firefly Algorithm,IFA)求解0-1背包问题的算法步骤为:(1)随机生成初始化种群,并初始化算法的各参数;(2)对种群中所有个体的实数编码进行离散化;(3)根据公式(1)计算每个萤火虫个体的亮度值,对于不满足约束条件的个体,按照贪心策略对其进行修正;(4)对所有个体的亮度进行排序,根据亮度选出最优个体;(5)随机从非最优个体中选择一个个体进行变异操作;(6)种群中的个体按照公式(5)进行更新;(7)如果达到最大迭代次数或者找到最优解,算法结束。否则,转步骤(2)继续执行。
4 实验仿真
实验所用PC机的操作系统为Windows8,处理器为2.94GHz,2G内存;所有实验基于matlab 7.0仿真环境。实验中,α取0.25,β取1,γ取1。对于每个算例均进行了50次独立实验。本文选取了3个测试算例,并将实验结果和现有实验结果进行对比分析。
算例1:n=10,V=269,weight={95,4,60,32,23,72,80,62,65,46},price={55,10,47,5,4,50,8,61,85,87}。运用回溯算法得到最优解为295。文献[4]采用蚂蚁优化算法在100次迭代后,可得最优解295;文献[5]采用蜂群算法在10次迭代后可得最优解295;文献[6]采用人工萤火虫群优化算法(Artificial glowworm swarm opti-mization algorithm,GSO)在20次迭代后可得最优解295;本文采用改进的萤火虫算法在10 次迭代内可得最优解295,其中,种群数目设置为20,最大迭代次数为100。收敛过程如图1所示。
算例2:n=20,V=878,weight={92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58},price={44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63}。运用回溯算法得到最优解为1024。文献[3]采用蚁群算法在200次迭代后得到最优解1024;文献[4]采用蜂群算法在50次迭代后得到最优解1024;文献[5]采用GSO在30次迭代后可得最优解1024;本文采用的改进的萤火虫算法在10次迭代后即可出现最优解1024。种群数目设置为100。收敛过程如图2所示。
将改进的萤火虫算法(IFA)的求解结果与文献[4]、[5]、[6]中的求解结果进行比较。本文对算例2 进行了50次独立实验,对比结果如表1、表2所示。
可以看出,改进的萤火虫算法的求解效率明显优于蚁群算法、蜂群算法和人工萤火虫优化算法,此外,当迭代次数大于100时,改进的萤火虫算法的求解最优解的概率达到96%以上。改进的萤火虫算法求得的最优解对应的0、1序列为{1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1}。
算例3:n=50,V=1000,weight={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1},price={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}。种群规模为100,分别进行50次独立实验。改进的萤火虫算法和粒子群算法(IFA)、GSO算法的实验结果对比如表2所示。
由表2可以看出,萤火虫算法的求解效率和稳定性较PSO、GSO算法均有明显提高。萤火虫算法求得的最优解对应的0、1序列为{1,1,0,1,0,1,0,1,1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,0,1,0,0,0,0,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0},萤火虫算法求解算例3的收敛过程如图3所示。
5 结语
本文针对0-1背包问题的自身特点,设计了一种改进的萤火虫算法对0-1背包问题进行求解,通过对标准萤火虫算法进行离散化编码,引入变异策略,有效地对背包问题进行求解。此外,引入贪心策略修正萤火虫算法的不可行解,取得了较好的效果。目前,萤火虫算法主要应用在函数优化、调度等方面,本文应用其对背包问题进行求解,拓宽了萤火虫算法的应用范围。0-1背包问题只是背包问题中一种最基础的问题,下一步还可以将萤火虫算法应用到多维背包问题中。
参考文献
[1]田烽楠,王于.求解0-1背包问题算法综述[J].软件导刊,2009,8(1):59-61.
[2]YANG XINSHE.Firefly algorithms for multimodal optimization[C].Proceedings of the 5th International Conference on Stochastic Algorithms:Foundations and Applications.Berlin/Heidelberg,Germany:Springer-Verlag,2009.
[3]郭丽萍,李向涛,谷文祥,等.改进的萤火虫算法求解阻塞流水线调度问题[J].智能系统学报,2013,8(1):33-38.
[4]樊小毛,马良.0-1背包问题的蜂群优化算法[J].数学的实践与认识,2010,40(6):155-160.
[5]程魁,马良.0-1背包问题的萤火虫群优化算法[J].计算机应用研究,2013,30(4):993-994.
改进萤火虫算法 篇4
随机载荷识别的算法改进与实验验证
文章结合逆虚拟激励法给出了一种条件数加权平均算法,在计算机上模拟了这一算法并与常规方法进行了比较,取得了较好的结果.通过实验验证了这一算法的可行性,证明了条件数加权平均法能在一定程度上克服频响函数在某些频率处的`病态问题;并采用以频响函教条件教大小来选定参与识别的响应测点组合的方法,减少了工作量,取得较好的识别效果.
作 者:廖俊 孔宪仁 作者单位:哈尔滨工业大学,卫星技术研究所,哈尔滨150001 刊 名:航天器环境工程 ISTIC英文刊名:SPACECRAFT ENVIRONMENT ENGINEERING 年,卷(期):2008 25(4) 分类号:V414.3+3 关键词:随机振动 载荷识别 逆虚拟激励法 条件数改进萤火虫算法 篇5
关键词:萤火虫算法,非线性方程组,函数优化,仿生原理
0 引言
线性方程组的求解是数值代数的基本问题之一, 许多工程应用和科学计算问题最后都要求解方程组, 因此, 对方程组的解法的研究具有重要的意义[1]。对于该问题的解法, 有传统方法和进化算法。传统方法的特点是:对方程组的组成要求高, 适用方程组少, 但具有很高的求解精度。进化算法是近年来新兴的一些算法, 如遗传算法、蝙蝠算法、萤火虫算法、蚁群算法等, 用于解决各类工程性问题有些专家也用这些进化算法来解决线性方程组问题, 并且已经得出了不错的结果。
1 萤火虫算法基本原理
萤火虫算法是模拟自然界中萤火虫成虫发光的生物学特性发展而来, 是一种群体优化算法[2]。最早是由印度学者Krishnanand等提出。其仿生原理是:萤火虫个体表示搜索路径中的点, 萤火虫个体的吸引和移动过程表示路径搜索和优化过程, 个体所处位置的好坏表示求解问题的目标函数值, 个体的优胜劣汰过程为表示为路径搜索和优化过程中用较好的解取代较差的解的过程。
萤火虫算法有两个要素, 即亮度和吸引度。亮度表示萤火虫所处位置并决定萤火虫的移动方向, 吸引度表示萤火虫移动的距离, 萤火虫通过亮度和吸引度的不断更新, 从而实现目标函数优化。在萤火虫算法中, 亮度、吸引度和更新规则的描述如下[2]。
(1) 萤火虫的亮度表示为
其中:h0表示萤火虫的最大亮度, 即自身 (r=0处) 荧光亮度, 与目标函数值相关, 目标函数值越优自身亮度越高;z表示光强吸收系数, 是一个常数;rij为萤火虫i与萤火虫j之间的距离。
(2) 萤火虫的吸引度为
其中:r0为最大吸引度, 即光源处 (r=0处) 的吸引度;z, rij意义同上。
(3) 萤火虫i向萤火虫j移动的位置更新公式如下:
其中, 表示萤火虫i向萤火虫j移动之后的位置, 表示萤火虫i和萤火虫j在萤火虫群更新之前所处的位置;α表示步长因子, 是[0, 1]上的常数;rand为[0, 1]上服从均匀分布的随机因子。
在萤火虫算法中, 先将萤火虫群体随机散布在解空间中, 每一只萤火虫发出的荧光亮度各不相同, 亮度低的萤火虫向亮度高的萤火虫移动, 移动的距离由吸引度的大小决定。萤火虫在搜索过程中, 为了避免过早陷入早熟, 采用式3来进行更新, 并根据式3来确定更新后的位置。这样通过多次移动后, 所有萤火虫个体都将聚集在亮度最高的萤火虫的位置上, 从而实现寻优。
目前, 人们已经发现很多昆虫存在莱维飞行 (Lévy flights) [2]。目前莱维飞行已经应用于各类组合优化问题, 并取得了很好的效果。在萤火虫算法中, 为了增强算法的全局搜索性能, 避免种群陷入局部最优, 把莱维飞行引入到萤火虫算法中, 当某个萤火虫找不到比自己更好的个体时, 选择莱维飞行。在萤火虫群, 荧光不是最亮的萤火虫, 则选择随机飞行, 并且对它们的飞行进行了限制, 当萤火虫们发现比自己更亮的个体时, 首先由系统产生一个随机数q, q是一个介于0和1之间的数, 如果q小于0.5, 采用公式 (4) 进行移动;否则采用公式 (3) 进行移动。
式中:xj表示萤火虫j在移动之前的位置, xi'表示第i个萤火虫移动之后的新位置, xi"表示xi'朝着比自己亮的萤火虫j移动之后的位置, ρ表示萤火虫j对萤火虫i的吸引力。
本文对上述萤火虫算法进行了一些改进, 提出一种改进的萤火虫算法。算法中将萤火虫群中的萤火虫根据选择运动的概率大小动态划分为不同的萤火虫群, 将每个萤火虫群中拥有局部最优值的萤火虫作为该萤火虫群的种子, 种子的局部最优解被设为该萤火虫群的全局最优值。这样就使得每个萤火虫群中的萤火虫都收敛于该萤火虫群的局部最优值, 而不是收敛于萤火虫群系统的全局最优值, 这样就可以并行地产生多个萤火虫最优值, 从而进行有效地多峰寻优。
另外, 为了改善萤火虫群的收敛, 本文还对α进行了改进, α随着迭代次数的变化而变化。具体如下:
式中:α0选用0.9, τ为迭代次数。通过求解非线性方程组实例, 验证结果表明本文所提算法所得到的结果好于现有的萤火虫算法。
2 改进的萤火虫算法
该算法的具体步骤如下:
1) 初始化。设置萤火虫数目s, 最大吸引度, 光强吸收系数z, 最大萤光亮度h0, 随机参数, 最大迭代次数t max=1000, 当前进化代数t=0。
2) 由公式 (1) 、公式 (2) 计算群体中萤火虫的相对亮度h和吸引度ρ, 根据相对亮度h决定萤火虫的移动方向。
3) 将s只萤火虫随机放在解空间中, 并将它们人为划分为许多群, 每个萤火虫群中的萤火虫围绕在拥有该子群中荧光最强的萤火虫周围, 萤火虫的亮度由公式 (1) 确定。
4) 对当前每个子群的萤火虫个体, 如果有比自己更亮的个体, 则根据q值的大小进行移动, 若q小于0.5采用公式 (4) 进行移动;q大于0.5而小于1, 则采用公式 (3) 进行移动;否则, 采用莱维飞行对个体位置进行移动。
5) 当每只萤火虫都构造完成各自的解之后, 记录当前每个萤火虫群的最优解, 并将这些最优解作为每个萤火虫群的种子, 种子的最优值是每个萤火虫群的全局最优值。
6) 根据移动后萤火虫的位置, 将每个子群的种子萤火虫重新计算它们的亮度。
7) 判断是否满足算法的终止条件。如达到最大迭代次数tmax=1000或最好解停滞不再变化, 则停止迭代, 否则τ=τ+1, 然后转步骤4。
3 仿真实例分析
试验选择文献[3]中用到的三个方程。方程如下:
实验中, 种群萤火虫个数选择100。最大迭代次数设置为1.0, z设置为0.9。
为了测试本文算法的求解效率, 文中将本文算法与文献[2]使用的算法进行比较。由表1可知, 本文提出的算法具有更高的收敛效率 (搜索空间/解空间) , 寻找到最优解的平均迭代次数少于参考文献[2]提出的算法。
4 小结
本文提出一种改进的萤火虫算法, 将物种起源原理和莱维飞行原理加入其中, 并重新设计了算法中个体位置的更新方式。改进后的萤火虫算法在求非线性方程组问题时, 性能有了明显提高, 而且随着问题规模的增大, 这种提高更加明显。实验证明:该算法对于解决非线性方程组问题是可行和有效的。
参考文献
[1]杨万安, 曾安平。求解非线性方程的新方法[J].计算机工程与应用, 2009 (28) :41-42.
[2]杨新社.一种新的智能算法-萤火虫算法[J].智能计算研究, 2010, 284:101-111.
[3]郭海燕, 金鑫, 胡小兵。基于微粒群优化的非线性方程组求解研究[J].计算机工程与应用, 2006 (15) :72-74.
改进萤火虫算法 篇6
人工萤火虫群优化算法基本思想是模拟自然界萤火虫群中的所有萤火虫通过发光来进行群体觅食或吸引伴侣的行为, 萤火虫发出的光的亮度越大对其它萤火虫的吸引力也就越大。一直到最后, 大部分的萤火虫在聚集在多个集中的位置一起发出亮光来吸引伴侣或者一起进行觅食活动。
萤火虫优化算法整体分为四个阶段:萤火虫的部署阶段, 荧光素值更新阶段, 萤火虫位置更新阶段以及决策域半径更新阶段。
部署阶段就是将萤火虫随机的部署在要求解的目标函数的可行域中, 并且开始的时候假设所有的萤火虫的初始荧光亮度和感应半径都相同。
在荧光素值更新阶段, 所有的萤火虫在移动结束之后都会更新它们的荧光素值。荧光素值更新公式如下:
其中, il (t) 表示萤火虫i在迭代t的荧光素的值即萤火虫i的亮度;ρ表示亮度衰减常数 (0<ρ<1) , (1-ρ) 表示亮度衰减率, 用于控制过去经验的比重, 使得萤火虫在迭代中遗忘过去的非优解;γ表示比例常数, 用于控制迭代中搜索解的经验比重。
萤火虫位置更新, 也就是萤火虫的移动。在这个阶段中, 所有的萤火虫都会根据决策域半径和荧光素亮度来产生一个邻居集合, 然后在邻居集合中找出比它本身亮的萤火虫, 最后按照概率选择公式选出一只萤火虫作为移动目标, 然后向着目标飞行。
在算法的执行过程中, 萤火虫会在位置更新之后会根据所在位置的邻居密度的基础上对区域决策半径进行更新。决策区域的半径大小是由该萤火虫当下决策域所涵盖的邻居数量比率, 即邻居密度决定的, 若邻居密度小于一个给定的值, 半径会加大以便下次迭代时能搜索到更多邻居, 反之决策区域半径会缩小, 若密度没有变化半径也保持不变。
二、基于蛙跳算法的人工萤火虫群优化算法
蛙跳算法的基本思想很简单, 我们用到的是蛙跳算法中的分组思想, 所谓分组思想指的是将所有种群先进行分组, 分组结束之后在子群内进行寻优, 子群寻优结束之后在重新组合进行全局寻优。
我们在人工萤火虫群优化算法中引入蛙跳算法中的分组思想, 先将萤火虫进行分组, 在每个组内对萤火虫应用萤火虫优化算法, 组内优化结束之后对萤火虫进行组合在继续寻优, 直到达到最大迭代次数。改进后的算法记为GSO-SFLA。
改进后的算法的步骤如下:
Step 1初始化萤火虫算法和蛙跳算法的参数。
Step 2把种群中的萤火虫随机进行排序, 然后进行个体的分组。将第一个个体分配给子群1, 第二个个体分配到子群2, 一次类推, 第groupm分配到groupm, 第 (groupm+1) 分配到子群1中, 一直到分配完所有的个体。
Step 3每个子群内部进行相关的更新。按照荧光素更新公式更新荧光素值。
Step 4每个子群内的萤火虫计算邻域集合, 统计概率, 选择最优个体。
Step 5利用模拟退火准则来判断被选中的最优个体是否被接受, 如果被选中的最优个体的目标函数值确实比当前位置的目标函数值优, 就接受最优解, 否则以一定的概率接受劣解。
Step 6更新萤火虫的位置。萤火虫移动后, 按照萤火虫感知半径更新公式更新萤火虫的感知半径。判断是否达到组内最大迭代次数group MAX, 如果达到, 则跳转到Step7, 否则, 跳转到Step3继续进行组内循环。
Step 7判断是否达到最大迭代次数max DT, 如果达到, 输出最优解, 保存最优个体, 否则, 跳到Step2。
三、实验仿真
为了证明改进后算法的有效性, 现选取函数来进行测试。
Rastrigin’s函数是由Rastrign率先提出来的。该函数有广泛的搜索空间、大量的局部最小值和局部最大值, 由于它的以上一些特性, 该函数成为一个相当棘手的问题, 它在定义域内有100个峰, 需要性能较好的算法才能搜索到全部的峰, 因此Rastrigin’s函数常常用来测试优化算法的基准函数。由于函数具有较多的峰, 为了加快算法测试的速度, 我们选取x、y在[-2, 2]的搜索空间, Rastrigin’s函数在这个区间内有16个函数值不等的峰。函数如下:
在这里我们需要证明函数既能有效减少种群规模, 又能减少迭代次数, 因此, 首先我们设置迭代次数固定, iter_max=100, 来看一下算法的平均捕峰数与种群规模的关系, 再接着让种群规模固定, 设置规模为150, 看一下算法的平均捕峰数与迭代次数的关系。
迭代次数为100时函数测试如下所示:
测试结果图一开始就显示出了改进后的算法在捕峰能力上的优势。并且优势逐渐增大, 在个体数增加到80左右的时候改进后的算法基本能够捕捉到所有的峰值, 原来的算法在个体数接近200的时候仅仅捕捉到10个峰左右, 有力的证明了改进后的算法在捕峰能力上的提升, 说明了改进的有效性。
设置种群规模为150。函数测试结果如图所示。
测试结果很直观, 改进后的算法在迭代次数很少的时候就能捕捉到16个峰, 并且没有波动, 算法平稳, 而未改进的算法则一直未捕捉到全部的峰并且还存在较大的波动。
摘要:人工萤火虫群优化算法 (GSO) 是最近提出的一种群智能优化算法, 算法具有参数少、优化求解速度快以及占用内存少等优势, 但是GSO算法还是存在许多的不足, 本文就是来讨论解决GSO算法中的一些不足之处。
关键词:人工萤火虫群优化算法,蛙跳算法,分组思想
参考文献
[1]黄正新, 周永权.自适应步长萤火虫群多模态函数优化算法[J].计算机科学, 2011, 07:220-224.
基于混合变异的萤火虫群优化算法 篇7
萤火虫群优化GSO算法是印度学者K N Krishnanand和Debasish Ghose于2005 年模拟自然界萤火虫求偶或觅食行为而提出的一种新型仿生群体智能优化算法[1]。该算法通过萤火虫个体之间的相互吸引达到寻优的目的,其计算速度快,需要调节的参数少,简单易于实现,具有很强的通用性,已逐渐成为计算智能研究领域一个新的研究方向,并成功应用于传感器的噪声测试[2]、聚类分析[3]、模拟机器人[4]、函数优化[5]等。但与其他群智能算法一样,也存在着后期收敛速度慢、容易陷入局部极值、求解精度不高等问题。
针对这些问题,文献[5]提出一种基于荧光因子的自适应调整步长的方法,使得萤火虫算法寻优的解获得了更高的精度。文献[6]提出了一种带交尾行为的混沌萤火虫优化算法,通过混沌进行初始化,提高了初始解的质量,又在GSO算法中引入交配行为,进一步提高了萤火虫群优化算法的收敛速度和求解精度。文献[7,8]分别运用高斯变异和自适应t分布变异的方法增加萤火虫种群的多样性,提高了解的精度和寻优的速度。本文采用混沌变异和边界变异的混合变异策略,对陷入局部极值的萤火虫利用混沌变异的方法搜索周围的最优解来代替本身; 对飞出边界的萤火虫进行边界变异,避免边界萤火虫聚集的行为,提高种群的效率。
1 基本萤火虫群优化算法
基本萤火虫群优化算法思想来源于自然界的萤火虫用闪光来吸引其他萤火虫,借此进行沟通、求偶等。闪光越亮代表萤火虫吸引力越大,最后形成萤火虫聚集在亮度较大的萤火虫周围。萤火虫闪光的亮度取决于萤火虫携带的的荧光素值,荧光素值越大,萤火虫的闪光越亮。
算法初始时在D维解空间内随机生成N只萤火虫,萤火虫i的当前位置表示为Xi( t) ,初始时每只萤火虫都携带相同的萤火素值l0,并且具有相同的决策半径r0。在萤火虫移动的过程中,如果萤火虫j在萤火虫i的决策范围内,并且萤火虫j荧光素值比萤火虫i的高,萤火虫i就以一定的概率向其邻居萤火虫j移动。萤火虫所在位置对应一个适应度值,荧光素的大小与萤火虫所在位置的适应度值有关,荧光素值越大,所在位置越好,即有较好的适应度值。最后,萤火虫会聚集在适应度值较高的萤火虫周围。在完成初始化后,GSO每次迭代包括三个过程: 荧光素更新、位置更新、感知范围更新。
1) 荧光素更新阶段
荧光素与萤火虫所在位置密切相关,所在位置越好,荧光素值就越大,闪光越亮; 荧光素除了受所在位置影响,还与萤火虫上一时刻所携带的荧光素值和挥发速度有关。荧光素值根据下式进行更新:
式中,li( t) 表示在t时刻萤火虫i的荧光素值,ρ( 0 < ρ < 1) 为常数,表示荧光素的挥发速度,γ 也为常数,表示荧光素更新率,f( Xi( t) ) 表示在t时刻萤火虫i所在位置的适应度值。
2) 位置更新阶段
萤火虫i的移动方向由其所有邻居萤火虫的荧光素决定,邻居萤火虫是在萤火虫i的决策范围内荧光素值比萤火虫i的荧光素值大的萤火虫集合,即:
式中,‖·‖表示欧氏距离,ri( t) 表示t时刻萤火虫i的决策半径。对所有邻居萤火虫j,根据下式计算t时刻萤火i向萤火虫j移动的概率:
萤火虫i根据Pij( t) 选择移动方向为j,然后根据下式更新萤火虫i的位置:
其中,s为移动步长。
3) 感知范围更新
移动后,每只萤火虫根据邻居萤火虫的数量动态地更新各自的感知范围,如果邻居萤火虫数量多,则减小感知范围,反之增大感知范围,如下式更新:
其中,rs是控制萤火虫感知范围阀值,β 是领域变化率,ri( t)( 0 < ri( t) < rs) 是t时刻萤火虫i的感知范围,nt是控制邻居萤火虫数量的阈值,| Ni( t) | 表示邻居集合数量。
2 混合变异优化GSO算法
2. 1 种群混沌变异机制
文献[8]提出的ATM-AGSO算法进行变异时,非最优萤火虫采用自适应t分布变异,最优萤火虫采用高斯变异,即:
其中,k为变异控制因子,当i为非最优萤火虫时,H( t) 为以迭代次数t为参数自由度的t分布,当i是最优萤火虫时,H( t) 为服从均值为0 方差为1 的高斯分布。但这种变异方法变异的幅度相对较大,容易错过附近更优解。为提高算法局部搜索的遍历性和效率,本文采用混沌立方映射[9]产生混沌变量来代替ATM-AGSO算法中的随机变量H( t) ,进行混沌变异。该策略表示为:
式中,t表示当前迭代次数,Tmax表示算法最大迭代次数,Z( n)为混沌序列。
混沌是自然界广泛存在的非线性现象,是一种状似随机混乱,却具有遍历性和规律性的非随机运动,能按自身规律在一定范围内不重复地遍历所有状态[10]。运用混沌运动的这些特性对GSO算法进行优化搜索,有助于算法跳出局部最优,增加种群的多样性,增强算法的全局搜索能力。混沌立方映射产生的是( - 1,1) 之间的序列,只要立方映射的迭代初值不为0,混沌就会发生。首先在D维解空间内根据式( 8) 随机产生一个( - 1,1) 之间的D维向量,作为第一个混沌变量:
然后根据下式对每一维迭代M - 1 次,最后得到M个混沌序列。
利用产生的混沌序列根据式( 7) 进行变异,比较变异扰动前、后的的适应度值。若变异产生的最优适应度值优于原有个体的适应度值,就用该最优适应度值所处的状态取代原有个体状态。这样根据已有个体状态增加混沌扰动项Xi× k × Z( n) ,获得有更好适应度值的个体,种群的多样性得到了保证,也赋予了算法跳出局部极值的能力,同时提高了搜索能力。
2. 2 边界变异
在其他一些GSO算法中,当萤火虫飞出搜索区域后,通常将搜索空间的边界值赋值给该萤火虫:
或者
其中,Xmax、Xmin分别是搜索区域的最大和最小边界值。经过这样的处理后,所有越界的萤火虫会在边界聚集,其状态将趋于相同,不仅降低了种群的多样性,也会影响算法的全局搜索能力; 如果边界附近存在局部最优,还使得算法容易陷入局部极值。
文献[11]把边界变异引入到量子粒子群算法中,有效控制了粒子越界的行为,提高了算法的全局搜索能力。同理,我们也可以把边界变异引入到萤火虫群算法中,在每代萤火虫越界时进行边界变异,该变异策略可表示为:
或者
其中,c = 0. 01 。从上述变异过程可以看出,对越界萤火虫进行变异操作后,萤火虫不再聚集在边界处,而是分布在搜索区域内,克服了萤火虫聚集边界的缺点,同时增加了种群的多样性,避免了萤火虫陷入局部极值,提高了算法的整体搜索速度。
2. 3 HM-GSO混合变异描述
HM-GSO算法是将混沌变异和边界变异相结合,在算法迭代过程中,随着种群的不断进化,个体之间的差异逐渐变小,并出现萤火虫严重聚集的现象,导致算法极容易陷入局部极值。此时对种群中的每只萤火虫进行混沌变异搜索,对搜索过程中越界的萤火虫进行边界变异,最后用混沌扰动后的最优状态更新为当前萤火虫的状态。每次萤火虫群变异后用最优萤火虫的状态和适应度值和公告板上的最优萤火虫比较,公告板将记录更优的萤火虫的状态和适应度值。当公告板上的适应度值在连续三次迭代中没有改变或者改变很小( | 变化量| < u ) 时,判断算法陷入局部最优。此时进行混合变异,帮助种群跳出局部极值,从而增加种群的多样性,提高全局搜索速度。u的取值一般为10- 6~ 10- 4之间的数。
2. 4 HM-GSO算法步骤
HM-GSO算法的具体步骤设计如下:
1) 初始化 ρ、γ、β、s、l0、r0、rs、nt、N、D、Tmax、u等参数,并随机初始化萤火虫种群;
2) 计算所有萤火虫的适应度值,初始化公告板;
3)根据式(1)对所有萤火虫进行荧光素更新;
4) 用式( 2) 计算所有萤火虫的邻居集合,式( 3 ) 计算萤火虫的选择概率,然后用轮盘赌方法选择移动目标,根据式( 4) 进行位置更新;
5) 用式( 5) 更新萤火虫的感知半径;
6) 计算当前种群每个个体的适应度值,若最优适应度值优于公告板,则更新公告板的状态和适应度值;
7) 判断是否陷入局部最优值,如果公告板上的最优适应度值在连续三次迭代中没有发生改变或者改变很小( |变化量| < u) 时,则执行步骤8) ,否则,执行步骤9) ;
8) 在每个萤火虫周围进行混沌变异,对飞出边界的萤火虫用边界变异策略控制在搜索范围内,计算混沌扰动后的适应度值,取最优适应度值与原适应度值比较,若优于原有适应度值,则用扰动后最优适应度值所在的位置取代原有位置。比较变异后萤火虫群的最优萤火虫和公告板的最优萤火虫,如果由优于公告板,则更新公告板的状态和适应度值;
9) 完成一次迭代,判断终止条件是否满足( 迭代次数达到Tmax ) ,如果满足,记录结果,退出迭代,否则转步骤3) ,进入下一次迭代。
HM-GSO算法的流程如图1 所示。
3 HM-GSO算法性能测试与分析
3. 1 实验测试函数
为了验证HM-GSO算法的收敛速度、收敛率和求解精度等,将本文提出的基于混合变异的萤火虫群( HM-GSO) 算法与基本GSO算法及文献[8]提出的基于自适应t分布混合变异的人工萤火虫( ATM-AGSO) 算法进行性能比较,采用了6 个标准测试函数进行对比测试实验。6 个测试函数如下:
标准测试函数如表1 所列。
3. 2 实验参数设置
在GSO算法中,步长s根据经验选取,F1、F3中取为5,F2、F4、F5和F6中取为1,对于ATM-AGSO算法和HM-GSO算法,s取值为0. 3,其他实验参数设置如表2 所示。
3. 3 实验平台
本实验的运行测试环境为: 处理器为Intel( R) Core( TM)i3-3110M CPU,主频2. 4 GHz,内存4 GB,操作系统: Windows 7,集成开发环境为Matlab R2012a。
3. 4 实验仿真结果与分析
仿真实验中对这三种算法用这6 个标准测试函数分别进行20 次独立实验,对每一个函数求得这三种算法的最优值、最差值、均值、收敛迭代次数、平均收敛时间和收敛率等,并通过收敛曲线来比较三种算法的收敛速度和求解精度,从而测试本文算法的有效性。在给出收敛精度 ε = 10-5的情况下,如果满足| Fitnessbest- Fitness | < ε,则认为算法收敛; 否则为不收敛。其中,Fitnessbest为实际求得的最优解,Fitness为理论上的最优解。
从表3、表4 可以看出,GSO对6 个函数都没有收敛,HM-GSO和ATM-AGSO测试6 个函数时的收敛率达到100% ,收敛精度以HM-GSO最大,ATM-AGSO次之,GSO最小。对于函数F1,HM-GSO的平均最优解精度比GSO提高了42 个数量级,平均收敛迭代次数比ATM-AGSO减少了65 次。对于函数F2,HM-GSO的平均最优解精度比GSO提高了30 个数量级,比ATM-AGSO提高了20 个数量级,平均收敛迭代次数比ATM-AGSO减少了85 次。对于函数多个F3,HM-GSO的最优解精度达到了e-75,平均最优解精度远优于GSO,比ATM-AGSO提高了40 个数量级,平均收敛迭代次数比ATM-AGSO减少了47 次。对于函数F4,HM-GSO的平均最优解精度比GSO提高了63 个数量级,比ATM-AGSO提高了45 个数量级,平均收敛迭代次数比ATM-AGSO减少了61 次。对于函数F5,HM-GSO的平均最优解精度比GSO提高了52 个数量级,比ATM-AGSO提高了33 个数量级,平均收敛迭代次数比ATM-AGSO减少了44次。对于函数F6,HM-GSO的最优解精度达到了e-102,平均最优解精度比ATM-AGSO提高了26 个数量级,平均收敛迭代次数比ATM-AGSO减少了12 次。
结合图2 - 图7 分析,HM-GSO的寻优曲线更加稳定。随着迭代次数的增加,在增加不到50 时,HM-GSO的最优函数值就到达了收敛精度。HM-GSO的平均收敛时间也比ATM-AGSO更少,且在同一次迭代里面。HM-GSO获得的最优函数值比GSO和ATM-AGSO更优,说明HM-GSO比GSO和ATM-AGSO具有更快的收敛速度,更高的求解精度。可见,HM-GSO算法在搜索过程中通过混沌变异和边界变异混合变异的方法增加了种群的多样性,避免了算法陷入局部最优、容易聚集边界的缺点,克服了过早收敛的问题。因而全局寻优能力、求解精度、收敛速度和稳定性等方面比其他两种算法都得到了提高,具有更好的寻优能力。
4 结语
本文提出了一种基于混合变异的萤火虫群优化算法。算法中运用混沌的方法进行变异,并对越界的萤火虫进行边界变异,使算法避免陷入局部极值,提高了寻优速度和求解精度。通过函数优化实验可以看出,改进后的算法优于基本萤火虫群优化算法,较ATM-AGSO算法有更快的收敛速度和更精确的函数值。下一步我们将融合其他算法,并应用于求解实际问题中。
参考文献
[1]Krishnanand K N,Ghose D.Glowworm swarm optimization:a new method for optimizing multi-modal functions[J].International Journal of Computational Intelligence Studies,2009,1(1):93-119.
[2]Krishnanand K N,Ghose D.A glowworm swarm optimization based multi-robot system for signal source localization[M]//Liu D K,Wang L F,Tan K C.Design and Control of Intelligent Robotic Systems.Berlin:Springer,2009:53-74.
[3]Huang Z X,Zhou Y Q.Using glowworm swarm optimization algorithm for clustering analysis[J].Journal of Convergence Information Technology,2011,6(2):78-85.
[4]Krishnanand K N,Ghose D.Chasing multiple mobile signal sources:a glowworm swarm optimization approach[C]//Third Indian International Conference on Artificial Intelligence(IICAI 07).Indian,2007.
[5]欧阳喆,周永权.自适应步长萤火虫优化算法[J].计算机应用,2011,31(7):1804-1807.
[6]黄凯,周永权.带交尾行为的混沌人工萤火虫优化算法[J].计算机科学,2012,39(3):231-234.
[7]莫愿斌,刘付永,张宇楠.带高斯变异的人工萤火虫优化算法[J].计算机应用研究,2013,30(1):121-123.
[8]杜晓昕,张剑飞,孙明.基于自适应t分布混合变异的人工萤火虫算法[J].计算机应用,2013,33(7):1922-1925.
[9]冯艳红,刘建芹,贺毅朝.基于混沌理论的动态种群萤火虫算法[J].计算机应用,2013,33(3):796-799.
[10]郁书好,苏守宝.混沌萤火虫优化算法的研究及应用[J].计算机科学与探索,2014(3):1-6.
改进萤火虫算法 篇8
1 灰色理论模型
1.1 灰色理论模型的建立
GM (1, 1) 模型[3]模型的白化方程为:
undefined
时间响应函数
undefined
离散响应函数
undefined
其灰色参数为
undefined
建立预测模型为
undefined
得出X (0) 的灰色预测模型为
undefined
2.2 模型精度评定
可求得残差
εundefined=xundefined-x (1) (t) (1.6)
观测数据方差
undefined
预测误差均值
undefined
预测误差方差
undefined
后验差比值C
C=S2/S1 (1.10)
小误差概率
undefined
对于评定一个预测模型的好坏, C值越小越好, 一般要求C<0.35, 最大不超过0.65。预测模型精度评定的另一个指标为小误差概率p, p值越大越好, 一般要求p大于0.95, 不得小于0.7。参照p与C的大小, 可将精度分为4个等级。
人工萤火虫算法源于对自然界中萤火虫发光求偶、觅食等行为的研究。它是一种群智能算法, 其基本原理是:利用萤光素诱导萤火虫发光来吸引伴侣或猎物, 光芒越明亮越炽热就越有吸引力, 荧光素值也越高, 萤火虫向荧光素值高的位置移动。荧光素值对应适应度函数值, 因此萤火虫通过在动态决策域内寻找最高荧光素值的位置而确定适应度函数的最优值。该算法存在捕捉极值域速度快、捕捉效率高, 具有较强的通用性等优点。而本文主要是把GM (1, 1) 预测模型作为萤火虫算法中的目标函数, 搜索解空间, 得到全局最优解, 根据最优解推解模型值以及预测精度。
2 人工萤火虫算法优化的GM (11) 模型的基本思路
1.根据灰色理论模型原理, 使用matlab进行最基本的编程, 主要是计算出灰色理论模型, 以及模型值, 残差, 后验方差比。
2.根据文献[1][2][6]以及借助网上资源进行最基本的萤火虫算法编程, 在此期间将第一步算出的函数作为目标函数带入到该算法中, 得到最优解, 根据最优解, 解算出一组模型值。
3.根据灰色理论模型精度评定该模型是否最优, 如果不是就继续迭代, 直到达到精度。
3 实例应用
取一组数据建立预测模型进行说明, 取前7次观测数据建模, 对后两期进行预测。主要是把GM (1, 1) 预测模型作为萤火虫算法中的目标函数, 搜索解空间, 得到全局最优解, 根据最优解推解模型值, 及后两期进行预测精度评定。
经过多次预测, 取其中较为接近的结果做出比较, 可以看出在种群数目为100时, GM (1, 1) 的预测精度较高。
从表3可以看出优化后的模型比未优化的模型的残差小了很多, GM (1, 1) 模的后验方差比值为0.967953, 而萤火虫优化的GM (1, 1) 模型的后验方差比值0.1248, 优化后的模型比未优化的后验方差比值要小的多, 其精度更高。从两个模型
与原始值的的比较图来看萤火虫优化的GM (1, 1) 模型更近原始值的发展趋势, GM (1, 1) 模型虽能大体上预测原始值的发展趋势, 但是局部值相差太大, 从而导致整体的精度不高。萤火虫优化的GM (1, 1) 模型整体上更近原始值的发展趋势, 局部也与原始值相差无及, 以使整体的精度提高。从而突出萤火虫算法的捕捉效率高, 具有较强的通用性等优点。
4 结束语
改进萤火虫算法 篇9
1 系统组成
1.1 硬件选择
图1为本系统结构框图, 其组成由采集模块、数据传输和数据处理单元组成。采集模块主要是安装在井壁的压力和温度传感器, 数据传输单元包括有单总线、RS485总线和RS232总线, 数据处理单元包括有上位机、监测仪表R T U;监测仪表R T U包括有主控器MCU以及与主控器MCU连接的网络接口控制、液晶电路、报警电路, 主控器MCU内置有RTU管理控制程序。图中1为多路温度传感器;2为多路压力传感器;3为上位机;4为485转232接口;5为电源;6为监测仪表RTU。
1.2 工作原理
温度传感器和压力传感器采集的数据通过单总线发送到监测仪表RTU的主控器MCU, 并将所得数据显示在液晶显示器上, 同时转换成RS485数据送到RS485总线上;上位机上设有RS232接口电路和相应软件、485总线上传输的数据通过232/485转换器转换成PC机能识别的电平, 将数据经RS232总线送到上位机的RS232接口, 随即送入上位机中的萤火虫算法模型软件中, 经过演算可以获得较准确的未来发展趋势预警, 并将数据实时显示在上位机上。便于工作人员查看。
压力传感器包括检测部分和输出芯片DS2438, 由于输出为数字量, 故可以将所得压力信号直接挂到单总线上。对传感器所得信号在井下采用单总线传输, 地面采用485总线。
2 萤火虫算法的理论基础
2.1 模型的说明
井壁在坍塌前都会有一定的变形, 尽管井壁变形有多种表现类型, 但井壁坍塌的直接原因都是由于井壁所受压力过大, 此外温度对井壁的承受能力也有一定的影响, 所以本系统需要检测井壁各处的压力和温度即可实现对井壁变形程度和状态的掌握, 对这些数据进行在上位机上进行萤火虫算法演算, 得出井壁是不是处于危险状态。
2.2 井壁预警的萤火虫算法实现
采用萤火虫算法对矿井井壁的安全进行预测, 通过上位机软件计算后, 密集度最高的区域对应着比较危险的部位, 需要加大维护力度, 防患于未然。萤火虫算法的基本步骤是, 首先将萤火虫群体随机散布在解空间, 处于不同位置的不同萤火虫发出的荧光亮度也不同, 其次, 根据荧光亮度的不同, 荧光强度低的萤火虫会飞向比自己亮的萤火虫, 飞行的路程由吸引度的大小来确定。在实际应用中为了能够在更大范围内搜索, 找到全局的最优解防止局部最优解干扰, 导致算法不收敛, 在计算萤火虫更新后的位置时需要在位置更新过程中增加扰动项。最后, 通过多次迭代后, 算法收敛于亮度最高的萤火虫, 也就是说该萤火虫会把其他萤火虫都吸引到自己的位置处, 便完成了对最优解的寻找, 达到精确预测的目地。
3 系统仿真测试
在计算机中, 对建立的模型, 对采集的部分数据进行萤火虫算法防真, 运行得到如图2的结果, 所用萤火虫收敛于几个点, 也即在些地方需要加强防范, 很有可能会在这些地方出现事故。
4 结语
本文完成了一种基于萤火虫算法的井壁变形监测系统, 该系统具有如下特点:完全实现自动化。从数据采集到数据传输到数据处理, 整个过程完全由计算机控制, 不需人的参与。 (2) 实时监测。位于井下的传感器可以实现连续采集数据, 所得数据被传输至地面中心计算机, 整个系统可以实现工作。 (3) 报警功能。工作人员在地面上位机可以设定报警阈值, 软件的输出达到或者超过该设定值是系统便会发出报警信号。 (4) 速度快。整个系统从数据采集到最终结果显示在终端设备和PC上, 仅需几分钟。
摘要:本文针对煤矿井壁变形问题设计了一种实时监控系统, 来预防井壁事故的发生。结合现代检测、通讯技术和萤火虫算法, 采用温度传感器, 多路压力传感器测量井壁的变形信息, 并将各检测单元所得数据经由MCU演算, 同时把数据传送到地面中心计算机, 地面工作人员即可实时地掌握井壁的形变情况。该系统可实时测量和监控, 其检测精度高、鲁棒性好, 且可根据需要接入Ethernet或者LAN, 实现远程监控和数据共享。
关键词:井壁变形,萤火虫算法,煤矿预警,实时监测
参考文献
[1]刘延强, 吕英民, 蔡强康.井壁变形和摩擦阻力对底部钻具组合的影响[J].石油大学学报 (自然科学版) , 1991, 01:32-41.
[2]梁化强.矿井井壁变形监测及治理研究[J].矿业安全与环保, 2008, 05:45-46+55.
[3]张黎明, 王在泉, 任禀洁.井壁安全远程自动监测及井壁变形的灰色马尔柯夫预测[J].煤矿安全, 2005, 12:50-52.
[4]刘鹏飞.井壁变形全自动监测系统的工程应用[J].煤炭科学技术, 2005, 02:7-9+6.