还剩4页未读,继续阅读
文本内容:
用遗传算法解决TSP问题设计思路
1.初始化城市距离采用以城市编号(ij=1代表北京,=2代表上海,=3代表天津,=4代表重庆,=5代表乌鲁木齐)为矩阵行列标的方法,输入任意两个城市之间的距离,用矩阵city表示,矩阵中的元素cityij代表第i个城市与第j个城市间的距离
2.初始化种群通过randperm函数,生成一个一维随机向量(是整数1,2,3,4,5的任意排列),然后将其赋给二维数组group的第一列,作为一个个体如此循环N次(本例生成了50个个体),生成了第一代种群,种群的每个个体代表一条路径
3.计算适应度采用的适应度函数为个体巡回路径的总长度的函数具体为adapt1i=5*maxdis-dis1在式
(1)中,adapt1i表示第i个个体的适应度函数,maxdis为城市间的最大距离,为4077kmdis为个体巡回路径的总长度,这样定义的适应度,当路经越短时适应度值越大在适应度值的基础上,给出的计算个体期望复制数的表达式为adaptnum1i=N*adapt1i/sumadapt2其中,sumadapt为种群适应度之和
4.复制采用优秀个体的大比例保护基础上的随机数复制法具体做法为在生成下一代个体时,先将最大适应度对应的路径个体以较大的比例复制到下一代,然后再用随机数复制法生成下一代的其他个体其中,有一个问题必须考虑,即若某一次生成的随机数过大,结果能复制一个或极少个样本为了避免这一情况,采用了限制措施,即压低了随机数的上限
5.交叉采用的方法为按步长的单点交叉,为随机选择一对样本,再随机选择一个交叉点位置,按一定的步长进行交叉点的选择选择一个步长而不是将其设为1,是因为若某一位置处的城市代码因为进行了交叉而发生了改变,则其经过该处的两个距离都会改变这种交叉兼有遗传和变异两方面的作用,因为若交叉点处的城市编号都相同,则对两个个体而言交叉后样本无变化,否则样本有变化
6.变异方法为随机两点I,J的交互位置法对于A=
[12345678910],若I=3J=8,则变异后B=
[12845673910]虽然是简单的随机两点交互,但实际上已经有40%的距离发生了改变若用dij表示城市i与j之间的距离,则变异后与变异前样本路径的距离差为B23十B34+B78十B89一A23十A34+A78+A89可见,随机两点交互足以产生新的模式样本较大地提高变异率就会产生大量的新样本,全局最优样本出现的概率随之提高为了收敛到最优解,借鉴模拟退火算法的思想,采取了变异率由很大逐渐衰减到较小的数量,这样做也利于找到全局最优解
7.将复制,交叉,变异后得到的种群group1重新赋给group然后重复3,4,5,6步操作直至满足循环停止条件,即找到最优路径程序实现clcclearallcity=[0145315720873768;14530132625234077;1571326023003900;20872523230003358;37684077390033580]%初始化城市距离maxdis=4077;%城市间最大距离N=50;%每一代种群中的个体数maxlun=100;%迭代次数设为100fori=1:Nttemp=randperm5;%初始化种群,即随机产生50种路径,放在5行,N列的矩阵group中forj=1:5groupji=ttempj;endendforlun=1:maxlun%迭代循环maxlun次sumadapt=0;%适度值之和maxadapt1lun=0;%最大适度值初值minadapt1lun=100;%最小适度值初值viprate=
0.1;%最优个体复制率copyrate=
0.02;%复制率参数maxadaptloc=0;%最大适应值对应的个体号码初值mindisiii1lun=100000;%每一代的最忧路径对应的旅行距离总和初值fori=1:Ndis1i=0;forj=1:4dis1i=dis1i+citygroupjigroupj+1i;enddis1i=dis1i+citygroup1igroup5i;%求一次旅行个体的总长度adapt1i=5*maxdis-dis1i;%第i个个体的适应度函数sumadapt=sumadapt+adapt1i;%适应度函数总和ifdis1imindisiii1lunmindisiii1lun=dis1i;endendfori=1:Nadaptnum1i=N*adapt1i/sumadapt;%第i个个体的期望复制数ifadaptnum1imaxadapt1lunmaxadapt1lun=adaptnum1i;%求本代最大适应值maxadaptloc=i;%求最大适应值对应的个体号码endifadaptnum1iminadapt1lunminadapt1lun=adaptnum1i;%求本代最小适应值endend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%.%复制操作tcopy50=0;%复制个数初值num=maxadapt1lun-copyrate-minadapt1lun*rand1+minadapt1lun;%生成随机数vipnum=viprate*N;%N=50,确定最优个体复制个数fortcopy50=1:vipnum%先复制vipnum个最优个体至中间矩阵group1fori=1:5group1itcopy50=groupimaxadaptloc;endendwhiletcopy50N%再复制其余N-vipnum个fori=1:Nifadaptnum1inumtcopy50Ntcopy50=tcopy50+1;fork=1:5%由于针对5个城市,故每个个体有五个元素group1ktcopy50=groupki;endendendend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%交叉操作pc=
0.5-
0.5-
0.1*lun-1/maxlun-1;%交叉率pair=pc*N/2;%最多交叉对数step=2;%交叉步长取为2pairno=0;%当前交叉过的个体数whilepairnopaira=floorN*rand1+1;%随机产生两个交叉个体,floor为向负无穷取整函数b=floorN*rand1+1;marri1a=2;%参与交叉的个体标记初值marri1b=3;ifmarri1a~=1marri1b~=1a~=bmarri1a~=1;marri1b~=1;%参与交叉的个体标记为1pairno=pairno+1;location=floor5*rand1+1;%用随机数确定个体中单交叉点位置l1=0;l2=0;fori=location:step:5%以下按步长step进行交叉forj=1:5%用for确定交叉位置ifgroup1ia==group1jbl1=j;endendforj=1:5ifgroup1ib==group1jal2=j;endendtemp=group1ia;group1ia=group1l2a;group1l2a=temp;temp=group1ib;group1ib=group1l1b;group1l1b=temp;endendend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%变异操作pb=
0.02;%个体变异率bnum=pb*N;%变异个体数fori=1:bnum%逐个取个体,随机选择位置进行变异a1=floor5*rand1+1;a2=floor5*rand1+1;b=floorN*rand1+1;temp=group1a1b;group1a1b=group1a2b;group1a2b=temp;end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%fori=1:Nforj=1:5groupji=group1ji;%构造经过复制,交叉,变异后的矩阵,group准备下次循环endendendgroupdisp最优路径为fori=1:5switchgroupi1case1disp北京case2disp上海case3disp天津case4disp重庆otherwisedisp乌鲁木齐%用文字列出最优路径endenddisp更多精彩,即将出现,请稍等......figure1;lun=1:1:50;mindis=mindisiii1lun;plotlunmindis;gridon;figure2;worldmapchinapatch;fori=1:5switchgroupi1case1x1i=
0.12;y1i=
0.72;case2x1i=
0.23;y1i=
0.54;%在地图中定出五个城市的坐标case3x1i=
0.15;y1i=
0.7;case4x1i=0;y1i=
0.53;otherwisex1i=-
0.2;y1i=
0.73;endendfori=1:4u1i+1=x1i;v1i+1=y1i;endu11=x15;v11=y15;fori=1:5u1i=u1i-x1i;v1i=v1i-y1i;endquiverxyuv0;%画矢量图x=[
0.
120.
230.150-
0.2];y=[
0.
720.
540.
70.
530.73];s=str2mat北京上海天津重庆乌鲁木齐;textxys;%在地图中标出各城市的位置disp图2中闭合曲线即为最优路径disp图1绘出了每一代种群最短距离的收敛过程。