基于遗传算法的TSP问题解决.docx
《基于遗传算法的TSP问题解决.docx》由会员分享，可在线阅读，更多相关《基于遗传算法的TSP问题解决.docx（13页珍藏版）》请在冰点文库上搜索。
基于遗传算法的TSP问题解决
实验题目：
的遗传算法解决TSP问题
姓名：
谢稳文
班级：
智能1001
学号：
20100840126
一:
问题描述
旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行商问题,货郎担问题，是数学领域中著名问题之一。
假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。
路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。
该问题可以被证明具有NPC计算复杂性。
因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
二:
遗传算法的基本原理
遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。
遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。
遗传算法在模式识别、神经网络、图像处理、机器
学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。
在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智一样，都是对今后十年的计算技术有重大影响的关键技术”。
基本步骤为:
标准的遗传算法包括群体的初始化，选择，交叉，变异操作。
所示，其主要步骤可描述如下：
（1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。
（2）判断算法的收敛准则是否满足。
若满足输出搜索结果；否则执行以下步骤。
（3）根据适配值大小以一定方式执行选择操作。
（4）按交叉概率Pc执行交叉操作。
（5）按变异概率Pm执行变异操作。
（6）返回步骤
（2）
算法流程图为:
三:
TSP问题的遗传算法设计
初始种群：
对于n个城市的问题，每个个体即每个解的长度为n，用s行,t列的pop矩阵表示初始群体，s表示初始群体的个数，t为n+1，矩阵的每一行的前n个元素表示城市编码，最后一个元素表示这一路径的长度。
这一算法通过start.m程序实现。
适应度：
在TSP的求解中，可以直接用距离总和作为适应度函数。
个体的路径长度越小，所得个体优越，以pop矩阵的每一行最后一个元素作为个体适应值。
选择：
选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。
这里采用方法是最优保存方法。
算法就是首先将群体中适应度最大的k个个体直接替换适应度最小的k个体。
交叉：
受贪婪算法的启发,本文设计一种有目的使适应值上升的交叉算子。
已知两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）如果j1（4）如果j1>j2,则把dr2作为a1'的第二个点，从a1和a2中删除d，并且把当前点改为dr2。
（5）若此时p1和p2的个数为1，结束，否则回到第二步继续执行。
同理，把第二步中的右城市改成左城市dle1和dle2，通过计算（d,d1e1）和（d,d1e2）的距离并比较大小来确定子代a2'。
变异：
变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。
这里采用的方法是倒置变异法。
假设当前个体X为（1374805962）。
如果Pm>rand，那么随机选择
来自同一个体的两个点mutatepoint
（1）和mutatepoint
（2），比如说3和7，倒置P1和P之间的部分，产生下面的子体X'为（1375084962）。
四：
实验代码
1主函数部分
clc;
clearall;
closeall;
globalxy
cityfile=fopen（'city30.txt','rt'）;%取30个城市的样本
cities=fscanf（cityfile,'%f%f',[2,inf]）;
fclose（cityfile）;
t=30+1;%城市的数目是30个
s=1500;%样本的数目是1400个
G=300;%运算的代数
c=25;%选择算子中每次替代的样本的数量
x=cities（1,:
）;
y=cities（2,:
）;
pc=0.10;%交叉的概率
pm=0.8;%变异的概率
pop=zeros（s,t）;%得初始的pop矩阵，矩阵的最后一列表示所在行的样本的路径距离
fori=1:
s
pop（i,1:
t-1）=randperm（t-1）;%随机产生1—（t-1）的t-1个数
end
fork=1:
1:
G%GA开始
ifmod（k,50）==1
k
end
pop=distance（pop）;%调用距离函数求距离
pop=select（pop,c）;%调用选择函数
p1=rand;
ifp1>=pc
pop=cross（pop）;%调用交叉函数
end
p2=rand;
ifp2>=pm
pop=mutate（pop）;%调用变异函数
end
end%GA结束
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
bestL=min（pop（:
t））
J=pop（:
t）;
fi=1./J;
[Oderfi,Indexfi]=sort（fi）;%对于fi进行排序
BestS=pop（Indexfi（s）,:
）;%得到最短路
I=BestS;
fori=1:
1:
t-1
x1（i）=x（I（i））;
y1（i）=y（I（i））;
end
x1（t）=x（I
（1））;
y1（t）=y（I
（1））;
cities_new=[x1;y1];
disp（'BestRouteis:
'）;disp（cities_new）;
pos=[cities_newcities_new（:
1）];
lentemp=0;
fori=1:
1:
t-1
temp=sqrt（（pos（1,i）-pos（1,i+1））^2+（pos（2,i）-pos（2,i+1））^2）;
lentemp=lentemp+temp;
end
disp（'ShortestLengthis:
'）;disp（lentemp）;
figure
（1）;
subplot（1,2,1）;%窗口分割的左边部分
x（t）=x
（1）;y（t）=y
（1）;
plot（x,y,'-or'）;
xlabel（'Xaxis'）,ylabel（'Yaxis'）,title（'原始路径'）;
axis（[0,1,0,1]）;
axis（[0,100,0,100]）;
axison
holdon;
subplot（1,2,2）;%窗口分割的右边部分
plot（x1,y1,'-or'）;
xlabel（'Xaxis'）,ylabel（'Yaxis'）,title（'最新的路径'）;
axis（[0,1,0,1]）;
axis（[0,100,0,100]）;
axison
2距离函数
function[pop]=distance（pop）
globalxy
[s,t]=size（pop）;
fori=1:
1:
s
dd=0;
pos=pop（i,1:
t-1）;
pos=[pospos（:
1）];
forj=1:
1:
t-1
m=pos（j）;
n=pos（j+1）;
dd=dd+sqrt（（x（m）-x（n））^2+（y（m）-y（n））^2）;
end
pop（i,t）=dd;
end
3选择函数
unction[pop]=select（pop,c）
[s,t]=size（pop）;
m11=（pop（:
t））;
m11=m11';
mmax=zeros（1,c）;
mmin=zeros（1,c）;
num=1;
whilenum[a,mmax（num）]=max（m11）;%选取当前样本的最大值并记录样本编号给mmax（num）
m11（mmax（num））=0;
num=num+1;
end
num=1;
whilenum[b,mmin（num）]=min（m11）;
m11（mmin（num））=a;
num=num+1;
end
fori=1:
c
pop（mmax（i）,:
）=pop（mmin（i）,:
）;%用距离小的C个样本替换距离大的C个样本
end
4交叉函数
function[pop]=cross（pop）
[s,t]=size（pop）;
pop_1=pop;
n=randperm（s）;%将种群随机排序
fori=1:
2:
s
%随机选择两个交叉点
m=randperm（t-3）+1;
crosspoint
（1）=min（m
（1）,m
（2））;
crosspoint
（2）=max（m
（1）,m
（2））;
%任意两行交叉
x1=n（i）;
x2=n（i+1）;
%将x1左边与x2的左边互换
middle=pop（x1,1:
crosspoint
（1））;
pop（x1,1:
crosspoint
（1））=pop（x2,1:
crosspoint
（1））;
pop（x2,1:
crosspoint
（1））=middle;
%将x1右边与x2的右边互换
middle=pop（x1,crosspoint
（2）+1:
t）;
pop（x1,crosspoint
（2）+1:
t）=pop（x2,crosspoint
（2）+1:
t）;
pop（x2,crosspoint
（2）+1:
t）=middle;
%检查x1左边的重复性并得到x1的左边
forj=1:
crosspoint
（1）
whilefind（pop（x1,crosspoint
（1）+1:
crosspoint
（2））==pop（x1,j））
zhi=find（pop（x1,crosspoint
（1）+1:
crosspoint
（2））==pop（x1,j））;%确定重复位置
temp=pop（x2,crosspoint
（1）+zhi）;
pop（x1,j）=temp;
end
end
%检查x1的右边的重复性并得到x1的右边
forj=crosspoint
（2）+1:
t-1
whilefind（pop（x1,crosspoint
（1）+1:
crosspoint
（2））==pop（x1,j））
zhi=find（pop（x1,crosspoint
（1）+1:
crosspoint
（2））==pop（x1,j））;%确定重复的位置
temp=pop（x2,crosspoint
（1）+zhi）;
pop（x1,j）=temp;
end
end
%检查x2左边的重复性并得到x2的左边
forj=1:
crosspoint
（1）
whilefind（pop（x2,crosspoint
（1）+1:
crosspoint
（2））==pop（x2,j））
zhi=find（pop（x2,crosspoint
（1）+1:
crosspoint
（2））==pop（x2,j））;确定重复位置
temp=pop（x1,crosspoint
（1）+zhi）;
pop（x2,j）=temp;
end
end
%检查x2的右边的重复性并得到x2的右边
forj=crosspoint
（2）+1:
t-1
whilefind（pop（x2,crosspoint
（1）+1:
crosspoint
（2））==pop（x2,j））
zhi=find（pop（x2,crosspoint
（1）+1:
crosspoint
（2））==pop（x2,j））;%确定重复的位置
temp=pop（x1,crosspoint
（1）+zhi）;
pop（x2,j）=temp;
end
end
end
%生成的新的种群与交叉前进行比较，并取两者最优
[pop]=distance（pop）;
fori=1:
s
ifpop_1（i,t）pop（i,:
）=pop_1（i,:
）;
end
end
5变异函数
function[pop]=mutate（pop）
[s,t]=size（pop）;
pop_1=pop;
fori=1:
2:
s
m=randperm（t-3）+1;
%随机取两个点
mutatepoint
（1）=min（m
（1）,m
（2））;
mutatepoint
（2）=max（m
（1）,m
（2））;
%用倒置变异的方法倒置两个点中间部分的位置
mutate=round（（mutatepoint
（2）-mutatepoint
（1））/2-0.5）;
forj=1:
mutate
zhong=pop（i,mutatepoint
（1）+j）;
pop（i,mutatepoint
（1）+j）=pop（i,mutatepoint
（2）-j）;
pop（i,mutatepoint
（2）-j）=zhong;
end
end
[pop]=distance（pop）;%生成的新的种群与变异前比较，并取两者最优
fori=1:
s
ifpop_1（i,t）pop（i,:
）=pop_1（i,:
）;
end
end
用上面的贪婪算法在matlab里运算的结果如下：
五：
实验心得
本实验利用遗传算法解决了小规模的TSP问题。
文章首先介绍了TSP问题，并给出TSP问题的数学定义，然后介绍了遗传算法的原理以及算法的基本过程。
本文程序解决小规模的TSP问题还可以，随着城市数目的增大，计算精度有所下降，计算时间增长很快，效率较低较快，这也是下一步需要改进的地方。
升级会员 