遗传算法实现TSP问题.docx
《遗传算法实现TSP问题.docx》由会员分享，可在线阅读，更多相关《遗传算法实现TSP问题.docx（12页珍藏版）》请在冰点文库上搜索。
遗传算法实现TSP问题
遗传算法实现TSP问题
问题提出
旅行商问题（travelingsalemanproblem,简称tsp）：
已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。
如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？
解题思路
用图论的术语来说，假设有一个图g=（v,e），其中v是顶点集，e是边集，设d=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
这个问题可分为对称旅行商问题（dij=dji,,任意i,j=1,2,3，…,n）和非对称旅行商问题（dij≠dji,,任意i,j=1,2,3，…,n）。
若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=（t1,t2,t3,…,ti,…,tn）,其中
ti∈v（i=1,2,3,…,n），且记tn+1=t1，则旅行商问题的数学模型为：
minl=σd（t（i）,t（i+1））（i=1,…,n）
旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。
遗传算法求解TSP的基本步骤
1.种群初始化
个体编码方法有二进制编码和实数编码，在解决TSP问题过程中个体编码方法为实数编码。
对于TSP问题，实数编码为1-n的实数的随机排列，初始化的参数有种群个数M、染色体基因个数N（即城市的个数）、迭代次数C、交叉概率Pc、变异概率Pmutation。
2.适应度函数
在TSP问题中，对于任意两个城市之间的距离D（i,j）已知，每个染色体（即n个城市的随机排列）可计算出总距离，因此可将一个随机全排列的总距离的倒数作为适应度函数，即距离越短，适应度函数越好，满足TSP要求。
3.选择操作
遗传算法选择操作有轮盘赌法、锦标赛法等多种方法，本程序采用基于适应度比例的选择策略，即适应度越好的个体被选择的概率越大，同时在选择中保存适应度最高的个体。
4.交叉操作
遗传算法中交叉操作有多种方法。
本程序中对于个体，随机选择两个个体，在对应位置交换若干个基因片段，同时保证每个个体依然是1-n的随机排列，防止进入局部收敛。
5.变异操作
本程序中对于变异操作，随机选取个体，同时随机选取个体的两个基因进行交换以实现变异操作。
流程图
N
Y
实验结果
MATLAB实现程序如下：
（1）适应度函数fit.m
functionfitness=fit（len,m,maxlen,minlen）
fitness=len;
fori=1:
length（len）
fitness（i,1）=（1-（len（i,1）-minlen）/（maxlen-minlen+0.0001））.^m;
end
（2）个体距离计算函数 mylength.m
functionlen=myLength（D,p）
[N,NN]=size（D）;
len=D（p（1,N）,p（1,1））;
fori=1:
（N-1）
len=len+D（p（1,i）,p（1,i+1））;
end
end
（3）交叉操作函数 cross.m
function[A,B]=cross（A,B）
L=length（A）;
ifL<10
W=L;
elseif（（L/10）-floor（L/10））>=rand&&L>10
W=ceil（L/10）+8;
else
W=floor（L/10）+8;
end
p=unidrnd（L-W+1）;
fprintf（'p=%d',p）;
fori=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
end
（4）对调函数exchange.m
function[x,y]=exchange（x,y）
temp=x;
x=y;
y=temp;
end
（5）变异函数Mutation.m
functiona=Mutation（A）
index1=0;index2=0;
nnper=randperm（size（A,2））;
index1=nnper
（1）;
index2=nnper
（2）;
%fprintf（'index1=%d',index1）;
%fprintf（'index2=%d',index2）;
temp=0;
temp=A（index1）;
A（index1）=A（index2）;
A（index2）=temp;
a=A;
end
（6）连点画图函数plot_route.m
functionplot_route（a,R）
scatter（a（:
1）,a（:
2）,'rx'）;
holdon;
plot（[a（R
（1）,1）,a（R（length（R））,1）],[a（R
（1）,2）,a（R（length（R））,2）]）;
holdon;
fori=2:
length（R）
x0=a（R（i-1）,1）;
y0=a（R（i-1）,2）;
x1=a（R（i）,1）;
y1=a（R（i）,2）;
xx=[x0,x1];
yy=[y0,y1];
plot（xx,yy）;
holdon;
end
end
（7）主函数
clear;
clc;
%%%%%%%%%%%%%%%输入参数%%%%%%%%
N=50; %%城市的个数
M=100; %%种群的个数
C=100; %%迭代次数
C_old=C;
m=2; %%适应值归一化淘汰加速指数
Pc=0.4; %%交叉概率
Pmutation=0.2; %%变异概率
%%生成城市的坐标
pos=randn（N,2）;
%%生成城市之间距离矩阵
D=zeros（N,N）;
fori=1:
N
forj=i+1:
N
dis=（pos（i,1）-pos（j,1））.^2+（pos（i,2）-pos（j,2））.^2;
D（i,j）=dis^（0.5）;
D（j,i）=D（i,j）;
end
end
%%生成初始群体
popm=zeros（M,N）;
fori=1:
M
popm（i,:
）=randperm（N）;
end
%%随机选择一个种群
R=popm（1,:
）;
figure
（1）;
scatter（pos（:
1）,pos（:
2）,'rx'）;
axis（[-33-33]）;
figure
（2）;
plot_route（pos,R）; %%画出种群各城市之间的连线
axis（[-33-33]）;
%%初始化种群及其适应函数
fitness=zeros（M,1）;
len=zeros（M,1）;
fori=1:
M
len（i,1）=myLength（D,popm（i,:
））;
end
maxlen=max（len）;
minlen=min（len）;
fitness=fit（len,m,maxlen,minlen）;
rr=find（len==minlen）;
R=popm（rr（1,1）,:
）;
fori=1:
N
fprintf（'%d',R（i））;
end
fprintf（'\n'）;
fitness=fitness/sum（fitness）;
distance_min=zeros（C+1,1）; %%各次迭代的最小的种群的距离
whileC>=0
fprintf（'迭代第%d次\n',C）;
%%选择操作
nn=0;
fori=1:
size（popm,1）
len_1（i,1）=myLength（D,popm（i,:
））;
jc=rand*0.3;
forj=1:
size（popm,1）
iffitness（j,1）>=jc
nn=nn+1;
popm_sel（nn,:
）=popm（j,:
）;
break;
end
end
end
%%每次选择都保存最优的种群
popm_sel=popm_sel（1:
nn,:
）;
[len_mlen_index]=min（len_1）;
popm_sel=[popm_sel;popm（len_index,:
）];
%%交叉操作
nnper=randperm（nn）;
A=popm_sel（nnper
（1）,:
）;
B=popm_sel（nnper
（2）,:
）;
fori=1:
nn*Pc
[A,B]=cross（A,B）;
popm_sel（nnper
（1）,:
）=A;
popm_sel（nnper
（2）,:
）=B;
end
%%变异操作
fori=1:
nn
pick=rand;
whilepick==0
pick=rand;
end
ifpick<=Pmutation
popm_sel（i,:
）=Mutation（popm_sel（i,:
））;
end
end
%%求适应度函数
NN=size（popm_sel,1）;
len=zeros（NN,1）;
fori=1:
NN
len（i,1）=myLength（D,popm_sel（i,:
））;
end
maxlen=max（len）;
minlen=min（len）;
distance_min（C+1,1）=minlen;
fitness=fit（len,m,maxlen,minlen）;
rr=find（len==minlen）;
fprintf（'minlen=%d\n',minlen）;
R=popm_sel（rr（1,1）,:
）;
fori=1:
N
fprintf（'%d',R（i））;
end
fprintf（'\n'）;
popm=[];
popm=popm_sel;
C=C-1;
%pause
（1）;
end
figure（3）
plot_route（pos,R）;
axis（[-33-33]）;
结论分析
本文采用MATLAB实现遗传算法求解TSP问题,并根据实验结果进行了分析,遗传算法是一种智能优化算法,它的实现有些关键点,一是串的编码方式,本质就是问题编码,串长度及编码形式对算法收敛影响极大;二是适应函数的确定,这是选择的基础;三是自身参数的设定,其中重要的是群体大小,最大迭代次数,交叉概率和变异概率,通过实验我们可以看到最大迭代次数对问题求解的精度有影响,交叉概率和变异概率的设定对问题的收敛速度和求解精度都有极大的影响,目前很多研究都是根据具体的领域问题,改进交叉算子,变异算子,寻找最优的参数设定来提高算法收敛速度和保证最优解的得到,对算子的改进和保证最优解的得到,对算子的改进和参数值的设定这是将来的研究工作。
升级会员 