《TSP遗传算法.doc》由会员分享，可在线阅读，更多相关《TSP遗传算法.doc（6页珍藏版）》请在课桌文档上搜索。
1、word实验二基于遗传算法的求解一、实验目的掌握遗传算法求解TSP问题的实现过程。二、实验内容用遗传算法求解TSP。由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间所有合法的城市序列中搜索最优解。这正适合用遗传算法求解。三、实验步骤1编码路径表示是表示旅程对应的基因编码的最自然、最简单的表示方法。例如，旅程(517894623)可以直接表示为(517894623)，基于路径表示的编码方法，要求个个体(即一条旅程)的染色体编码中不允许有重复的基因码，也就是说要满足任一个城市必须而且只能访问一次的约束。2定义适应度函数我们将一个合法的城市
2、序列s=c1, c2, , 作为一个个体。这个序列中相邻两城市之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是：例如，对于9个城市的TSP，我们用符号1、2、3、4、5、6、7、8、9代表相应的城市，用这9个符号的序列表示可能解即染色体。然后进展遗传操作用局部匹配交叉PMX方法：匹配操作要求随机选取两个交叉点，确定一个匹配段，根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体. 例如，对下面两个父个体的表示,随机选择两个交义点 P1: 1 2 3 4 5 6 7 8 9 o1:4 2 3 1 8 7 6 5 9 P2: 4 5 2 1 8 7 6 9 3 02
3、:1 8 2 4 5 6 7 9 3交叉方法:随机选取染色体上两个元，然后交换它们的位置例如:4 5 2 1 8 7 6 9 3交换后：4 5 6 1 8 7 2 9 3求解的Tsp问题的城市坐标如下：四、程序实现%基于遗传算法的TSP问题求解%D是距离矩阵，n为种群个数,建议取为城市个数的12倍，%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和消耗的时间而定%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大%R为最短路径,Rlength为路径长度close all;clc;clear;%城市坐标city=38.24 20.42; 39.57 26.15;
4、 40.56 25.32; 36.26 23.12; 33.48 10.54; 37.56 12.19; 38.42 13.11; 37.52 20.44; 41.23 9.10; 41.17 13.05; 36.08 -5.21; 38.47 15.13; 38.15 15.35; 37.51 15.17; 35.49 14.32; 39.36 19.56; 38.09 24.36; 36.09 23.00; 40.44 13.57; 40.33 14.15; 40.37 14.23; 37.57 22.56; D=dist(city,city); %城市间距离矩阵n=100;C=100;m
5、=2;alpha=0.9;N,NN=size(D);farm=zeros(n,N); %用于存储种群for i=1:n farm(i,:)=randperm(N);%随机生成初始种群endR=farm(1,:);%存储最优种群len=zeros(n,1);%存储路径长度fitness=zeros(n,1);%存储归一化适应值counter=0; %记录迭代次数while counter=alpha*rand nn=nn+1; FARM(nn,:)=farm(i,:); end end aa,bb=size(FARM);%交叉和变异 while aan if nnn FARM=FARM(1:n,
6、:);%保持种群规模为n end farm=FARM; clear FARM counter=counter+1;endRlength=len(16) % 最优路径farm(16,:) % 城市访问次序newcood=city(:,farm(16,:); newcood=newcood newcood(:,1); %路径是封闭连续的分段曲线plot(newcood(1,:),newcood(2,:),o-);title(最优路径图)%计算归一化适应值子程序function fitness=fit(len,m,maxlen,minlen)fitness=len;for i=1:length(le
7、n) fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.000001).m;end% 计算路径的子程序function len=myLength(D,p)N,NN=size(D);len=D(p(1,N),p(1,1);for j=1:N-1 len=len+D(p(1,j),p(1,j+1);endfunction x,y=exchange(x,y)temp=x;x=y;y=temp;function a,b=intercross(a,b)L=length(a);if L=rand&L10 W=ceil(L/10);else W=floor
8、(L/10);endp=unidrnd(L-W+1);%随机选择交叉X围，从p到p+Wfor i=1:W%交叉 x=find(a=b(1,p+i-1); y=find(b=a(1,p+i-1); a(1,p+i-1),b(1,p+i-1)=exchange(a(1,p+i-1),b(1,p+i-1); a(1,x),b(1,y)=exchange(a(1,x),b(1,y); End运行结果：counter = % 迭代100次 100Rlength = % 最优路径程度ans = % 最优路径次序 Columns 1 through 10 14 17 3 18 4 11 9 5 6 10 Columns 11 through 20 20 2 22 8 16 12 19 21 7 13 Columns 21 through 22 1 15五、问题思考比拟用Hopfield求解TSP问题和遗传算法求解TSP问题的异同。（1） Hopfield算法是基于对TSP问题分析，建立一个换位矩阵模型，进而对矩阵的各项约束条件以能量的形式表示，只要使能量收敛，如此可以满足各项约束条件，寻到最优解；（2） 遗传算法是基于对TSP问题的各种可能的排列组合进展优选，通过复制、交叉、变异等根本操作，使得种群各种可能的排列组合不断优化，最终取得最优解。6 / 6
