求解旅行商问题的新型果蝇优化算法*

姜天水，王 枚

(烟台职业学院，山东 烟台 264670)

1 引言

旅行商问题(Traveling Salesman Problem，简称TSP)是一个经典NP-hard组合优化问题。现实中很多复杂问题都可以转换成TSP问题的求解[1]，所以，高效的TSP求解算法一直是组合优化领域的研究热点。传统的旅行商求解算法主要是包括分支定界法、线性规划法在内的精确算法，这类算法无法求解高维的TSP问题。而随着人工智能的发展，许多智能优化算法被应用于求解TSP问题，诸如遗传算法、蚁群算法、猴群算法、布谷鸟算法、帝国竞争算法、果蝇优化算法(Fruit Fly Optimization Algorithm，简称FOA)等，并取得了不错的效果。

FOA是一种从果蝇觅食行为中得到启发而提出的一种智能优化算法[2]。该算法在提出初期，主要用于求解连续的优化问题，目前也已逐步应用到求解组合优化问题中。Tao等利用FOA求解多维背包问题并取得了高质量的结果[3]；Du等将FOA用于结构优化设计，通过实验验证了FOA的寻优能力[4]；Wang等将FOA用于生产作业调度优化，有效的提高了参数[5]；Zhang等将FOA用于求解控制器设计问题，有效的协调和优化了系统的参数[6]；Polo等将FOA应用于天线结构优化设计，并得到了较单纯形法和遗传算法更好的结果[7]；Kanarachos等将FOA用于车辆悬架参数设计之中，并得到了较传统更佳的设计方案[8]。相比于粒子群算法、蚁群算法以及鱼群算法等群智能算法，FOA具有简单易理解、编程易实现、运行时间少等优点，但是由于FOA提出时间较晚，所以国内外对该算法的研究还处于初级阶段，算法理论还不成熟，所以有必要进一步研究FOA在诸如TSP等问题中的应用。

针对旅行商问题，提出了一种新型FOA，通过引入果蝇强化策略，加强对果蝇种群中的最优个体的开发，同时，提出了果蝇转化过程，根据解的情况自适应的调节果蝇种群的搜索方向，以改善传统FOA存在的收敛速度慢易于陷入局部最优解的问题，提高了FOA的求解精度和寻优速度。利用国际通用TSPLIB测试库实例对新型FOA性能进行测试，通过对比新型FOA的求解结果，验证了该算法的高效性，对比新型FOA和传统FOA的收敛速度和求解精度，验证了改进的有效性。

2 问题描述

TSP问题是指给定n个城市坐标点，求解从某一个城市出发，访问所有城市一次并且回到起始城市的最短路径，其在图论意义下又被称为最小Hamilton图问题。若设城市点集合为V={V1,V2,…,Vn},dij表示城市i和城市j之间的距离，为0-1变量，若由城市i到城市j的线路存在于回路路径中则xij为1，否则为0。因而，TSP的数学模型可表示如下：

3 求解TSP问题的新型果蝇优化

3.1 传统FOA算法

FOA是2011年台湾学者潘文超博士从果蝇觅食行为中得到启发而提出的一种群智能优化算法，其主要算法过程描述如下：

步骤1：设定果蝇种群规模Sizepop和最大迭代次数Maxgen，并随机初始化果蝇群体位置；

步骤2：设定果蝇个体嗅觉搜索食物的随机方向与距离；

步骤3：计算味道浓度判定值Si，并带入味道浓度判定函数，求出果蝇个体i的味道浓度Smelli；

步骤4：找出果蝇群体中味道浓度最佳的果蝇(最优个体)；

步骤5：记录并保留最佳味道值以及最优个体的位置，果蝇群体利用视觉搜索向该位置飞去；

步骤6：判断是否满足终止条件，若满足，则结束搜索，否则跳回步骤3。

3.2 新型FOA算法

