一些解决TSP问题算法源代码

个人资料整理 仅限学习使用模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/(kT>，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退b5E2RGbCAP火模拟组合优化问题，将内能 E模拟为目标函数值 f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始p1EanqFDPw解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的DXDiTa9E3d当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(CoolingRTCrpUDGiTSchedule>控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。3.5.1模拟退火算法的模型模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想:(1>初始化：初始温度T(充分大>，初始解状态S(是算法迭代的起点>，每个T值的迭代次数L(2>对k=1，，L做第(3>至第6步：(3>产生新解S′(4>计算增量t′=C(S′>-C(S>，其中C(S>为评价函数(5>若t′<0则接受S′作为新的当前解，否则以概率exp(-t′/T>接受S′作为新的当前解.(6>如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。(7>T逐渐减少，且T->0，然后转第2步。算法对应动态演示图：模拟退火算法新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当5PCzVD7HxA前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法jLBHrnAILg决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。xHAQX74J0X1/67个人资料整理 仅限学习使用事实表明，对大多数应用而言，这是计算目标函数差的最快方法。第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则:若t′<0则接受S′作LDAYtRyKfE为新的当前解S，否则以概率exp(-t′/T>接受S′作为新的当前解S。第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正 Zzz6ZB2Ltk目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮实验。而当新解被判定为舍弃时，则在原当前解的dvzfvkwMI1基础上继续下一轮实验。模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点>无关；模拟退火算法具有渐近收敛性，已在rqyn14ZNXI理论上被证明是一种以概率l收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。3.5.2模拟退火算法的简单应用作为模拟退火算法应用，讨论货郎担问题 (TravellingSalesmanProblem，简记为TSP>：设有n个城市，用数码 1, ,n代表EmxvxOtOco。城市i和城市j之间的距离为d(i，j>i,j=1,．,nTSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最SixE2yXPq5短.。求解TSP的模拟退火算法模型可描述如下：解空间解空间S是遍访每个城市恰好一次的所有回路，是{1，，n}的所有循环排列的集合，S中的成员记为(w1,w2,6ewMyirQFL，wn>，并记wn+1=w1。初始解可选为(1，，n>目标函数此时的目标函数即为访问所有城市的路径总长度或称为代价函数：kavU42VRUs我们要求此代价函数的最小值。新解的产生随机产生1和n之间的两相异数 k和m，若k<m，则将(w1,w2, ，wk,wk+1, ，wm, ，wn>变为：(w1,w2, ，wm,wm-1,，wk+1,wk, ，wn>.如果是k>m，则将(w1,w2, ，wk,wk+1, ，wm, ，wn>变为：(wm,wm-1,，w1,wm+1,，wk-1,wn,wn-1,，wk>.上述变换方法可简单说成是 “逆转中间或者逆转两端”。也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交2/67个人资料整理 仅限学习使用替使用，得到一种更好方法。代价函数差设将(w1,w2, ，wn>变换为(u1,u2, ，un>,则代价函数差为： y6v3ALoS89根据上述分析，可写出用模拟退火算法求解 TSP问题的伪程序：ProcedureTSPSA:begininit-of-T。{T为初始温度}S={1，，n}。{S为初始值}termination=false。whiletermination=falsebeginfori=1toLdobegingenerate(S′formS>。{从当前回路S产生新回路S′}t:=f(S′>>-f(S>。{f(S>为路径总长}IF( t<0>OR(EXP(- t/T>>Random-of-[0,1]>S=S′。IFthe-halt-condition-is-TRUETHENtermination=true 。End。T_lower。End。End模拟退火算法的应用很广泛，可以较高的效率求解最大截问题 (MaxCutProblem>、0-1背包问题(ZeroOneKnapsackM2ub6vSTnPProblem>、图着色问题(GraphColouringProblem> 、调度问题(SchedulingProblem>等等。0YujCfmUCw3.5.3模拟退火算法的参数控制问题模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：(1>温度T的初始值设置问题。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但eUts8ZQVRd因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要sQsAEJkW5T依据实验结果进行若干次调整。(2>退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火>是相当必要的，但这GMsIasNXkA3/67个人资料整理 仅限学习使用需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。(3>温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采TIrRGchYzg用如下所示的降温方式：T(t+1>＝k×T(t>式中k为正的略小于1.00的常数，t为降温的次数使用SA解决TSP问题的Matlab程序：functionout=tsp(loc>TSPTravelingsalesmanproblem(TSP>usingSA(simulatedannealing>.TSPbyitselfwillgenerate20citieswithinaunitcubeandthenuseSAtoslovethisproblem.%TSP(LOC>solvethetravelingsalesmanproblemwithcities'coordinatesgivenbyLOC,whichisanMby2matrixandMisthenumberofcities.%Forexample:%loc=rand(50,2> 。%tsp(loc>。ifnargin==0,ThefollowingdataisfromthepostbyJenniferMyers(jmyers@>edu>tocomp.ai.neural-nets.It'sobtainedfromthefigureinHopfield&Tank's1985paperinBiologicalCybernetics(Vol52,pp.141-152>.loc=[0.3663,0.9076 。0.7459,0.8713。0.4521,0.8465。0.7624,0.7459。0.7096,0.7228。0.0710,0.7426。0.4224,0.7129。0.5908,0.6931。0.3201,0.6403。0.5974,0.6436。0.3630,0.5908。0.6700,0.5908。0.6172,0.5495。0.6667,0.5446。0.1980,0.4686。0.3498,0.4488。0.2673,0.4274。0.9439,0.4208。0.8218,0.3795。0.3729,0.2690。0.6073,0.2640。0.4158,0.2475。0.5990,0.2261。0.3927,0.1947。0.5347,0.1898。0.3960,0.1320。0.6287,0.0842。0.5000,0.0396。0.9802,0.0182。0.6832,0.8515]。endNumCity=length(loc> 。%Numberofcities4/67个人资料整理 仅限学习使用distance=zeros(NumCity> 。%Initializeadistancematrix%Fillthedistancematrixfori=1:NumCity,forj=1:NumCity,distance(i,j>=norm(loc(i,-loc(j,> 。distance(i,j>=norm(loc(i,-loc(j,> 。endend%Togenerateenergy(objectivefunction>frompath%path=randperm(NumCity>。%energy=sum(distance((path-1>*NumCity+[path(2:NumCity>path(1>]>>。FindtypicalvaluesofdEcount=20。all_dE=zeros(count,1> 。fori=1:countpath=randperm(NumCity> 。energy=sum(distance((path-1>*NumCity+[path(2:NumCity>path(1>]>> 。new_path=path。index=round(rand(2,1>*NumCity+.5> 。inversion_index=(min(index>:max(index>> 。new_path(inversion_index>=fliplr(path(inversion_index>> 。all_dE(i>=abs(energy-...sum(sum(diff(loc([new_pathnew_path(1>],>'.^2>>> 。enddE=max(all_dE>。dE=max(all_dE>。temp=10*dE。%Choosethetemperaturetobelargeenoughfprintf('Initialenergy=%f\n\n',energy> 。%Initialplotsout=[pathpath(1>] 。plot(loc(out(,1>,loc(out(,2>,'r.','Markersize',20> 。axissquare。holdonh=plot(loc(out(,1>,loc(out(,2>> 。holdoffMaxTrialN=NumCity*100。%Max.#oftrialsatatemperatureMaxAcceptN=NumCity*10。%Max.#ofacceptancesatatemperatureStopTolerance=0.005。%StoppingtoleranceTempRatio=0.5。%TemperaturedecreaseratiominE=inf。%Initialvalueformin.energymaxE=-1。%Initialvalueformax.energy%Majorannealingloop5/67个人资料整理 仅限学习使用while(maxE-minE>/maxE>StopTolerance,minE=inf。minE=inf。maxE=0。TrialN=0。%NumberoftrialmovesAcceptN=0。%NumberofactualmoveswhileTrialN<MaxTrialN&AcceptN<MaxAcceptN,new_path=path。index=round(rand(2,1>*NumCity+.5>。inversion_index=(min(index>:max(index>>。new_path(inversion_index>=fliplr(path(inversion_index>>。new_energy=sum(distance(...(new_path-1>*NumCity+[new_path(2:NumCity>new_path(1>]>>。ifrand<exp((energy-new_energy>/temp>,%acceptit!energy=new_energy。path=new_path。minE=min(minE,energy>。maxE=max(maxE,energy>。AcceptN=AcceptN+1。endTrialN=TrialN+1。endend%Updateplotout=[pathpath(1>] 。set(h,'xdata',loc(out(,1>,'ydata',loc(out(,2>> 。drawnow。%Printinformationincommandwindowfprintf('temp.=%f\n',temp> 。tmp=sprintf('%d',path> 。fprintf('path=%s\n',tmp> 。fprintf('energy=%f\n',energy> 。fprintf('[minEmaxE]=[%f%f]\n',minE,maxE> 。fprintf('[AcceptNTrialN]=[%d%d]\n\n',AcceptN,TrialN> 。%Lowerthetemperaturetemp=temp*TempRatio 。endPrintsequentialnumbersinthegraphicwindowfori=1:NumCity,text(loc(path(i>,1>+0.01,loc(path(i>,2>+0.01,int2str(i>,...6/67个人资料整理 仅限学习使用'fontsize',8>。end7EqZcWLZNX又一个相关的Matlab程序function[X,P]=zkp(w,c,M,t0,tf>[m,n]=size(w> 。L=100*n。t=t0。clearm。x=zeros(1,n>xmax=x。fmax=0。whilet>tffork=1:Lxr=change(x>gx=g_0_1(w,x> 。gxr=g_0_1(w,xr> 。ifgxr<=Mfr=f_0_1(xr,c> 。f=f_0_1(x,c> 。df=fr-f。ifdf>0x=xr。iffr>fmaxfmax=fr。xmax=xr。endelsep=rand。ifp<exp(df/t>x=xr。endendendendt=0.87*tendP=fmax。X=xmax。下面的函数产生新解function[d_f,pi_r]=exchange_2(pi0,d>[m,n]=size(d> 。clearm。7/67个人资料整理 仅限学习使用u=rand。u=u*(n-2> 。u=round(u> 。ifu<2u=2。endifu>n-2u=n-2。endv=rand。v=v*(n-u+1> 。v=round(v>。ifv<1v=1。endv=v+u。ifv>nv=n。endpi_1(u>=pi0(v> 。pi_1(u>=pi0(u> 。ifu>1fork=1:(u-1>pi_1(k>=pi0(k> 。endendifv>(u+1>fork=1:(v-u-1>pi_1(u+k>=pi0(v-k> 。endendifv<nfork=(v+1>:npi_1(k>=pi0(k> 。endendd_f=0。ifv<nd_f=d(pi0(u-1>,pi0(v>>+d(pi0(u>,pi0(v+1>> 。fork=(u+1>:nd_f=d_f+d(pi0(k>,pi0(k-1>>-d(pi0(v>,pi0(v+1>> 。endd_f=d_f-d(pi0(u-1>,pi0(u>> 。fork=(u+1>:n8/67个人资料整理 仅限学习使用d_f=d_f-d(pi0(k-1>,pi0(k>> 。endelsed_f=d(pi0(u-1>,pi0(v>>+d(pi0(u>,pi0(1>>-d(pi0(u-1>,pi0(u>>-d(pi0(v>,pi0(1>>。fork=(u+1>:nd_f=d_f-d(pi0(k>,pi0(k-1>> 。endfork=(u+1>:nd_f=d_f-d(pi0(k-1>,pi0(k>> 。endendpi_r=pi_1。lzq7IGf02E遗传算法

GA遗传算法：旅行商问题(travelingsalemanproblem, 简称tsp>：已知n个城市之间的相互距离，现有一个推销员必须遍访这 n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e>，其中v是顶点集，e是边集，设d=(dij>是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，,n>和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，,n>。若对于城市v={v1,v2,v3,,vn}的一个访问顺序为t=(t1,t2,t3,,ti,,tn>,其中ti∈v(i=1,2,3,，,n>且记tn+1=t1，则旅行商问题的数学模型为：minl=σd(t(i>,t(i+1>><i=1,）,n旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。遗传算法：初始化过程：用v1,v2,v3,,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i>,t(i+1>>.评价函数eval(vi>：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1>，本文定义基于序的评价函数为eval(vi>=alpha*(1-alpha>.^(i-1>。[随机规划与模糊规划]选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。9/67意义的染色体，本文采用这种情况的出现。所谓的队员中的位置，如：个人资料整理 仅限学习使用step1、对每个染色体vi,计算累计概率qi，q0=0。qi=σeval(vj>j=1,。i=,i1,pop-size.step2、从区间(0,pop-size>中产生一个随机数r；step3、若qi-1<r<qi,则选择第i个染色体；step4、重复step2和step3共pop-size次，这样可以得到 pop-size个复制的染色体。grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际grefenstette编码《遗传算法原理及应用》可以避免grefenstette编码就是用所选队员在未选<不含淘汰）815216107431114612951813171对应：81421386325734324221 。交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过程：从[0，1]中产生一个随机数r，如果r<pc，则选择vi作为一个父代。将所选的父代两两组队，随机产生一个位置进行交叉，如：814213863257343242216123568563185633211交叉后为：814213863251856332116123568563734324221变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在 r<pm的标准下选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置按均匀变异<该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点变异为x'k=ukmin+r(ukmax-ukmin>）操作。如：81421386325734324221变异后：814213106322734524121反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。zvpgeqJ1hkMatlab程序：function[bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha>%————————————————————————%[bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha>%d:距离矩阵%termops:种群代数10/67个人资料整理 仅限学习使用%num:每代染色体的个数%pc:交叉概率%cxops:由于本程序采用单点交叉，交叉点的设置在本程序中没有很好的解决，所以本文了采用定点，即第cxops，可以随机产生。%pm:变异概率%alpha:评价函数eval(vi>=alpha*(1-alpha>.^(i-1>.%bestpop:返回的最优种群%trace:进化轨迹%------------------------------------------------%####@@@##版权所有！欢迎广大网友改正，改进！##@@@####%e-mail:tobysidney33@%####################################################%citynum=size(d,2> 。n=nargin。ifn<2disp('缺少变量！！'>disp('^_^ 开个玩笑^_^'>endifn<2termops=500。num=50。pc=0.25。cxops=3。pm=0.30。alpha=0.10。endifn<3num=50。pc=0.25。cxops=3。pm=0.30。alpha=0.10。endifn<4pc=0.25。cxops=3。pm=0.30。alpha=0.10。endifn<5cxops=3。pm=0.30。11/67个人资料整理 仅限学习使用alpha=0.10。endifn<6pm=0.30。alpha=0.10。endifn<7alpha=0.10。endifisempty(cxops>cxops=3。endNrpoJac3v1[t]=initializega(num,citynum>。fori=1:termops[l]=f(d,t>。[x,y]=find(l==max(l>>。trace(i>=-l(y(1>>。bestpop=t(y(1>,:>。[t]=select(t,l,alpha>。[g]=grefenstette(t>。[g1]=crossover(g,pc,cxops>。[g]=mutation(g1,pm>。%均匀变异[t]=congrefenstette(g>。end1nowfTG4KI---------------------------------------------------------function[t]=initializega(num,citynum>fori=1:numt(i,:>=randperm(citynum> 。end-----------------------------------------------------------function[l]=f(d,t>[m,n]=size(t> 。fork=1:mfori=1:n-1l(k,i>=d(t(k,i>,t(k,i+1>> 。endl(k,n>=d(t(k,n>,t(k,1>> 。l(k>=-sum(l(k,:>> 。end-----------------------------------------------------------function[t]=select(t,l,alpha>[m,n]=size(l> 。12/67个人资料整理 仅限学习使用t1=t。[beforesort,aftersort1]=sort(l,2> 。%fsortfromltoufori=1:naftersort(i>=aftersort1(n+1-i> 。%changeendfork=1:n。t(k,:>=t1(aftersort(k>,:> 。l1(k>=l(aftersort(k>> 。endt1=t。l=l1。fori=1:size(aftersort,2>evalv(i>=alpha*(1-alpha>.^(i-1> 。endm=size(t,1>。q=cumsum(evalv> 。qmax=max(q>。fork=1:mr=qmax*rand(1> 。forj=1:mifj==1&r<=q(1>t(k,:>=t1(1,:> 。elseifj~=1&r>q(j-1>&r<=q(j>t(k,:>=t1(j,:> 。endendend--------------------------------------------------function[g]=grefenstette(t>[m,n]=size(t> 。fork=1:mt0=1:n。fori=1:nforj=1:length(t0>ift(k,i>==t0(j>g(k,i>=j。t0(j>=[] 。breakendendendend-------------------------------------------function[g]=crossover(g,pc,cxops>13/67个人资料整理 仅限学习使用[m,n]=size(g> 。ran=rand(1,m> 。r=cxops。[x,ru]=find(ran<pc> 。ifru>=2fork=1:2:length(ru>-1g1(ru(k>,:>=[g(ru(k>,[1:r]>,g(ru(k+1>,[(r+1>:n]>] 。g(ru(k+1>,:>=[g(ru(k+1>,[1:r]>,g(ru(k>,[(r+1>:n]>] 。g(ru(k>,:>=g1(ru(k>,:> 。endend--------------------------------------------function[g]=mutation(g,pm>% 均匀变异[m,n]=size(g> 。ran=rand(1,m> 。r=rand(1,3> 。%daigaijinrr=floor(n*rand(1,3>+1> 。[x,mu]=find(ran<pm> 。fork=1:length(mu>fori=1:length(r>umax(i>=n+1-rr(i> 。umin(i>=1。g(mu(k>,rr(i>>=umin(i>+floor((umax(i>-umin(i>>*r(i>> 。endend---------------------------------------------------function[t]=congrefenstette(g>[m,n]=size(g> 。fork=1:mt0=1:n。fori=1:nt(k,i>=t0(g(k,i>> 。t0(g(k,i>>=[] 。endend------------------------------------------------- fjnFLDa5Zo又一个Matlab程序，其中交叉算法采用的是由 Goldberg和Lingle于1985年提出的PMX(部分匹配交叉>，淘汰保护指数alpha是我自己设计的，起到了加速优胜劣汰的作用。tfnNhnE6e5%TSP问题<又名：旅行商问题，货郎担问题）遗传算法通用 matlab程序%D是距离矩阵，n为种群个数,建议取为城市个数的 1~2倍，%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费14/67个人资料整理 仅限学习使用的时间而定%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4,不宜太大%alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0%R为最短路径,Rlength为路径长度function[R,Rlength]=geneticTSP(D,n,C,m,alpha> HbmVN777sL[N,NN]=size(D> 。farm=zeros(n,N> 。%用于存储种群fori=1:nfarm(i,:>=randperm(N> 。%随机生成初始种群endR=farm(1,:> 。%存储最优种群len=zeros(n,1>。%存储路径长度fitness=zeros(n,1> 。%存储归一化适应值counter=0。V7l4jRB8Hswhilecounter<Cfori=1:nlen(i,1>=myLength(D,farm(i,:>>。%计算路径长度endmaxlen=max(len> 。minlen=min(len> 。fitness=fit(len,m,maxlen,minlen> 。%计算归一化适应值rr=find(len==minlen> 。R=farm(rr(1,1>,:> 。%更新最短路径 83lcPA59W9FARM=farm。%优胜劣汰，nn记录了复制的个数nn=0。fori=1:niffitness(i,1>>=alpha*randnn=nn+1。FARM(nn,:>=farm(i,:> 。endendFARM=FARM(1:nn,:>。mZkklkzaaP[aa,bb]=size(FARM>。%交叉和变异whileaa<nifnn<=2nnper=randperm(2> 。elsennper=randperm(nn> 。end15/67个人资料整理 仅限学习使用A=FARM(nnper(1>,:> 。B=FARM(nnper(2>,:> 。[A,B]=intercross(A,B> 。FARM=[FARM。A。B]。[aa,bb]=size(FARM>。endifaa>nFARM=FARM(1:n,:>。%保持种群规模为nendAVktR43bpwfarm=FARM。clearFARMcounter=counter+1endRlength=myLength(D,R> 。function[a,b]=intercross(a,b>L=length(a>。ifL<=10% 确定交叉宽度W=1。elseif((L/10>-floor(L/10>>>=rand&&L>10W=ceil(L/10>。elseW=floor(L/10> 。endp=unidrnd(L-W+1>。%随机选择交叉范围，从p到p+Wfori=1:W%交叉x=find(a==b(1,p+i-1>> 。y=find(b==a(1,p+i-1>> 。[a(1,p+i-1>,b(1,p+i-1>]=exchange(a(1,p+i-1>,b(1,p+i-1>> 。[a(1,x>,b(1,y>]=exchange(a(1,x>,b(1,y>> 。endfunction[x,y]=exchange(x,y>temp=x。x=y。y=temp。ORjBnOwcEd计算路径的子程序functionlen=myLength(D,p>[N,NN]=size(D> 。len=D(p(1,N>,p(1,1>> 。fori=1:(N-1>16/67个人资料整理 仅限学习使用len=len+D(p(1,i>,p(1,i+1>> 。end2MiJTy0dTT计算归一化适应值子程序functionfitness=fit(len,m,maxlen,minlen>fitness=len。fori=1:length(len>fitness(i,1>=(1-((len(i,1>-minlen>/(maxlen-minlen+0.000001>>>.^m 。endgIiSpiue7A一个

C++

的程序：//c++的程序#include<iostream.h>#include<stdlib.h>template<classT>classGraph{public:Graph(intvertices=10>{n=vertices

。e=0

。}~Graph(>{}virtualboolAdd(intu,intv,constT&w>=0virtualboolDelete(intu,intv>=0 。virtualboolExist(intu,intv>const=0 。intVertices(>const{returnn 。}intEdges(>const{returne 。}protected:

。e。}。template<classT>classMGraph:publicGraph<T>{public:MGraph(intVertices=10,TnoEdge=0> 。~MGraph(> 。boolAdd(intu,intv,constT&w>boolDelete(intu,intv> 。boolExist(intu,intv>const 。voidFloyd(T**&d,int**&path>voidprint(intVertices> 。

。。17/67个人资料整理 仅限学习使用private:TNoEdge。T**a。}。template<classT>MGraph<T>::MGraph(intVertices,TnoEdge>{n=Vertices。NoEdge=noEdge。a=newT*[n] 。for(inti=0。i<n。i++>{a[i]=newT[n] 。a[i][i]=0 。for(intj=0 。j<n。j++>if(i!=j>a[i][j]=NoEdge 。}}template<classT>MGraph<T>::~MGraph(>{for(inti=0。i<n。i++>delete[]a[i] 。delete[]a。}template<classT>boolMGraph<T>::Exist(intu,intv>const{if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge>returnfalse 。returntrue。}template<classT>boolMGraph<T>::Add(intu,intv,constT&w>{if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]!=NoEdge>{cerr<<"BadInput!"<<endl 。returnfalse。}a[u][v]=w 。e++。returntrue。}template<classT>boolMGraph<T>:delete(intu,intv>{if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge>{cerr<<"BadInput!"<<endl 。18/67个人资料整理 仅限学习使用returnfalse。}a[u][v]=NoEdge 。e--。returntrue。}template<classT>voidMGraph<T>::Floyd(T**&d,int**&path>{d=newT*[n] 。path=newint*[n] 。for(inti=0。i<n。i++>{d[i]=newT[n] 。path[i]=newint[n] 。for(intj=0 。j<n。j++>{d[i][j]=a[i][j] 。if(i!=j&&a[i][j]<NoEdge>path[i][j]=i 。elsepath[i][j]=-1 。}}for(intk=0。k<n。k++>{for(i=0。i<n。i++>for(intj=0 。j<n。j++>if(d[i][k]+d[k][j]<d[i][j]>{d[i][j]=d[i][k]+d[k][j] 。path[i][j]=path[k][j] 。}}}template<classT>voidMGraph<T>::print(intVertices>{for(inti=0。i<Vertices。i++>for(intj=0 。j<Vertices。j++>{cout<<a[i][j]<<'' 。if(j==Vertices-1>cout<<endl 。}}#definenoEdge10000#include<iostream.h>voidmain(>{cout<<"请输入该图的节点数："<<endl。19/67个人资料整理 仅限学习使用intvertices。cin>>vertices。MGraph<float>b(vertices,noEdge> 。cout<<"请输入u,v,w:"<<endl 。intu,v。floatw。cin>>u>>v>>w 。while(w!=noEdge>{//u=u-1 。b.Add(u-1,v-1,w> 。b.Add(v-1,u-1,w> 。cout<<" 请输入u,v,w:"<<endl 。cin>>u>>v>>w 。}b.print(vertices> 。int**Path 。int**&path=Path 。float**D。float**&d=D 。b.Floyd(d,path>。for(inti=0。i<vertices。i++>{for(intj=0 。j<vertices。j++>{cout<<Path[i][j]<<'' 。if(j==vertices-1>cout<<endl 。}}int*V。V=newint[vertices+1] 。cout<<"请输入任意一个初始 H-圈："<<endl。for(intn=0。n<=vertices。n++>{cin>>V[n] 。}for(n=0。n<55。n++>{for(i=0。i<n-1。i++>{for(intj=0 。j<n-1。j++>{if(i+1>0&&j>i+1&&j<n-1>{if(D[V[i]][V[j]]+D[V[i+1]][V[j+1]]<D[V[i]][V[i+1]]+D[V[j]][V[j+1]]>{intl 。l=V[i+1] 。V[i+1]=V[j] 。V[j]=l。}}}20/67个人资料整理 仅限学习使用}}floattotal=0 。cout<<"最小回路："<<endl。for(i=0。i<=vertices。i++>{cout<<V[i]+1<<'' 。}cout<<endl 。for(i=0。i<vertices。i++>total+=D[V[i]][V[i+1]] 。cout<<"最短路径长度："<<endl。cout<<total 。}uEh0U1Yfmh语言程序#include<stdio.h>#include<stdlib.h>#include<math.h>#include<alloc.h>#include<conio.h>#include<float.h>#include<time.h>#include<graphics.h>#include<bios.h> IAg9qLsgBX#define maxpop100#define maxstring100structpp{unsignedcharchrom[maxstring] 。floatx,fitness 。unsignedintparent1,parent2,xsite 。}。structpp*oldpop,*newpop,*p1 。unsignedintpopsize,lchrom,gem,maxgen,co_min,jrand 。unsignedintnmutation,ncross,jcross,maxpp,minpp,maxxy 。floatpcross,pmutation,sumfitness,avg,max,min,seed,maxold,oldrand[maxstring]。unsignedcharx[maxstring],y[maxstring]

。float*dd,ff,maxdd,refpd,fm[201]

。FILE*fp,*fp1

。floatobjfunc(float>

。voidstatistics(>

。21/67个人资料整理 仅限学习使用intselect(>。intflip(float> 。intcrossover(>。voidgeneration(> 。voidinitialize(>。voidreport(>。floatdecode(>。voidcrtinit(>。voidinversion(>。floatrandom1(> 。voidrandomize1(>。WwghWvVhPEmain(>{unsignedintgen,k,j,tt 。charfname[10]。floatttt。clrscr(>。co_min=0。if((oldpop=(structpp*>farmalloc(maxpop*sizeof(structpp>>>==NULL>{printf("memoryrequstfail!\n"> 。exit(0>。}if((dd=(float*>farmalloc(maxstring*maxstring*sizeof(float>>>==NULL>{printf("memoryrequstfail!\n"> 。exit(0>。}if((newpop=(structpp*>farmalloc(maxpop*sizeof(structpp>>>==NULL>{printf("memoryrequstfail!\n"> 。exit(0>。}if((p1=(structpp*>farmalloc(sizeof(structpp>>>==NULL>{printf("memoryrequstfail!\n"> 。exit(0>。}for(k=0。k<maxpop。k++>oldpop[k].chrom[0]='\0' 。for(k=0。k<maxpop。k++>newpop[k].chrom[0]='\0' 。printf("EnterResultDataFilename:"> 。gets(fname>。if((fp=fopen(fname,"w+">>==NULL>{printf("cannotopenfile\n">

。exit(0>

。}

asfpsfpi4kgen=0。randomize(>。initialize(>。fputs("thisisresultoftheTSPproblem:",fp> 。fprintf(fp,"city:%2dpsize:%3dRef.TSP_path:%f\n",lchrom,popsize,refpd>。fprintf(fp,"Pc:%fPm:%fSeed:%f\n",pcross,pmutation,seed>fprintf(fp,"Xsite:\n"> 。for(k=0。k<lchrom。k++>{if((k%16>==0>fprintf(fp,"\n"> 。

。22/67个人资料整理 仅限学习使用fprintf(fp,"%5d",x[k]> 。}fprintf(fp,"\nYsite:\n"> 。for(k=0。k<lchrom。k++>{if((k%16>==0>fprintf(fp,"\n"> 。fprintf(fp,"%5d",y[k]> 。}fprintf(fp,"\n"> 。ooeyYZTjj1crtinit(>。statistics(oldpop>。report(gen,oldpop> 。getch(>。maxold=min。fm[0]=100.0*oldpop[maxpp].x/ff 。do{gen=gen+1 。generation(> 。statistics(oldpop> 。if(max>maxold>{maxold=max 。co_min=0。}fm[gen%200]=100.0*oldpop[maxpp].x/ff 。report(gen,oldpop> 。gotoxy(30,25> 。ttt=clock(>/18.2 。tt=ttt/60 。printf("RunClock:%2d:%2d:%4.2f",tt/60,tt%60,ttt-tt*60.0> 。printf("Min=%6.4fNm:%d\n",min,co_min> 。}while((gen<100>&&!bioskey(1>> 。printf("\ngen=%d",gen> 。do{gen=gen+1 。generation(> 。statistics(oldpop> 。if(max>maxold>{maxold=max 。co_min=0。}fm[gen%200]=100.0*oldpop[maxpp].x/ff 。report(gen,oldpop> 。if((gen%100>==0>report(gen,oldpop> 。23/67个人资料整理 仅限学习使用gotoxy(30,25>。ttt=clock(>/18.2。tt=ttt/60。printf("RunClock:%2d:%2d:%4.2f",tt/60,tt%60,ttt-tt*60.0>。printf("Min=%6.4fNm:%d\n",min,co_min>。}while((gen<maxgen>&&!bioskey(1>>。BkeGuInkxIgetch(>。for(k=0。k<lchrom。k++>{if((k%16>==0>fprintf(fp,"\n">。fprintf(fp,"%5d",oldpop[maxpp].chrom[k]>。}fprintf(fp,"\n">。PgdO0sRlMofclose(fp>。farfree(dd>。farfree(p1>。farfree(oldpop>。farfree(newpop>。restorecrtmode(>。exit(0>。}3cdXwckm15/*%%%%%%%%%%%%%%%%*/floatobjfunc(floatx1>{floaty。y=100.0*ff/x1 。returny。}h8c52WOngM/*&&&&&&&&&&&&&&&&&&&*/voidstatistics(pop>structpp*pop。{intj。sumfitness=pop[0].fitness 。min=pop[0].fitness 。max=pop[0].fitness 。maxpp=0。minpp=0。for(j=1。j<popsize。j++>{sumfitness=sumfitness+pop[j].fitness 。if(pop[j].fitness>max>{max=pop[j].fitness 。24/67个人资料整理 仅限学习使用maxpp=j。}if(pop[j].fitness<min>{min=pop[j].fitness 。minpp=j。}}v4bdyGiousavg=sumfitness/(float>popsize 。}/*%%%%%%%%%%%%%%%%%%%%*/voidgeneration(>{unsignedintk,j,j1,j2,i1,i2,mate1,mate2 。floatf1,f2。j=0。do{mate1=select(> 。pp:mate2=select(> 。if(mate1==mate2>gotopp 。crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j> 。newpop[j].x=(float>decode(newpop[j].chrom> 。newpop[j].fitness=objfunc(newpop[j].x> 。newpop[j].parent1=mate1 。newpop[j].parent2=mate2 。newpop[j].xsite=jcross 。newpop[j+1].x=(float>decode(newpop[j+1].chrom> 。newpop[j+1].fitness=objfunc(newpop[j+1].x>。newpop[j+1].parent1=mate1。newpop[j+1].parent2=mate2。newpop[j+1].xsite=jcross。if(newpop[j].fitness>min>{for(k=0。k<lchrom。k++>oldpop[minpp].chrom[k]=newpop[j].chrom[k] 。oldpop[minpp].x=newpop[j].x 。oldpop[minpp].fitness=newpop[j].fitness 。co_min++。return。}J0bm4qMpJ9if(newpop[j+1].fitness>min>{for(k=0。k<lchrom。k++>oldpop[minpp].chrom[k]=newpop[j+1].chrom[k] 。oldpop[minpp].x=newpop[j+1].x 。25/67个人资料整理 仅限学习使用oldpop[minpp].fitness=newpop[j+1].fitness 。co_min++。return。}j=j+2 。}while(j<popsize> 。}XVauA9grYP/*%%%%%%%%%%%%%%%%%*/voidinitdata(>{unsignedintch,j。clrscr(>。printf("-----------------------\n">。printf("ASGA\n">。printf("------------------------\n">。/*pause(>。*/clrscr(>。printf("*******SGADATAENTRYANDINITILIZATION*******\n">。printf("\n">。printf("inputpopsize">。scanf("%d",&popsize>。printf("inputchromlength">。scanf("%d",&lchrom>。printf("inputmaxgenerations">。scanf("%d",&maxgen>。printf("inputcrossoverprobability">。scanf("%f",&pcross>。printf("inputmutationprob">。scanf("%f",&pmutation>。randomize1(>。clrscr(>。nmutation=0。ncross=0。}bR9C6TJscw/*%%%%%%%%%%%%%%%%%%%%*/voidinitreport(>{intj,k。printf("popsize=%d\n",popsize>。printf("chromosomelength=%d\n",lchrom>。printf("maxgen=%d\n",maxgen>。printf("pmutation=%f\n",pmutation>。printf("pcross=%f\n",pcross>。printf("initialgenerationstatistics\n">。printf("inipopmaxfitness=%f\n",max>。printf("inipopavrfitness=%f\n",avg>。printf("inipopminfitness=%f\n",min>。printf("inipopsumfit=%f\n",sumfitness>。}pN9LBDdtrd26/67个人资料整理 仅限学习使用voidinitpop(>{unsignedcharj1。unsignedintk5,i1,i2,j,i,k,j2,j3,j4,p5[maxstring] 。floatf1,f2。j=0。for(k=0。k<lchrom。k++>oldpop[j].chrom[k]=k 。for(k=0。k<lchrom。k++>p5[k]=oldpop[j].chrom[k] 。randomize(>。for(。j<popsize。j++>{j2=random(lchrom> 。for(k=0 。k<j2+20。k++>{j3=random(lchrom> 。j4=random(lchrom> 。j1=p5[j3] 。p5[j3]=p5[j4] 。p5[j4]=j1 。}for(k=0 。k<lchrom。k++>oldpop[j].chrom[k]=p5[k] 。}for(k=0。k<lchrom。k++>for(j=0。j<lchrom。j++>dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]> 。for(j=0。j<popsize。j++>{oldpop[j].x=(float>decode(oldpop[j].chrom> 。oldpop[j].fitness=objfunc(oldpop[j].x> 。oldpop[j].parent1=0 。oldpop[j].parent2=0 。oldpop[j].xsite=0 。}}DJ8T7nHuGT/*&&&&&&&&&&&&&&&&&*/voidinitialize(>{intk,j,minx,miny,maxx,maxy 。initdata(>。minx=0。miny=0。maxx=0。maxy=0。for(k=0。k<lchrom。k++>{x[k]=rand(> 。27/67个人资料整理 仅限学习使用if(x[k]>maxx>maxx=x[k] 。if(x[k]<minx>minx=x[k] 。y[k]=rand(> 。if(y[k]>maxy>maxy=y[k] 。if(y[k]<miny>miny=y[k] 。}if((maxx-minx>>(maxy-miny>>{maxxy=maxx-minx 。}else{maxxy=maxy-miny 。}maxdd=0.0。for(k=0。k<lchrom。k++>for(j=0。j<lchrom。j++>{dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]> 。if(maxdd<dd[k*lchrom+j]>maxdd=dd[k*lchrom+j] 。}refpd=dd[lchrom-1] 。for(k=0。k<lchrom。k++>refpd=refpd+dd[k*lchrom+k+2] 。for(j=0。j<lchrom。j++>dd[j*lchrom+j]=4.0*maxdd 。ff=(0.765*maxxy*pow(lchrom,0.5>> 。minpp=0。min=dd[lchrom-1] 。for(j=0。j<lchrom-1。j++>{if(dd[lchrom*j+lchrom-1]<min>{min=dd[lchrom*j+lchrom-1] 。minpp=j。}}initpop(>。statistics(oldpop>。initreport(>。}QF81D7bvUA/*&&&&&&&&&&&&&&&&&&*/voidreport(intl,structpp*pop>{intk,ix,iy,jx,jy 。unsignedinttt。floatttt。cleardevice(>。gotoxy(1,1>。printf("city:%4dpara_size:%4dmaxgen:%4dref_tour:%f\n",lchrom,popsize,maxgen,refpd> 。28/67个人资料整理 仅限学习使用n",ncross,nmutation,l,avg,min> 。printf("Rinpath:%6.4fMinpathlength:%10.4fRef_co_tour:%f\n",pop[maxpp].x/maxxy,pop[maxpp].x,ff> 。printf("Co_minpath:%6.4fMaxfit:%10.8f",100.0*pop[maxpp].x/ff,pop[maxpp].fitness> 。ttt=clock(>/18.2 。tt=ttt/60。printf("Runclock:%2d:%2d:%4d.2f\n",tt/60,tt%60,ttt-tt*60.0> 。setcolor(1%15+1> 。for(k=0。k<lchrom-1。k++>{ix=x[pop[maxpp].chrom[k]] 。iy=y[pop[maxpp].chrom[k]]+110 。jx=x[pop[maxpp].chrom[k+1]] 。jy=y[pop[maxpp].chrom[k+1]]+110 。line(ix,iy,jx,jy> 。putpixel(ix,iy,RED> 。}ix=x[pop[maxpp].chrom[0]] 。iy=y[pop[maxpp].chrom[0]]+110 。jx=x[pop[maxpp].chrom[lchrom-1]] 。jy=y[pop[maxpp].chrom[lchrom-1]]+110 。line(ix,iy,jx,jy> 。putpixel(jx,jy,RED> 。setcolor(11>。outtextxy(ix,iy,"*"> 。setcolor(12>。for(k=0。k<1%200。k++>{ix=k+280 。iy=366-fm[k]/3 。jx=ix+1 。jy=366-fm[k+1]/3 。line(ix,iy,jx,jy> 。putpixel(ix,iy,RED> 。}printf("GEN:%3d",l> 。printf("Minpath:%fMaxfit:%f",pop[maxpp].x,pop[maxpp].fitness> 。printf("Clock:%2d:%2d: