蛙跳萤火虫算法及其在无线电频谱分配中的应用*

李卫军（北方民族大学　网络信息技术中心，宁夏 银川 750021）

蛙跳萤火虫算法及其在无线电频谱分配中的应用*

李卫军
（北方民族大学网络信息技术中心，宁夏 银川 750021）

萤火虫算法是一种生物群智能的随机优化算法，该算法通过模拟萤火虫在觅食、择偶中产生荧光而相互吸引、移动、合作等行为来解决最优化问题。虽然该算法具有设置参数少、原理简单、更新公式清晰等优点，但是存在着种群过早收敛到局部最优解或者种群收敛速度慢等问题。为此本文提出蛙跳萤火虫算法。该算法利用蛙跳的分群思想来优化萤火虫算法。利用蛙跳算法对种群进行分群和局部深度优化，不断地迭代以寻得最优解。在对蛙跳萤火虫算法研究的基础上把它应用于无线电频谱分配中，获得比较满意的频谱分配方式。

萤火虫算法；蛙跳算法；蛙跳萤火虫算法；无线电频谱

0　引言

在当今社会的生产生活中，众多学者利用进化成功的生物的生活方式来解决经典控制理论及优化方法在解决实际问题时所出现的瓶颈问题。其中蚁群优化算法利用了蚂蚁群体分工协作的寻径方式；随机蛙跳算法模拟一群青蛙在觅食过程中分组交换信息再重新分组的过程。这类算法都源于学习或模拟某些生物的生存本领，因此此类算法多用于寻优或并行处理，因此又被统称为群智能优化算法。本文将这两种算法结合起来取长补短，用于无线电频谱分配中。

1　萤火虫算法

1.1算法的仿生原理

萤火虫算法是一种仿生群智能优化算法，是受萤火虫个体的发光行为启发而设计的，最早是由印度学者Krishnanand［1］等人于2005年提出的GSO（Glowworm Swarm Optimization），后来剑桥大学的 Yang［2］也提出类似的算法，称为FA（Firefly Algorithm）。

在热带和温带地区，夏天的晚上都会出现数量巨大的萤火虫群，据统计自然界中有大概 2000种萤火虫，大多数都会发出短促而有节奏的闪烁荧光，有的是为了求偶，有的是为了捕食或警戒等，科学家对此进行深入的研究发现其中的规律，构造出了萤火虫算法。萤火虫算法是模拟萤火虫发光行为构造出的一种随机优化算法，该算法根据其搜索区域寻找提供个体，向较优的萤火虫移动，从而实现位置优化。

萤火虫根据两个因素更新自己的位置，一是荧光亮度，二是吸引度［3］。越亮的萤火虫吸引同伴向其移动的概率就越大，以至于最后都聚集在最亮的萤火虫周围。萤火虫算法是一种群体智能优化算法，通过萤火虫的种群表示搜索空间中的解，衡量萤火虫所处的位置的优劣程度（即荧光亮度大小）用目标函数来表示，将萤火虫种群优胜劣汰过程表示为可行解的替换和变换过程。

1.2萤火虫算法的数学描述

萤火虫个体之间相互吸引主要由亮度和吸引度决定。亮度体现了萤火虫所处位置的优劣，位置又决定了萤火虫的亮度，亮度又决定了吸引度，吸引度进而决定了位置移动的距离大小和方向。由亮度和吸引度的不断变化完成目标的优化过程。从数学的角度描述［4-5］如下：

（1）萤火虫的亮度表达式

式（1）中 Ii，j表示萤火虫 i对萤火虫 j的相对亮度即吸引度；Ii表示萤火虫i在r=0处的荧光亮度，它与相对的目标函数相关，目标函数越优，自身亮点越高；ε表示荧光吸收系数，表示荧光在传输过程中随着传输距离的增加而减少的特性。

（2）萤火虫i被萤火虫j吸引后的位置移动更新函数其中，xi、xj表示萤火虫所处的位置坐标，β为步长因子，α为扰动因子，rand为［0，1］的随机函数，α（rand-）是为了避免种群陷入局部最优解而设定的扰动项。

（3）萤火虫的移动概率

萤火虫先确定某个萤火虫周围最亮的个体，这个更亮的个体对这个萤火虫的吸引度，计算这些吸引度的总和，然后根据各个更亮萤火虫的吸引度占据总吸引度的比例作为萤火虫移动的概率，计算公式如下：

其中，pij表示萤火虫个体 j向 i移动的概率，n表示萤火虫的个体i周围比它亮的个体数目。

1.3萤火虫算法流程

算法流程如下：

（1）初始化基本参数：萤火虫数目 n，光强吸收系数γ，步长因子 β，扰动因子 α，最大迭代次数 tmax等。

（2）根据约束条件随机初始化萤火虫个数，计算各个萤火虫的目标函数作为萤火虫自身的亮度。

