2012公益讲座启发式算法简介及其在数学模型中的应用

1定启发式数学建模中的2算例分3算例分 作中 力学 1

定启发式数学建模中的2算例分3算例分 作中 力学 启发式算法的定

化算法.启发式算法的定义： 规则中启发出来的方法称之为启发式算法.现在的启发式算问题每一个实例的一个可行解,该可行解与最优解的偏离程启发式算法是一种技术,该技术使得能在可接受的计算费用内去寻找尽可能好的解,但不一定能保证所得解的可行性和最优性,甚至在多数情况下,无法描述所得解与最优解的近中 力学 几种启发式算

搜索(TabuSearch):它是对局部领域搜索的一种扩展是一种全局逐步寻优算法,是对人类智力过程的一种模拟 (GeneticAlgorithms):它是一种通过模拟自然进化4神经网络(NeuralNetworks):为特征,进行分布式并行信息处理的算法数学模型5蚁群算法(AntAlgorith):它是一种模仿蚂蚁在寻找食物过程中 力学 经典问题:旅行商问

旅行商问题(TSP):假设有一个旅行商人要拜访n个城市,dij表示两城市间距离.xij为0,1变量,表示拜访路径是否包函路径dij. 最后要回到原来出发的城市,即dd13,x13=

xij=d34,x34=

i j路程为所有路径之中的最小值,即X 中 力学 经典问题:旅行商问

