遗传算法（GA）解决TSP问题
            　遗传算法解决TSP问题
遗传算法
遗传算法的基本原理是通过作⽤于染⾊体上的基因寻好的染⾊体来求解问题，它需要对算法所产⽣的每个染⾊体进⾏评价，并基于适应度值来选择染⾊体，使适应性好的染⾊体有更多的繁殖机会，在遗传算法中，通过随机⽅式产⽣若⼲个所求解问题的数字编码，即染⾊体，形成初始种；通过适应度函数给每个个体⼀个数值评价，淘汰低适应度的个体，选择⾼适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下⼀代新的种，对这个新的种进⾏下⼀轮的进化。
TSP问题
TSP问题即旅⾏商问题，经典的TSP可以描述为：⼀个商品推销员要去若⼲个城市推销商品，该推销员从⼀个城市出发，需要经过所有城市后，回到出发地。应如何选择⾏进路线，以使总的⾏程最短。从图论的⾓度来看，该问题实质是在⼀个带权完全⽆向图中，⼀个权值最⼩的哈密尔顿回路。
遗传算法解决TSP问题
概念介绍：
种 ==> 可⾏解集
个体 ==> 可⾏解
染⾊体 ==> 可⾏解的编码
基因 ==> 可⾏解编码的分量
基因形式 ==> 遗传编码
适应度 ==> 评价的函数值（适应度函数）
选择 ==> 选择操作
交叉 ==> 编码的交叉操作
变异 ==> 可⾏解编码的变异
遗传操作：就包括优选适应性强的个体的“选择”；个体间交换基因产⽣新个体的“交叉”；个体间的基因突变⽽产⽣新个体的“变异”。其中遗传算法是运⽤遗传算⼦来进⾏遗传操作的。即：选择算⼦、变异算⼦、交叉算⼦。
遗传算法的基本运算过程
（1）种初始化：个体编码⽅法有⼆进制编码和实数编码，在解决TSP问题过程中个体编码⽅法为实数编码。对于TSP问题，实数编码为1-n的实数的随机排列，初始化的参数有种个数M、染⾊体基因个数N（即城市的个数）、迭代次数C、交叉概率Pc、变异概率Pmutation。
（2）适应度函数：在TSP问题中，对于任意两个城市之间的距离D(i,j)已知，每个染⾊体（即n个城市的随机排列）可计算出总距离，因此可将⼀个随机全排列的总距离的倒数作为适应度函数，即距离越短，适应度函数越好，满⾜TSP要求。
（3）选择操作：采⽤基于适应度⽐例的选择策略，即适应度越好的个体被选择的概率越⼤，同时在选择中保存适应度最⾼的个体。
（4）交叉操作：对于个体，随机选择两个个体，在对应位置交换若⼲个基因⽚段，同时保证每个个体依然是1-n的随机排列，防⽌进⼊局部收敛。
例如：
对A的4 3 2进⾏和B的交叉时，将B的2 6 7换⾄A，同时将A中的6 7（B换上来但A已包含）和B中对应的数字进⾏交叉，6->3 7->2
（5）变异操作：对于变异操作，随机选取个体，同时随机选取个体的两个基因进⾏交换以实现变异操作。
产⽣新的体后再次进⾏评估，然后再选择、交叉、变异，⼀直循环这⼏步，最终到⼀个近似最优解。
遗传算法的终⽌条件
1. 当最优个体的适应度达到给定的阈值
fprintf作用2. 最优个体的适应度和体适应度不再上升
3. 迭代次数达到预设的代数时，算法终⽌
运⾏结果：
第⼀次测试
N=25; %城市的个数
M=100; %种的个数
TER=2000; %迭代次数
Pc=0.8; %%交叉概率
Pmutation=0.05; %%变异概率
迭代2000次之后运⾏结果并不能算是很好，整体迭代了600次左右趋于平稳，但仍有部分细微波动，运⾏时间相较于蚁算法更快。
第⼆次测试
N=25; %城市的个数
M=100; %种的个数
TER=2000; %迭代次数
Pc=0.95; %交叉概率
Pmutation=0.1; %变异概率
提⾼了变异概率和交叉概率，虽然最终结果的准确性有略微提升，但是牺牲了运⾏时间和迭代次数，迭代次数远远⼤于第⼀次测试，可见变异概率和交叉概率过⼤对实验结果存在⼀定影响。
第三次测试
N=25; %城市的个数
M=100; %种的个数
TER=2000; %迭代次数
Pc=0.4; %交叉概率
Pmutation=0.01; %变异概率
结合第⼆次测试可以看出，交叉概率和变异概率不能过⼤，否则波动较⼤，迭代时间较长，同样也不能过⼩，否则很难到最优解
第四次测试
N=25; %城市的个数
M=200; %种的个数
TER=2000; %迭代次数
Pc=0.8; %交叉概率
Pmutation=0.05; %变异概率
种的个数增加成原来的⼀倍后，运⾏的结果更加精确，但是相应的迭代次数会增加，时间成本增加
第五次测试
N=25; %城市的个数
M=500; %种的个数
TER=2000; %迭代次数
Pc=0.8; %交叉概率
Pmutation=0.05; %变异概率
可以发现当种个数增加更多之后，迭代次数⼤幅减少，但是运⾏的时间与第四次测试相⽐增加了近20秒，时间成本增加了很多，所以种个数同样不应该过⼤。
总结
对同⼀个TSP问题，分析种规模、交叉概率和变异概率对算法结果的影响：
（1）改变种个数后的影响-->种个数增⼤，算法结果的精确度会有⼀定的提升，但是运⾏时间相较之前更久了。
（2）改变交叉概率后的影响-->交叉概率过低将很难得不到最优解，交叉概率越⾼则平均适应度越好，但是也不能过⾼，否则会影响迭代时间。
（3）改变变异概率概率后的影响-->变异概率过⾼或者过低都会影响运⾏得到最优解
（4）遗传算法得到的结果的精确度会受到交叉概率、变异概率、迭代次数的影响：迭代次数越⼤，变异概率越⼩，则遗传算法的精确度越⾼。执⾏时间随着迭代次数的增加⽽增加。当交叉概率为0.8，变异概率为0.5，结果相对来说会稍微好⼀些，整体来说运⽤遗传算法来求解TSP问题的速度要⽐⽤蚁算法来解决TSP问题快的多，所以适当将迭代次数增加⼀些也没有什么影响。
代码
%main
clear;
clc;
%%%%%%%%%%%%%%%输⼊参数%%%%%%%%
N=25;              %%城市的个数
M=100;              %%种的个数
ITER=2000;              %%迭代次数
%C_old=C;
m=2;                %%适应值归⼀化淘汰加速指数
Pc=0.8;            %%交叉概率
Pmutation=0.05;      %%变异概率
%%⽣成城市的坐标
pos=[-0.0596300734351115    -0.851297433985992;
0.4383984583357350.841724248850041;
-0.251804207069105    -1.30744728793171;
1.177906921643880.0952195708913433;
1.66427009988301    -0.133382476901910;
-0.337308956003599    -0.407225198007313;
0.311862707690034    -0.431724333072457;
0.182396732713558    -0.157788333124223;
0.0378390295101906    -0.367920724129644;
-0.8537099513566730.0363449796675028;
-1.64191242274810    -0.565028275383299;
-
0.821481309108439    -1.36166562718530;
-0.06665027037263640.756667745411741;
2.25931856568426    -1.30140683361980;
0.759098750479421  2.81038357991309;
-0.009251051442074780.672464995693229;
0.862239245550680    -0.576524359942781;
-0.7425126282020770.740723643506810;
0.371005938734921    -0.835740815137822;
0.677683424862960    -0.284758907693345;
-1.482341806289740.955162776644004;
0.4528068316645900.608019647737753;
1.22196689592397    -0.878318328597688;
0.352173262723895  1.60512181080303;
1.807294846252930.593061432086341
];
%%⽣成城市之间距离矩阵
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);%随机排列，⽐如[245613]
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);
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;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。