文章快速检索 高级检索

1. 北方工业大学 电气与控制工程学院, 北京 100144;
2.北方工业大学 城市道路交通智能控制技术北京市重点实验室, 北京 100144

An improved adaptive step glowworm swarm optimization algorithm
TANG Shaohu1,2 , LIU Xiaoming1,2
1. College of Electrical and Control Engineering, North China University of Technology, Beijing 100144, China;
2. Beijing Key Lab of Urban Intelligent Traffic Control Technology, North China University of Technology, Beijing 100144, China
Abstract:In the basic glowworm swarm optimization (GSO), it is easy to fall into local optimum and the oscillation phenomenon of function adaptive values may occur because of the fixed step length. In some adaptive-step glowworm swarm optimization (A-GSO) algorithms, neighborhood sets of some fireflies may be empty in the iterative process of the algorithm, which leads to lower convergence speed and falls into local optimal value. Therefore, an improved foraging-behavior adaptive-step GSO (FA-GSO) algorithm was designed. The foraging behavior of the fireflies without neighborhood peer and adaptive step is introduced in order to find the optimization direction in the improved algorithm. The precision, stability, and global convergence analysis of FA-GSO is presented. After extracting and comparing the relevant optimization indicators of GSO, A-GSO and FA-GSO by several standard test functions, the effectiveness of the FA-GSO algorithm was verified, which indicates that the improved algorithm can improve the accuracy of function optimization and the iteration speed.
Key words: glowworm swarm optimization     adaptive step     foraging behavior     global convergence

1 人工萤火虫算法原理 1.1 基本的人工萤火虫算法

GSO算法主要有4个阶段：萤火虫初始化阶段、荧光素更新阶段、位置移动阶段以及动态感知范围更新阶段。算法流程如图 1所示。

1)初始化阶段。

2)荧光素更新阶段。

3)位置移动阶段。

4)动态感知范围更新阶段。

 图 1 基本的GSO算法流程 Fig. 1 Flow chart of basic GSO algorithm
1.2 自适应步长人工萤火虫算法

2 改进的人工萤火虫算法原理 2.1 基于觅食行为的自适应步长人工萤火虫算法

 图 2 觅食次数为不同值时函数迭代值对比 Fig. 2 Iterative value contrast of different foraging times
2.2 FA-GSO算法收敛性分析

GSO算法、PSO算法(粒子群算法)都属于随机优化算法，刘洲洲等[9]和张慧斌等[10]分别对2种算法的收敛性给出了分析证明，他们依据的是Solis[11]给出的随机优化算法收敛性判定标准。

2.3 FA-GSO实现步骤

1)初始化萤火虫群体和参数。将n只萤火虫随机地分布在搜索空间m维中，同时为每只萤火虫初始化以相同的荧光素l0和感应半径r0，初始化最大移动步长smax，最小移动步长smin，萤光素挥发系数ρ，觅食次数N，萤光素更新率γ以及设定迭代次数Nmax等，形成初始萤火虫群；

2)执行FA-GSO算法搜索。

a)对每一个萤火虫i按式(1)更新荧光素的值，判断li(t+1)≤li(t)是否成立，如果是则转向b)，否则在转向b)前，令xi(t+1)=xi(t)。

b)在动态决策域半径rdi(t)内，求萤火虫i的邻域集合Ni(t)。

c)选择t+1时刻移动的方向：

Ni(t)不为空集，利用式(2)计算向邻域内萤火虫j的移动概率pij(t)，其中0 ＜rdi(t) ＜rs,rs为萤火虫个体的感知半径，并采用轮盘赌法则选择邻域内萤火虫个体，确定为下一时刻萤火虫的移动方向；

Ni(t)为空集，在其动态决策半径rdi(t)内执行觅食行为，设定觅食次数最大值为N次，每次觅食意味着寻找下次迭代移动方向，如果存在食物假定为一个萤火虫j的所在位置，符合条件j:di,j(t) ＜rdi(t);li(t) ＜lj(t)，则确定找到食物(同伴)；如果觅食次数超过N次，没有找到符合条件的食物(同伴)，则认定当前位置已是最好的觅食地，位置不再移动。

d)根据式(5)计算每个萤火虫的荧光因子，并用式(6)计算动态移动步长。

e)萤火虫进行位置移动，根据式(3)更新位置；

f)根据式(4)更新萤火虫的动态感知范围。

3)判断是否达到指定的迭代次数，如果达到则转向步骤4)，否则转向2)。

