一种基于最大最小荧光素值改进的萤火虫算法

一种基于最大最小萤光素值的人工萤火虫算法摘要: 人工萤火虫算法是近年在群智能研究领域出现的一个新群智能算法，该算法在多峰复杂函数优化方面取得了成功，但也存在着易陷入局部极小值和进化后期收敛速度慢等问题。为解决这一问题本文提出了一种基于最大最小萤光素值改进的人工萤火虫算法。该算法在人工萤火虫算法萤光素值更新过程中加入最大最小萤光素值的限定范围，从而避免算法陷入局部极小值。实验表明，新算法具有较强的全局搜索能力，而且能有效避免常规算法的早熟收敛问题，显著提高了优化性能。关键词：人工萤火虫算法；最大最小萤光素；函数优化A Glowworm Swarm Optimization Algorithm Based on Max-Min LuciferinAbstract：Artificial glowworm swarm optimization algorithm is a new research orientation in the field of swarm intelligence recently. The algorithm has been achieved success in the complex multi-modal function optimization; but it is easy to fall into local optimization, and having the low speed of convergence in the late. In order to solve these problems this article raise A glowworm swarm optimization algorithm based on max-min luciferin. In the process of glowworm swarm optimization algorithm integrates into max-min luciferin to restrict the change of luciferin，so that to avoid falling into local optimization. Simulation results show that this new algorithm has stronger global searching ability，and effective method to avoid fall into local optimization earlier，obviously improving the optimization ability.Keywords：Glowworm Swarm Optimization (GSO)；Max-Min luciferin；function optimization1 引言人工萤火虫算法(Glowworm Swarm Optimization, GSO)1-2是由K.N.Krishnanad和D.Ghose于2005年提出的一种基于多峰函数优化的新的群智能优化算法，该算法已在复杂函数优化方面取得了成功。人工萤火虫算法越来越引起人们的关注，已经成为计算智能研究领域一个新的研究热点。随着研究的不断深入, 该算法已成功应用于传感器的噪声测试4和模拟机器人5等。虽然GSO算法收敛快，具有较强的通用性，但也存在早熟收敛、搜索精度不高、后期迭代效率不高的缺点。本文基于最大最小萤光素值的设置，限定萤光素只值的变化范围，结合算法自身动态变化过程所体现出来的特点，提出了一种基于最大最小萤光素值改进的萤火虫算法(MAX-MIN Glowworm Swarm Optimization ,MMGSO)。仿真结果表明，与传统GSO算法相比，MMGSO算法能取得较好的优化性能，全局收敛性得到显著提高。2 基本的萤火虫算法在GSO算法中，每一只人工萤火虫分布在目标函数的定义空间内，这些人工萤火虫各自携带自身的萤光素，并且拥有各自的视野范围，称为区域决策范围(local-decision range)。它们的亮度与自己所在位置上的目标函数适应度值有关。月亮的萤火虫表示它所在的位置越好，即有较好的目标值。萤火虫在区域决策范围内寻找邻居集合，在集合当中，越亮的萤火虫拥有越高的吸引力吸引此萤火虫往这个方向移动，每次的飞行方向会随着挑选邻居不同而改变。另外，区域决策范围的大小会受邻居数量的影响，当邻居密度较低，萤火虫的决策半径会加大以利于寻找更多的邻居；反之，决策半径减小。最终，大部分的萤火虫回聚集在较优点处。每一个萤火虫在当前位置对应着一个目标函数值和此处的萤光素值，每一个萤火虫在它的邻居范围内传递信息。邻居数是在决策域范围内那些具有相对较高的萤光素值的萤火虫个数，初始决策范围根据目标函数的定义域来确定，以后每次迭代按式(1)进行更新。决策域范围更新公式： (1)其中, 为第代第个萤火虫第代的决策范围(即决策半径), 为感知范围, 为控制萤火虫邻居数目的邻域阈值，为控制邻居变化范围的常数。确定决策域范围内的萤火虫个数的公式为： (2)其中，为第代第个萤火虫的位置，为第代第个萤火虫的萤光素值；邻居数目被限制在动态决策域范围内，动态决策域的上界为感知范围。当萤火虫找到萤光素值比本身大的邻居萤火虫，且它们的距离差在感知范围内，则萤火虫以一定概率按公式(3)选择邻居，并且向邻居方向移动，按(4)式进行位置更新，计算此处的目标函数值，进一步的按式(5)更新萤光素的值。这种移动只取决于萤火虫的局部信息，使萤火虫群体分为不相交的子群体，呈现出一种自发的滑行行为，最后找出目标函数的最优值。路径概率选择公式： (3)位置更新公式： (4)更新萤光素值的公式： (5)其中，为第代第个萤火虫的萤光素值，为控制萤光素值的参数，为衡量函数值的参数，为适应度函数值。3 基于最大最小萤光素值的萤火虫算法3.1 算法思想在GSO的萤光素值更新阶段引入最大最小思想，对萤光素值的改变范围进行控制，按式(6)动态的改变最大最小的的限定范围，从而控制每只萤火虫的萤光素值在区间范围之内，达到避免算法陷入局部搜索停滞。 (6)3.2算法的实施步骤下面给出MMGSO的基本步骤：初始化, ,等参数；在目标函数定义域内初始化各萤火虫的位置；将最大函数适应度值赋给，最小函数适应度值赋给；fortodo 初始化萤光素值；设置最大迭代次数，当前迭代次数变量；while() do:对每个萤火虫用公式(5)进行萤光素值的更新:判定更新后的萤光素值，将其控制在范围之内:If ; If ;对每个萤火虫进行位置移动对每只萤火虫执行公式(3):使用轮盘赌方法选择移动方向的萤火虫，并用公式(4)进行位置的更新：同时用公式(1)对搜索半径进行修改：用公式(6)对萤光素值的上下限进行更新： 4 实验仿真4.1 测试函数为了验证本文算法的有效性，本文选取四个基准测试函数进行验证，并与标准GSO算法进行了比较。这四个常用测试函数如下:a) , , 即Sphere函数，在处取得全局最小值0；b），在处取得全局最小值0；c），, 即Schaffer函数，在处取得全局最小值0；d），即Goldstein-Price函数，在出取得全局最小值3。4.2 测试平台本实验用MATLAB7.0编写的仿真程序，在windows 7 操作系统，Intel Core2 T5870 2.00GHz处理器,2G内存的PC机。4.3 参数设置算法的参数设计如下：初始化时，萤火虫规模为n=100，最大迭代次数maxt=500，控制萤光素值的参数=0.4,衡量函数值的参数=0.6,控制邻居变化范围的参数=0.08,移动的步长s=0.03, 控制萤火虫邻居数目的邻域阈值nt为5初始萤光素的值l0=5。4.4 实验结果讨论对函数f1f4进行测试，进行10次独立实验，求出最优值，最差值，平均值，并与基本萤火虫算法进行比较，结果如表1所示。表1 测试函数结果比较函数算法最优值最差值平均值f1MMGSO2.462249690694056e+0033.526102419612455e+0033.029304517790742e+003GSO3.745882192827203e+0035.310507032686764e+0034.214287461976544e+003f2MMGSO1.664574118176205e+0021.994873297900615e+0021.78674173639555GSO2.071272377431366e+0022.353669670332888e+0022.194340327205097f3MMGSO0.002456080623360.003213835877440.0027391065113225GSO0.022480726071550.061102593700650.038138874802928f4MMGSO3.000000838105983.000006695199983.000003646373474GSO3.000572994846593.002210742419793.001048349543113从表1中可以看出，MMGSO无论在最优值，最差值还是平均值与原始GSO相比计算精度有了明显提高，MMGSO得到的解更接近理论最优值，尤其是f3，f4表现效果更为明显。函数f3的全局极小点是，其最优值是0;而在距全局最优点大约3.14附近有许多局部最优点，其函数强烈振荡，因此一般算法难以得到最优解。基本萤火虫算法(GSO)当进化到一定代数后，易陷入局部收敛，本文提出的MMGSO通过限制萤光素的变化范围有效的减少了陷入局部收敛的可能，从而收敛到全局最优值。函数f3，f4属于局部极小点数随维数增加而成指数增加的多峰函数，从实验结果来看，本文提出的MMGSO算法效果较好，特别是对于高维且有较多局部极小点的多峰函数更是如此。图1 f1函数的收敛曲线对比 图2 f2函数的收敛曲线对比图3 f3函数的收敛曲线对比 图4 f4函数的收敛曲线对比图1-4是本文算法和GSO算法的收敛曲线，直观地看出MMGSO算法收敛速度更快，迭代次数少，而且能收敛到复杂多极值点函数的全局最优解。5 结束语本文针对基本萤火虫算法(GSO)易陷入局部极值的缺点，提出一种基于最大最小萤光素值改进的萤火虫算法(MMGSO) 。此算法在每次迭代过程中根据目标函数适应值的改变动态地更改最大最小萤光素值，从而限定个人工萤火虫的萤光素值，已达到避免算法陷入局部极值。实验表明，新算法具有较强的全局搜索能力，而且能有效避免常规算法的早熟收敛问题，显著提高了优化性能。Reference:1 Krishnanand,K.N.D. Ghose,D. Glowworm swarm optimization: a new method for optimizing multi-modal functionsJ.Computational Intelligence Studies, 2009,1(1):93-119.2 Krishnanand,K.N. Glowworm swarm optimization: a multimodal function optimization paradigm with applications to multiple signal source localization tasksD. Indian: Department of Aerospace Engineering, Indian Institute of Science, 2007.3 Krishnanand, K.N. and Ghose, D. Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locationsJ.Robotics and Autonomous Systems, 2008,7(56): 549569.4 Krishnanand, K.N. and Ghose, D. A glowworm swarm optimization based multi-robot system for signal source localization M.Design and Control of Intelligent Robotic Sys