实验五遗传算法-TSP.doc

实验五、用遗传算法解决TSP问题 一、实验目的及要求 1、掌握遗传算法的基本原理。 2、理解TSP问题。 3、掌握遗传算法的编程步骤。 二、实验内容 1. 使用Matlab编程实现遗传算法 2. 调节城市数量，观察对收敛速度的影响（迭代次数） 三、实验原理 设计思路： 初始化城市距离 采用以城市编号（i,j=1代表北京，=2代表上海，=3代表天津，=4代表重庆，=5代表乌鲁木齐）为矩阵行列标的方法，输入任意两个城市之间的距离，用矩阵city表示，矩阵中的元素city(i,j)代表第i个城市与第j个城市间的距离。 初始化种群 通过randperm函数，生成一个一维随机向量（是整数1，2，3，4，5的任意排列），然后将其赋给二维数组group的第一列，作为一个个体。如此循环N次（本例生成了50个个体），生成了第一代种群，种群的每个个体代表一条路径。 计算适应度 采用的适应度函数为个体巡回路径的总长度的函数。具体为 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为种群适应度之和。 复制 采用优秀个体的大比例保护基础上的随机数复制法。具体做法为在生成下一代个体时，先将最大适应度对应的路径个体以较大的比例复制到下一代，然后再用随机数复制法生成下一代的其他个体。其中，有一个问题必须考虑，即若某一次生成的随机数过大，结果能复制一个或极少个样本。为了避免这一情况，采用了限制措施，即压低了随机数的上限。 交叉 采用的方法为按步长的单点交叉，为随机选择一对样本，再随机选择一个交叉点位置，按一定的步长进行交叉点的选择。选择一个步长而不是将其设为1，是因为若某一位置处的 城市代码因为进行了交叉而发生了改变，则其经过该处的两个距离都会改变。这种交叉兼有 遗传和变异两方面的作用，因为若交叉点处的城市编号都相同，则对两个个体而言交叉后样 本无变化，否则样本有变化。 变异 方法为随机两点I，J的交互位置法。对于A= [1 2 3 4 5 6 7 8 9 10]，若I= 3, J=8，则变异后B= [1 2 8 4 5 6 7 3 9 10]虽然是简单的随机两点交互，但实际上已经有40%的距离发生了改变。若用dij表示城市i与j之间的距离，则变异后与变异前样本路径的距离差为B23十B34 + B78十B89一A23十A34 + A78 + A89可见，随机两点交互足以产生新的模式样本。较大地提高变异率就会产生大量的新样本，全局最优样本出现的概率随之提高。为了收敛到最优解，借鉴模拟退火算法的思想，采取了变异率由很大逐渐衰减到较小的数量，这样做也利于找到全局最优解。 将复制，交叉，变异后得到的种群group1重新赋给group,然后重复3，4，5，6步操作。 直至满足循环停止条件，即找到最优路径。 四． 参考代码 程序实现： clc clear all city=[0 1453 157 2087 3768; 1453 0 1326 2523 4077; 157 1326 0 2300 3900; 2087 2523 2300 0 3358; 3768 4077 3900 3358 0] %初始化城市距离 maxdis=4077; %城市间最大距离 N=50; %每一代种群中的个体数 maxlun=100; %迭代次数设为100 for i=1:N ttemp=randperm(5); %初始化种群，即随机产生50种路径，放在5行，N列的矩阵group中 for j=1:5 group(j,i)=ttemp(j); end end for lun=1:maxlun %迭代循环maxlun次 sumadapt=0; %适度值之和 maxadapt(1,lun)=0; %最大适