分析上述传统FOA的算法流程，可以发现嗅觉搜索过程和视觉搜索过程都没有对果蝇群体中的最优个体进行开发，而对种群中优秀个体的开发往往会得出更优解，所以引入了果蝇强化策略，通过对果蝇种群中的优秀个体采取专门的开发操作，以改善果蝇优化算法的求解精度，同时，为了避免算法陷入局部最优解，引入了果蝇转化策略，根据具体的求解情况改变果蝇种群的搜索方向。下面具体描述新型FOA的方法步骤。

3.2.1 编码

由问题分析可知，设城市集合为V={V1,V2,…,Vn}，则TSP问题中的一条可行路径可表示为有序序列W={W1,W2,…,Wn},Wi∈V(i=1,2,…,n)，而且∀Wi≠Wj,i≠j。所以为了方便FOA的求解，设编码所表示的是8个城市的一个解，具体的编码方式即城市访问顺序描述为：7-3-2-5-8-6-1-4。

3.2.2 嗅觉搜索和视觉搜索

FOA通过嗅觉搜索过程找出果蝇群体中的最优个体，然后整个果蝇群体通过视觉搜索向最优个体靠拢，所以可知果蝇群体的视觉搜索是算法收敛的关键。取城市数目为m，xbest表示果蝇种群中的最优个体，x表示视觉搜索前的果蝇，x*表示视觉搜索后生成的新果蝇。新型FOA的视觉搜索过程主要分为以下5步：

步骤1：随机生成一串长度为m的0到1之间的随机数串δ={δ1,δ2,…,δm}；

步骤2：若位置i处的随机数δi≤ρ，则视觉搜索后的新果蝇位置i处的编码x*取果蝇种群中的最优个体对应位置的编码xbest；

步骤3：对于位置i处的随机数δi≤ρ时，若xi在搜索后的果蝇中没有出现，则x*取xi；

步骤4：其余视觉搜索后的果蝇中未存在的城市编码，按照搜索前果蝇中的相对位置依次插入x*中的空缺位置；

步骤5：生成视觉搜索后的新果蝇x*。

其中ρ是一个反应视觉搜索步长的阈值，通过大量实验，取0.5对求解最为有效。具体的视觉搜索过程如图1所示，其中ρ取0.5。

图1 视觉搜索过程示意图

3.2.3 果蝇强化

果蝇强化策略是通过对果蝇群体进行专门的开发，以提高求解质量和收敛速度。具体的果蝇强化策略分为以下3步：

步骤1：复制最优果蝇的解，随机选择最优果蝇中的两个城市，将两者之间的城市反序排列，生成新解，计算该新解的浓度，若优于该最优果蝇，则替换原最优个体，否则不进行替换；

步骤2：复制最优果蝇的解，随机选择最优果蝇中两个片段S1和S2，交换两个片段，生成新解，计算该新解的浓度，若优于该最优果蝇，则替换原最优个体，否则不进行替换；

步骤3：复制最优果蝇的解，随机选择最优果蝇中的两个城市，交换两个城市的位置，生成新解，计算该新解的浓度，若优于该最优果蝇，则替换原最优个体，否则不进行替换。

3.2.4 果蝇转化

果蝇转化是为了改善算法易于陷入局部最优解而引入的新过程。定义δ为果蝇开发因子，具体的果蝇转化过程分为以下3步：

步骤1：取果蝇开发因子δ，判断种群中最优个体是否在δ代内没有发生变化，若不是则跳到步骤3；

步骤2：若种群中最优个体在δ代内没有发生变化，则保留该最优解，同时在果蝇群体中寻找次优个体代替最优个体；

步骤3：结束果蝇转化。

通过果蝇转化过程可以看出，该过程的引入可以避免果蝇群体对一个局部最优解进行过度的开发，进而可以有效的改善果蝇算法易于陷入局部最优解的问题，提高算法全局搜索能力。

3.2.5 算法流程

改进后果蝇优化算法的框图流程如图2所示。

