改进混合蛙跳算法求解旅行商问题.doc

第7期罗雪晖等：改进混合蛙跳算法求解旅行商问题135改进混合蛙跳算法求解旅行商问题罗雪晖，杨烨，李霞（深圳大学 信息工程学院，广东 深圳 518060）摘 要：以旅行商问题（TSP）为例，引入调整序思想设计了局部搜索策略，同时在全局信息交换过程中加入变异操作，提出一种改进混合蛙跳算法求解TSP问题。实验结果表明，与遗传算法和粒子群优化算法相比较，改进混合蛙跳算法在求解TSP问题上具有更好的搜索性能和顽健性。关键词：混合蛙跳算法；旅行商问题；局部搜索；全局信息交换中图分类号：TP18 文献标识码：A 文章编号：1000-436X(2009)07-0130-06Modified shuffled frog-leaping algorithm to solve traveling salesman problemLUO Xue-hui, YANG Ye, LI Xia（College of Information Engineering, Shenzhen University, Shenzhen 518060，China）Abstract: Modified shuffled frog-leaping algorithm to solve TSP was proposed, which presented the concept of adjustment sequence to design the strategy of local searching, and added the mutation operation in the global exchange of information. Experimental results indicate that, compared with genetic algorithm and particle swarm optimization algorithm, the proposed algorithm has more powerful search capability and more strong robustness in solving TSP.Key words: shuffled frog-leaping algorithm; traveling salesman problem; local search; global information exchange1 引言收稿日期：2008-08-02；修回日期：2008-11-20基金项目：国家自然科学基金资助项目（60772148）Foundation Item: The National Natural Science Foundation of China (600772148)混合蛙跳算法是2000年由Muzaffar Eusuff和Kevin Lansey提出的一种基于群智能的亚启发式计算优化算法，用于解决离散组合优化问题1。作为一种新型的仿生物学智能优化算法，SFLA结合了基于模因（meme）进化的模因演算法（MA，memetic algorithm）和基于群体行为的粒子群算法（PSO, particle swarm optimization）2种群智能优化算法的优点。该算法具有概念简单，调整的参数少，计算速度快，全局搜索寻优能力强，易于实现的特点2。混合蛙跳算法主要应用于解决多目标优化问题，例如水资源分配、桥墩维修、车间作业流程安排等工程实际应用问题35。著名的旅行商问题6（TSP, traveling salesman problem）是一类典型组合优化问题，求得一条遍历所有城市的最短回路，属于NP难问题。对TSP问题一般分为两大类的研究：一类着重于研究算法解决大规模实际问题7，如文献7中解决的TSP问题城市规模最大达到316 228个，侧重点在于算法能快速地有效求得可行解；另一类则是利用TSP问题来验证优化算法解决离散组合优化问题的有效性。几十年来，出现了很多近似优化算法用于求解TSP问题，基本分为2类：与问题本身特征相关的局部启发式搜索算法，如2-Opt、3-Opt和Lin-Kernighan（LK）8等。这类优化算法多数充分利用问题本身特征的相关信息有效寻找问题的局部最优解，但是这些算法过分依赖于问题本身特征，当问题的规模扩大后，问题本身特征的相关信息更复杂，大大增加算法计算量，使得算法搜索时间过长。独立于问题的经典智能优化算法，如蚁群算法、遗传算法、模拟退火法、粒子群算法、免疫算法等。此类算法大多数是模拟生物进化算法，不依赖于问题本身特征，具有较强的全局搜索能力。近年来，许多学者将局部启发式搜索算法和智能优化算法相结合产生新型混合算法应用于求解TSP问题。文献8提出了一种求解TSP问题的混合遗传算法，该算法结合了基于领域的LK算法和采用了交叉逆转算子；文献9介绍了求解TSP问题的蚁群算法，在算法中引入局部信息激素、信息激素更新策略与变参数策略等；文献10提出了基于改进粒子群优化算法求解旅行商问题，文中引入了速度变异机制和粒子自探索机制。这些研究成果表明把智能优化算法与局部启发式搜索相结合能有效提高算法搜索到最优解的能力。混合蛙跳算法提出时间不长，无论在理论还是在实践方面都处于起步阶段。文献11 尝试提出了运用混合蛙跳算法求解TSP问题，本文在此基础上引入调整序思想设计了局部搜索策略，同时在全局信息交换过程中加入变异操作，从而提出一种改进的混合蛙跳算法求解TSP问题。实验结果表明，与遗传算法和粒子群优化算法相比较，改进的混合蛙跳算法在求解TSP问题上具有更好的搜索性能和顽健性。2 混合蛙跳算法的数学模型1混合蛙跳算法(SFLA)是一种受自然生物模仿启示而产生的基于群体的协同搜索方法。这种算法模拟青蛙群体寻找食物时，按族群分类进行模因信息传递的过程。混合蛙跳算法主要包括2个部分：局部搜索和全局信息交换。各族群局部搜索使模因信息在局部个体间传递优化局部个体，混合全部青蛙，然后排序再分族群的过程使局部间的模因信息得到全局信息交换。局部搜索和全局信息交换一直持续交替进行到满足收敛条件结束为止。以下简要介绍混合蛙跳算法的数学模型。2.1 基本概念随机生成只青蛙组成初始群体，每个青蛙个体表示问题的一个可行解为，计算青蛙个体适应度，其中表示解空间的维数。在随机生成初始群体之后，将青蛙个体按适应度降序排列存储于，然后按照特定的划分原则将整个青蛙群体分成个族群Y1，Y2，Ym，每个族群中包含只青蛙，满足下列关系：(1)若设定=3，只青蛙按适应度由高到低排列，位置位于第1的青蛙分入第1族群，第2的青蛙分入第2族群，第3的青蛙分入第3族群，第4的青蛙分入第1族群，依次类推，将所有青蛙个体划分到3个族群中。2.2 局部搜索青蛙种群中各族群执行局部搜索策略的目的是在不同的搜索方向上搜索局部最优，搜索迭代一定次数后使得族群中局部最优个体逐步趋向于全局最优个体。首先将青蛙种群划分成多个族群，对每个族群进行局部搜索，但是为了避免青蛙个体过早陷入局部最优，同时加快收敛速度，在每个族群中按照特定的原则选择一定数目的青蛙构成该族群的子族群。对于青蛙群体，具有全局最好适应度的解表示为；对于每一个子族群，具有最好适应度的解表示为，最差适应度的解表示为。首先对每个子族群进行局部搜索，即对子族群中最差适应度的青蛙个体进行更新操作，更新策略为(2)(3)其中，表示青蛙个体的调整矢量，表示青蛙个体允许改变的最大步长。如设=1 3 5 4 2, UB=2 1 5 3 4,允许改变的最大步长=3，若rand=0.5，则=1+minint0.5(21),3=1; =3+maxint0.5(13), 3=2;依此相同的操作完成更新策略后可得到一个新解=1 2 5 4 3。2.3 全局信息交换全局信息交换有助于收集各族群搜索的局部信息，通过模因在全局中的传递，获得新的搜索全局最优解的方向。当所有族群经过一定次数的局部搜索后，将各族群中青蛙个体混合在一起，按适应度降序排列后，重新划分族群，这样使得青蛙个体间的模因信息得到充分的传递，然后继续进行局部搜索，如此反复直到满足收敛条件算法停止。3 混合蛙跳算法求解TSP问题TSP问题描述如下：给定个城市及各个城市的坐标，求一条经过各城市一次且仅一次，起始城市和终止城市相同的最短闭合路径。3.1 青蛙个体位置向量表示每个青蛙个体的位置向量表示TSP问题的一个可行解。设青蛙，其中代表个城市的编号，表示从城市出发依次经过城市最后回到城市的路径。另外，青蛙个体适应度函数定义为闭合路径长度的倒数。3.2 子族群的构造和青蛙个体的更新策略子族群中青蛙个体的选择策略是青蛙个体的选择权重大小与适应度的大小成正比，即适应度越大的青蛙个体，选择权重越大，越容易被选入子族群；反之亦然。族群中的青蛙依概率选取构造成子族群，其概率公式为，(4)其中，表示在当前族群中第青蛙被选入子族群的概率，表示每个族群中青蛙个数，族群中每个青蛙被选择的概率之和满足关系式。2.1节中有关混合蛙跳算法的青蛙个体更新策略有可能会出现不可行解，所以针对TSP问题，混合蛙跳算法中的青蛙个体更新策略为任意截取中的一段路径序列，替换与之相对应的位置，其余位置的城市序号若出现在这段路径序列中，则将其去除掉，反之保持不变，最后将没有出现的城市序号随机插入路径序列中，从而生成一个新的可行解。若优于，用更新，否则，用全局最优的代替，然后进行上述相同操作，生成一个新的可行解。若优于，用更新，否则，随机产生一个新的可行解更新Uw。4 改进的混合蛙跳算法求解TSP问题虽然文献11中混合蛙跳算法采用的局部搜索能保证更新解的可行性，但是随机截取一段的操作存在盲目性，使得局部搜索容易早熟。为此，本文在文献11的基础上，引入调整因子和调整序思想设计了局部搜索策略，同时在全局信息交换过程中加入变异操作，从而提出了一种改进的混合蛙跳算法求解TSP问题。4.1 基于调整序的局部搜索策略调整序12是一个可行解向另一个可行解转换的一个调整序列。局部搜索中子族群的最差解利用调整序思想优化，比简单的随机截取一段替换更有指导性，所以在局部搜索中引入这种思想更新子族群的最差解。4.1.1 调整因子和调整序121) 调整因子设个城市的TSP问题的解为 定义调整因子为将中的插入到位置之前，则为经调整因子操作后的新解。例如，当=(1 3 5 2 4)，调整因子为，则=(1 2 3 5 4)2) 调整序一个或多个调整因子的有序排列就是调整序，记作，其中是调整因子，它们之间的顺序是有意义的。、分别为2个不同解，调整序表示将调整为的调整序，即(5)构造一个调整序。设定=(1 3 5 2 4)，=(3 1 4 2 5)，需要构造一个调整序，使得。可见,所以第一个调整因子,得到=(3 1 5 2 4)；,所以第二个调整因子是, ,由此类推，可得文献12中求解2个TSP解序列之间的调整序之前，需要将两个TSP解序列转化为均以1为起点，预处理的目的是求解出两个TSP解序列之间的最简短的调整序列（即调整因子个数最少）。因为在求解过程中，大多数所得的调整序是将局部最差解调整为局部最优解的情况，为了尽可能使得调整序中调整因子个数较多，增加青蛙个体更新的多样性，从而增加了算法搜索能力，避免过早陷入局部最优，本文在求解调整序列时，不需要进行解序列预处理。4.1.2 青蛙个体的更新策略青蛙个体之间的差异是青蛙个体之间的调整序，调整序的数目为非负数，所以青蛙个体的更新策略为(6)(7)(8)其中，表示调整序中全部调整因子个数，表示更新所选用的部分调整因子个数，表示允许选用的最大调整因子个数，表示更新的调整序。图1所示为青蛙个体更新的一个例子， 。图1 改进的混合蛙跳算法中局部搜索的青蛙个体更新策略4.2 全局信息交换策略求解TSP问题的混合蛙跳算法并未考虑到TSP问题所具有的特点，即边与边之间的邻接关系，不能很好地保留原有边的邻接关系，所以不能将可行解中的优良性能很好地保留在青蛙群体中，不能提高算法的收敛速度。因此在改进的算法中，各个族群的青蛙进行过局部搜索之后，将全体青蛙重新混合在一起，按照一定的概率对每一个青蛙个体进行贪婪倒位变异操作。改进的混合蛙跳算法在全局信息交换过程中加入青蛙个体变异操作，保证了青蛙个体的多样性，缩短算法搜索到全局最优解的时间。贪婪倒位变异算子13利用了贪婪法的基本思想，其主要思想是：对某一青蛙个体，随机选择一个城市，与城市左、右连接的城市分别表示为，然后选取除了、以外的距离最近的城市，若在中与之间间隔的城市数少于与之间间隔的城市数，则对到之间的城市进行倒位；反之，则对与之间的城市进行倒位。例如：对青蛙个体（1 3 5 2 6 4 8 7 9），随机选择一个城市=5，则=2，=3，离城市5最近的城市=8，则倒位后产生新的青蛙个体（1 3 5 8 4 6 2 7 9），如果新的青蛙个体优于青蛙个体，则用取代U放入青蛙群体中。4.3 算法实现不失一般性，假设算法收敛的准则为连续多次迭代所得TSP路径的总长度未有改善。以下给出改进的混合蛙跳算法求解TSP问题的基本步骤。1) 初始化参数（青蛙族群数，族群中青蛙数n(总青蛙数F=(mn),子族群中青蛙数q，还有族群中青蛙更新迭代次数的设置）;2) 随机产生个初始可行解，并计算青蛙个体的适应度；3) 青蛙个体按适应度降序排列划分成个族群，构造子族群；4) 局部搜索。对每个族群中的子族群按4.1节的方式进行青蛙个体的更新；5) 所有族群混合，每个青蛙个体进行4.2节青蛙个体变异操作，如产生的新个体优于原来个体则取代原来青蛙个体放入青蛙种群中，重新计算适应度；6) 判断是否满足算法收敛条件，若满足，输出最优路径序列；否则，更新全局最优解，返回到步骤3）。5 实验仿真本文采用TSPLIB14中的Burma14、Bays29、Eil51和Eil101对算法进行测试。实验环境：PC机PIV-2.8GHz CPU，512M RAM，Window XP，Matlab 6.5。参数设置：青蛙群体总数,族群数，子族群中青蛙个数，族群中青蛙更新迭代次数IT=q，青蛙个体允许选择的最大调整因子个数（其中表示城市数）。采用平均距离对算法的性能进行客观评价，收敛时所需的平均时间对算法运算量进行评价；算法稳定性的评价是基于相对误差。实验仿真是以同样实验条件下对每个TSP问题进行50次计算机仿真的统计平均，结果如表1所示，其中针对不同规模TSP问题，第一行表示混合蛙跳算法的实验结果，第二行是改进混合蛙跳算法的实验结果。表1 混合蛙跳算法和改进混合蛙跳算法在不同规模TSP问题上的测试结果TSP实例已知最优值算法最优值平均距离相对误差/%平均运行时间/sBurma1430.8830.8830.880.001.8430.8830.880.002.35Bays2920202 0202 0441.206.752 0202 0200.008.21Eil51428.8711428.87436.761.8417.42428.87430.660.4222.36Eil1016296556736.9928.386296493.1842.74注：相对误差由表1可知，与混合蛙跳算法相比较，改进算法在求解Burma14、Bays29和 Eil51问题能够搜索到最优路径，而且寻找到最优路径的成功率有显著改善。值得注意的是，混合蛙跳算法在求解Eil101问题搜索不到最优解，而改进算法可以搜索到最优解。以51点Eil51为例，运行10次每次迭代50代。将改进混合蛙跳算法与混合蛙跳算法在搜索最优值时，随迭代次数变化的平均情况如图2所示。由图中可见，虽然改进混合蛙跳算法每一次迭代需要操作的步骤增多了，但是它所需的收敛次数明显比混合蛙跳算法少，而且搜索的平均结果也有改善，所以所耗费的运行时间虽然较长，但综合考虑还是可接受范围。图2 混合蛙跳算法和改进混合蛙跳算法求解Eil51问题的搜索收敛速度对比表2给出了改进混合蛙跳算法，改进粒子群优化算法15，遗传局部搜索算法16在运行环境大致相同的情况下求解Eil51问题所得到的算法最优值、平均距离、相对误差和平均运行时间的数据结果。表2 混合蛙跳算法与其他改进算法在求解Eil51问题上的测试结果算法类型平均距离算法最优值相对误差/%平均运行时间/s改进粒子群优化算法15440.78436.772.77遗传局部搜索算法16437.83431.992.0918.44改进混合蛙跳算法430.66428.870.4222.36实验结果显示，在各算法运行时间相当的情况下，改进混合蛙跳算法在求解较大规模TSP问题上与其他2种优化算法相比，其性能更稳定。6 结束语混合蛙跳算法是一种基于群智能的亚启发式计算优化算法，用于解决离散组合优化问题。本文在文献11的基础上引入调整序思想设计了局部搜索策略，同时在全局信息交换过程中加入变异操作，从而提出一种改进的混合蛙跳算法求解TSP问题。实验仿真结果表明，与遗传算法和粒子群优化算法相比较，改进的混合蛙跳算法在求解TSP问题上具有更好的搜索性能和顽健性。在通信网络中，网路的QoS路由规划问题是计算带有多个条件限制的最短路径问题，与TSP问题同属于离散组合优化问题。改进混合蛙跳算法已经成功地应用于TSP问题，取得了较好的结果。由于混合蛙跳算法与其他群智能优化算法相比，其算法涉及参数少、易于实现、搜索能力强，所以下一步工作将探讨如何将混合蛙跳算法应用于QoS路由规划问题。参考文献：1EUSUFF M M, LANSEY K E. Water distribution network design using the shuffled frog leaping algorithmA.World Water CongressC. 2001.2李英海, 周建中, 杨俊杰等. 一种基于阈值选择策略的改进的混合蛙跳算法J. 计算机工程与应用,2007,43(35),19-21.LI Y H, ZHOU J Z, YANG J J, et al. Modified shuffled frog leaping algorithm based on threshold selection strategyJ. Computer Engineering and Applications, 2007, 43(35):19-21.3EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithmJ. J Water Resource Plan Manage, 2003, 129(3):10-25.4HATEM E, EMAD E, TAREK H, et al. Comparison of two evolutionary algorithms for optimization of bridge deck repairsJ. Computer-Aided Civil and Infrastructure Engineering, 2006, 21:561-572.5ALIREZA R V, ALI H M. Solving a Bi-criteria Permutation Flow-shop Problem Using Shuffled Frog-Leaping AlgorithmM. Soft Comput, Springer-Verlag, 2007.6LAWLER E L, LENSTRA J K, RINNOOY K, et al. The Travelling Salesman Problem: a Guided Tour of Combinatorial OptimizationM. Chichester: John Wiley & Sons, 1985.7NGUYEN H D, YOSHIHARA I, YAMAMORI K, et al. Implementation of an effective hybrid ga for large-scale traveling salesman problemsJ. IEEE Trans on Systems, man, and Cybernetics-Part B: Cybernetics, 2007, 37(1):92-99.8莫海芳, 康立山. 求解TSP的混合遗传算法J. 计算机工程与应用，2007,43(18),40-44.MO H F, KANG L S. Hybrid genetic algorithm for traveling salesman problemJ. Computer Engineering and Applications, 2007, 43(18): 40-44.9张军英，敖磊，贾江涛等. 求解TSP问题的改进蚁群算法J.西安电子科技大学学报（自然科学版）,2005,32(5),681-685. ZHANG J Y, AO L, JIA J T, et al. An improvement of the ant colony algorithm for solving TSP problemsJ. Journal of Xidian Unviersity, 2005, 32(5):681-685.10王翠茹，冯海讯，张江维等. 基于改进粒子群优化算法求解旅行商问题J.微计算机信息（测控自动化）,2006,22(8),273-275.WANG C P, FENG H X, ZHANG J W, et al. Solving traveling salesman problem based on improved particle swarm optimization algorithmJ. Micro-Computer Information (Automation of measurement and control), 2006, 22(8):273-275.11LUO X H, YANG Y, LI X. Solving TSP with shuffled frog-leaping algorithmA. The Eighth International Conference on Intelligent Syste