混合遗传算法解决单目标旅行商问题的研究.pdf

《混合遗传算法解决单目标旅行商问题的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、总第15卷166期大众科技Vol.15No.62013年6月PopularScience&TechnologyJune2013混合遗传算法解决单目标旅行商问题的研究1,2袁成林（1.广西大学计算机与电子信息学院，广西南宁530004；2.广西医科大学基础医学院，广西南宁530021）【摘要】对混合遗传算法解决单目标旅行商问题进行研究，提出了一种基于对应连通子图交叉的混合遗传算法。本算法还包括初始种群的生成、适应度函数的计算、选择、变异、LK局部搜索和小生境操作。最后通过具体算例的实验和对比表明算法是有效的，在计算精度和速度上有较大提高。【关键词】混合遗传算法；旅行商问题；对应连通子图交叉【中

2、图分类号】TP309【文献标识码】A【文章编号】1008-1151(2013)06-0004-03ResearchofHybridGeneticAlgorithmtoSolvetheSingleObjectiveTravelingSalesmanProblemAbsract:Hybridgeneticalgorithmtosolvethesingle-objectivetravelingsalesmanproblem,hybridgeneticalgorithmisproposedbasedonlookingfortheCorrespondingConnectedSubgraphCrosso

3、ver.Thealgorithmalsoincludesthegenerationoftheinitialpopulationtoadapttothecalculationofthefunction,selection,mutation,LKlocalsearchandnicheoperation.Finally,experimentalandcomparisonofspecificnumericalexamplesshowthatthealgorithmiseffectiveandhasimprovedgreatlyinaccuracyandspeed.Keywords:hybridgen

4、eticalgorithm;travelingsalesmanproblem;correspondingconnectedsubgraphcrossover[1]遗传算法是一种基于进化策略的优化算法，被广泛使方向进化。对于旅行商问题通常采取自然编码，即每个基因用在组合优化问题中。但是遗传算法在解决问题的时候也有位对应一个城市的号码。例如1-2-3-4-5-6表示依次经过城[2]诸多不足，首先是在早期的搜索中常常丢失种群的多样性。市1到6最后回到1。这种编码容易理解，效率高。但是在在单目标优化中，对于种群的适应性方面的研究很多，多样这种编码方式下普通的交叉算法就不再适用了，因为可能产性保持方面

5、常常用的手段是小生境方法。其次由于遗传算法生没有意义的个体。图1中两条可用路径经过交叉操作以后，的局部能力差，也有学者采用其他局部搜索算法来构造混合产生的1-1-5-6-3-6路径是没有意义的。为了解决这个问题，[3]遗传算法，这些方法对在种群适应性方面是有效的，但是很多学者提出了适用于TSP的交叉算子，像顺序插入法，启在种群多样性方面却不足，对于有的优化问题来说，多样性发式交叉等，但是这些算法会打乱交叉片段中的基因位置因保持对搜索最优解有着重要的作用。最后在旅行商问题中普而不能保存父体的优秀基因片段。通的交叉算子会破坏要交换的基因片段，针对这个问题本文提出了对应连通子图交叉(Corresp

6、ondingConnectedSubgraphCrossover,CCSC)，结合LK局部搜索和小生境等操作构造一种基于CCSC的混合遗传算法(CHGA)。通过几个实例的计算和对比表明，算法的设计是有效的，求解质量也有较大提高。1对应连通子图交叉交叉算子是遗传算法中最重要的部分，既可以使个体发图1普通交叉操作产生的不可用路径生变化，又能保留父体的优秀基因片段，使种群向着理想的【收稿日期】2013-05-10【基金项目】广西大学科研基金（XJZ110585）；广西研究生教育创新项目（YCSZ2012018）。【作者简介】袁成林（1982－），男，广西大学计算机与电子信息学院硕士生，研究方向为计

7、算智能。-4-基于以上分析，本文提出一种新的交叉算子：对应连通下一代进行交叉和变异操作，本文采用的是轮盘赌法，根据子图交叉(CCSC)。这种交叉方法可以做到严格的交叉，即子个体的适应度进行选择，适应度越大个体被选择的概率就越代的基因都是从父代继承所得，所有基因片段都可以在两个大，并且可以保留少量适应度较差的个体，增加种群多样性。父体中找到。CCSC通过合并两条父体路径，构造连通图G。2.2变异和交叉算子对G中