DOI:10.11990/jheu.201605106
, , , 2. 海军驻哈尔滨汽轮机厂有限责任公司军事代表室, 黑龙江 哈尔滨 150046;
3. 哈尔滨工程大学 自动化学院, 黑龙江 哈尔滨 150001;
4. Design Engineering and Mathematics, Middlesex University, Hendon NW4 4BT, UK
, , , 2. Department of Navy Equipment Military Representative Office Shenyang Region, Harbin 150046, China;
3. College of Automation, Harbin Engineering University, Harbin 150001, China;
4. Design Engineering and Mathematics, Middlesex University, Hendon NW4 4BT, UK
自然科学、社会科学和工程应用中的大部分问题都可以归结为全局优化问题。全局优化问题广泛应用于图像处理[1]、路径规划[2]、金属橡胶卡箍隔振[3]、电力系统[4]、无线网络规划[5]等领域。近年，随着对全局优化问题研究的不断深入，其理论和方法得到了进一步的发展，一些优秀的优化算法也不断被提出[6-8]。目前，主要的优化算法可分为确定性算法和随机性算法两大类。确定性算法主要包括爬山法 (Hill-Climbing)[9]、牛顿迭代法 (Newton-Raphson)[10]和单纯型法 (simplex method)[11]等。对于确定性算法如果迭代开始于同样的初始化猜想，算法将得到相同的系列解。其优点主要集中于对于特定的问题拥有很高的收敛效率，往往仅需要很少的迭代次数。但是由于确定性算法属于局部搜索算法，不可避免的容易陷入局部最优。
而随机搜索算法因其所特有的随机机制可以使算法很容易跳出局部最优从而找到全局最优解。即使在相同的初始化条件下，算法也将会产生不同的解集。所以对于不同的个体其寻优路线一般是不可重复的 [12]。
大部分随机搜索算法可以被认为是元启发式算法 (metaheuristic algorithm)。很多新型的元启发式算法大部分是受到自然界中物理过程或生物智能的启发而提出的。比较有代表性的算法主要包括：模拟退火算法 (simulated annealing，SA)[13]、差分进化算法 (differential evolution，DE)[14]、粒子群算法 (particle swarm optimization，PSO)[15]、遗传算法 (genetic algorithm，GA)[16]、蚁群算法 (ant colony optimization，ACO)[17]、人工蜂群算法 (artificial bee colony，ABC)[18]、蝙蝠算法 (bat algorithm，BA)[19]和萤火虫算法 (firefly algorithm，FA)[20]等。其优点主要包括两部分：算法自身所具有的良好的信息共享机制可以使算法在一定条件下快速收敛；随机搜索算法不容易陷入局部最优。
本文在深入分析萤火虫算法基本原理的基础上，提出基于随机机制的改进萤火虫算法，以平衡算法间的全局探测与局部搜索能力。然后使用13个基本测试函数验证改进算法的有效性。并对本文提出的算法与粒子群算法、差分算法和模拟退火算法进行性能间的横向比较。
1 萤火虫算法 1.1 萤火虫算法的生物学原理萤火虫算法 (firefly algorithm，FA) 是由剑桥大学学者Xinshe Yang于2008年提出的一种新型的自然启发式优化算法，该算法模拟自然界中热带萤火虫的发光机制和行为方式，是一种基于群体智能的随机搜索算法[21]。
自然界中的绝大多数萤火虫都会闪光，萤火虫利用这种闪光机制进行求偶、沟通或者防御潜在的捕食者。这种闪光仅在一定范围内可以被其他萤火虫感知，主要有以下两方面原因：光强度和距离光源的距离成平方反比关系；光会被空气所吸收。
为了构建萤火虫算法的数学模型，使用以下三个理想化准则：
1) 算法中的所有萤火虫都不分雌雄，即萤火虫之间的吸引只基于亮度，不考虑性别。
2) 萤火虫之间的吸引力和亮度成正比，亮度越大，吸引力越强。因此亮度小的萤火虫会向亮度大的萤火虫移动。
3) 萤火虫的光亮度与待优化目标函数的值有关。
1.2 标准萤火虫算法的数学描述及实现由于距离的增加和空气对光的吸收，萤火虫i的亮度会随着距离r的增加而逐渐减小。为了对萤火虫之间相互吸引力进行建模，本文首先给出萤火虫绝对亮度和相对亮度的定义。
定义1：绝对亮度。对于萤火虫i，初始光强度 (r=0处的光强度) 为萤火虫i的绝对亮度，记作Ii。
定义2：相对亮度。萤火虫i在萤火虫j所在位置处的光强度为萤火虫i对萤火虫j的相对亮度，记作Iij。
萤火虫算法的核心思想是萤火虫被种群中所有绝对亮度比它大的萤火虫所吸引，并根据算法中的位置更新公式进行位置更新，不断迭代直至达到算法的停止准则 (达到既定的迭代次数或寻优精度)。下面，将分别对相对亮度、吸引力和位置更新机制进行数学建模[22]。
一般情况下，我们用待优化函数的目标函数值表征算法的绝对亮度。假设在点x=(x1，x2，…，xd) 处萤火虫i的绝对亮度Ii与x处的目标函数值成正比，即Ii∝f(x)。
考虑到萤火虫i的亮度随着距离的增加以及空气的吸收而减弱，可以定义萤火虫i对萤火虫j的相对亮度为
| $ {I_{ij}}\left( {{r_{ij}}} \right) = {I_i}{{\rm{e}}^{-\gamma r_{ij}^2}} $ | (1) |
式中：Ii为萤火虫i的绝对亮度。γ为光吸收系数，可设为常数；rij为到萤火虫i到萤火虫j的笛卡尔距离:
| $ {r_{ij}} = {x_i}-{x_j} = \sqrt {\sum\limits_{k = 1}^d {{{\left( {{x_{i, k}}-{x_{j, k}}} \right)}^2}} } $ | (2) |
假设萤火虫j的绝对亮度比萤火虫i的绝对亮度大，则萤火虫i被萤火虫j吸引而向j移动。这种吸引力的大小是由萤火虫j对萤火虫i的相对亮度决定的，相对亮度越大，吸引力越大。则由萤火虫j相对亮度的定义，可得萤火虫j对萤火虫i的吸引力βij(rij) 为
| $ {\beta _{ij}}\left( {{r_{ij}}} \right) = {\beta _0}{{\rm{e}}^{-\gamma r_{ij}^2}} $ | (3) |
式中：β0为最大吸引力，即在光源处 (r=0处) 萤火虫的吸引力。此吸引力模型可以使种群中的个体自动分成几个小的种群，同时进行寻优，大大增加了算法的求解速度，尤其适合解决多模态问题。
由于被萤火虫j吸引，萤火虫i向其移动而更新自己的位置，i位置更新公式为
| $ x_i^{t + 1} = x_i^t + {\beta _0}{{\rm{e}}^{-\gamma r_{ij}^2}}\left( {x_j^t-x_i^t} \right) + \alpha {\mathit{\boldsymbol{\varepsilon }}_i} $ | (4) |
式中：t为算法的迭代次数；εi是由高斯分布、均匀分布或者其他分布得到的随机数；α为随机项系数。此位置更新公式由三部分组成：第一部分为萤火虫当前时刻的位置信息，第二项为吸引力项，第三项是带有特定系数的随机项。
2 基于随机机制的改进萤火虫算法探测能力和搜索能力的平衡是大多数元启发式式算法的核心问题[23-25]。探测能力体现出算法探测到新的解空间的能力，而搜索能力指的是算法在局部邻域内搜索到更高精度的解的能力。根据不同的分类方法，探测能力和搜索能力的平衡也可以理解为算法的多样性和一致性之间的平衡[26]。
在元启发式算法中，探测能力的提高一般可以通过引入随机机制来实现[27-28]。随机机制的引入可以使算法以更大的几率跳出局部最优从而实现全局搜索，以保证算法收敛到全局最优。而搜索能力的提升更多是依赖于丰富的局部信息，如梯度、模态和算法运行过程中的历史信息。
事实上，随机机制是元启发式算法中非常重要的一种搜索机制。一方面，当随机步长较长时，算法可在全局范围内进行搜索，从而可以在一定层度上增强算法的探测能力。另一方面，当随机步长大小减小到局部范围内的时候，算法可以在当前最优解附近进行深度搜索，以增强算法的搜索能力。
综合以上分析，在本文中，我们从两个方面对萤火虫算法的位置移动公式进行改进。首先对式 (4) 中第二项吸引力项进行改进。在吸引力算子中加入随机因素以对吸引力系数进行扰动，增加算法跳出局部最优的能力。
| $ \beta = {\beta _0}{{\rm{e}}^{-\gamma r_{ij}^2}}{R_i} $ | (5) |
本文中，分别取Ri为指数分布 (exponential distribution) 和韦伯布 (weibull distribution)，并分别记为EFA和WFA。
其次，对第3项带有特定系数的随机项进行改进。若随机项系数α取固定值时，第3项则可以被认为是完全随机项。此时随机项在整个算法运行的过程中并不能特别有效的调节算法的探测能力和搜索能力。所以在本文中对随机项系数α进行递减操作。以便随机项在迭代初期拥有较大的随机步长，使算法更好的在全局范围内进行搜索；迭代后期步长逐渐减小，以便算法在局部范围内精细化搜索。α递减公式为
| $ \alpha = {\alpha _0}{\delta ^t}S, \;\;\;\;\;\;\;0 < \delta < 1 $ | (6) |
式中：α0为初始随机步长，δ为冷却系数，S为待优化问题的问题域。
综上所述，改进后的算法位置移动公式为
| $ x_i^{t + 1} = x_i^t + {\beta _0}{{\rm{e}}^{-\gamma r_{ij}^2}}{R_i}\left( {x_j^t-x_i^t} \right) + {\alpha _0}{\delta ^t}S{\varepsilon _i} $ | (7) |
改进萤火虫算法的伪代码可表示为：
1) 定义目标函数f(x)，x=(x1，x2，…，xd)T
2) 设置算法参数β0，γ，α0，Ri，δ以及最大迭代次数MaxGeneration
3) 初始化萤火虫种群xi(i=1，2，…n)，n为萤火虫的个数
4) 根据xi处的目标函数值确定各个萤火虫的绝对亮度
5) while (t < MaxGeneration)
6) for i=1:n全部萤火虫
7) for j=1:n全部萤火虫
8) 计算xi和xj之间的笛卡尔距离rij
9) if (Ij > Ii)
10) 计算萤火虫j对萤火虫i的吸引力βij(rij)
11) 由位置更新式 (7) 更新萤火虫i的位置
12) end if
13) 更新目标函数值及萤火虫的亮度
14) end for j
15) end for i
16) 重新排列所有萤火虫，找到当前最优解
17) end while
18) 输出最优解及其对应的位置信息
3 仿真实验与分析 3.1 基本测试函数测试函数在评估算法性能方面起到了至关重要的作用，例如算法的收敛速度、求解精度、鲁棒性以及性能表现的通用性。为了测试改进的萤火虫算法与其他已知算法的性能，本文从CEC2005推荐的基本测试函数中选取了13个测试函数进行算法性能测试，所有函数都以求取极小值为例[29-30]。并根据其局部最优解的个数，将13个测试函数分为：单模测试函数和多模测试函数。分别如表 1和表 2所示。
| 函数 | 表达式 | 问题域 | 最小值 |
| Sphere | [－100，100]D | 0 | |
| Schwefel′s 2.22 | [－10，10]D | 0 | |
| Schwefel′s 1.20 | [－100，100]D | 0 | |
| Schwefel′s 2.21 | f4(x)=maxi{|xi|，1≤i≤D} | [－100，100]D | 0 |
| Rosenbrock | [－30，30]D | 0 | |
| Step | [－100，100]D | 0 | |
| Quartic Noise | [－1.28，1.28]D | 0 |
| 函数 | 表达式 | 问题域 | 最小值 |
| Schwefel′s 2.26 | [－500，500]D | -12 569.5 | |
| Rastrigin | [－5.12，5.12]D | 0 | |
| Ackley | [－32，32]D | 0 | |
| Griewank | [－600，600]D | 0 | |
| Pendlized | [－50，50]D | 0 | |
| Generalized Pendlized | u(xi，a，k，m) 取值同f12的u(xi，a，k，m) |
[－50，50]D | 0 |
单模测试函数在问题域内只含有一个全局最优，因此适合测试函数的局部搜索能力。相对于算法最终的收敛精度，我们更关心此类测试函数的收敛速度的快慢。对于多模测试函数，随着问题维数的增加其局部最优值的数量呈指数级增加。所以此类测试函数适合测试算法的探测能力。由于关系到算法是否具有跳出局部最优并寻找到近全局最优的点的能力，因此我们更关注优化算法求解此类问题时的求解精度问题。
3.2 算法参数设置为了测试改进的算法的性能，我们将其得到的结果与标准FA，SA，PSO以及DE进行比较。
在所有算法中，种群大小设置为40，基本测试函数中问题的维数设置为30，最大迭代次数 (即算法的停止准则) 为2 000，并在测试函数的问题域内对种群进行随机初始化。另外，为了对算法性能进行统计学分析，设置算法在不同的初始化条件下独立运行30次，并利用适应度函数的最小值、最大值、均值和标准差进行统计结果分析。
对于标准FA，设其初始化吸引力系数β0=1，光吸收系数γ=1，随机系数α在整个迭代过程中单调递减 (α=0.25×0.95iter，其中0.25为初始化随机因子，iter为当前迭代代数)。最后，由于Lévy飞行可以提供一些较长的跳跃使算法跳出局部最优，选择莱维飞行来产生随机数εi。对于SA算法，其初始温度t0=0.1，温度下降率α=0.99，并以p=e－δ/iter，δ=(fnew－f)/f的概率接受非最优解。对于PSO算法，设置其学习因子c1=c2=2，惯性权重由ωmax=0.9到ωmin=0.4进行线性递减。在DE算法中设置缩放因子F=0.5，交叉系数Cr=0.9。表 3为算法参数选取总结。
| 算法 | 控制参数 | ||||
| EFA | β0=1 | γ=1 | R=指数分布 | α=0.25×0.95iter | εi=lévy飞行 |
| WFA | β0=1 | γ=1 | R=韦布分布 | α=0.25×0.95iter | εi=lévy飞行 |
| FA | β0=1 | γ=1 | α=0.25×0.95iter | εi=lévy飞行 | |
| PSO | ωmax=0.9 | ωmin=0.4 | c1=2 | c2=2 | |
| DE | F=0.5 | Cr=0.9 | |||
| SA | t0=0.1 | α=0.99 | p=e－δ/iter | δ=(fnew－f)/f | |
如上文所讨论的，对于单模测试函数f1~f7，主要用来测试算法的局部搜索能力和收敛速度。对于30维的单模测试函数，其30次独立实验的统计学结果如表 4所示，其中最优的均值结果已加粗显示。
| 算法 | 统计方法 | f1 | f2 | f3 | f4 | f5 | f6 | f7 |
| EFA | Best | 5.33×10-87 | 2.8×10-44 | 3.49×10-23 | 8.69×10-44 | 0.030 6 | 0 | 0.000 134 |
| Worst | 8.67×10-87 | 3.62×10-44 | 3.50×10-20 | 1.55×10-40 | 11.068 6 | 0 | 0.000 867 | |
| Mean | 6.84×10-87 | 3.20×10-44 | 5.76×10-21 | 1.08×10-41 | 8.175 6 | 0 | 0.000 398 | |
| Stdev | 9.15×10-88 | 2.15×10-45 | 1.00×10-20 | 3.48×10-41 | 3.237 6 | 0 | 0.000 153 | |
| WFA | Best | 1.14×10-87 | 1.37×10-44 | 2.360 90 | 1.30×10-44 | 26.112 1 | 0 | 0.000 781 |
| Worst | 1.88×10-87 | 1.82×10-44 | 133.493 1 | 1.79×10-44 | 87.990 4 | 0 | 0.004 299 | |
| Mean | 1.52×10-87 | 1.64×10-44 | 29.588 6 | 1.62×10-44 | 29.042 3 | 0 | 0.002 161 | |
| Stdev | 1.91×10-88 | 1.08×10-45 | 25.212 2 | 1.05×10-44 | 11.135 5 | 0 | 0.001 034 | |
| FA | Best | 3.19×10-87 | 2.62×10-44 | 208.32 | 2.486 5 | 22.938 | 0 | 0.020 281 |
| Worst | 5.54×10-87 | 3.32×10-44 | 2 034.50 | 12.650 0 | 354.220 | 1 | 0.107 39 | |
| Mean | 4.41×10-87 | 2.90×10-44 | 802.94 | 7.022 7 | 80.872 | 0.2 | 0.050 547 | |
| Stdev | 6.09×10-88 | 1.58×10-45 | 446.09 | 2.135 4 | 84.038 | 0.4 | 0.023 087 | |
| SA | Best | 2.04×10-32 | 5.90×10-17 | 5.82×10-32 | 6.03×10-17 | 0.014 6 | 0 | 0.000 962 |
| Worst | 3.60×10-32 | 8.22×10-17 | 1.83×10-31 | 8.43×10-17 | 126.135 1 | 0 | 0.006 317 | |
| Mean | 2.94×10-32 | 6.95×10-17 | 1.07×10-31 | 7.15×10-17 | 8.958 6 | 0 | 0.003 122 | |
| Stdev | 4.35×10-33 | 5.93×10-18 | 2.23×10-32 | 6.24×10-18 | 27.362 4 | 0 | 0.001 226 | |
| PSO | Best | 1.26×10-13 | 3.37×10-9 | 192.70 | 3.080 3 | 4.226 | 0 | 0.015 834 |
| Worst | 1.22×10-9 | 1.14×10-7 | 1136.00 | 9.760 7 | 200.370 | 0 | 0.062 052 | |
| Mean | 9.07×10-11 | 3.53×10-8 | 530.87 | 6.159 2 | 51.998 | 0 | 0.032 401 | |
| Stdev | 2.28×10-10 | 2.76×10-8 | 230.55 | 1.889 1 | 42.090 | 0 | 0.010 712 | |
| DE | Best | 1.51×10-9 | 3.13×10-4 | 6.09×10-2 | 3.75×10-1 | 15.119 | 0 | 0.004 727 |
| Worst | 4.65×10-8 | 1.67×10-3 | 1.24×100 | 1.80×100 | 26.360 | 0 | 0.020 627 | |
| Mean | 1.26×10-8 | 6.26×10-4 | 3.24×10-1 | 9.53×10-1 | 22.138 | 0 | 0.013 124 | |
| Stdev | 1.11×10-8 | 2.44×10-4 | 2.82×10-1 | 3.97×10-1 | 2.698 | 0 | 0.004 42 |
通过表 4的统计分析结果可以看出，除了f3之外，对于单模测试函数EFA和WFA得到的测试结果要远远优于其他的对比算法。通过分析30次独立运算得到的结果的均值，可以看出EFA和WFA具有较高的求解精度；同样，通过分析表 4中的方差结果可以看出，EFA和WFA具有较高的鲁棒性。事实上，以上结论的得出符合无免费午餐定理 (no-free lunch theorem)[31-32]，即没有一个普适的算法其求解所有问题的能力都优于其他算法。
球函数f1是最为常用的单模测试函数，在原点处取全局最优。EFA、WFA和FA算法都能以较高的精度找到全局最优，但相比较而言，PSO和DE算法最终解的精度并不高。对于f3而言，WFA和FA等陷入局部最优，并不能得到理想的优化解，但EFA和SA可以摆脱局部最优从而寻找到全局最优解。函数f5又可称为banana function，其全局最优处在一个平坦的抛物线形的峡谷地带，相对较难优化。对于此函数，WFA和SA都能得到比较理想的解，但SA得到的解的稳定性相对较差。对于函数f6和f7来说，本文提到的几种算法都可以得到较好的解，但EFA和WFA可以得到相对更优秀的解。
下面，通过函数的收敛曲线进一步分析本文涉及到的算法的性能。
如图 1所示，对于Sphere函数，EFA、WFA和FA算法在收敛速度和精度上都优于SA、PSO和DE算法。其中，EFA、WFA和FA算法仅需200次迭代就能达到PSO和DE算法2000次迭代的精度；同样，EFA、WFA和FA算法仅需800次迭代就能超越SA算法2 000次迭代的精度。从局部放大图上可见，在整个迭代过程中，EFA、WFA和FA几乎拥有相同的收敛性能。PSO算法在迭代初期收敛速度较慢，后期收敛速度加快，在1 700次迭代左右其收敛性能超越DE算法。
|
| 图1 基于Sphere函数的算法性能比较 Figure 1 Comparison between the mentioned algorithms on Sphere function |
从图 2可以看出，对于Schwefel′s 2.22函数，在迭代初期，所有的算法都具有较快的收敛速率。但是当算法运行到200代左右时，PSO算法和DE算法迅速陷入局部最优。而EFA、WFA和FA则能跳出局部最优，并向全局最优进行进一步的搜索。
|
| 图2 基于Schwefel′s 2.22函数的算法性能比较 Figure 2 Comparison between the mentioned algorithms onSchwefel′s 2.22 function |
对于Schwefel′s 2.21函数，通过图 3可知，EFA和WFA依然具有比较优秀的表现，但是FA、PSO和DE却在算法迭代初期就陷入局部最优且在整个迭代过程中并没有有效的机制使其跳出局部最优。
|
| 图3 基于Schwefel′s 2.21函数的算法性能比较 Figure 3 Comparison between the mentioned algorithms onSchwefel′s 2.21 function |
同样，对30维的多模测试函数进行30次独立测试，并对测试结果进行统计学分析。对于多模测试函数，主要测试算法跳出局部最优以寻求全局最优的能力，即算法的全局探测能力。相对于算法的收敛速度，我们更看重其最终的收敛精度。
从表 5中可以看出，对于多模测试函数，EFA、WFA和SA算法表现出较强的全局优化能力。尤其是WFA算法，几乎对所有的多模测试函数都能找到比较优秀的全局最优解。由此可以说明韦布分布可以为FA算法提供比较适宜的随机扰动步长，使算法能够高效的跳出局部最优，并向全局最优解靠近。FA、PSO和DE算法则比较容易陷入局部最优，使最终得到的优化结果并不理想。
| 算法 | 统计方法 | f8 | f9 | f10 | f11 | f12 | f13 |
| EFA | Best | -10 931.10 | 16.914 3 | 7.99×10-15 | 0 | 1.57×10-32 | 1.35×10-32 |
| Worst | -8 328.49 | 49.747 9 | 2.22×10-14 | 0.007 4 | 1.57×10-32 | 1.35×10-32 | |
| Mean | -9 935.95 | 31.175 4 | 1.38×10-14 | 0.000 2 | 1.57×10-32 | 1.35×10-32 | |
| Stdev | 610.31 | 8.029 4 | 5.23×10-15 | 0.001 4 | 5.57×10-32 | 5.57×10-32 | |
| WFA | Best | -10 240.20 | 4.974 8 | 7.99×10-15 | 0 | 1.57×10-32 | 1.35×10-32 |
| Worst | -7 752.90 | 16.914 3 | 2.22×10-14 | 0 | 1.57×10-32 | 1.35×10-32 | |
| Mean | -8 968.14 | 9.319 4 | 1.42×10-14 | 0 | 1.57×10-32 | 1.35×10-32 | |
| Stdev | 576.62 | 3.041 3 | 4.06×10-15 | 0 | 5.57×10-32 | 5.57×10-32 | |
| FA | Best | -10 714.00 | 17.909 0 | 1.51×10-14 | 0 | 1.57×10-32 | 1.35×10-32 |
| Worst | -9 587.22 | 51.738 0 | 3.29×10-14 | 0.056 7 | 1.751 2 | 0.016 9 | |
| Mean | -10 193.00 | 31.408 0 | 2.04×10-14 | 0.010 4 | 0.286 2 | 0.000 6 | |
| Stdev | 274.10 | 8.128 1 | 6.03×10-15 | 0.011 7 | 0.479 8 | 0.003 1 | |
| SA | Best | -12 451.05 | 18.904 2 | 4.44×10-15 | 0 | 1.57×10-32 | 1.35×10-32 |
| Worst | -11 503.54 | 45.768 0 | 7.99×10-15 | 0.049 3 | 1.04×10-1 | 1.35×10-32 | |
| Mean | -12 056.91 | 34.127 1 | 6.93×10-15 | 0.020 1 | 3.46×10-3 | 1.35×10-32 | |
| Stdev | 229.76 | 6.641 8 | 1.66×10-15 | 0.012 4 | 0.018 9 | 5.57×10-48 | |
| PSO | Best | -10 057.00 | 17.910 0 | 3.37×10-7 | 1.42×10-12 | 5.67×10-12 | 2.03×10-11 |
| Worst | -7670.50 | 46.763 0 | 5.94×10-5 | 0.112 7 | 0.414 7 | 0.011 0 | |
| Mean | -8974.30 | 30.647 0 | 5.37×10-6 | 0.025 0 | 0.038 0 | 0.003 3 | |
| Stdev | 514.80 | 7.456 4 | 1.08×10-5 | 0.026 0 | 0.088 1 | 0.005 1 | |
| DE | Best | -5 930.30 | 158.610 0 | 4.42×10-5 | 1.14×10-6 | 3.00×10-9 | 2.62×10-8 |
| Worst | -4 608.10 | 185.960 0 | 0.931 6 | 0.086 4 | 0.002 8 | 0.000 2 | |
| Mean | -5 081.20 | 174.160 0 | 0.031 4 | 0.008 1 | 0.000 1 | 1.95×10-5 | |
| Stdev | 339.35 | 8.339 8 | 0.170 0 | 0.017 9 | 0.000 5 | 3.78×10-5 |
下面，通过函数的收敛曲线进一步分析本文涉及到的算法的性能。
如图 4所示，对于Rastrigin函数，WFA可以得到比较理想的优化效果。在初始化迭代过程中，WFA、FA、EFA和SA算法都拥有较快收敛速度。随着迭代的进行，FA、EFA和SA算法迅速陷入局部最优。有趣的是对于Rastrigin函数，FA和EFA几乎拥有同样的收敛曲线。PSO算法一直尝试跳出局部最优并向全局最优点移动，但整个迭代过程中，由于其收敛速率较慢，导致最终的收敛精度并不理想。DE算法在算法迭代初期就陷入局部最优，并一直在局部最优附近游荡，直到算法迭代结束。
|
| 图4 基于Rastrigin函数的算法性能比较 Figure 4 Comparison between the mentioned algorithms onRastrigin function |
从图 5可知，对于Griewank函数，WFA和EFA具有相当快的收敛速度，在算法迭代400次左右时即能达到全局最优并跳出迭代。FA和SA在算法迭代初期拥有较快的收敛速度，但是在400次迭代左右陷入局部最优，且没能成功跳出局部最优，导致算法寻优失败。PSO算法在算法迭代初期，收敛速度较慢，但是当算法迭代到第1 600代左右时，迅速向全局最优点收敛。DE算法则一直以较慢的速度进行寻优。
|
| 图5 基于Griewank函数的算法性能比较 Figure 5 Comparison between the mentioned algorithms onGriewank function |
对于Pendlized函数，通过图 6可以看出，EFA和WFA依然拥有较快的收敛速率和较高的收敛精度。FA和SA在算法迭代初期拥有较快的收敛速度，但很快就陷入局部最优，直至算法迭代结束。PSO和DE则在整个迭代过程中以较慢的速率进行收敛，最终得到优于FA和SA算法的优化解。
|
| 图6 基于Pendlized函数的算法性能比较 Figure 6 Comparison between the mentioned algorithms onPendlized function |
本文提出的改进萤火虫算法具有以下优势：
1) 改进算法中的随机机制可以增加算法的全局探测能力，从而增加算法的求解速度；
2) 随机步长单调递减机制可以使算法在迭代初期拥有较强的全局探测能力，后期拥有较强的局部探测能力，提高算法的收敛精度；
3) 以上两种机制的混合，可以使算法更好的平衡算法的全局探测能力和局部搜索能力，从而提升算法跳出局部最优的能力和鲁棒性。
4) 由数值结果和算法的收敛曲线可以明显看出改进的萤火虫算法的收敛速度和精度要远远高于粒子群算法和差分进化算法。
| [1] | HORNG M H. Vector quantization using the firefly algorithm for image compression[J]. Expert systems with applications, 2012, 39(1): 1078–1091. DOI:10.1016/j.eswa.2011.07.108 |
| [2] |
刘利强. 蚁群优化方法研究及其在潜艇导航规划中的应用[D]. 哈尔滨: 哈尔滨工程大学, 2007.
LIU Liqiang. Ant colony optimization methods and its applications in navigation planning for submarine[D]. Harbin:Harbin Engineering University, 2007. |
| [3] |
李鑫, 张利剑, 何银铜. 改进PSO的金属橡胶卡箍隔振仿真分析与参数优化[J].
智能系统学报, 2015(4): 599–606.
LI Xin, ZHANG Lijian, HE Yintong. Simulation analysis and parameter optimization of vibration isolation of metal rubber clamps based on the modified PSO[J]. CAAI transactions on intelligent systems, 2015(4): 599–606. |
| [4] |
赵娜, 张伏生, 魏平, 等. 基于改进多粒子群算法的电力系统无功优化[J].
西安交通大学学报, 2006, 40(4): 463–467.
ZHAO Na, ZHANG Fusheng, WEI Ping, et al. Reactive power optimization based on improved poly-particle swarm optimization algorithm[J]. Journal of Xi'an Jiaotong University, 2006, 40(4): 463–467. |
| [5] |
常远, 谢红, 解武. 改进智能算法的认知无线Mesh网络优化频谱分配算法[J].
应用科技, 2015(2): 24–28.
CHANG Yuan, XIE Hong, XIE Wu. Spectrum allocation optimization algorithm based on improved intelligence algorithm in cognitive wireless Mesh networks[J]. Applied science and technology, 2015(2): 24–28. |
| [6] | PARDALOS P M, ROMEIJN H E. Handbook of global optimization:Vol.2.[M].[S.l.]:Springer Science & Business Media, 2013. |
| [7] | KAVOUSI-FARD A, SAMET H, MARZBANI F. A new hybrid modified firefly algorithm and support vector regression model for accurate short term load forecasting[J]. Expert systems with applications, 2014, 41(13): 6047–6056. DOI:10.1016/j.eswa.2014.03.053 |
| [8] | SU C T, LEE C S. Network reconfiguration of distribution systems using improved mixed-integer hybrid differential evolution[J]. Power delivery, 2003, 18(3): 1022–1027. DOI:10.1109/TPWRD.2003.813641 |
| [9] | GOLDFELD S M, QUANDT R E, TROTTER H F. Maximization by quadratic hill-climbing[J]. Econometrica:journal of the econometric society, 1966: 541–551. |
| [10] | ABBASBANDY S. Improving Newton-Raphson method for nonlinear equations by modified Adomian decomposition method[J]. Applied mathematics and computation, 2003, 145(2): 887–893. |
| [11] | NELDER J A, MEAD R. A simplex method for function minimization[J]. The computer journal, 1965, 7(4): 308–313. DOI:10.1093/comjnl/7.4.308 |
| [12] | YANG X S. Nature-inspired metaheuristic algorithms, 2ed Edition[M].[S.l.]:Luniver Press, 2010. |
| [13] | HWANG C R. Simulated annealing:theory and applications[J]. Acta applicandae mathematicae, 1988, 12(1): 108–111. |
| [14] | STORN R, PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of global optimization, 1997, 11(4): 341–359. DOI:10.1023/A:1008202821328 |
| [15] |
李小为, 胡立坤, 王琥. 速度约束下PSO的六自由度机械臂时间最优轨迹规划[J].
智能系统学报, 2015(3): 393–398.
LI Xiaowei, HU Likun, WANG Hu. PSO-based time optimal trajectory planning for six degrees of freedom robot manipulators with speed constraints[J]. CAAI transactions on intelligent systems, 2015(3): 393–398. |
| [16] | DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. Evolutionary computation, 2002, 6(2): 182–197. DOI:10.1109/4235.996017 |
| [17] | DORIGO M, BIRATTARI M, STVTZLE T. Ant colony optimization[J]. Computational intelligence magazine, 2006, 1(4): 28–39. DOI:10.1109/MCI.2006.329691 |
| [18] | KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization:artificial bee colony (ABC) algorithm[J]. Journal of global optimization, 2007, 39(3): 459–471. DOI:10.1007/s10898-007-9149-x |
| [19] | YANG X S. A new metaheuristic bat-inspired algorithm[M]. Nature inspired cooperative strategies for optimization (NICSO 2010). Springer Berlin Heidelberg, 2010:65-74. |
| [20] | YANG X S. Firefly algorithm, stochastic test functions and design optimization[J]. International journal of bio-inspired computation, 2010, 2(2): 78–84. DOI:10.1504/IJBIC.2010.032124 |
| [21] | YANG X S. Firefly algorithm, Levy flights and global optimization[M]. Research and development in intelligent systems XXVI. Springer London, 2010:209-218. |
| [22] | YANG X S. Firefly algorithm[J]. Nature-inspired metaheuristic algorithms, 2008, 20: 79–90. |
| [23] | EIBEN A E, SCHIPPERS C A. On evolutionary exploration and exploitation[J]. Fundamenta informaticae, 1998, 35(1-4): 35–50. |
| [24] | ČREPINŠEK M, LIU S H, MERNIK M. Exploration and exploitation in evolutionary algorithms:a survey[J]. ACM computing surveys (CSUR), 2013, 45(3): 35. |
| [25] | HARIK G R, LOBO F G, GOLDBERG D E. The compact genetic algorithm[J]. Evolutionary computation, 1999, 3(4): 287–297. DOI:10.1109/4235.797971 |
| [26] | LENSTRA J K. Local search in combinatorial optimization[M]. Princeton: Princeton University Press, 2003. |
| [27] | YANG X S. Efficiency analysis of swarm intelligence and randomization techniques[J]. Journal of computational and theoretical nanoscience, 2012, 9(2): 189–198. DOI:10.1166/jctn.2012.2012 |
| [28] | TALBI E G. Metaheuristics:from design to implementation[M].[S.l.]:John Wiley & Sons, 2009. |
| [29] | BREST J, GREINER S, BOŠKOVIC' B, et al. Self-adapting control parameters in differential evolution:a comparative study on numerical benchmark problems[J]. Evolutionary computation, 2006, 10(6): 646–657. DOI:10.1109/TEVC.2006.872133 |
| [30] | YAO X, LIU Y, LIN G. Evolutionary programming made faster[J]. Evolutionary computation, 1999, 3(2): 82–102. DOI:10.1109/4235.771163 |
| [31] | YANG X S. Free lunch or no free lunch:that is not just a question?[J]. International journal on artificial intelligence tools, 2012, 21(3): 1240010. DOI:10.1142/S0218213012400106 |
| [32] | WOLPERT D H, Macready W G. No free lunch theorems for optimization[J]. Evolutionary computation, 1997, 1(1): 67–82. DOI:10.1109/4235.585893 |