TSP问题枚举的算法复以第一个城市为始终点,计算任意一条路径[1i2···in1]的长度的基本运算为两两城市间距离求和,基本操作次数为n.路径的条数为(n1求和运算的总次数为(n1n=n!.比较所有路径以得到最短路径,需要比较的次数为(n1).TSP问题枚举的计算开如果计算机每秒能完成24个城市的枚举,城市数计算时∞中 力学 启发式算法与特

近十二年MCM比赛中用到启发式算法的特等 数2003MCM- 刀治疗方退火1＋遗传2006MCM-灌溉洒水器的安置和退火1＋遗传2006MCM-通过机场的轮退火2007MCM-飞机座位方遗传2008MCM-建立数独拼图游退火2009MCM-交通环岛的设遗传2011MCM-滑雪赛道优化设遗传中 力学 1

定启发式数学建模中的2算例分3算例分 作中 力学 物理

物理退火过 中 力学 物理退火过程的数学描

,于n种不同的状态中,每种状态数为M1···Mn.Mi(τ+1

空间构象满 概率分 Pi= M→∞

dτPi(τ)= πjiPi(τ)−πijPj(τ其中πij为j状态向i状态的转移率中 力学 物理退火过程的数学描

,于n种不同的状态中,每种状态数为M1···Mn.Mi(τ+1

空间构象满 概率分 Pi= M→∞

dτPi(τ)= πjiPi(τ)−πijPj(τ其中πij为j状态向i状态的转移率中 力学 物理退火过程的数学描细致平衡条πjiPi(τ)=πijPj(τ)=⇒

=Pj(τ)=e−(Vj−Vi其中转移尝试运动

πj←i=α(j←i)·acc(j←iα(j←i) n− acc(j←i)acc(i←

=e−(Vj−Vi中 力学 物理退火过程的数学描细致平衡条πjiPi(τ)=πijPj(τ)=⇒

=Pj(τ)=e−(Vj−Vi其中转移尝试运动

πj←i=α(j←i)·acc(j←iα(j←i) n− acc(j←i)acc(i←

=e−(Vj−Vi中 力学 物理退火过程的数学描细致平衡条πjiPi(τ)=πijPj(τ)=⇒

=Pj(τ)=e−(Vj−Vi其中转移尝试运动

πj←i=α(j←i)·acc(j←iα(j←i) n− acc(j←i)acc(i←

=e−(Vj−Vi中 力学 Metropolis

接受概率的设acc(j←i)=

验acc(j←i) 1

ifVj<ifVj≥Vj—acc(j←i)acc(i←

−(V−V)/KT== =

ifVj<Vj =e— ifVj≥中 力学 Metropolis准则在物理中的应用:Ising模模型是最早以自旋模型研究磁性物质相变问题的模型.二维的模型是统计物理中最简单的格点系统之一,考虑一个二维方点阵,每个格点为一个自旋,可能的状态si1+1}.单个自旋的能量和系统总能量分jEi=−JP{s}sisj,H=−JPhi,jisisjj,,U=hHiT,Cv=∂U= TM=

isiiT,χ=

=T=T其中var(xhx2iThxi2T如何找到某个给定温度下的平衡状态中 力学 Metropolis准则在物理中的应用:Ising模模型的计算机模拟步p

1随机的选择一个点(i2计算改变(ij)自旋引起的能3以一定的概率p接受(ij)自p=min(1,e−∆Eij/kT4重复以上1,2,3,三个步骤中 力学 Metropolis准则在物理中的应用:Ising模模型的计算机模拟结果T0EnergyEnergyperT=

中 力学 Metropolis准则在物理中的应用:Ising模模型的计算机模拟结果T0EnergyEnergyperT=

中 力学 Metropolis准则在物理中的应用:Ising模模型的计算机模拟结果T=0EnergyEnergyperT=

中 力学

与Metropolis准EA state/Paccept(Ei+1≤Ei)=1,Paccept(Ei+1>Ei)=e−(Ei+1−Ei中 力学

与物理退火过程的相似与物理退火过程的对 模拟退物理退解粒子状目标函能设定初加温过扰热涨Metropolis采样过分控制参数的下冷中 力学 基本思伪代1:constructinitialsolutionx0,andxcurrent=2:setinitialtemperatureT=T03:whilecontinuingcriteriondo fori=1toTLdo if∆C≤0orrandom(0,1)<exp(−∆C) xcurrent=x0{acceptnew 12:end中 力学 设计要初始解的生通常是以一个随机解作为初始解 理论上能够生成.初始解不宜太好”,否则很难从这个解的邻域跳出邻解生成函 邻域应尽可能的小:能够在少量循环步中允分探测.但每次中 力学 设计要初始温度如何确定初始温度应该设置的尽可能的高,以确保最终解不受初始均匀抽样一组状态，以各状态目标值的方差为初温,确定出初始温度T0,以使初始接受概率P=e−|∆C|max/T足够大.|∆C|max可由随机产生一组状态的最大目标值差来替代.,逐渐增加温度,直到所有的尝试尝试运动都被接受,将此时由经验给出,或通过尝试找到较好的初始温度中 力学 设计要等温步数如何确定 下产生候选解的数目.通常取决于解空间和邻域的大小等温过程是为了让系统达到平衡,因此可通过检验目标函数有时为了考虑方便,也可直接按一定的步数抽样中 力学 设计要如何降温经 的降温方 T(t)=log(1+快 的降温方T(t)=1+常用 T(t+∆t)=αT中 力学 设计要花费函数应该能被快速的计算,花费函数的计算是程序的可能瓶颈.花费函数COST一般由目标函数来构造.目标函数或目标函数的倒数相反数经常直接作为花费函数.终止条理论上温度要降为0才终止退火算法.但实际上温度较低时,,算法搜索到的最优值连续若干步保持不变中 力学 TSP问题的模拟退火

,要求从 游遍34个城市,最后回到 .用 如何设置初始解如何产生邻解如何定义COST函数Pi=1

T0=1000,Tτ+dτ=中 力学 主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;主程 代routes=initial_routes temperature=initial_temperature;T tions=1; previous_distance=total_distanceroutes);whiletemperature>temperature_thresholdtemp_routes =reorder_routesroutesreverse’); 邻解current_distance=total_distancetemp_routesdiff=current_distance-previous_distanceif(diff<0)||(rand<exp(-diff/(temperature))routes=temp_routes; previous_distance=current_distanceT tions=T tions+1;18

ifT tions>=temperature=cooling_rate*temperature T tions=0;距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)距离矩阵函数distancefunctiondis=distance_matrix(citynumberofcities=length(city)R=6378137 地球半径,fori=1:numberofcities;forj=i+1:numberofcitiesdis(i,j)=distance(city(i).lat,city(i).long,...city(j).lat city(j).long R); dis(j,i)=dis(i,j) end; 9. functiond=total_distance(dis,routes10d=0;fork=1:length(routes)-i=routes(k);j=routes(k+1)d=d+dis(i,j)TSP问题的模拟退火产生邻解的函数reorderfunctionroutes=reorder_routes(routes,method)numbercities=length(routes)-2;city1=ceil(numbercities*rand)+1;04city2=ceil(numbercities*rand)+1;05switchmethod

[1,2,...,n,2<=city1,city2<=n12

case’reverse’ [123456]->[154326]cmin=min(city1,city2);cmax=max(city1,city2)routes(cmin:cmax)=routes(cmin:-1:cmax);case [123456]->[15342routes([city1,city2])=routes([city2,city1])中 力学 TSP问题的模拟退火产生邻解的函数reorderfunctionroutes=reorder_routes(routes,method)numbercities=length(routes)-2;city1=ceil(numbercities*rand)+1;04city2=ceil(numbercities*rand)+1;05switchmethod

[1,2,...,n,2<=city1,city2<=n12

case’reverse’ [123456]->[154326]cmin=min(city1,city2);cmax=max(city1,city2)routes(cmin:cmax)=routes(cmin:-1:cmax);case [123456]->[15342routes([city1,city2])=routes([city2,city1])中 力学 TSP问题的模拟退火产生邻解的函数reorderfunctionroutes=reorder_routes(routes,method)numbercities=length(routes)-2;city1=ceil(numbercities*rand)+1;04city2=ceil(numbercities*rand)+1;05switchmethod

[1,2,...,n,2<=city1,city2<=n12

case’reverse’ [123456]->[154326]cmin=min(city1,city2);cmax=max(city1,city2)routes(cmin:cmax)=routes(cmin:-1:cmax);case [123456]->[15342routes([city1,city2])=routes([city2,city1])中 力学 TSP问题的模拟退火产生邻解的函数reorderfunctionroutes=reorder_routes(routes,method)numbercities=length(routes)-2;city1=ceil(numbercities*rand)+1;04city2=ceil(numbercities*rand)+1;05switchmethod

[1,2,...,n,2<=city1,city2<=n12

case’reverse’ [123456]->[154326]cmin=min(city1,city2);cmax=max(city1,city2)routes(cmin:cmax)=routes(cmin:-1:cmax);case [123456]->[15342routes([city1,city2])=routes([city2,city1])中 力学 TSP问题的模拟退火产生邻解的函数reorderfunctionroutes=reorder_routes(routes,method)numbercities=length(routes)-2;city1=ceil(numbercities*rand)+1;04city2=ceil(numbercities*rand)+1;05switchmethod

[1,2,...,n,2<=city1,city2<=n12

case’reverse’ [123456]->[154326]cmin=min(city1,city2);cmax=max(city1,city2)routes(cmin:cmax)=routes(cmin:-1:cmax);case [123456]->[15342routes([city1,city2])=routes([city2,city1])中 力学 TSP问题的模拟退火产生邻解的函数reorderfunctionroutes=reorder_routes(routes,method)numbercities=length(routes)-2;city1=ceil(numbercities*rand)+1;04city2=ceil(numbercities*rand)+1;05switchmethod

[1,2,...,n,2<=city1,city2<=n12

case’reverse’ [123456]->[154326]cmin=min(city1,city2);cmax=max(city1,city2)routes(cmin:cmax)=routes(cmin:-1:cmax);case [123456]->[15342routes([city1,city2])=routes([city2,city1])中 力学 TSP问题的模拟退火产生邻解的函数reorderfunctionroutes=reorder_routes(routes,method)numbercities=length(routes)-2;city1=ceil(numbercities*rand)+1;04city2=ceil(numbercities*rand)+1;05switchmethod

[1,2,...,n,2<=city1,city2<=n12

case’reverse’ [123456]->[154326]cmin=min(city1,city2);cmax=max(city1,city2)routes(cmin:cmax)=routes(cmin:-1:cmax);case [123456]->[15342routes([city1,city2])=routes([city2,city1])中 力学 TSP问题的模拟退火

中 力学 TSP问题的模拟退火

TotalDistance= TotalDistance=TotalDistance= TotalDistance=中 力学 1

定启发式数学建模中的2算例分3算例分 作中 力学 的

生物中的遗传与进化理和遗传理 和进化中 力学 基本概

种 112345224389.n7112345224389.n78360由一组 构成,问题种群 中 力学 基本

伪代1:setinitialgenerationk= 11:end 中 力学 编

中,首要问题就是如何对解进行编码(解的形式).编码影响到交叉,变异等运算,很大程度上决定了遗传进化的效率.码0123456码0123456789编码:与二进制编码类似,连续两个整数所对应编码仅之差.实数编码:每个值用某一符号编码 编码串中而只有代码含义的符号集中 力学 适应度函

适应度函数也称评价函数,是根据目标函数确定的用于区分群体中好坏的标准.适应度函数值的大小是对的优胜劣汰的通常适应度函数可以由目标函数直接或间接改造得到比如,目标函数,或目标函数的倒数相反数经常被直接用作适应一般情况下适应度是非负的,并且总是希望适应度越大越适应度函数不应过于复杂,越简单越好,以便于计算机的快中 力学 选

进行优胜劣汰:从父代群体中选取一些 ,遗传到下一代群体.赌 又称比例选择算子 i被选中p=f/P j两两竞争:从父代中随机地选取两个,比较适应值,保存优秀,淘汰较差的.排序选择:根据各的适应度大小进行排序,然中 力学 交交叉运算是指对两个相互配对

依据交叉概率按某式相互交换其部 00011010111100000011010111100000101000110010111000010110001101011110000010100000000111101101101 两点交中 力学 变变异操作对群体中

的某

座上

值作变动,模 中 会以一定的概率出错11111010000011101000001111100010001100100100单点变 换位变中 力学 TSP问题 求

,要求从 游遍34个城市,最后回到 .用 如何构造适应度函数fP

i

i 如何设计选择运算中 力学 TSP问题 求交叉运算的设 12345678945376894534567924236792部分映射

12345678945367894537659318456792顺序杂中 力学 TSP问题 求变异运算的设987654321987654321123756489中 力学 TSP问题 求变异运算的设123123456789123756489123765489 中 力学 TSP问题 求变异运算的设12312345678912375648912123765489894567123中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求主程 代01popSize=initial_popSize;02max_generation＝10000;03fori=1:popSize

pop(i,:)=randperm(numberofcities);forgeneration=1max_generation fitness=1total_distancepopdis);计算距离适应度pop=selectpopfitness

pop=crossover(pop);pop=mutate(pop);

popDist=total_distancepopdis);计算距离适应度minDist,index]=minpopDist); optRoute=popindex 中 力学 TSP问题 求选择操作函数 functionpopselect=select(pop,fitness,popSize=size(pop,1)p=fitness/sum(fitness)i=interp1([0cump],1:(popSize+1),rand(1,n),’linear’);i=floor(i)popselect=pop(i)中 力学 TSP问题 求选择操作函数 functionpopselect=select(pop,fitness,popSize=size(pop,1)p=fitness/sum(fitness)i=interp1([0cump],1:(popSize+1),rand(1,n),’linear’);i=floor(i)popselect=pop(i)中 力学 TSP问题 求选择操作函数 functionpopselect=select(pop,fitness,popSize=size(pop,1)p=fitness/sum(fitness)i=interp1([0cump],1:(popSize+1),rand(1,n),’linear’);i=floor(i)popselect=pop(i)中 力学 TSP问题 求选择操作函数 functionpopselect=select(pop,fitness,popSize=size(pop,1)p=fitness/sum(fitness)i=interp1([0cump],1:(popSize+1),rand(1,n),’linear’);i=floor(i)popselect=pop(i)中 力学 TSP问题 求选择操作函数 functionpopselect=select(pop,fitness,popSize=size(pop,1)p=fitness/sum(fitness)i=interp1([0cump],1:(popSize+1),rand(1,n),’linear’);i=floor(i)popselect=pop(i)中 力学 TSP问题 求选择操作函数 functionpopselect=select(pop,fitness,popSize=size(pop,1)p=fitness/sum(fitness)i=interp1([0cump],1:(popSize+1),rand(1,n),’linear’);i=floor(i)popselect=pop(i)中 力学 TSP问题 求选择操作函数 functionpopselect=select(pop,fitness,popSize=size(pop,1)p=fitness/sum(fitness)i=interp1([0cump],1:(popSize+1),rand(1,n),’linear’);i=floor(i)popselect=pop(i)中 力学 TSP问题 求选择操作函数 functionpopselect=select(pop,fitness,popSize=size(pop,1)p=fitness/sum(fitness)i=interp1([0cump],1:(popSize+1),rand(1,n),’linear’);i=floor(i)popselect=pop(i)中 力学 交叉操作函数functionchildren=crossover(parents[popSize,numberofcities]=size(parents)childre parents04fori=1:2:popSize

16

child1=children(i+0,:);child2=children(i+1,:)InsertPoints=ceilnumberofcities*rand12forj=min(InsertPoints):max(InsertPoints)ifchild1j~child2j child1(child1==child2(j))=child1(j)child1(j)=child2(j)child2(child2==child1(j))=child2(j);child2(j)=child1(j);children(i+0,:)=child1;children(i+1,:)=child2交叉操作函数functionchildren=crossover(parents[popSize,numberofcities]=size(parents)childre parents04fori=1:2:popSize

16

child1=children(i+0,:);child2=children(i+1,:)InsertPoints=ceilnumberofcities*rand12forj=min(InsertPoints):max(InsertPoints)ifchild1j~child2j child1(child1==child2(j))=child1(j)child1(j)=child2(j)child2(child2==child1(j))=child2(j);child2(j)=child1(j);children(i+0,:)=child1;children(i+1,:)=child2交叉操作函数functionchildren=crossover(parents[popSize,numberofcities]=size(parents)childre parents04fori=1:2:popSize

16

child1=children(i+0,:);child2=children(i+1,:)InsertPoints=ceilnumberofcities*rand12forj=min(InsertPoints):max(InsertPoints)ifchild1j~child2j child1(child1==child2(j))=child1(j)child1(j)=child2(j)child2(child2==child1(j))=child2(j);child2(j)=child1(j);children(i+0,:)=child1;children(i+1,:)=child2交叉操作函数functionchildren=crossover(parents[popSize,numberofcities]=size(parents)childre parents04fori=1:2:popSize

16

child1=children(i+0,:);child2=children(i+1,:)InsertPoints=ceilnumberofcities*rand12forj=min(InsertPoints):max(InsertPoints)ifchild1j~child2j child1(child1==child2(j))=child1(j)child1(j)=child2(j)child2(child2==child1(j))=child2(j);child2(j)=child1(j);children(i+0,:)=child1;children(i+1,:)=child2交叉操作函数functionchildren=crossover(parents[popSize,numberofcities]=size(parents)childre parents04fori=1:2:popSize

16

child1=children(i+0,:);child2=children(i+1,:)InsertPoints=ceilnumberofcities*rand12forj=min(InsertPoints):max(InsertPoints)ifchild1j~child2j child1(child1==child2(j))=child1(j)child1(j)=child2(j)child2(child2==child1(j))=child2(j);child2(j)=child1(j);children(i+0,:)=child1;children(i+1,:)=child2交叉操作函数functionchildren=crossover(parents[popSize,numberofcities]=size(parents)childre p