程 魁， 马 良

（上海理工大学管理学院，上海 200093）

平面选址问题的萤火虫算法

程 魁， 马 良

（上海理工大学管理学院，上海 200093）

平面选址问题是工程设计、线路布置、项目选址等工作中经常碰到的典型组合优化难题，根据群集智能优化原理，给出一种基于人工萤火虫群优化算法的求解方法，并针对平面选址问题进行求解.为避免算法陷入局部极值，将一种邻域搜索的局部搜索方法引入萤火虫算法中.通过对典型平面选址问题的仿真实验和与其它算法的比较，表明算法可行有效，且具良好的全局优化能力.

平面选址；萤火虫群优化算法；优化算法

1 算法思想

GSO算法是一种新型群智能优化算法，并在2009年成功地将其应用在函数数值优化问题上.近年来，国外诸多学者已将GSO算法应用在寻找危险信号源的位置、网络机器系统定位多个气味源、追逐多个移动信号源［8-9］等诸多方面.在基本的GSO算法中，每只人工萤火虫分布在目标函数的定义空间内，这些人工萤火虫各自携带自身的萤光素，并且拥有各自的视野范围，称为区域决策范围.区域决策范围的大小会受邻居数量的影响，当邻居密度较低，萤火虫的决策半径会加大，以利于寻找更多的邻居；反之，决策半径减小.在萤火虫的运动当中，每一只萤火虫以一定的概率向其邻域范围内的邻居萤火虫前进.萤火虫j要成为萤火虫i的邻居萤火虫，必须满足j在i的邻域范围之内，并且j的荧光素要高于i.最终，通过萤火虫群的不断运动，越来越多的萤火虫会聚集在适应度值最高的萤火虫周围，从而确定目标函数的最优值.

在GSO当中每一次迭代都由两个阶段组成，第一阶段是萤光素更新阶段，第二阶段是萤火虫的运动阶段.

在荧光素更新阶段中，每一只萤火虫对荧光素的更新式为

式中，li（t）为第t代第i个萤火虫的荧光素值；p为荧光素值的消失率，p∈（0，1）；γ为荧光素更新率；f（xi（t））为函数适应度值.

在萤火虫运动阶段中，萤火虫i以一定的概率选择邻域范围内的萤火虫j，并朝其运动，概率选择式为

萤火虫i在其邻域内按照交叉换位策略进行位置更新，运动的最后进行决策域范围的更新式为

在邻域搜索中，当前解（x，y）邻域定义为

其中，搜索半径r＞0（取0.1），θ在［0，2π］之间随机生成.由以上表述可知，求解选址问题的人工萤火虫群优化算法的步骤可概括如下：

a.初始化所有萤火虫的位置，邻域范围和相关参数值.

b.计算萤火虫的适应度值.

c.利用式（1），更新萤火虫的荧光素值和邻域范围.

d.萤火虫在其邻域内按照交叉换位策略更新位置，按式（3）更新动态决策域范围.

e.对当前解进行邻域搜索.

f.满足最大迭代次数，则输出当前最好结果，否则，返回b.

2 仿真实验

为验证算法的运行效果，用MATLAB7.0为算法编写了程序，并在PC系列机的Windows 7环境下运行.萤火虫算法的参数设置采用文献［10］推荐的取值，即荧光素的初值L0=5，动态决策域初值R0=3，动态决策域的更新率β=0.08，邻域个数nt=5，荧光素更新率γ=0.6，荧光素消失率ρ=0.4.测试算例来源于文献［3］和文献［11］，如表1所示.为公平起见，3种算法均采用本文定义的邻域搜索方法.

2.1 无区域约束的平面选址问题

运行萤火虫算法求解，并与当前求解该问题效果最好的两种智能优化算法——人工蜂群算法（artificial bee colony algorithm，ABC）和引力搜索算法（gravitational search algorithm，GSA）进行求解性能比较.具体的求解结果对比如表2所示，其中，人工蜂群算法和引力搜索算法的参数设置分别参考文献［5］和文献［6］.3种算法的群体规模均为50，最大迭代次数N均为1 000.

表1 测试算例Tab.1 Instances

表2 无约束情形求解结果Tab.2 Solutions under unconstrained situation

从表2可看出，在求解绝对值距离平面问题时，对算例1和算例3而言，GSO算法的结果最好；对算例2而言，这3种算法的求解结果一样；对算例4和算例5而言，GSO算法和GSA算法的结果一样，都优于ABC算法.在求解欧氏距离平面问题选址时，对所有5个算例，GSO算法的求解结果都是最好的.总体而言，GSO算法的优化性能要好于ABC算法和GSA算法.

