求解TSP 的变异算子的设计及优化应用.pdf

2006年第23卷·增刊微电子学与计算机183

求解TSP的变异算子的设计及优化应用

钟文亮
(中山大学计算机科学系,广东广州510275)

摘要:通过选择合适的算子和参数,遗传算法(GA)可以有效求解旅行商问题(TSP)。GA通常可以获得满意解,
但容易陷入早熟,因而较难求得全局最优解。传统的变异算子在求解该问题时性能并不理想,甚至会引起反作用。
文章通过实验分析多种变异算子在求解TSP时的表现,提出了一个改进的破坏重建变异法,并利用该方法对算法
进行优化。经仿真实验测试,该方法效果明显。
关键词:TSP,遗传算法,变异算子
中图分类号:TP18文献标识码:A文章编号:1000-7180(2006)S0-0183-04

StrategyofDesigningtheMutationOperatorforTSPandits
Application

ZHONGWen-liang
(DepartmentofComputerScience,SunYat-senUniversity,Guangzhou510275,China)

Abstract:Bychoosingappropriateoperatorsandparameters,geneticalgorithms(GA)cansolvethetravelingsalesman
problem(TSP)effectively.However,obtainingtheglobalbestsolutiontoTSPusingGAisalwaysdifficult,especially
withoutsomegoodenoughmutationoperators.AstheperformancesofGAforTSPusingtraditionalmutationoperators
arenotsatisfying,thispaperproposesthedestroyingandrebuildingmutationoperatorafteranalyzingvariousmutation
operatorsforTSP.Thenewoperatorisimplementedandtheexperimentalresultsdemonstratetheeffectivenessoftheal-
gorithm.
Keywords:TSP,Geneticalgorithms,Mutationoperator

1引言环(同时具有一定概率产生变异),直到求得满意解
旅行商问题TSP(TravelingSalesmanProblem)或满足其他终止条件为止。算法的运行过程具有很
是著名组合优化问题。问题的描述非常简单:假设强的指向性,适合众多复杂问题的求解。
一个旅行商要选择一条路径拜访n个城市,限制是旅行商问题规定了每个城市只能出现一次,因
每个城市只能且必须拜访一次,而且最后要回到原此编码有其特殊性。简单遗传算法(SGA)求解TSP
来出发的城市。路径的选择目标是求得的路径路程的效果并不好,主要原因就是传统的交配和变异方
为所有路径之中的最小值。穷举解决该问题的算法式通常很容易产生非法的解序列,很多学者专门为
复杂度是n!,当n比较大的时候,现有的计算机根该问题设计了多种交配算子、变异算子和选择算
本无法短时间完成运算。因此一个高效的算法对于子,并且取得了显著的效果。本文通过实验,比较了
求解TSP至关重要。近年比较流行的算法有模拟退5种变异算子的设计思想在TSP中的表现,并总结
火、遗传算法和蚁群算法等。出一种变异算子的设计策略,仿真证明,利用该变
遗传算法模拟自然选择和生物进化的过程,以异算子设计策略改进后变异效果明显变好,求得最
优胜劣汰的方式求解问题。算法需选择一种合适的优解的概率明显增大。
编码方式表示解,并选择一种评价函数用来每个解
的适应值,适应值高的解更容易被选中并进行交2求解TSP的遗传算法描述
配,然后产生新的子代。选择和交配的过程一直循2.1算法流程图
收稿日期:2006-04-28算法流程图如图1所示。
基金项目:国家自然科学基金项目(60573066)2.2适应度函数
广东省自然科学基金项目(5003346)适应度函数:f(x)=1/S,S是路径总长度。
184微电子学与计算机2006年第23卷·增刊

(4)基于插入的变异,按某种方式选出若干个
基因(本文采用随机方式),把它们从染色体中删
去,然后按某种方式,如最佳插入(即每次把城市插
入到代价最小的位置),逐个插入到已经删去变异
基因后的染色体中。
(5)根据前面几种实验结果,本文改进了破坏
重建法[5],改进后方法说明如下:在坐标地图上选出
一个中心城市,以该城市为中心,以r为半径作圆,
在圆内