资源描述：
《求解tsp 的变异算子的设计及优化应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2006年第23卷·增刊微电子学与计算机183求解TSP的变异算子的设计及优化应用钟文亮(中山大学计算机科学系,广东广州510275)摘要:通过选择合适的算子和参数,遗传算法(GA)可以有效求解旅行商问题(TSP)。GA通常可以获得满意解,但容易陷入早熟,因而较难求得全局最优解。传统的变异算子在求解该问题时性能并不理想,甚至会引起反作用。文章通过实验分析多种变异算子在求解TSP时的表现,提出了一个改进的破坏重建变异法,并利用该方法对算法进行优化。经仿真实验测试,该方法效果明显。关键词:TSP,遗传算法,变异算子中图分类号:TP18文
2、献标识码:A文章编号:1000-7180(2006)S0-0183-04StrategyofDesigningtheMutationOperatorforTSPanditsApplicationZHONGWen-liang(DepartmentofComputerScience,SunYat-senUniversity,Guangzhou510275,China)Abstract:Bychoosingappropriateoperatorsandparameters,geneticalgorithms(GA)cansolvethet
3、ravelingsalesmanproblem(TSP)effectively.However,obtainingtheglobalbestsolutiontoTSPusingGAisalwaysdifficult,especiallywithoutsomegoodenoughmutationoperators.AstheperformancesofGAforTSPusingtraditionalmutationoperatorsarenotsatisfying,thispaperproposesthedestroyingandre
4、buildingmutationoperatorafteranalyzingvariousmutationoperatorsforTSP.Thenewoperatorisimplementedandtheexperimentalresultsdemonstratetheeffectivenessoftheal-gorithm.Keywords:TSP,Geneticalgorithms,Mutationoperator1引言环(同时具有一定概率产生变异),直到求得满意解旅行商问题TSP(TravelingSalesmanProble
5、m)或满足其他终止条件为止。算法的运行过程具有很是著名组合优化问题。问题的描述非常简单:假设强的指向性,适合众多复杂问题的求解。一个旅行商要选择一条路径拜访n个城市,限制是旅行商问题规定了每个城市只能出现一次,因每个城市只能且必须拜访一次,而且最后要回到原此编码有其特殊性。简单遗传算法(SGA)求解TSP来出发的城市。路径的选择目标是求得的路径路程的效果并不好,主要原因就是传统的交配和变异方为所有路径之中的最小值。穷举解决该问题的算法式通常很容易产生非法的解序列,很多学者专门为复杂度是n!,当n比较大的时候,现有的计算机根该问题设计
6、了多种交配算子、变异算子和选择算本无法短时间完成运算。因此一个高效的算法对于子,并且取得了显著的效果。本文通过实验,比较了求解TSP至关重要。近年比较流行的算法有模拟退5种变异算子的设计思想在TSP中的表现,并总结火、遗传算法和蚁群算法等。出一种变异算子的设计策略,仿真证明,利用该变遗传算法模拟自然选择和生物进化的过程,以异算子设计策略改进后变异效果明显变好,求得最优胜劣汰的方式求解问题。算法需选择一种合适的优解的概率明显增大。编码方式表示解,并选择一种评价函数用来每个解的适应值,适应值高的解更容易被选中并进行交2求解TSP的遗传算
7、法描述配,然后产生新的子代。选择和交配的过程一直循2.1算法流程图收稿日期:2006-04-28算法流程图如图1所示。基金项目:国家自然科学基金项目(60573066)2.2适应度函数广东省自然科学基金项目(5003346)适应度函数:f(x)=1/S,S是路径总长度。184微电子学与计算机2006年第23卷·增刊(4)基于插入的变异,按某种方式选出若干个基因(本文采用随机方式),把它们从染色体中删去,然后按某种方式,如最佳插入(即每次把城市插入到代价最小的位置),逐个插入到已经删去变异基因后的染色体中。(5)根据前面几种实验结果,
8、本文改进了破坏重建法[5],改进后方法说明如下:在坐标地图上选出一个中心城市,以该城市为中心,以r为半径作圆,在圆内的所有城市都将被抽出来,然后以随机次序对它们进行最佳插入。r的大小理论上可以任意,但2.3选择操作显然大于地图上任意两