（3）由式（1）计算各个萤火虫的相对吸引度，根据吸引度的大小决定萤火虫向其他萤火虫移动的概率。

（4）由式（2）计算各个萤火虫的更新位置，最佳位置的萤火虫进行随机扰动。

（5）根据更新后的位置重新计算亮度，即适应值。

（6）当满足搜索精度或达到最大的搜索次数时转向（7），否则搜索次数加 1，跳转到（3），进行下一轮搜索。

（7）输出全局极致个数和最优个体值。

算法的时间复杂度是 O（n2），n为萤火虫的数目。

虽然萤火虫算法有诸多优点，如原理简单、参数少、更新清晰，但与其他群智算法一样存在过早收敛到局部最优解或收敛速度过慢的问题，为此本文结合分群的思想进行改进。

2　随机蛙跳算法

2.1算法的仿生学原理

与萤火虫算法相似，随机蛙跳算法［6］也是一种群智优化算法，最初是为了解决组合优化问题，具有高效的计算性能和优良的全局搜索能力。具体思想是［7］：在一片湿地中生活着一群青蛙，它们又分为几个族群，每个族群内的每个青蛙进行信息共享来一起寻找食物，每个族群在各自寻找食物一段时间以后所有的族群又聚集在一起，以达到共享信息的目的，然后重新分群，各个族群又独自寻找食物，通过循环这个过程，青蛙共享信息，尽快找到食物。该过程既有局部信息的交流，又有全局的信息交流，算法在执行过程中可以有效防止过早陷入局部最优解，向全局最优解方向移动。

2.2算法的数学描述

（1）初始蛙跳的群体，随机产生 n只青蛙，每只青蛙的位置表示解空间的一个解，X=（x1，x2，…xm），x1，x2，…xm表示解的分量，m表示解得维数。

（2）根据实际情况状况计算出每个青蛙的目标值，对目标值优劣进行排序。

（3）对青蛙进行分子群，若分为 p个族群，每族群有q只青蛙，其中p，q满足p×q=n，第1只青蛙分到第1族群，第2只青蛙分到第2族群，以此类推，第p只青蛙分到第p族群，……，第2p只青蛙分到第p个族群。依次循环直到分配完毕。

利用式（4）随机从青蛙种群中选取q个进行分组，并将组进行排序，j表示第 j只青蛙，pj表示第 j只青蛙被选中的概率。找出最好的族群 PB和最差的族群 PW，按式（5）和（6）对每个族群进行局部深度搜索。

上面的公式中 rand（）产生 0～1之间的一个随机数，Dmax表示青蛙的跳动步长，newpw表示更新后青蛙的位置。如果 newpw处于可行解空间，计算 newpw对应的适应值，如果 newpw对应的适应值次于 oldpw所对应的适应值，则采用全集最优解PX代替上面公式中的PB更新oldpw。如果更新之后仍然没有改进，随机产生的新的青蛙来代替PW，重复上述过程，直到预设的迭代次数完毕。所有的族群完成深度搜索后，将所有的族群进行混合重新排序，之后再将青蛙分成子族群，继续全局搜索，直到预设的条件满足为止。

3　蛙跳萤火虫算法

蛙跳萤火虫算法［8］就是把萤火虫算法和随机蛙跳算法结合起来，具体结合方式如下：设置好算法各项参数：迭代次数r，族群规模n，分群数目m等，初始化萤火虫的族群粒子，根据目标函数计算各个萤火虫粒子的目标值，按照目标值的优劣进行排序，按照蛙跳算法进行分群。分群之后各个子种群按照蛙跳算法独立进行深度优化，当达到迭代次数后又合为一个种群，对总的种群按照萤火虫算法进行寻优，达到迭代次数后重新分群，重复以上步骤直到达到要求或者满足迭代次数。

4　利用蛙跳萤火虫算法对无线电频谱进行分配

传统的频谱管理机制限定某一频段内的频谱只有该频段的授权用户可以使用，造成了这些频道的频谱利用率低下且存在大量的频谱空洞。本文利用蛙跳萤火虫算法对这一情况将分配方法进行改进。

4.1基于蛙跳萤火虫算法中的基本概念

（1）萤火虫

每一种频谱分配方案只有一只萤火虫，用矩阵X表示，X=［x1，x2，…xn］T，其中 xj是对信道 j的分配向量，xj= ［x1j，x2j，…xNj］，xij∈｛0，1｝，xij=1表示第 i个次级用户获得信道j的使用权，反之失败。同时萤火虫的位置更新，即每一种方案代表的分配矩阵的元素改变。

（2）荧光亮度

每一只萤火虫所处的位置都会对应一个荧光亮度，即每一种分配方案都能计算出一个与之对应的目标函数值。个体在当前所处的位置的亮度，取决于目标函数值，目标函数值越高自身亮度越亮。

（3）空间距离 rij

