遗传算法与TSP问题
遗传算法与TSP问题
-
-
1.TSP问题简介
-
2.原理
-
3.流程
-
4.代码
-
5.运行结果与分析
-
- 一、运行结果
- 二、结果分析
-
6.总结
-
- 参考
-
1.TSP问题简介
旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
2.原理
遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
3.流程
遗传算法的基本运算过程如下：
初始化：设置进化代数计数器t=0、设置最大进化代数T、交叉概率、变异概率、随机生成M个个体作为初始种群P
个体评价：计算种群P中各个个体的适应度
选择运算：将选择算子作用于群体。以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代
交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉
变异运算：在变异概率的控制下，对群体中的个体两两进行变异，即对某一个体的基因进行随机调整
经过选择、交叉、变异运算之后得到下一代群体P1。
重复以上1-6，直到遗传代数为T，以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
4.代码
（1）交叉操作函数 cross.m
%交叉操作函数 cross.m
function [A,B]=cross(A,B)
L=length(A);
if L<10
W=L;
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10)+8;
else
W=floor(L/10)+8;
end
%%W为需要交叉的位数
p=unidrnd(L-W+1);%随机产生一个交叉位置
%fprintf('p=%d ',p);%交叉位置
for 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
end
（2）对调函数 exchange.m
%对调函数 exchange.m
function [x,y]=exchange(x,y)
temp=x;
x=y;
y=temp;
end
（3）适应度函数 fit.m
%适应度函数fit.m，每次迭代都要计算每个染色体在本种群内部的优先级别，类似归一化参数。越大约好！
function fitness=fit(len,m,maxlen,minlen)
fitness=len;
for i=1:length(len)
fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001)).^m;
end
（4）主函数 main
%main
clear;
clc;
%%%%%%%%%%%%%%%输入参数%%%%%%%%
N=25; %%城市的个数
M=100; %%种群的个数
ITER=2000; %%迭代次数
%C_old=C;
m=2; %%适应值归一化淘汰加速指数
Pc=0.8; %%交叉概率
Pmutation=0.05; %%变异概率
%%生成城市的坐标
pos=randn(N,2);
%%生成城市之间距离矩阵
D=zeros(N,N);
for i=1:N
for j=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);
for i=1:M
popm(i,:)=randperm(N);%随机排列，比如[2 4 5 6 1 3]
end
%%随机选择一个种群
R=popm(1,:);
figure(1);
scatter(pos(:,1),pos(:,2),'rx');%画出所有城市坐标
axis([-3 3 -3 3]);
figure(2);
plot_route(pos,R); %%画出初始种群对应各城市之间的连线
axis([-3 3 -3 3]);
%%初始化种群及其适应函数
fitness=zeros(M,1);
len=zeros(M,1);
for i=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);%找到最小值的下标，赋值为rr
R=popm(rr(1,1),:);%提取该染色体，赋值为R
for i=1:N
fprintf('%d ',R(i));%把R顺序打印出来
end
fprintf('\n');
fitness=fitness/sum(fitness);
distance_min=zeros(ITER+1,1); %%各次迭代的最小的种群的路径总长
nn=M;
iter=0;
while iter<=ITER
fprintf('迭代第%d次\n',iter);
%%选择操作
p=fitness./sum(fitness);
q=cumsum(p);%累加
for i=1:(M-1)
len_1(i,1)=myLength(D,popm(i,:));
r=rand;
tmp=find(r<=q);
popm_sel(i,:)=popm(tmp(1),:);
end
[fmax,indmax]=max(fitness);%求当代最佳个体
popm_sel(M,:)=popm(indmax,:);
%%交叉操作
nnper=randperm(M);
% A=popm_sel(nnper(1),:);
% B=popm_sel(nnper(2),:);
%%
for i=1:M*Pc*0.5
A=popm_sel(nnper(i),:);
B=popm_sel(nnper(i+1),:);
[A,B]=cross(A,B);
% popm_sel(nnper(1),:)=A;
% popm_sel(nnper(2),:)=B;
popm_sel(nnper(i),:)=A;
popm_sel(nnper(i+1),:)=B;
end
%%变异操作
for i=1:M
pick=rand;
while pick==0
pick=rand;
end
if pick<=Pmutation
popm_sel(i,:)=Mutation(popm_sel(i,:));
end
end
%%求适应度函数
NN=size(popm_sel,1);
len=zeros(NN,1);
for i=1:NN
len(i,1)=myLength(D,popm_sel(i,:));
end
maxlen=max(len);
minlen=min(len);
distance_min(iter+1,1)=minlen;
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
fprintf('minlen=%d\n',minlen);
R=popm_sel(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
popm=[];
popm=popm_sel;
iter=iter+1;
%pause(1);
end
%end of while
figure(3)
plot_route(pos,R);
axis([-3 3 -3 3]);
figure(4)
plot(distance_min);
（5）变异函数 Mutation.m
%变异函数 Mutation.m
function a=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）染色体的路程代价函数 mylength.m
%染色体的路程代价函数 mylength.m
function len=myLength(D,p)%p是一个排列
[N,NN]=size(D);
len=D(p(1,N),p(1,1));
for i=1:(N-1)
len=len+D(p(1,i),p(1,i+1));
end
end
（7）连点画图函数 plot_route.m
%连点画图函数 plot_route.m
function plot_route(a,R)
scatter(a(:,1),a(:,2),'rx');
hold on;
plot([a(R(1),1),a(R(length(R)),1)],[a(R(1),2),a(R(length(R)),2)]);
hold on;
for i=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);
hold on;
end
end
5.运行结果与分析
一、运行结果
遗传算法有4个参数需要提前设定：
（1）群体大小：
迭代次数ITER=2000
交叉概率Pc=0.8
变异概率Pmutation=0.05
①：种群的个数M=100
②：种群的个数M=85
③：种群的个数M=70
④：种群的个数M=55
（2）交叉概率：
迭代次数ITER=2000
变异概率Pmutation=0.05
种群的个数M=85
①：交叉概率Pc=0.8
②：交叉概率Pc=0.7
③：交叉概率Pc=0.6
④：交叉概率Pc=0.5
（3）遗传算法的终止进化代数：
交叉概率Pc=0.7
变异概率Pmutation=0.05
种群的个数M=85
①：迭代次数ITER=2000
②：迭代次数ITER=1750
③：迭代次数ITER=1500
④：迭代次数ITER=1250
（4）变异概率：
迭代次数ITER=1500
交叉概率Pc=0.7
种群的个数M=85
①：变异概率Pmutation=0.05
②：变异概率Pmutation=0.07
③：变异概率Pmutation=0.09
④：变异概率Pmutation=0.03
二、结果分析
（1）群体大小：
经测试得，当种群数目在85左右时，易得无交叉的最短路径，而其他数据上下相较于85难以获得无交叉最短路径，而且种群数目不超过70时收敛过晚，说明该数目过小，所以最终取种群数目为85时为最优。
（2）交叉概率：
经测试得，交叉概率为0.7时易得优秀的路径，交叉概率不低于0.8时，迭代次数过多且所得路径较长，交叉概率在0.6时，迭代次数过高，交叉概率在0.5时，所得路径较长，综合实验结果得，交叉概率为0.7时较易得到优秀的路径。
（3）迭代次数：
经测试得，迭代次数小于1500时难以得出优秀的路径，而超过1500时又过高，延长了测试时间，得出的结果也无太大变化，所以，将迭代次数设置为1500次时较为合理。
（4）变异概率：
经测试得，当变异概率在0.07时，最容易获得优秀的路径，当变异概率在0.09时，容易陷入局部最优，而变异概率在0.05及以下时，更难以取得优秀的路径，易出现交叉路径，陷入局部最优，最终取变异概率为0.07为最佳。
6.总结
（1）影响因素：
①：
种群数目过小，易出现近亲交配，产生病态的基因，即便变异算子较大，也难以得到较好的结果，遗传算子存在随机误差会妨碍有效模式的正确传播，种群进化无法产生期望的结果。种群数目过大，则结果收敛过晚，且浪费时间与资源，并无益处。
②：
交叉概率过小时，无法有效地进行种群的更新。交叉概率过大时，容易影响现有的有利模式，增大随机性，使结果变得难以预测。
③：
变异概率过小时，种群难以产生进化，多样性下降，错过优秀基因的概率变大。变异概率过大时，多样性优秀但容易产生偏差过大的结果，从而影响最终结果。
④：
迭代次数过小时，算法未收敛，种群难以成熟，难以得到结果。迭代次数过大时，算法进化成熟，或种群过于早熟无法再收敛，进化失去意义。
（2）遗传算法分析：
①：优点：
（1）与问题领域无关切快速随机的搜索能力。
（2）搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较，robust.
（3）搜索使用评价函数启发，过程简单
（4）使用概率机制进行迭代，具有随机性。
（5）具有可扩展性，容易与其他算法结合。
②：缺点：
（1）编码不规范及编码存在表示的不准确性。
（2）单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。
（3）遗传算法通常的效率比其他传统的优化方法低。
（4）遗传算法容易过早收敛。
（5）遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法