求解旅行商问题的改进果蝇算法

王克甫，薛 鹏，黄全振，2，李恒宇

（1.河南工程学院 电气信息工程学院，河南 郑州451191；2.上海大学 机电工程与自动化学院，上海200072）

0 引 言

TSP作为一类经典的NP 难组合优化问题，在车辆调度、物流配送、管道铺设、电路板布局等领域得到广泛应用，国内外学者对此已开展大量的研究工作，并提出一些求解算法，总的可归为两方面：精确算法和启发式算法。然而，TSP解空间随问题规模呈指数级增长，对于大规模问题，传统精确算法很难在可接受的时间内找到最优解。比如：分支－切割法［1］，动态规划法［2］等；而启发式算法本身具有一定的智能性，它们可依靠自身的这些特性，对解空间进行启发式搜索。与精确算法相比，在同等条件下它们就可以获得较为满意的解。启发式算法一般有：蚁群算法［3，4］，遗传算法［5］，人工蜂群算法［6］，粒子群算法［7－8］等。在这样的背景下，启发式算法越来越得到广大学者的关注。

鉴于果蝇算法 （Fruit fly algorithm，FFA）在求解连续优化问题中表现出的良好性能［9］，本文对其求解TSP 组合优化问题进行了探索性的尝试，并针对它易陷入局部最优及收敛速度慢等问题，提出基于局部最优区域半径的启发式变异策略以及觅食步长自适应调整策略。最后，在对其全局收敛性进行证明的同时，也通过国际标准实例库TSPLIB验证了它的有效性。

1 果蝇算法

中国台湾学者潘文超受果蝇觅食行为的启发，于2011年6月提出了基于群体智能的果蝇算法［9］，并在连续优化问题领域得到应用［10－12］。其原理为：群体中的果蝇在觅食过程中利用相对发达的嗅觉朝食物气味浓度最高的区域飞行，并在飞近食物过程中利用视觉发现觅食能力最高的果蝇，并向该果蝇飞行，以快速觅到食物。觅食行为如图1所示。

图1 果蝇觅食行为

然而，目前FFA 算法还未应用于TSP等离散组合优化问题。固定的觅食步长影响了收敛速度。群体觅食行为的趋同性降低了种群的多样性，易于陷入局部最优。针对这些不足，对觅食步长进行了改进，提出步长自适应调整策略，以提高收敛速度；同时，提出局部最优半径的概念，并提出启发式变异算子，使处于局部最优半径中的部分个体进行启发式变异，在保护最优解的同时，提高种群多样性，改善优化性能。

2 果蝇算法改进

定义1 不同于连续优化问题，对于采用城市序号编码的离散TSP问题，不重复遍历所有城市的一个序列为一条染色体，序列中的任一城市为一个基因位，对染色体中任两个基因位进行一次2－opt操作的行为，称为一步觅食。

定义2 在进行2－opt过程中，任选染色体中的2个基因的行为，称为觅食方向选择。

定义3 对于TSP问题，假如第i个果蝇的当前位置为C（i）＝（ci1，ci2，…，cin），cij（j∈｛1，2，…n｝）表示一个城市的编号，则第i个果蝇位置处食物的浓度可表示为式 （1）

式中：dj，j＋1——城市cij与城市cij＋1之间的距离。

2.1 步长自适应设计

定义4 对于C（i）＝（ci1，ci2，…，cin）、C（j）＝（cj1，cj2，…，cjn）2个果蝇，则这2个果蝇之间的解空间距离定义为C（i）与C（j）相同位置处不同基因位的对数。比如：C（1）＝ （1，2，3，4，5，6，7，8）、C（2）＝ （4，8，3，6，1，7，2，5）。则C（1）与C（2）之间的解空间距离为7。则为C（i）与C（j）之间的解空间距离可定义为

由于果蝇算法采用固定步长进行觅食，如果步长设置过大，则较容易进行全局搜索，但却带来求解精度的降低；然而，步长设置过小，在求解精度提高的同时，会造成搜索效率的降低。为使精度与效率达到一种平衡，需对步长进行自适应调整。鉴于所有果蝇从当前食物浓度最大处进行觅食的情况，为避免不必要的重复搜索，因而觅食的步长不应超出上代果蝇群体中距离食物浓度最大处果蝇的最短距离。同时，为兼顾到全局寻优，对每个果蝇的步长调整为

其中，C（i），i∈｛1，2，…，Popsize｝＆＆i≠j）为非食物浓度最大处的果蝇，C（j）为食物浓度最大处的果蝇。rand（）为0、1之间的随机数。

2.2 参考局部最优区域半径的变异算子设计