为更好地说明GSO算法在求解连续优化问题上的性能，选取算例3和算例5，做出3种算法求解欧氏距离最优值的收敛性态如图1所示（见下页），无论是收敛速度还是求解精度，GSO算法都体现了令人满意的性能.

2.2 有区域约束的平面选址问题

为验证算法在该问题上的有效性，将求解结果与蚁群算法（ant colony optimization，ACO）和人工蜂群算法（ABC）［5］的求解结果作对比.具体对比结果见表3（见下页）.其中，算例4和算例5的区域约束分别为

图1 收敛性对比Fig.1 Convergence comparison

表3 有约束情形求解结果Tab.3 Solutions under constrained situation

由表3可知，对于算例4而言，在求解绝对值距离平面问题时，3种算法求解结果一样；在求解欧氏距离平面问题时，GSO算法优于其它两种算法.对于算例5来说，两种形式下，GSO和ACO算法求解效果相同，均优于ABC算法.因这类算法出现时间不长，理论基础尚未完善，渐进收敛性、鲁棒性等性质的严格数学证明尚有待于以后更深入的工作.

3 结束语

一系列数值试算结果表明，无论是求解无区域约束的平面选址问题还是求解有区域约束的平面选址问题，萤火虫算法都具有较为理想的收敛特性和寻优能力，在实际操作上是行之有效的.萤火虫算法作为一种新型智能优化算法，应用领域还在不断丰富，理论研究也有待探索.此外，将算法用于多目标的平面选址问题是下一步的研究工作.

［1］ 张天赐.平面选址问题概述［J］.运筹学杂志，1985，4（1）：4-11.

［2］ 马良.多目标平面选址问题的模拟退火算法［J］.系统工程理论与实践，1997，17（3）：70-73.

［3］ 马良，朱刚，宁爱兵.蚁群优化算法［M］.北京：科学出版社.2008.

［4］ 邱模杰，马良.约束平面选址问题的蚂蚁算法［J］.上海理工大学学报，2000，22（3）：217-220.

［5］ 樊小毛，马良.约束平面选址问题的蜂群优化算法［J］.上海理工大学学报，2010，32（4）：378-380.

［6］ 刘勇，马良.平面选址问题的引力搜索算法求解［J］.计算机工程与应用，2012，48（27）：42-44，62.

［7］ Krishnanand K N，Ghose D.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics［C］∥Proc of IEEE Swarm Intelligence Symposium.Piscataway：IEEE Press，2005：84-91.

［8］ Krishnanand K N，Ghose D.A glowworm swarm optimization based multi-robot system for signal source localization［M］.Springer：Design and Control of Intelligent Robotic Systems，2009：53-74.

［9］ Krishnanand K N，Ghose D.Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple location［J］.Robotics and Autonomous System，2008，7（56）：549-569.

［10］ 黄正新，周永权.变步长自适应萤火虫群多模态函数优化算法［J］.计算机工程与应用，2012，48（8）：43 -47.

［11］ 蒋良奎.平面选址问题的一种混合算法［J］.上海海运学院学报，1999，20（4）：98-102.

（编辑：金 虹）

Artificial Glowworm Swarm Optimization Algorithm for Location Problem

CHENGKui， MALiang
（Business School，University of Shanghai for Science and Technology，Shanghai 200093，China）

The location problem is a typical combinatorial optimization problem in the work of engineering design，line routing，project location，etc.According to the principle of swarm intelligence，a new optimization algorithm based on the idea of glowworms-the glowworm swarm algorithm was presented to solve the location problem.To avoid getting stuck into local optima，a neighborhood search strategy was introduced into the artificial glowworm swarm optimization algorithm.Simulated tests of the location problem and comparisons with other algorithms show that the algorithm is feasible and effective and has strong global optimization ability.

location problem；artificial glowworm swarm optimization algorithm；optimization algorithm

O 211.1；N 94

A

1007-6735（2013）03-0205-04

2012-12-24

国家自然科学基金资助项目（70871081）；上海市研究生创新基金资助项目（JWCXSL1202）

程 魁（1989-），男，硕士研究生.研究方向：智能优化.E-mail：iamchengkui＠126.com

马 良（1964-），男，教授.研究方向：智能优化、系统工程.E-mail：maliang＠usst.edu.cn