D0I:10.13374/1.issm100103.2008.10.022 第30卷第10期 北京科技大学学报 Vol.30 No.10 2008年10月 Journal of University of Science and Technology Beijing 0ct.2008 求解TSP问题的一种基于信息素的遗传交叉算子 赵方庚)李苏剑孙江生) 刘伟民)梅冬) 1)北京科技大学机械工程学院，北京1000832)汽车管理学院车管系，蚌埠233011 摘要提出了求解TSP问题的一种新的基于信息素的遗传交叉算子，并对算子构造子个体的过程进行了实验分析·在生 成子个体时，基于信息素的遗传交叉算子不仅能够利用包括边长度和邻接关系在内的局部信息，还可以利用以信息素形式保 存的全局信息。在纯遗传算法框架内，利用TSP基准算例对所提出的交叉算子的性能进行了实验测试·结果表明，该算子在 精度和收敛速度上均优于其他知名的交叉算子· 关键词信息素：交叉算子；遗传算法；旅行商问题(TSP) 分类号TP301.6 Pheromone-based crossover operator of genetic algorithm for the traveling sales- man problem ZHAO Fanggeng.LI Sujian)SUN Jiangsheng),LIU Weimin MEI Dong) 1)School of Mechanical Engineering.University of Science and Technology Beijing.Beijing 100083.China 2)Department of Vehicle Management.Institute of Vehicle Management,Bengbu 233011,China ABSTRACI A new pheromone-based crossover operator of genetic algorithm for the traveling salesman problem was proposed.and the working process of the operator was analyzed when constructing offspring.When constructing offspring.the proposed operator utilizes both local and global information.The local information includes edge lengths and adjacency relations,while the global informa- tion is stored as pheromone trails.The proposed operator was tested in a pure genetic algorithm framwork using the TSP benchmark instances.Experimental results show its better performance in both of speed and accuracy than other well known crossover operators. KEY WORDS pheromone:crossover operator:genetic algorithm:traveling salesman problem (TSP) 旅行商问题(traveling salesman problem,TSP) 题的启发式方法主要包括2opt、3-opt,L-K算法、 是广受关注的组合优化问题之一，一般的T$P问 蚁群算法3]、遗传算法[山以及禁忌搜索算法可等 题可以用一网络图G=(N,A)来描述，其中N为 由Holland提出的遗传算法(genetic algorithm, 城市集合，即旅行商所需经过的城市；A是弧集，表 GA)是一种基于进化原则的全局搜索算法，遗传算 示旅行商可能走过的路线段的集合，A中每一个路 法一般包括选择、交叉和变异三种算子，其中，选择 线段(i,),都有一表示城市i、j之间距离的数值 算子用于从种群中挑选合适的个体（方案）作为下一 d,与之对应·求解TSP问题即在图G中找出总距 代个体的父体；交叉算子则用于生成以某种机制继 离最短的哈密尔顿回路， 承父代基因的子代个体；变异算子通常随机的改变 TSP问题的求解方法可分为精确算法和启发 个体以避免搜索过程陷入局部最优，在遗传算法 式算法（或近似算法）·由于TSP是一种NP-hard问 中，进行交叉的概率一般较高，故该算子对算法性能 题，精确算法，如分支定界算法山，只适于求解规模 具有重要的影响，因此，研究人员提出了很多适用 较小的问题，要在合理的时间内求解较大规模的 于求解TSP问题的交叉算子，如部分映射交叉 TSP问题，目前只能应用启发式方法，求解TSP问 (partially mapped crossover,PMX)[o、顺序交又 收稿日期：2007-09-17修回日期：2007-11-09 作者简介：赵方庚(1978-)，男，博士研究生：李苏剑(1959-)，男，教授，博士生导师，E-mail:lichaorong@263.net
求解 TSP 问题的一种基于信息素的遗传交叉算子 赵方庚12） 李苏剑1） 孙江生1） 刘伟民1） 梅 冬2） 1） 北京科技大学机械工程学院北京100083 2） 汽车管理学院车管系蚌埠233011 摘 要 提出了求解 TSP 问题的一种新的基于信息素的遗传交叉算子并对算子构造子个体的过程进行了实验分析．在生 成子个体时基于信息素的遗传交叉算子不仅能够利用包括边长度和邻接关系在内的局部信息还可以利用以信息素形式保 存的全局信息．在纯遗传算法框架内利用 TSP 基准算例对所提出的交叉算子的性能进行了实验测试．结果表明该算子在 精度和收敛速度上均优于其他知名的交叉算子． 关键词 信息素；交叉算子；遗传算法；旅行商问题（TSP） 分类号 TP301∙6 Pheromone-based crossover operator of genetic algorithm for the traveling salesman problem ZHA O Fanggeng 12）LI Sujian 1）SUN Jiangsheng 1）LIU Weimin 1）MEI Dong 2） 1） School of Mechanical EngineeringUniversity of Science and Technology BeijingBeijing100083China 2） Department of Vehicle ManagementInstitute of Vehicle ManagementBengbu233011China ABSTRACT A new pheromone-based crossover operator of genetic algorithm for the traveling salesman problem was proposedand the working process of the operator was analyzed when constructing offspring．When constructing offspringthe proposed operator utilizes both local and global information．The local information includes edge lengths and adjacency relationswhile the global information is stored as pheromone trails．T he proposed operator was tested in a pure genetic algorithm framwork using the TSP benchmark instances．Experimental results show its better performance in both of speed and accuracy than other well known crossover operators． KEY WORDS pheromone；crossover operator；genetic algorithm；traveling salesman problem （TSP） 收稿日期：2007-09-17 修回日期：2007-11-09 作者简介：赵方庚（1978—）男博士研究生；李苏剑（1959—）男教授博士生导师E-mail：lichaorong＠263．net 旅行商问题（traveling salesman problemTSP） 是广受关注的组合优化问题之一．一般的 TSP 问 题可以用一网络图 G＝（ NA ）来描述其中 N 为 城市集合即旅行商所需经过的城市；A 是弧集表 示旅行商可能走过的路线段的集合．A 中每一个路 线段（ ij）都有一表示城市 i、j 之间距离的数值 dij与之对应．求解 TSP 问题即在图 G 中找出总距 离最短的哈密尔顿回路． TSP 问题的求解方法可分为精确算法和启发 式算法（或近似算法）．由于 TSP 是一种 NP-hard 问 题精确算法如分支定界算法［1］只适于求解规模 较小的问题．要在合理的时间内求解较大规模的 TSP 问题目前只能应用启发式方法．求解 TSP 问 题的启发式方法主要包括2-opt、3-opt、L-K 算法［2］、 蚁群算法［3］、遗传算法［4］以及禁忌搜索算法［5］等． 由 Holland 提出的遗传算法（genetic algorithm GA）是一种基于进化原则的全局搜索算法．遗传算 法一般包括选择、交叉和变异三种算子．其中选择 算子用于从种群中挑选合适的个体（方案）作为下一 代个体的父体；交叉算子则用于生成以某种机制继 承父代基因的子代个体；变异算子通常随机的改变 个体以避免搜索过程陷入局部最优．在遗传算法 中进行交叉的概率一般较高故该算子对算法性能 具有重要的影响．因此研究人员提出了很多适用 于求解 TSP 问题的交叉算子如部分映射交叉 （partially mapped crossoverPMX ） ［6］、顺 序 交 叉 第30卷 第10期 2008年 10月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．10 Oct．2008 DOI:10．13374／j．issn1001－053x．2008．10．022
第10期 赵方庚等：求解ISP问题的一种基于信息素的遗传交叉算子 ,1185 (order crossover,OX)[、基于位置的交又(position 调节信息素和可见度之间相对重要性的参数，S表 based crossover,POS)[]、循环交叉(cyde 示所有未被访问过的城市集合，随机变量J服从下 crossover)[9)、最大保留交叉(maximal preservative 式定义的概率分布： crossover,MPX)o)、边重组交叉(edge recombina 「(t)1·「2]° tiom,ERX)、贪婪选择交叉(greedy selection fj∈s P(t)= 1 (2) crossover,GSX),距离保持交叉(distance preserv- 0 ing crossover,DPX)I以及贪婪子路径交叉(greedy otherwise subtour crossover,GSX-II)[131. 按照这一规则，基于信息素的交叉算子将以q0(0≤ q≤1)的概率选择“最合适”的城市作为子个体中的 早期的遗传交叉算子（如PMX、OX、POS及循 下一城市，而以1一q0的概率按照式(2)所定义的概 环交叉)在生成子个体时，往往只考虑各城市的位置 率分布进行随机选择，上述过程将重复进行，直至 或它们之间的顺序，这类算子可以看作是“盲”交叉， 所有城市都被访问一次，这样一个可行的子个体即 另外一些交叉算子（如MPX、ERX、GSX、DPX及 构造完毕 GSX-Ⅱ)在构造子个体时只能利用一些局部信息， 基于信息素的遗传交叉算子的流程如图1所 如边的长度、邻接关系，而忽视或者不多地利用了可 示，其中n为城市总数，0表示子个体，o(k)表示0 能会有助于产生较优个体的全局信息，因此，本文 中的第k个城市. 提出了一种新的基于信息素的遗传交叉算子，该算 子在构造子个体时不仅能利用局部信息，还可利用 回 以信息素形式保存的全局信息，同时，这些用于保 随机选择任一城市作为子 存全局信息的信息素采用蚁群优化(ant colony 个体0的第一个城市) optimization,ACO)算法中信息素更新的方式进行更 kn? Y 子个体0构造完成 新.为验证所提出的交叉算子的有效性，本文在纯 N 遗传算法的框架下对算子进行了测试，结果表明， 分别在两父个体巴和P: 中搜索c()的位置 本文提出的基于信息素的交叉算子具有优异的性 能 0()所有邻居 都被访问过？ 1基于信息素的遗传交叉算子 N 从neighbors内未被访问过的城市 本文所提出的基于信息素的交叉算子适于采用 中选择距离)最近的城市j 按照式()选择城市j 路径表示的遗传算法，在生成子个体时，该算子不 仅能利用局部信息，还会使用全局信息，其中，局部 =k+ok)j 信息包括边长度和父代中各城市间的邻接关系，而 全局信息则来自网络图各边上的信息素， 图1基于信息素的遗传交叉算子流程图 在交叉时，基于信息素的交叉算子首先随机选 Fig.I Flow chart of the pheromone-based crossover operator 择一个城市i作为子个体中第一个城市，然后在其 供交叉算子获取全局信息的信息素按照最大一 两个父代个体中搜索城市，以获取其紧前和紧后 最小蚂蚁系统(max min ant system,MMAS)5]中 城市（称之为neighbors),显然，neighbors最多包含 的机制进行初始化和更新.在算法的起始阶段，各 四个城市.交叉算子将从neighbors中未访问过的 边上的信息素值均被初始化为tmax,并且在整个运 城市内，选取距离上一城市最近的那个作为子个体 算过程中，信息素值被限制在区间[min,mr]之 中的下一城市.如果neighbors中的城市都已经被 内.tm和tmim定义如下： 访问过，算子将按照下述伪随机比例(pseudo 1 1 random proportional)4的原则选取下一城市： Tmas-1-p'f(s) (3) arg max[()][],if qqo Tmin Tmax/2 n (4) (1) 其中，常数P(0<p<1)表示信息素的持久度， otherw ise 其中，(t)表示t时刻边(i,)上的信息素值， f(s中)为全局最优路线(s中)的总长度，n为城市总 (=1/dg)为从城市i到城市j的可见度，a为 数
（order crossoverOX） ［7］、基于位置的交叉（position based crossoverPOS ） ［8］、 循 环 交 叉 （ cycle crossover） ［9］、最大保留交叉（maximal preservative crossoverMPX） ［10］、边重组交叉（edge recombinationERX ） ［4］、贪 婪 选 择 交 叉 （ greedy selection crossoverGSX） ［11］、距离保持交叉（distance preserving crossoverDPX） ［12］以及贪婪子路径交叉（greedy subtour crossoverGSX-Ⅱ） ［13］． 早期的遗传交叉算子（如 PMX、OX、POS 及循 环交叉）在生成子个体时往往只考虑各城市的位置 或它们之间的顺序这类算子可以看作是“盲”交叉． 另外一些交叉算子（如 MPX、ERX、GSX、DPX 及 GSX-Ⅱ）在构造子个体时只能利用一些局部信息 如边的长度、邻接关系而忽视或者不多地利用了可 能会有助于产生较优个体的全局信息．因此本文 提出了一种新的基于信息素的遗传交叉算子．该算 子在构造子个体时不仅能利用局部信息还可利用 以信息素形式保存的全局信息．同时这些用于保 存全局信息的信息素采用蚁群优化 （ant colony optimizationACO）算法中信息素更新的方式进行更 新．为验证所提出的交叉算子的有效性本文在纯 遗传算法的框架下对算子进行了测试．结果表明 本文提出的基于信息素的交叉算子具有优异的性 能． 1 基于信息素的遗传交叉算子 本文所提出的基于信息素的交叉算子适于采用 路径表示的遗传算法．在生成子个体时该算子不 仅能利用局部信息还会使用全局信息．其中局部 信息包括边长度和父代中各城市间的邻接关系而 全局信息则来自网络图各边上的信息素． 在交叉时基于信息素的交叉算子首先随机选 择一个城市 i 作为子个体中第一个城市然后在其 两个父代个体中搜索城市 i以获取其紧前和紧后 城市（称之为 neighbors）．显然neighbors 最多包含 四个城市．交叉算子将从 neighbors 中未访问过的 城市内选取距离上一城市最近的那个作为子个体 中的下一城市．如果 neighbors 中的城市都已经被 访问 过算 子 将 按 照 下 述 伪 随 机 比 例 （pseudorandom-proportional） ［14］的原则选取下一城市： j＝ arg max j∈ S ｛［τij（ t）］·［ηij ］ α｝ if q≥q0 J otherwise （1） 其中τij （ t）表示 t 时刻边（ ij ）上的信息素值 ηij（ηij＝1／dij）为从城市 i 到城市 j 的可见度α为 调节信息素和可见度之间相对重要性的参数S 表 示所有未被访问过的城市集合随机变量 J 服从下 式定义的概率分布： pij（ t）＝ ［τij（ t）］ ·［ηij ］ α ∑k∈ S ［τik（ t）］ ·［ηik ］ α if j ∈ S 0 otherwise （2） 按照这一规则基于信息素的交叉算子将以 q0（0≤ q0≤1）的概率选择“最合适”的城市作为子个体中的 下一城市而以1—q0 的概率按照式（2）所定义的概 率分布进行随机选择．上述过程将重复进行直至 所有城市都被访问一次这样一个可行的子个体即 构造完毕． 基于信息素的遗传交叉算子的流程如图1所 示其中 n 为城市总数o 表示子个体o（ k）表示 o 中的第 k 个城市． 图1 基于信息素的遗传交叉算子流程图 Fig．1 Flow chart of the pheromone-based crossover operator 供交叉算子获取全局信息的信息素按照最大— 最小蚂蚁系统（max-min ant systemMMAS） ［15］ 中 的机制进行初始化和更新．在算法的起始阶段各 边上的信息素值均被初始化为 τmax并且在整个运 算过程中信息素值被限制在区间 ［τminτmax ］ 之 内．τmax和 τmin定义如下： τmax＝ 1 1—ρ · 1 f （ s gb ） （3） τmin＝τmax／2n （4） 其中常数 ρ（0＜ρ＜1） 表示信息素的持久度 f （ s gb ）为全局最优路线（ s gb ）的总长度n 为城市总 数． 第10期 赵方庚等： 求解 TSP 问题的一种基于信息素的遗传交叉算子 ·1185·
,1186 北京科技大学学报 第30卷 在遗传算法每代运算的最后，各边上的信息素 2.1交叉过程分析 值将按下式进行更新： 基于信息素的遗传交叉算子在逐步构造子个体 (t十1)=r(t)十△咄 (5) 的过程中，算子首先从当前城市的“邻居”中选出下 一城市，当所有“邻居”都被访问过后，再利用信息素 其中， (式(1)进行选择.为了能对交叉过程有进一步的 1/f(s中)if(i,j)∈s中 了解，本文对子个体的构造过程进行了统计实验， △= (6) 0 othervise 实验以TSPLIB中的基准算例eil51(51个城市的 TSP问题)为例，且算法独立运行20次，图3所示 显然，只有包含在全局最优路线中的边上的信息素 为在构造子个体的过程中，交叉算子利用信息素选 才会得到加强， 出下一城市的平均概率。由图3可知：在遗传搜索 2实验结果及分析 的初期，由于种群个体间的差异较大，交叉算子利用 式(1)构造子个体的概率较高（约8.5%）；随着遗传 在基于信息素的交叉算子当中，有一些参数需 搜索的进行，种群个体的质量普遍提高，个体间的差 在使用前预先确定，本文先对这些参数进行实验分 异逐渐减小，这使得交又算子从“邻居”中选出下一 析.实验在图2所示“纯”遗传算法的框架内进行， 城市的可能性增加，而利用信息素进行选择的概率 其中的变异算子采用常用的3一交换变异，交叉、变 异之后，如果子个体不同于种群中的所有个体，则进 也逐渐稳定在4.5%左右， 入种群，同时为保持种群规模不变，删去种群中最差 的个体 初始化各参数及信息素值 应用Nearest Neighbor方法 生产初始种群P 1 N i≤pop_size/22 终止条件 满足？ Y 1000 2000300040005000 从P中按轮盘赌规则选择两 Y 进化代数 个体进行交叉，生成子个体0 算法结束 图3交叉过程中利用信息素选择的概率 以概率P。对o,进行变异操作 Fig.3 Probability of selection utilizing pheromone during crossover o,不同于P中 N 所有个体？ 2.2不同交叉算子间的比较 Y 为了检验基于信息素的遗传交叉算子的有效 ©，进人P,制除P中最差个体 性，在图2所示的纯遗传算法的框架内将该算子和 其他知名的交叉方法（包括MPX、GSX、DPX和 =+l GSX-Ⅱ)进行了比较.在比较时，各参数均设置如 前所示，且算法共搜索5000代，各基准算例20次独 图2遗传算法流程图 Fig.2 Flow chart of genetic algorithm 立运算的平均计算结果如表1所示，由表1可知， 对于所有的基准算例，基于信息素的交叉算法都获 在图2所示的遗传算法中，各通用参数设置如 得优于其他各交叉方法的路线， 下：种群规模pop-size=60;交叉概率pe=1;变异概 另外，本文还以算例d198为例，比较了应用不 率pm=0.1:算法终止条件为运算5000代.对于所 同交叉算子时的最优路线长度的进化过程，如图4 提出的基于信息素的交叉算子中的参数，即a、q0 所示，比较结果显示，基于信息素的交叉方法无论 和P,则按照文献[14]的建议分别设置为：a=3, 是在精度和还是在收敛速度上均优于其他几种遗传 g0=0.9,0=0.95 交叉算子
在遗传算法每代运算的最后各边上的信息素 值将按下式进行更新： τij（ t＋1）＝ρτij（ t）＋Δτgb ij （5） 其中 Δτgb ij ＝ 1／f （ s gb ） if （ ij）∈s gb 0 othervise （6） 显然只有包含在全局最优路线中的边上的信息素 才会得到加强． 2 实验结果及分析 在基于信息素的交叉算子当中有一些参数需 在使用前预先确定本文先对这些参数进行实验分 析．实验在图2所示“纯”遗传算法的框架内进行 其中的变异算子采用常用的3—交换变异交叉、变 异之后如果子个体不同于种群中的所有个体则进 入种群同时为保持种群规模不变删去种群中最差 的个体． 图2 遗传算法流程图 Fig．2 Flow chart of genetic algorithm 在图2所示的遗传算法中各通用参数设置如 下：种群规模 pop—size＝60；交叉概率 pc＝1；变异概 率 pm＝0∙1；算法终止条件为运算5000代．对于所 提出的基于信息素的交叉算子中的参数即 α、q0 和ρ则按照文献 ［14］ 的建议分别设置为：α＝3 q0＝0∙9ρ＝0∙95． 2∙1 交叉过程分析 基于信息素的遗传交叉算子在逐步构造子个体 的过程中算子首先从当前城市的“邻居”中选出下 一城市当所有“邻居”都被访问过后再利用信息素 （式（1））进行选择．为了能对交叉过程有进一步的 了解本文对子个体的构造过程进行了统计实验． 实验以 TSPLIB 中的基准算例 eil51（51个城市的 TSP 问题）为例且算法独立运行20次．图3所示 为在构造子个体的过程中交叉算子利用信息素选 出下一城市的平均概率．由图3可知：在遗传搜索 的初期由于种群个体间的差异较大交叉算子利用 式（1）构造子个体的概率较高（约8∙5％）；随着遗传 搜索的进行种群个体的质量普遍提高个体间的差 异逐渐减小这使得交叉算子从“邻居”中选出下一 城市的可能性增加而利用信息素进行选择的概率 也逐渐稳定在4∙5％左右． 图3 交叉过程中利用信息素选择的概率 Fig．3 Probability of selection utilizing pheromone during crossover 2∙2 不同交叉算子间的比较 为了检验基于信息素的遗传交叉算子的有效 性在图2所示的纯遗传算法的框架内将该算子和 其他知名的交叉方法（包括 MPX、GSX、DPX 和 GSX-Ⅱ）进行了比较．在比较时各参数均设置如 前所示且算法共搜索5000代各基准算例20次独 立运算的平均计算结果如表1所示．由表1可知 对于所有的基准算例基于信息素的交叉算法都获 得优于其他各交叉方法的路线． 另外本文还以算例 d198为例比较了应用不 同交叉算子时的最优路线长度的进化过程如图4 所示．比较结果显示基于信息素的交叉方法无论 是在精度和还是在收敛速度上均优于其他几种遗传 交叉算子． ·1186· 北 京 科 技 大 学 学 报 第30卷
第10期 赵方庚等：求解$问题的一种基于信息素的遗传交叉算子 ,1187, 表1计算结果比较 Fig-I Comparison of computational results 算例 最优值 基于信息素的交叉 MPX GSX DPX Gsx-Ⅱ eil51.tsp 426 428.2 465.0 430.2 429.2 460.1 eil76.tsp 538 542.1 604.1 544.7 542.7 593.3 lin105.tsp 14379 14484.6 16823.0 14609.3 14510.9 15658.9 ch130.tsp 6110 6201.8 7064.3 6340.3 6233.9 6923.6 d198.tsp 15780 15875.6 17728.7 16038.7 17583.6 17562.2 18500 [4]Nguyen H D.Yoshihara I.Yamamori K.et al.Implementation 18000 d198 of an effective hybrid GA for large"seale traveling salesman prob- lems.IEEE Trans Syst Man Cybern B.2007.37(1):92 17500 本文提出算子 [5]Tsubakitani S.Evans JR.Optimizing tabu list size for the travel- 17000 DPX …GSX-Ⅱ ing salesman problem.Comput Oper Res.1998.25(2):91 16500 --.GSX [6]Goldberg D E.Lingle R.Alleles.loci,and the traveling salesman -·MPX 16000 problem//Proceedings of the First International Conference on Genetic Algorithms and Their Applications.New Jersey.1985: 15500 1001 20013001 4001 5001 154 进化代数 [7]Syswerda G.Handbook of Genetic Algorithms.New York:Van Nostrand Reinhold.1991:332 图4不同交叉算子下最优路线进化过程比较 [8]Oliver I.Smith D.Holland J.A study of permutation crossover Fig.4 Comparison of evolutional process of GA using different operators on the traveling salesman problem/Proceedings of 2nd crossover operators International Conference on Genetic Algorithms.Massachusetts 1987:224 3结论 [9]Nguyen H D.Hybrid Genetic Algorithms for Combinatorial Op- timization Problems Dissertation ]Miyazaki:University of 本文提出了求解TSP问题的一种新颖的交叉 Miyazaki.2004 方法一基于信息素的遗传交叉算子，该算子在进 [10]Nguyen H D.Yoshihara 1,Yasunaga M.Modified edge recom- 行交叉时，不仅能够利用包括边长度和邻接关系在 bination operators of genetic algorit hms for the traveling salesman problem//Proceedings of IEEE 26th Annual Conference on In- 内的局部信息，还可以从各边上的信息素中获取全 dustrial Electronics Society.Nagoya.2000:2815 局信息，在对所提出算子的交叉过程进行实验分析 [11]Cheng R.Gen M.Crossover on intensive search and traveling 之后，本文将该算子与其他四种知名的交叉方法进 salesman problem //Proceedings of 16th International Confer- 行了比较.实验结果表明，基于信息素的遗传交叉 ence on Computer Industrial Engineering.Nagoya.1994: 568 算子无论是在精度还是在收敛速度方面均优于其他 [12]Merz P,Freisleben B.Genetic local search for the TSP:New 四种交叉方法， results//Proceedings of IEEE International Conference on Evo- 参考文献 lutionary Computation.Indianapolis,1997:159 [13]Nguyen H D.Yoshihara I,Yamamori K.et al.Greedy genetic [1]Padberg M.Rinaldi R.Optimization of a 532-city symmetric algorithms for symmetric and asymmetric TSPs.IPSJ Trans traveling salesman problem by branch and cut.Oper Res Lett, Math Modeling Appl.2002.43(10):165 1987,6(1):1 [14]Gambardella L M.Dorigo M.Solving symmetric and asymmet- [2]Lin S.Kernighan B.An effective heuristic algorithm for the trav- ric TSPs by ant colonies//Proceedings of IEEE International eling salesman problem.Oper Res.1973.21(2):498 Conferenceon Evoluionary Compuatio Chicago.1996622 [3]Ellabib I.Calamai P,Basir O.Exchange strategies for multiple [15]Stutzle T.Hoos H.MAX-MIN ant system.Future Gener ant colony system.Inf Sci.2007,177(5):1248 Comput Syst,2000,16(8):889
表1 计算结果比较 Fig．1 Comparison of computational results 算例 最优值 基于信息素的交叉 MPX GSX DPX GSX-Ⅱ eil51．tsp 426 428∙2 465∙0 430∙2 429∙2 460∙1 eil76．tsp 538 542∙1 604∙1 544∙7 542∙7 593∙3 lin105．tsp 14379 14484∙6 16823∙0 14609∙3 14510∙9 15658∙9 ch130．tsp 6110 6201∙8 7064∙3 6340∙3 6233∙9 6923∙6 d198．tsp 15780 15875∙6 17728∙7 16038∙7 17583∙6 17562∙2 图4 不同交叉算子下最优路线进化过程比较 Fig．4 Comparison of evolutional process of GA using different crossover operators 3 结论 本文提出了求解 TSP 问题的一种新颖的交叉 方法———基于信息素的遗传交叉算子．该算子在进 行交叉时不仅能够利用包括边长度和邻接关系在 内的局部信息还可以从各边上的信息素中获取全 局信息．在对所提出算子的交叉过程进行实验分析 之后本文将该算子与其他四种知名的交叉方法进 行了比较．实验结果表明基于信息素的遗传交叉 算子无论是在精度还是在收敛速度方面均优于其他 四种交叉方法． 参 考 文 献 ［1］ Padberg MRinaldi R．Optimization of a 532-city symmetric traveling salesman problem by branch and cut． Oper Res Lett 19876（1）：1 ［2］ Lin SKernighan B．An effective heuristic algorithm for the traveling salesman problem．Oper Res197321（2）：498 ［3］ Ellabib ICalamai PBasir O．Exchange strategies for multiple ant colony system．Inf Sci2007177（5）：1248 ［4］ Nguyen H DYoshihara IYamamori Ket al．Implementation of an effective hybrid GA for large-scale traveling salesman problems．IEEE T rans Syst Man Cybern B200737（1）：92 ［5］ Tsubakitani SEvans J R．Optimizing tabu list size for the traveling salesman problem．Comput Oper Res199825（2）：91 ［6］ Goldberg D ELingle R．Alleleslociand the traveling salesman problem∥ Proceedings of the First International Conference on Genetic Algorithms and Their Applications．New Jersey1985： 154 ［7］ Syswerda G．Handbook of Genetic Algorithms．New York：Van Nostrand Reinhold1991：332 ［8］ Oliver ISmith DHolland J．A study of permutation crossover operators on the traveling salesman problem∥ Proceedings of 2nd International Conference on Genetic Algorithms．Massachusetts 1987：224 ［9］ Nguyen H D．Hybrid Genetic Algorithms for Combinatorial Optimiz ation Problems ［ Dissertation ］． Miyazaki： University of Miyazaki2004 ［10］ Nguyen H DYoshihara IYasunaga M．Modified edge recombination operators of genetic algorithms for the traveling salesman problem∥ Proceedings of IEEE26th A nnual Conference on Industrial Electronics Society．Nagoya2000：2815 ［11］ Cheng RGen M．Crossover on intensive search and traveling salesman problem∥ Proceedings of 16th International Conference on Computer ＆ Industrial Engineering．Nagoya1994： 568 ［12］ Merz PFreisleben B．Genetic local search for the TSP：New results∥ Proceedings of IEEE International Conference on Evolutionary Computation．Indianapolis1997：159 ［13］ Nguyen H DYoshihara IYamamori Ket al．Greedy genetic algorithms for symmetric and asymmetric TSPs． IPSJ T rans Math Modeling Appl200243（10）：165 ［14］ Gambardella L MDorigo M．Solving symmetric and asymmetric TSPs by ant colonies∥ Proceedings of IEEE International Conference on Evolutionary Computatio．Chicago1996：622 ［15］ Stützle THoos H． MAX-MIN ant system． Future Gener Comput Syst200016（8）：889 第10期 赵方庚等： 求解 TSP 问题的一种基于信息素的遗传交叉算子 ·1187·