基于模拟退火的果蝇优化算法

《基于模拟退火的果蝇优化算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于模拟退火的果蝇优化算法　　摘要：针对果蝇算法（FOA）寻优精度不高且易陷入局部最优的缺陷，提出了一种基于模拟退火思想的果蝇优化算法（SA-FOA）。所提算法对解的接收机制和寻优步长进行了改进：以广义的Gibbs分布产生的概率为接收概率，解的接收满足Metropolis准则；参考非均匀变异的思想，使步长随迭代次数的增加逐渐减小。通过对几种典型测试函数的仿真表明，改进算法具有较强的全局搜索能力，同时寻优精度和收敛速度比果蝇算法也有较大的提高。因此，可以用改进算法对神经网络和服务调度问题的参数进行优化。　　关键词：果蝇算法；模拟退火；寻优步长；接收概率；收敛速度　

2、　中图分类号：TP301　　文献标志码：A　　文章编号：1001-9081（2016）11-3118-05　　0引言　　果蝇优化算法（FruitFlyOptimizationAlgorithm，FOA）是一种新型的群智能优化算法，算法是根据果蝇的觅食行为进行推演形成的一种寻找全局最优解的新方法[1-5]。该算法与粒子群优化（ParticleSwarmOptimization，PSO）算法、人工鱼群算法（ArtificialFishSwarmAlgorithm，AFSA）和遗传算法（GeneticAlgorithm，11GA）等相比具有计算量较小、参数少、结构简单

3、、易于实现的特点，但同时该算法也存在不够稳定、易陷入局部最优的缺陷[6]。为了改善原算法的性能，文献[7]提出了自适应步长的改进策略对原算法进行优化，其思路是在原算法的基础上加入果蝇因子，影响该因子的因素是果蝇当前位置与果蝇最佳位置，这样果蝇寻优步长会随着果蝇的位置自适应改变；文献[8]提出了递减步长的改进方法，该算法与果蝇的迭代次数有关，每进行一次迭代，步长都减小一个定值，定值的大小为初始步长与最大迭代次数的比；文献[9]提出了自适应调整参数的果蝇优化算法，该算法用逆向云发生器确定下代果蝇的飞行方向与距离；文献[10]用轮盘赌策略对果蝇的飞行方向进行选择，其思

4、路是根据概率随机选择一个比当前位置好的果蝇作为下次迭代寻优的起始位置。文献[7-9]都是基于步长改进，影响的是果蝇的寻优速度，全局寻优能力没有改变；文献[10]的改进对果蝇历史最好位置依赖性大，如果上代果蝇陷入局部最优，则以后的寻优过程都很难跳出局部最优，因此效果也不是太好。　　为了提高果蝇优化算法的收敛速度与全局寻优能力，本文采用非均匀变异的思想对果蝇寻优步长进行改进，以提高算法的收敛速度与精度。同时将模拟退火算法与果蝇算法进行结合，提出了基于模拟退火思想的果蝇优化算法（SimulateAnneal-FruitflyOptimizationAlgorithm，

5、SA-FOA）。改进后的算法可以以一定的概率吸收最差的解，并以最差解作为下代果蝇寻优的新起点，从而使算法跳出局部最优值，增强全局寻优的能力。　　1果蝇优化算法　　1.1果蝇优化算法的原理11　　果蝇在寻找食物时，会沿着食物味道浓度大的方向飞行，而味道浓度的大小和果蝇与食物的距离有关系，果蝇距离食物的位置越近，味道浓度就越大，也越容易找到食物[1]。果蝇群体迭代寻优路线如图1所示。　　果蝇寻优原理为：随机初始果蝇群体的位置（x，y），果蝇以该位置为起点随机飞行去寻找食物，当果蝇个体发现食物最佳位置时，其他果蝇也会向该位置聚拢（x2，y2）；然后再以这个新位置为起点

6、进行下一次的寻优，直至找到食物的位置。　　1.2果蝇优化算法的步骤　　1）随机初始果蝇群体的位置（X_axis，Y_axis）并设置种群规模与迭代次数。　　2）以初始位置为起点，随机给定果蝇个体的飞行方向Random和寻优步长Value，以Random*value作为搜索距离。　　3）计算味道浓度判定值si，该值是果蝇位置坐标与原点距离的倒数。　　4）将味道浓度判定值代入味道浓度判定函数，求出果蝇个体的味道浓度。　　5）找出果蝇群体中味道浓度最小的果蝇。　　6）保留果蝇最小位置坐标，其他果蝇也向该位置飞去。　　7）进入迭代寻优，重复执行步骤2）～5），并判断味道

7、浓度是否优于前一代：若是，则执行步骤6）；若否，则保留前一代的最小味道浓度，算法结束。　　1.3果蝇算法的应用11　　果蝇优化算法和其他群智能优化算法一样有着广泛的应用领域。果蝇优化算法不仅可以对维数众多、结构复杂的函数进行求解，还可以用于求解实际问题。例如，文献[7]将其与功能流算法相结合，并将改进算法应用在蛋白质交互网络中，通过仿真表明改进算法具有较高的正确率与收敛速度；文献[10]将改进算法应用于置换流水车间模型。通过仿真表明，果蝇算法可以有效地对车间调度问题进行优化；另外，将果蝇优化算法应用于旅行商问题模型，可以快速有效地找出相对合理的路径；将果蝇优化算

8、法应用于神经网络中，可以