MATLAB关于旅行商问题遗传算法的研究

1基于遗传算法对TSP问题的研究摘要：作为一种模拟生物自然遗传与进化过程的优化方法,遗传算法(GA)因其具有隐并行性、不需目标函数可微等特点,常被用于解决一些传统优化方法难以解决的问题。旅行商问题(TSP)是典型的NP难题组合优化问题之一,且被广泛应用于许多领域,所以研究遗传算法求解TSP具有重要的理论意义和应用价值。关键字：遗传算法旅行商问题Abstract：Geneticalgorithm(GA)whichhasthecharacteristicoflatentparallelism,non-differentiabilityofobjectivefunctionandsoon,asaoptimizationmethodofsimulatingtheprocessofnaturalbioticinheritandevolution,isusedtosolvesomeproblemswhicharedifficulttosolvebythetraditionaloptimizationmethod.Travelsalesmanproblem(TSP)isatypicalNFscombinationandoptimizationproblem,andiswidelyusedinmanyfields.SothegeneticalgorithmtosolveTSPhasimportanttheoreticalsignificanceandapplicationvalue.Keywords：geneticalgorithmTSP一、引言在过去,人们往往只能够处理一些简单的问题，对于大型复杂系统的优化和自适应仍然无能为力。但是在自然界中，生物在这方面表现出了其优异的能力，他们能够通过优胜劣汰、适者生存的自然进化规则进行生存和繁衍，并且慢慢的产生对其生存环境适应性越来越高的优良物种。遗传算法就是模拟自然进化的一种高效的算法。其基本思想就是模拟自然界进化机制和生物进化论而形成的一种过程搜索最优解得算法。遗传算法是一门新的学科，各种理论、方法都尚未成熟，有待于进一步地发展和完善，但它却让我们看到了解决许多复杂问题的希望。尽管在遗传算法的研究和应用过程中出现过许多难题，同时也会产生许多不同的算法设计，但是，目前遗传算法的运用过程中已经展现出了其优异的性能和巨大的发展前景。我们相信，随着研究工作的进一步深入和发展，遗传算法一定能够在智能计算领域中起到关键性作用。巡回旅行商问题(TravelingSalesmanProblem,TSP),是一个著名的组合优化问题[1],该类问题具有很强的运用背景。如数控机床上的最优钻孔路线的选取、电路板的焊接、物流的调度问题都属于旅行商问题。因此旅行商问题受到了各方面的关注。目前解决TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描2述算法。有效解决TSP问题在计算理论和实际应用上都有很高的价值。本文主要介绍了运用遗传算法来解决TSP问题。二、研究背景旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值旅行推销员问题是数图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。迄今为止，这类问题中没有一个找到有效算法。倾向于接受NP完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法旅行商问题在很多领域中都可以应用，例如：1、如何规划最合理高效的道路交通，以减少拥堵；2、如何更好地规划物流，以减少运营成本；3、在互联网环境中如何更好地设置节点，以更好地让信息流动等。三、解决TSP问题所使用的方法旅行商问题是一个典型的NP完全问题，遗传算法是解决这类问题一个比较理想的算法。遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化方法。它的基本思想来自于Darwin的进化论和Mendel的遗传学。遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优解的方案，在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再3造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法广泛应用在生物信息学、系统发生学、计算科学、工程学、经济学、化学、制造、数学、物理、药物测量学和其他领域之中。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。遗传算法在解决TSP问题的流程图如图1所示。4图1遗传算法在解决TSP问题的流程图实例：假设有一个旅行商人要拜访30个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值基于遗传算法解决TSP问题的程序如下：clear;CityNum=30;[dislist,Clist]=tsp(CityNum);Tlist=zeros(CityNum);cl=100;bsf=Inf;5tl=50;l1=200;S0=randperm(CityNum);S=S0;BSF=S0;Si=zeros(l1,CityNum);StopL=2000;p=1;clf;figure(1);while(pStopL+1)ifl1CityNum*(CityNum)/2disp('候选解个数,不大于n*(n-1)/2(全部领域解个数)！系统自动退出！');l1=(CityNum*(CityNum)/2)^.5;break;endArrS(p)=CalDist(islist,S);i=1;A=zeros(l1,2);whilei=l1M=CityNum*rand(1,2);M=ceil(M);ifM(1)~=M(2)m1=max(M(1),M(2));m2=min(M(1),M(2));A(i,1)=m1;A(i,2)=m2;ifi==1isdel=0;elseforj=1:i-16ifA(i,1)==A(j,1)&&A(i,2)==A(j,2)isdel=1;break;elseisdel=0;endendendif~isdeli=i+1;elsei=i;endelsei=i;endendfori=1:l1Si(i,:)=S;Si(i,[A(i,1),A(i,2)])=S([A(i,2),A(i,1)]);CCL(i,1)=i;CCL(i,2)=CalDist(dislist,Si(i,:));CCL(i,3)=S(A(i,1));CCL(i,4)=S(A(i,2));end[fsfin]=sort(CCL(:,2));fori=1:clCL(i,:)=CCL(fin(i),:);end7ifCL(1,2)bsf%藐视准则(aspirationcriterion)bsf=CL(1,2);S=Si(CL(1,1),:);BSF=S;form=1:CityNumforn=1:CityNumifTlist(m,n)~=0Tlist(m,n)=Tlist(m,n)-1;endendendTlist(CL(1,3),CL(1,4))=tl;elsefori=1:clifTlist(CL(i,3),CL(i,4))==0S=Si(CL(i,1),:);form=1:CityNumforn=1:CityNumifTlist(m,n)~=0Tlist(m,n)=Tlist(m,n)-1;endendendTlist(CL(i,3),CL(i,4))=tl;break;endendendArrbsf(p)=bsf;drawTSP(Clist,BSF,bsf,p,0);8p=p+1;endBestShortcut=BSFtheMinDistance=bsffigure(2);plot(Arrbsf,'r');holdon;plot(ArrS,'b');grid;title('搜索过程');legend('最优解','当前解');四、结论与分析程序编好后，运算结果如图2、图3、图4所示。图2依次经过点的顺序90102030405060708090100010203040506070809010030城市TSP第2000步最短距离为439.6937图3最后路线的封闭图020040060080010001200140016001800200040050060070080090010001100120013001400搜索过程最优解当前解图4探索过程由计算结果可知，最优路径如图2所示，路径最短为439.6973。10四、结论与分析本文通过遗传算法求解TSP问题，成功获得了全局最优解。综上所述，在求解的过程中遗传算法能够收敛到某一稳定的“最优解”。在求解的质量和优化效率上都表现出了比较突出的能力。针对具体TSP问题，遗传算法的几个关键参数都有它自己的适合值，种群大小、交叉率、变异率、遗传代数都从一定程度上影响着算法的效率和质量五、参考文献[1]韩瑞锋编著.遗传算法原理与应用实例.北京：兵器工业出版社,2010.[2]孙健，钟义信，王伟，2000年8月1日-全国信息论与通信理论学术会议[3]石利平.改进型遗传算法求解TSP问题[J].实验技术与管理,2014,(第7期)[4]王剑文.戴光明.谢柏桥.张全元求解TSP问题算法综述[J]-计算机工程与科学2008(2)[5]张春霞,王蕊.基于遗传算法求解TSP问题的算法设计[J].安阳工学院学报,2008,(08):32-33.[6]高经维,张煦,李峰.求解TSP问题的遗传算法实现[J].计算机时代,2008,(07):30-31[7]周春辉;胡适军;文元桥.遗传算法求解TSP问题的实现与改进[J]软件导刊2013第2期