基于Matlab的遗传算法解决TSP问题的报告资料下载.pdf
《基于Matlab的遗传算法解决TSP问题的报告资料下载.pdf》由会员分享，可在线阅读，更多相关《基于Matlab的遗传算法解决TSP问题的报告资料下载.pdf（12页珍藏版）》请在冰点文库上搜索。
遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。
在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
2.22.22.22.2遗传算法的流程遗传算法的流程遗传算法的流程遗传算法的流程标准的遗传算法包括群体的初始化，选择，交叉，变异操作。
流程图如图1所示，其主要步骤可描述如下：
（1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。
（2）判断算法的收敛准则是否满足。
若满足输出搜索结果；
否则执行以下步骤。
（3）根据适配值大小以一定方式执行选择操作。
（4）按交叉概率Pc执行交叉操作。
（5）按变异概率Pm执行变异操作。
（6）返回步骤
（2）。
图1遗传算法流程图3.TSP3.TSP3.TSP3.TSP问题的遗传算法设计与实现问题的遗传算法设计与实现3.1TSP3.1TSP3.1TSP3.1TSP问题的图论描述问题的图论描述问题的图论描述问题的图论描述求最短路径问题，用图论术语描述如下：
在图G（V,A）中，V表示顶点集合，V=（v1,v2,vn）对G中的某一边（iv,jv），相应的有一个数d（iv,jv），如果G中不存在边（iv,jv），则令d（iv,jv）无穷大，如果把d（iv,jv）认为是边（iv,jv）的长度，则通路的长度定义为组成路的各条边的长度总和。
顶点iv,jv之间是否有边相连，由邻接矩阵来决定。
邻接矩阵A：
对一个具有v个顶点，e条边的图G的邻接矩阵A=ija是一个vv阶方阵，其中ija=1，表示iv和jv邻接，ija=0表示vi和vj不相邻接（或i=j）。
3.23.23.23.2读取读取读取读取txttxttxttxt文件文件文件文件标准的测试文件一般都是存储n*2的txt文件，为此本人编译了一个readfile.m的程序，方便了不同文件的使用。
此程序返回的是城市的坐标矩阵pop和城市的距离矩阵dista。
3.33.33.33.3初始种群初始种群初始种群初始种群对于n个城市的问题，每个个体即每个解的长度为n，用s行,t列的pop矩阵表示初始群体，s表示初始群体的个数，t为n+1，矩阵的每一行的前n个元素表示城市编码，最后一个元素表示这一路径的长度。
这一算法通过start.m程序实现。
3.33.33.33.3适应度适应度适应度适应度在TSP的求解中，可以直接用距离总和作为适应度函数。
个体的路径长度越小，所得个体优越，以pop矩阵的每一行最后一个元素作为个体适应值。
求适应值的qiujuli.m程序，见附录。
3.43.43.43.4选择选择选择选择选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。
这里采用方法是最优保存方法。
算法就是首先将群体中适应度最大的k个个体直接替换适应度最小的k个个体。
程序为select.m，见附录。
3.53.53.53.5交交交交叉受贪婪算法的启发,本文设计一种有目的使适应值上升的交叉算子。
已知两个父代a1（m11,m12,m13,.,m1n）,a2（m21,m22,m23,.,m2n），算法产生后代a1和a2的过程如下：
（1）随机产生一个城市d作为交叉起点,把d作为a1和a2的起始点
（2）分别从a1和a2中找出d的右城市dr1和dr2,并计算（d,dr1）和（d,dr2）的距离j1和j2。
（3）如果j1j2,则把dr2作为a1的第二个点，从a1和a2中删除d，并且把当前点改为dr2。
（5）若此时p1和p2的个数为1，结束，否则回到第二步继续执行。
同理，把第二步中的右城市改成左城市dle1和dle2，通过计算（d,d1e1）和（d,d1e2）的距离并比较大小来确定子代a2。
为程序cross.m，见附录。
3.63.63.63.6变异变异变异变异变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。
这里采用的方法是倒置变异法。
假设当前个体X为（1374805962）。
如果Pmrand，那么随机选择来自同一个体的两个点mutatepoint
（1）和mutatepoint
（2），比如说3和7，倒置P1和P之间的部分，产生下面的子体X为（1375084962）。
为mutate.m程序，见附录。
4.4.4.4.试验与结果分析试验与结果分析试验采用TSPLib标准库的eil51，eil76，eil101作为测试实例。
每个实例分别测试五次，求出平均值和最优值作为比较依据。
问题求解次数最优理论解最优解最差解平均值eil515426432.3981445.9899441.2703eil765538561.5283576.1645570.2783eil1015629678.3685699.7653693.5415下面给出五次运行中的最优路径图：
图1eil51最优路径图图2eil76最优路径图图3eil101最优路径图从图中可以看出，所获得路线都有交叉，明显不是最优路径。
对于51个城市和76个城市来说，都只有一个交叉，而对于101个城市来说，交叉比较多，求得最优路径的结果也不是太理想。
从参数设置来说，对于51个城市和76个城市，参数：
群体总数s=400，交叉概率Pc=0.9，变异概率Pm=0.2，最大迭代次数C=100。
对于不断调整试验参数中可以得出，最大迭代次数越多，结果比较接近理论最优解。
对于101个城市，参数：
群体总数s=500，交叉概率Pc=0.9，变异概率Pm=0.1，最大迭代次数C=200。
对于不断调整试验参数中可以得出，对于较大数目的城市数，变异概率小一些，得到结果也会相应好一些。
5.5.5.5.结语结语本文运用Matlab软件，利用遗传算法解决了小规模的TSP问题。
文章首先介绍了TSP问题，并给出TSP问题的数学定义，然后介绍了遗传算法的原理以及算法的基本过程，最后通过对标准TSPLib中的51、76和101个城市分别进行了测试，根据试验对参数进行分析。
本文程序解决小规模的TSP问题还可以，随着城市数目的增大，计算精度有所下降，计算时间增长很快，效率较低较快，这也是下一步需要改进的地方。
6.6.6.6.附录附录%此为主程序代码，将下面各个程序分别保存在同一文件下运行，即可得出比较%好的解，只是会有点交叉，但是最小路径值很接近最优理论值functiongas=500;
%群体中个体数目k=100;
%选择优化个数Pc=0.9;
%交叉概率Pm=0.1;
%变异概率C=200;
%最大循环次数M,dista=readfile（tsp76.txt）;
%读取城市坐标文件Ncities,b=size（M）;
t=Ncities+1;
farm=start（s,t）;
%随机初始化种群farm=qiujuli（farm,dista）;
%求出种群的适应度counter=0;
whilecounterrand）farm=cross（farm,dista）;
%交叉endif（Pmrand）farm=mutate（farm,dista）;
%变异endenda,b=size（farm）;
%求出总路径中的最小值A=zeros（1,a）;
fori=1:
aA（1,i）=farm（i,b）;
endshortest_path=min（A）%最短路径值c,d=find（A=shortest_path）;
e=c
（1）;
%画出最短路径图fori=1:
Ncitiesplot（M（i,1）,M（i,2）,ro）;
%ro可改holdonendfori=1:
t-2plot_ga（farm（e,1）,farm（e,t-1）,M）;
plot_ga（farm（e,i）,farm（e,i+1）,M）;
end-%读取城市坐标的txt文件，格式为n*2的坐标，n为城市数目，%filename为文件名，返回n*2的坐标pop，以及城市距离矩阵%city_distance，为n*nfunctionpop,city_distance=readfile（filename）fid=fopen（filename,r）;
pop=fscanf（fid,%d,2inf）;
pop=pop;
a,b=size（pop）;
city_distance=zeros（a,a）;
aforj=i:
acity_distance（i,j）=sqrt（pop（i,1）-pop（j,1）2+（pop（i,2）-pop（j,2）2）;
city_distance（j,i）=city_distance（i,j）;
endendfclose（fid）-%生成s*t列的种群，其中每一行的前t-1个数为1到t-1的随机不重复排列，用于%显示随机行走的路径，最后一列记录这样走的总距离，一般t等于城市数目+1，%s为初始设置的群体中个体数目functionpop=start（s,t）pop=zeros（s,t）;
spop（i,1:
t-1）=randperm（t-1）;
end-functiona=bianma（k,u）%编码，生成k个小于u的整数数组a=zeros（1,k）;
aa=0:
u-1;
kpoint=round（rand*（u-i）+1;
a（i）=aa（point）;
aa（point）=;
end=-%该算法主要实现pop矩阵中最后一列的值，即总距离functionpop=qiujuli（pop,D）%D为城市的距离矩阵，pop为种群s,t=size（pop）;
sdd=0;
forj=1:
t-2dd=D（pop（i,j）,pop（i,j+1）+dd;
enddd=dd+D（pop（i,1）,pop（i,t-1）;
%dd为每个访遍城市路径的适应度pop（i,t）=dd;
%存储适应度end-%该算法是将群体中适应度最大的k个个体直接替换适应度最小的k个%个体functionpop=select（pop,k）s,t=size（pop）;
m11=（pop（:
t）;
m11=m11;
mmax=zeros（1,k）;
mmin=zeros（1,k）;
num=1;
whilenumk+1;
a,mmax（num）=max（m11）;
m11（mmax（num）=0;
num=num+1;
endnum=1;
whilenum2%判断是否继续l=find（x1=c1）;
h=find（x2=c2）;
ifl=t+1-jlr=1;
elselr=l+1;
endifh=1hle=t+1-j;
elsehle=h-1;
endq=find（y1=c1）;
z=find（y2=c2）;
ifq=t+1-jqr=1;
elseqr=q+1;
endifz=1zle=t+1-j;
elsezle=z-1;
endifD（c1,x1（lr）D（c1,y1（qr）%根据比较两点间距离进行交换m（j）=x1（lr）;
c1=x1（lr）;
elsem（j）=y1（qr）;
c1=y1（qr）;
endx1（l）=;
%删除父节点y1（q）=;
%删除父节点ifD（c2,x2（hle）D（c2,y2（zle）%根据比较两点间距离进行交换n（j）=x2（hle）;
c2=x2（hle）;
elsen（j）=y2（zle）;
c2=y2（zle）;
endx2（h）=;
%删除父节点y2（z）=;
%删除父节点j=j+1;
endpop1（i,:
）=m;
pop1（i+1,:
）=n;
endpop1=qiujuli（pop1,D）;
%求出交叉后的路径矩阵fori=1:
s%选择适应度变小的交叉，进行更新ifpop1（i,t）pop（i,t）pop（i,:
）=pop1（i,:
）;
endend-%变异，D为城市的距离矩阵，进行变异functionpop=mutate（pop,D）s,t=size（pop）;
pop1=pop;
smutatepoint=bianma
（2）;
b=round（mutatepoint
（2）-mutatepoint
（1）/2-0.5）;
bzhong=pop1（i,mutatepoint
（1）+j）;
pop1（i,mutatepoint
（1）+j）=pop1（i,mutatepoint
（2）-j）;
pop1（i,mutatepoint
（2）-j）=zhong;
endendpop1=qiujuli（pop,D）;
sifpop1（i,t）pop（i,t）pop（i,:
）endend-%画图functionplot_ga（a,b,V）P=V（a,1）V（a,2）;
Q=V（b,1）V（b,2）;
c=P（1,2）;
P（1,2）=Q（1,1）;
Q（1,1）=c;
plot（P,Q,g-）%g表示颜色，-表示连线的形状，可改。
holdon
升级会员 