果蝇算法的觅食策略较为单一，难免会进入局部最优。为此，提出一种考虑局部最优区域半径的变异方法。通常，在某个区域中如果存在多个局部最优值，会进入局部最优。因而，结合本文定义的解空间距离概念，把距离当前最优解小于等于半径R 的区域定义为局部最优区域。变异策略为：从局部最优区域中随机选择R 个果蝇以概率pm（i）（i∈｛1，2，…，R｝）进行变异，对选中的果蝇则随机选择R 个连续的基因位进行倒序。假设Smax为局部最优区域中当前距离最优解的最大值，则被选择到的R 个果蝇的变异概率为

其中，i∈｛1，2，…，R｝，C（j）为食物浓度最大处的果蝇。

2.3 改进果蝇算法描述

步骤1 随机初始化Popsize 只果蝇的位置；

步骤2 依据式 （1）对Popsize 只果蝇进行食物浓度判定；

步骤3 找出食物浓度最大处的果蝇，并记录其浓度值fitness（C（j））及位置C（j）；

步骤4 按本文定义的觅食方向及觅食方式并按式 （5）进行自适应觅食

步骤5 保留食物浓度最大处的果蝇，如果当前代食物浓度最大值fitness（C（m））优于Smellbest，则更新

其中，Positionbest及Smellbest初始值为任一随机位置及其对应的浓度值。

步骤6 如果达到设定的迭代次数，则输出最优解；否则，转步骤7；

步骤7 按本文定义的变异策略进行自适应变异，转步骤2。

3 全局收敛性分析

定义5 在TSP问题中，果蝇C（i）＝（ci1，ci2，…cin）通过觅食行为到达果蝇C（j）＝（cj1，cj2，…cjn）处，记为状态变迁，序列（ci1，ci2，…cin）的全排列称为TSP问题的状态空间，也称为解空间Η。

定义6 设C＊为TSP解空间Η中的最优解，F（t）为觅食进行到第t代时的种群状态，如果

则称改进的果蝇算法以概率1收敛到全局最优解。

定理改进的果蝇算法以概率1收敛到全局最优解。

证明：通过对基本果蝇算法进行了步长自适应调整以及变异算子设计，改进果蝇算法的性能得到了提高。其核心思想为：所有果蝇从上一代中食物浓度最大的果蝇所在位置处进行觅食，具有引导向最优方向觅食的能力。假如B ＝｛b（1），b（2），…，b（t），b（t＋1）｝表示从第1代到第t＋1代中每代的最优解，则满足

4 仿真实验

为测试改进果蝇算法 （MFFA）的有效性，选用TSPLIB国际标准库中的Eil51作为测试函数，与标准果蝇算法 （FFA）及文献 ［14］中的改进的粒子群算法 （MPSO）进行了对比。种群规模Popsize 均为120，进化代数Gennum 均为500 代，IFFA 的局部最优区域半径R ＝15，MPSO 其他参数见文献 ［14］。实验环境：Windows XP 系统、G2030－3.0GHz CPU、4GRAM、VC＋＋2010。

从图2看出，与FFA、MPSO 相比，MFFA 能快速收敛到最优解，并且求解精度也得到很大程度的提高，说明本文采用的步长自适应调整及启发式变异策略是可行的。图3各代均值对比曲线显示MFFA 有效避免了 “早熟”现象，使果蝇在进化后期依然保持较强的觅食能力，因而提高了求解效率。特别与FFA 相比，觅食能力有很大的提升，再次印证了MFFA 启发式变异策略的可行性。

图2 算法收敛曲线对比

图3 算法各代均值对比

为测试MFFA 算法的适应能力，更好地检测MFFA 算法的性能，选用了TSPLIB 国际标准库中多个实例进行对比，同时，为排除随机性，采用统计学原理进行比较。为此，参与对比的算法各单独运行25次，结果见表1。在表1中TSPOPT 表示TSPLIB 的已知最优解，BST 表示最优解，AVG 表示平均解，DEV 表示平均解与已知最优解的偏差，CPU（s）表示耗费CPU 的时间。

由表1可看出，3 个算法相比，MFFA 在所有测试实例中获得的路径都是最优的。并且，通过对比不同规模实例中获得的最优路径的情况，我们发现，当TSP 城市规模较小时，MFFA 基本上能得到TSPLIB 已知的最优路径；而当TSP城市规模较大时，MFFA 尽管不能取得TSPLIB已知的最优路径，但已与之相当接近。另外，从与已知最优解的偏差这个角度来看，MFFA 依然是最小的，从中可以说明其具有较好的鲁棒性。特别与FFA 相比，收敛速度与精度的改善非常显著，这主要得益于两方面：首先，果蝇能根据距离觅食能力最强果蝇的距离进行自适应调整觅食步长，有效缩短了寻觅到食物的时间，即提高了收敛速度，缩短了收敛时间；其次，基于局部最优区域半径的启发式变异策略，在拓展了解空间的范围的同时，也较好的保护了最优解，不仅很好地解决了局部最优的问题，而且对算法的寻优方向也有一定的引导性，在一定程度上也为收敛效率的提高做出了贡献。因而，从以上两点的分析可以看出，本文提出MFFA 在求解效率与精度上都得到了很大程度的改善。