4)输出结果，程序结束。

3 实验结果与分析

 测试函数 算法 最优解 最差解 平均解 平均迭代次数 F1(x) GSO 0.235 3.360 2.370 85 A-GSO 0.081 2.760 1.640 72 FA-GSO 0.000 0.524 0.065 42 F2(x) GSO 0.256 3.560 2.130 75 A-GSO 0.102 1.560 0.850 56 FA-GSO 0.014 0.096 0.067 53 F3(x) GSO 1.95 10.58 6.54 106 A-GSO 0.41 3.57 2.65 80 FA-GSO 0.15 1.56 0.89 61 F4(x) GSO 0.16 2.67 2.130 81 A-GSO 0.12 2.92 1.360 77 FA-GSO 0.03 0.83 0.482 46

 图 3 F1(x)函数值随3个算法迭代曲线 Fig. 3 Iterative values graph of F1(x) tested by the three algorithms

 图 4 F2(x)函数值随3个算法迭代曲线 Fig. 4 Iterative values graph of F2(x) tested by the three algorithms

 图 5 F3(x)函数值随3个算法迭代曲线 Fig. 5 Iterative values graph of F3(x) tested by the three algorithms

 图 6 F4(x)函数值随3个算法迭代曲线 Fig. 6 Iterative values graph of F4(x) tested by the three algorithms
4 结束语

 [1] LIAO Wenhua, KAO Yucheng, LI Yingshan. A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks[J]. Expert Systems with Applications, 38(10): 12180-12188. [2] KRISHNANAND K N D, GHOSE D. Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J]. Multiagent and Grid Systems, 2006, 2(3) 209-222. [3] 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. [4] YANG Yan, ZHOU Yongquan, GONG Qiaoqiao. Hybrid artificial glowworm swarm optimization algorithm for solving system of nonlinear equations[J]. Journal of Computational Information Systems, 2010, 6(10) 3431-3438. [5] 黄正新, 周永权. 自适应步长萤火虫群多模态函数优化算法[J]. 计算机科学, 2011, 38(7): 220-224.HUANG Zhengxin, ZHOU Yongquan. Self-adaptive step glowworm swarm optimization algorithm for optimizing multimodal functions[J]. Computer Science, 2011, 38(7): 220-224. [6] 欧阳喆, 周永权. 自适应步长萤火虫优化算法[J]. 计算机应用, 2011, 31(7): 1804-1807.OUYANG Zhe, ZHOU Yongquan. Self-adaptive step glowworm swarm optimization algorithm[J]. Journal of Computer Applications, 2011, 31(7): 1804-1807. [7] KRISHNANAND K N D, GHOSE D. Glowworm swarm optimization: a new method for optimizing multi-modal functions[J]. Computational Intelligence Studies, 2009, 1(1): 93-119 [8] 张军丽, 周永权. 人工萤火虫与差分进化混合优化算法[J]. 信息与控制, 2011, 40(5): 608-613.ZHANG Junli, ZHOU Yongquan. A hybrid optimization algorithm based on artificial glowworm swarm and differential evolution[J]. Information and Control, 2011, 40(5): 608-613. [9] 刘洲洲, 王福豹, 张克旺. 基于改进萤火虫优化算法的WSN 覆盖优化分析[J]. 传感技术学报, 2013, 26(5): 675-682.LIU Zhouzhou, WANG Fubao, ZHANG Kewang. Performance analysis of improved glowworm swarm optimization algorithm and the application in coverage optimization of WSNs[J]. Chinese Journal of Sensors and Actuators, 2013, 26(5): 675-682. [10] 张慧斌, 王鸿斌, 胡志军. PSO算法全局收敛性分析[J]. 计算机工程与应用, 2011, 47(34): 61-63.ZHANG Huibin, WANG Hongbin, HU Zhijun. Analysis of particle swarm optimization algorithm global convergence method[J]. Computer Engineering and Applications, 2011, 47(34): 61-63. [11] SOLIS F J, WETS R J B. Minimization by random search techniques[J]. Mathematics of Operations Research, 1981, 6(1): 19-30.
DOI: 10.3969/j.issn.1673-4785.201403025

0

#### 文章信息

TANG Shaohu, LIU Xiaoming

An improved adaptive step glowworm swarm optimization algorithm

CAAI Transactions on Intelligent Systems, 2015, 10(03): 470-475.
DOI: 10.3969/j.issn.1673-4785.201403025