图2 改进后果蝇优化算法流程图

针对上述描述，下面以伪代码的形式对改进后新型果蝇算法FOA的算法流程进行描述。

7if ∃smell(x**)≤best_smell8best_smell ← smell(x**)9xbest ← x**10x ← x**11else12H ← x**13end if14xbest ← transformation(xbest,δ)15end for

4 实验结果与分析

利用国际通用TSPLIB测试实例库对新型FOA性能进行测试，利用Matlab2015b编程实现并运行于具有4.0G RAM 2.20 GHz的计算机上。

4.1 测试实例和比较算法

为了验证引入果蝇强化策略和果蝇转化策略对TSP算法整体性能的改进优势，采用了2种试验测试方法进行比较。

①新型FOR算法与传统FOR算法进行比较。方法是选择了10组国际通用TSPLIB测试实例，分别对传统FOR和新型FOR进行测试，2种算法的初始果蝇数均设置为100只，迭代次数均为100 000次。新型FOR和传统FOR算法的测试结果见表1。

表1 传统FOA与新型FOA对比结果

②新型FOR算法与较先进的TSP算法比较。方法是选择近期其他作者提出的较先进的不同的TSP算法[9-12]，随机采用6组实例进行测试比较，测试结果见表2。如图3所示是新型FOR算法求解的其中几组实例所得路径情况，如图4所示是依据测试实例获得的新型FOR与传统FOR算法收敛曲线。

表2 新型FOA与其他4种算法对比

图3 新型FOA求解所得路径情况

图4 新型FOA与传统FOA收敛曲线

4.2 实验结果与结果分析

测试实验中已知最优解来自TSPLIB标准库，定义偏差率为所求最优解与已知最优解的差与已知最优解的比值。由于编程测试时全为浮点型运算，而TSPLIB提供的已知最优解不全为浮点型，偏差率在之内的结果，均可认为接近已知最优解。进行测试的实例均运行20遍，统计最优解与平均解，其中若所求最优解优于已知最优解时，偏差率用“—”表示。

分析表1新型FOA与传统FOA算法测试结果，在选择的10个实例中，新型FOA有3个实例中的最优解优于传统FOA的求解结果，除dantzig42新型FOA所得平均解与传统FOA一致以外，其余9组实例新型FOA所求的平均解均优于传统FOA，进而可以看出引入果蝇强化和果蝇转化策略提高了算法的求解精度与求解效率。继续对比新型FOA所求的最优解与已知最优解，可以看到，新型FOA有1组最优解优于目前已知最优解，1组最优解与已知最优解一致，还有6组最优解的偏差率小于1%，即接近最优解，进而验证新算法在求解TSP上的优异性能。

分析表2新型FOR与其他4种算法测试结果对比，选择的是近期其他作者提出的4种求解TSP性能较先进算法,新型FOA与其他4种算法的对比结果可以看到，新型FOA在列出的6组对比实例中，有4组实例所求的最优解优于其余4种算法，其余2组dantzig42、eil51的求解结果与最优结果也相差不大，进而验证了新型FOA求解的高效性。

图4是新型FOA与传统FOA在Ch130、Pr107两组实例上的收敛曲线图，其中Ch130选择前2 000代的情况，Pr107选择了前5 000代的情况。观察分析新型FOA与传统FOA的收敛曲线可以看出，新型FOA的收敛速度与求解精度均优于传统的FOA，进一步证明了新算法的有效性。

5 结论

果蝇强化和果蝇转化策略的新型果蝇优化算法，通过对果蝇种群中的最优个体的开发，既显著提高算法的求解精度，同时根据求解的具体情况能够自适应的调整果蝇种群的搜索方向，进而解决了传统算法易于陷入局部最优解的难题。算法通过实验进行的性能测试表明，该算法具有求解精度高、求解收敛速度快的特点。实验数据表明，新型果蝇优化算法具有优异的求解能力，对求解旅行商问题具有重要的实用价值。