rij为萤火虫 i与 j之间的空间距离，萤火虫的位置用坐标（x1，x2，…xN）表示，其中 xj为对于信道 j的分配向量。公式（1）计算出萤火虫 i处看到个体j的亮度。

4.2算法的主要流程

（1）输入萤火虫算法的各项参数，输入无线分配的参数等。

（2）初始化萤火虫粒子，即各个频谱分配方案，每个粒子可以按如下的方式初始化：

其中，xij表示第 i个次级用户获得信道j的使用权。

（3）对各个粒子进行评价，计算出目标适应值，用蛙跳萤火虫算法对种群进化寻优，达到迭代次数后按目标适应值大小排序，分群。

（4）利用随机蛙跳算法对各个子种群局部深度优化，在寻优的过程中如果出现不符合约束的粒子则直接舍去，重新初始化新粒子代替，达到迭代次数后各种群重新混合。

（5）迭代次数减 1，判读迭代次数是否为 0，若不为0转到（3），否则选出此时最优解，实验完毕。

4.3实验仿真

本文利用MATLAB进行仿真，参数设置如表1。

系统中参数的设定不同会造成系统性能差异很大，最大迭代次数是一个很重要的参数，增大 tmax可以提高算法精度，但也增加计算量，因此选择合适的 tmax至关重要。本文中针对萤火虫数量分别在60、80、100三种情况下，次级用户数分别是10，12，14，16，18时，测试收敛的平均迭代次数，测试结果如图1所示。从图中可以看出，萤火虫的数量越多收敛速度越快，并且次级用户较少时收敛速度也快。除了最大的迭代次数，种群规模也就是萤火虫的数量n的大小也很重要。n越大算法精度越高，计算量越大，因此选择一个合适的种群规模对于提高算法整体性能非常重要。

表1　蛙跳萤火虫算法中相关参数的设定

图1　萤火虫数量不同情况下次级用户数对收敛迭代次数的影响

5　结论

本文主要介绍了萤火虫算法和随机蛙跳算法的基本原理，并用数学方法进行描述，对算法的执行流程进行了说明，然后把萤火虫算法和随机蛙跳算法两者结合，形成了蛙跳萤火虫算法，并且把该算法应用于无线电频谱分配。实验表明，蛙跳萤火虫算法在求解组合优化问题方面是有效的。

［1］KRISHNANAND K N，GHOSE D.Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications［J］.Multiagent and Grid Systems，2006，2（3）：209-222.

［2］Yang Xinshe.Firefly algorithms for multimodal optimization［J］. Lecture Note in Computer Sciences，2010（3）：169-178.

［3］KWIECIEN J，FILIPOWICZ B.Firefly algorithm in optimization of queueing system［J］.Bulletin of the Polish Academy of Sciences.Technical Sciences，2012，60（2）：363-368.

［4］GANDOMi A H，Yang Xinshe，ALAVI A H.Mixed variable structural optimization using firefly algorithm［J］.Computers&Structures，2011，89（23-24）：2325-36.

［5］莫愿斌，刘付永，马彦追.模拟生物理想自由分布模型的萤火虫算法［J］.计算机与应用化学，2014，31（2）：153-160.

［6］HENSHALL P，PALMER P.A leapfrog algorithm for coupledconductiveandradiativetransientheattransferin participating media［J］.InternationalJournal ofThermal Sciences，2008，47（4）：388-398.

［7］宋晓华，杨尚东，刘达.基于蛙跳算法的改进支持向量机预测方法及应用［J］.中南大学学报（自然科学版），2011，42（9）：2737-2740.

［8］李洋.蛙跳萤火虫算法及其在含风电场的电力系统调度中的应用［D］.上海：华东理工大学，2013.

Study on leapfrog firefly algorithm and its application in the radio spectrum allocation

Li Weijun
（Network Information Technology Center，Beifang University of Nationalities，Yinchuan 750021，China）

Firefly algorithm is a stochastic biota intelligent optimization algorithm，which simulates fireflies in foraging，mate choice in fluorescence attract each other，moving，and other acts of cooperation to solve the optimization problem.Although the firefly algorithm has many advantages，such as few parameters，simple principle，clear updating formulas，etc.，there is population of premature convergence to local optima，or populations of slow convergence and other issues.This paper proposes leapfrog firefly clustering algorithm that uses the leapfrog thought to optimize the firefly leapfrog algorithm.In order to find the optimal solution，leapfrog algorithm continuously iterates under clustering and local populations depth optimization.Based on research of the leapfrog firefly algorithm，it is applied to the radio frequency spectrum allocation，to obtain satisfactory way of spectrum allocation.

firefly algorithm；leapfrog algorithm；leapfrog firefly algorithm；radio spectrum

TP311

A

1674-7720（2015）05-0016-03

宁夏自然科学基金（NZ12138）；北方民族大学自然科学基金（2013XYZ028）

（2014-10-12）

李卫军（1979-），男，博士研究生，讲师，主要研究方向：智能信息处理。E-mail：liweijun51@163.com。