用遗传算法解决tsp问题

《用遗传算法解决tsp问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、用遗传算法解决TSP问题设计思路：1.初始化城市距离采用以城市编号（i,j=1代表北京，=2代表上海，=3代表天津，=4代表重庆，=5代表乌鲁木齐）为矩阵行列标的方法，输入任意两个城市之间的距离，用矩阵city表示，矩阵中的元素city(i,j)代表第i个城市与第j个城市间的距离。2.初始化种群通过randperm函数，生成一个一维随机向量（是整数1，2，3，4，5的任意排列），然后将其赋给二维数组group的第一列，作为一个个体。如此循环N次（本例生成了50个个体），生成了第一代种群，种群的每个个体代表一条路

2、径。3.计算适应度采用的适应度函数为个体巡回路径的总长度的函数。具体为adapt(1,i)=(5*maxdis-dis)(1)在式（1）中，adapt(1,i)表示第i个个体的适应度函数，maxdis为城市间的最大距离，为4077km,dis为个体巡回路径的总长度，这样定义的适应度，当路经越短时适应度值越大。在适应度值的基础上，给出的计算个体期望复制数的表达式为adaptnum(1,i)=(N*adapt(1,i)/sumadapt)(2)其中，sumadapt为种群适应度之和。4.复制采用优秀个体的大比例保护

3、基础上的随机数复制法。具体做法为在生成下一代个体时，先将最大适应度对应的路径个体以较大的比例复制到下一代，然后再用随机数复制法生成下一代的其他个体。其中，有一个问题必须考虑，即若某一次生成的随机数过大，结果能复制一个或极少个样本。为了避免这一情况，采用了限制措施，即压低了随机数的上限。5.交叉采用的方法为按步长的单点交叉，为随机选择一对样本，再随机选择一个交叉点位置，按一定的步长进行交叉点的选择。选择一个步长而不是将其设为1，是因为若某一位置处的城市代码因为进行了交叉而发生了改变，则其经过该处的两个距离都会改变

4、。这种交叉兼有遗传和变异两方面的作用，因为若交叉点处的城市编号都相同，则对两个个体而言交叉后样本无变化，否则样本有变化。6.变异方法为随机两点I，J的交互位置法。对于A=[12345678910]，若I=3,J=8，则变异后B=[12845673910]虽然是简单的随机两点交互，但实际上已经有40%的距离发生了改变。若用dij表示城市i与j之间的距离，则变异后与变异前样本路径的距离差为B23十B34+B78十B89一A23十A34+A78+A89可见，随机两点交互足以产生新的模式样本。较大地提高变异率就会产生大

5、量的新样本，全局最优样本出现的概率随之提高。为了收敛到最优解，借鉴模拟退火算法的思想，采取了变异率由很大逐渐衰减到较小的数量，这样做也利于找到全局最优解。7.将复制，交叉，变异后得到的种群group1重新赋给group,然后重复3，4，5，6步操作。直至满足循环停止条件，即找到最优路径。程序实现：clcclearallcity=[0145315720873768;14530132625234077;1571326023003900;20872523230003358;37684077390033580]%初始化

6、城市距离maxdis=4077;%城市间最大距离N=50;%每一代种群中的个体数maxlun=100;%迭代次数设为100fori=1:Nttemp=randperm(5);%初始化种群，即随机产生50种路径，放在5行，N列的矩阵group中forj=1:5group(j,i)=ttemp(j);endendforlun=1:maxlun%迭代循环maxlun次sumadapt=0;%适度值之和maxadapt(1,lun)=0;%最大适度值初值minadapt(1,lun)=100;%最小适度值初值vipra

7、te=0.1;%最优个体复制率copyrate=0.02;%复制率参数maxadaptloc=0;%最大适应值对应的个体号码初值mindisiii(1,lun)=100000;%每一代的最忧路径对应的旅行距离总和初值fori=1:Ndis(1,i)=0;forj=1:4dis(1,i)=dis(1,i)+city(group(j,i),group(j+1,i));enddis(1,i)=dis(1,i)+city(group(1,i),group(5,i));%求一次旅行个体的总长度adapt(1,i)=5*m

8、axdis-dis(1,i);%第i个个体的适应度函数sumadapt=sumadapt+adapt(1,i);%适应度函数总和ifdis(1,i)