表1 3种算法求解TSP实例的结果对比

5 结束语

果蝇算法作为一种新颖的优化算法，其在求解连续优化问题上显示出较好的性能。本文创新性地对果蝇算法进行了改进，并应用到离散组合优化问题中的经典NP 难TSP问题。结合TSPLIB 国际标准库中的实例，与其他智能算法进行了对比测试。测试结果表明，改进后的果蝇算法不仅有效克服了易 “早熟”及收敛速度慢的问题，而且相对其他算法也表现出较好的性能。从这点看，本文采取的基于局部最优区域半径的启发式变异策略及步长自适应调节策略是可行的，这也为改进的果蝇算法在相关组合优化问题中的应用提供了一个很好的参考。

鉴于其在本文中TSP问题中表现出的良好性能，为了拓宽其应用领域。下一步准备在有约束的TSP问题中进行尝试，有约束的TSP 也是一类经典问题，对其进行研究，不仅可以扩大本文提出的改进果蝇的算法的应用的广度，而且，也对相关带约束的车辆路径规划、水管电网线及电路板走线等规划问题的求解提供了一个很好的借鉴。

［1］Cordeaua JF，Dell’Amico M，Iori M.Branch－and－cut for the pickup and delivery traveling salesman problem with FIFO loading ［J］.Computers and Operations Research，2010，37（5）：970－980.

［2］Gromicho J，Hoorn JJV，Kok AL，et al.Restricted dynamic programming：A flexible framework for solving realistic VRPs ［J］.Computers and Operations Research，2012，39 （5）：902－909.

［3］WU Hao，NI Zhiwei，WANG Huiying.MapReduce－based ant colony optimization ［J］.Computer Integrated Manufacturing Systems，2012，18 （7）：1503－1509 （in Chinese）.［吴昊，倪志伟，王会颖.基于MapReduce的蚁群算法 ［J］.计算机集成制造系统，2012，18 （7）：1503－1509.］

［4］Tuba M，Jovanovic R.Improved ACO algorithm with pheromone correction strategy for the traveling salesman problem［J］.International Journal of Computers Communications and Control，2013，8 （3）：477－485.

［5］Nagata Y，Kobayashi S.A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem［J］.Informs Journal on Computing，2013，25 （2）：346－363.

［6］HU Zhonghua，ZHAO Min.Simulation on traveling salesman problem （TSP）based on artificial bees colony algorithm ［J］.Transactions of Beijing Institute of Technology，2009，29 （11）：978－982（in Chinese）. ［胡中华，赵敏.基于人工蜂群算法的TSP仿真［J］.北京理工大学学报，2009，29 （11）：978－982.］

［7］Marinakis Y，Marinaki M.A hybrid multi－swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem ［J］.Computers and Operations Research，2010，37 （3）：432－442.

［8］ZHANG Xumei，QIU Hanguang.Improved particle swarm optimization based on k－center and its application in traveling salesman problem ［J］.Computer Integrated Manufacturing Systems，2007，13 （1）：99－104 （in Chinese）. ［张旭梅，邱晗光.基于k－中心点法的改进粒子群算法在旅行商问题中的应用［J］.计算机集成制造系统，2007，13 （1）：99－104.］

［9］PAN WT.A new fruit fly optimization algorithm：Taking the financial distress model as an example ［J］.Knowledge－Based Systems，2012，26：69－74.

［10］WANG L，ZHENG XL，WANG SX.A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem ［J］.Knowledge－Based Systems，2013，48：17－23.

［11］SHENG W，BAO Y.Fruit fly optimization algorithm based fractional order fuzzy－PID controller for electronic throttle［J］.Nonlinear Dynamics，2013，73 （1－2）：611－619.

［12］LI HZ，GUO S，ZHAO HR.Annual electric load forecasting by a least squares support vector machine with a fruit fly optimization algorithm ［J］.Energies，2012，5 （11）：4430－4445.

［13］Lopez J，Dorronsoro JR.Simple proof of convergence of the SMO algorithm for different SVM variants ［J］.IEEE Transactions on Neural Networks and Learning Systems，2012，23（7）：1142－1147.

［14］Sedghi M，Aliakbar－Golkar M，Haghifam MR.Distribution network expansion considering distributed generation and storage units using modified PSO algorithm ［J］.International Journal of Electrical Power and Energy Systems，2013，52：221－230.