题目：用遗传算法求解中国34个省会TSP问题源代码分享在本人博客：Bbingo.org2012-1-17智能控制技术及其应用大作业专业:控制工程学号：XXXXXX姓名：XXX---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---用遗传算法求解中国34个省会TSP问题一、TSP问题的描述旅行商问题（TSP）可以具体描述为：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。现给出中国34个省会数据，要求基于此数据使用遗传算法解决该TSP问题。city=图1中国34省会位置1.西藏2.云南3.四川4.青海5.宁夏6.甘肃7.内蒙古8.黑龙江9.吉林10.辽宁11.北京12天津13.河北14.山东15.河南16.山西17.陕西18.安徽19.江苏20.上海21.浙江22.江西23.湖北24.湖南25,贵州26.广西27.广东28.福建29.海南30.澳门31.香港32.台湾33.重庆34.新疆像素坐标如下：Columns1through111001872011872212022583523463362902112652141581421651216685106127Columns12through22297278296274265239302316334325293135147158177148182203199206215233Columns23through33280271221233275322250277286342220216238253287285254315293290263226Column34---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---10477二、遗传算法的介绍2.1遗传算法遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。2.2遗传算法的过程遗传算法的基本过程是：1.初始化群体。2.计算群体上每个个体的适应度值3.由个体适应度值所决定的某个规则选择将进入下一代个体。4.按概率Pc进行交叉操作。5.按概率Pm进行变异操作。6.没有满足某种停止条件，则转第2步，否则进入第7步。7.输出种群中适应度值最优的染色体作为问题的满意解或最优界。停止条件有两种：一是完成了预先给定的进化代数则停止；二是种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。遗传算法过程图如图2：---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---图2遗传算法过程框图三、遗传算法解决TSP问题的Matlab程序实现3.1程序初始化程序首先读入34个省会城市坐标，计算任意两个城市的距离；设置遗传算法控制参数。clearall;clc;clf;load('testdata.mat');nlen=length(x1);xy=[x1;y1]';n=500;%种群数目C=5000;%进化迭代次数m=2;%适应度归一化淘汰加速指数，取值不宜太大alpha=0.8;%淘汰保护指数，范围0~1，为1时关闭保护a=meshgrid(1:nlen);%生成nxn矩阵dmat=reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),nlen,nlen);%计算城市距离矩阵遗传算法对求解问题本身是一无所知的，这里采用随机生成初始化种群，如下：---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---[N,NN]=size(dmat);farm=zeros(n,N);%用于存储种群fori=1:nfarm(i,:)=randperm(N);%随机生成初始化种群end3.2计算适应度本程序目标函数为经过34省会的总距离，适应度与目标函数的正相关，取值范围0~1，适应度计算公式为：fit(1lenminlen)mmaxlenminlen0.0001其中，len为某组解的总距离，minlen为该次迭代中最短距离，maxlen为该次迭代中最长距离，m为适应度归一化淘汰加速指数，源程序如下：functionfitness=fit(len,m,maxlen,minlen)fitness=len;fori=1:length(len)fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.0001))).^m;end3.3选择操作当个体适应度小于某一随机数值时，遭到淘汰，保留优秀个体，使它们有机会作为父代产生后代个...