实战1：基于遗传算法解决旅行商问题的MATLAB编程（3）TSP算法编写问题
2022/6/2 1:23:14
本文主要是介绍实战1：基于遗传算法解决旅行商问题的MATLAB编程（3）TSP算法编写问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
目录
0.先上程序
1.绪论+研究背景
2.研究方法
3.使用遗传算法编写TSP问题
3.0 初始化定义+城市坐标分布编码和显示
3.1 距离函数
3.2 适应度函数
3.3 选择算子
3.4 交叉算子
3.5 变异算子
3.6 迭代
3.7 作图
3.7.1 每代最小值散点图
3.7.2 总适应度折线图
3.7.3 最优路径图
4.参考
本节内容是为了对之前程序篇内容的解释，如下章节
实战1：基于遗传算法解决旅行商问题的MATLAB编程（1）程序篇
实战1：基于遗传算法解决旅行商问题的MATLAB编程（2）绪论、研究背景以及研究方法
3.使用遗传算法编写TSP问题
3.0 初始化定义+城市坐标分布编码和显示
（1）自己给定城市的坐标，这里举例用20个城市。
%% Define cities coordination city20=[29 54;71 76;74 78;81 71;25 38;58 35;4 50; 13 40;18 40;24 98;71 44;64 60;69 58;83 69;58 69;54 63;51 67;37 84; 41 94;3 85];
（2）定义初始化变量，如种群个数，编码对象个数，迭代次数，实际迭代次数，变异概率，交叉概率等等
N=20; %城市数 city_coordinate=city20; %城市位置，前面已经给点城市的数量，则可以确定城市的坐标。（8,15,20,30） s=100; %样本数（种群） c=30; %替换个数 pc=0.8; %交叉概率crossover pm=0.1; %变异概率mutation times=3000; %最大迭代次数 time=0; %实际迭代次数
（3）初始化变量，不同种群位置的矩阵定义、最短距离，最短路径编码排布
%%初始化变量，设定总群，总适应度以及最短距离以及最小距离。 pop=zeros(s,N+1); %初始种群+适应度,之所以加N+1，因为最后还要回到原点。 pop_fit_aver=[];%总适应度 min_dis=[]; %最短距离 pop_min=[];%最短距离的基因
（4）初始化种群，使用randperm为每一个种群产生随机的编码（随机的城市排布）
%初始化，其中s为种群数
for i=1:s
pop(i,1:N)=randperm(N); %%randperm函数产生1-N内任意排列的N维数组。
end
（5）标出城市的位置用圆点，给城市位置编码并作图
plot(city_coordinate(:,1),city_coordinate(:,2),'bo');%画平均适应度折线图 //一个列向量作为自变量，另一个列向亮作为应变量。
%%变量处理：城市间
for i=1:N
test_t=num2str(i); %%将变量类型转换为浮点型数
text(city_coordinate(i,1),city_coordinate(i,2),test_t);%标号 行不变，列改变
end
grid on;
title('城市坐标分布图');
xlabel('x');
ylabel('y');
（6）效果图，可以清晰知道城市的位置，城市的编码序号排布。
3.1 距离函数
function [city_distance] = CityDistance(city_coordinate,N)%城市距离矩阵
city_distance=zeros(N,N); %%通过zeros构造
for i=1:N
for j=1:N
city_distance(i,j)=((city_coordinate(i,1)-city_coordinate(j,1))^2+...
(city_coordinate(i,2)-city_coordinate(j,2))^2)^0.5; %%matlab是以矩阵的思维编写的，则每个距离都会存入city_diatance
end
end
end
代码解释：
由于我们知道城市坐标的位置，这样可以使用勾股定理求出任意两个城市之间的距离
city_distance之所以赋值为N BY N，是因为自己跟自己的距离在接下来城市距离计算中也存在。
通过双for循环，配合城市坐标，采用勾股定理求出距离，并填入相应两个城市之中。
回到主程序（GeneticAlgorithm_TSP.m）调用该函数。
city_distance=CityDistance(city_coordinate,N);%城市间距离
3.2 适应度函数
function [individual_fit,num,min_distance,index] = GroupFit(city_distance,N,pop,s)%种群适应度
individual_distance=zeros(s,1); %%目的是求得最短路劲的值，给定INDIVIDUAL为sx1的矩阵
for j=1:s
sum_distance=0;
for i=1:N-1
sum_distance=sum_distance+city_distance(pop(j,i),pop(j,i+1));
end
sum_distance=sum_distance+city_distance(pop(j,N),pop(j,1)); %%最后回到起点
individual_distance(j,1)=sum_distance; %%individual_distance是一个列矩阵
end
[min_distance,index]=min(individual_distance); %%找到最短的距离
individual_fit=1./individual_distance; %%分子越小，分母越大
num=0;
for i=1:s
num=num+individual_fit(i,1);
end
end
代码解释：
individual_distance 是用来接收不同种群的路径的距离（编码城市不同会产生不同的旅行距离）。
其中： individual_fit=1./individual_distance; （适应度函数变换，因为我们要求最小值，取反，求最大值即可）
不懂的朋友可以参考：https://www.cnblogs.com/yanshw/p/14749809.html 这篇文章，讲的很详细。
sum =所有列举种群中距离之和。
回到主程序，调用适应度库函数。
%适应度函数编写
[individual_fit,sum,min1,min_index]=GroupFit(city_distance,N,pop,s);
%%通过城市距离；城市数。pop（城市的随机分布）。s是城市分布的例子个数
sumP=sum;
pop_fit_aver=[pop_fit_aver;sum]; %%构造总群适应度函数
min_dis=[min_dis;min1]; %%构造最小距离 min_dis=min1
pop(:,N+1)=individual_fit; %%列矩阵的个体适应度函数
pop_min=[pop_min;pop(min_index,:)];
此时 min_dis 是最短种群编码的路径距离。
此时pop = （S x（N+1）），具体内容如下：
POP_min 具体内容如下
3.3 选择算子(selection.m)
function [pop_ok]=selection(pop,N,s,c)%选择父代
pop=sortrows(pop,N+1);
for i=1:c
pop(i,:)=pop(s+1-i,:);
end
randIndex=randperm(size(pop,1));
pop=pop(randIndex,:);
pop_ok=pop;
end
代码解释：
其中c在之间定义，替换的个数=30。
sortrows函数在help中的解释：（升序）
size 函数
size（A）=返回矩阵尺寸的行向量
size(A,1dim)=返回矩阵的行数
size（A,2dim）=返回矩阵的列数
size(A,3dim) =返回矩阵的第三维度dimension
返回主函数，下面解释选择算子在主函数中的作用。
%% 选择父代
pop=selection(pop,N,s,c);
for i=1:times
time=time+1;
E_new_new=[]; %子代
for j=1:s/2
a=rand(1);
b=rand(1);
代码解释：
X = rand(n) 返回一个 n×n 的随机数矩阵。
times：迭代次数
time： 实际迭代次数
3.4 交叉算子（crossover.m）
交叉算子：交叉分为单点交叉和多点交叉。与传统的遗传算法不同的是，进行交叉不能整体替换，即替换后
结果访问的城市不能有重复或者依然是1-N的排列方式。
function [a,b]=Crossover(pop1,pop2,crosspoint,N)%交叉
A=pop1;
if(crosspoint(:,1)<crosspoint(:,2)) %%由于交叉的位置是随机的，有可能是从小到大，也有可能是从大到小
pop1(crosspoint(:,1):crosspoint(:,2))=pop2(crosspoint(:,1):crosspoint(:,2));
pop2(crosspoint(:,1):crosspoint(:,2))=A(1,crosspoint(:,1):crosspoint(:,2));
while 1
tbl = tabulate(pop1(1:N)); %%Create Frequency table
if (tbl(:,3)<=(100/N)) %%如果个数超过一个就退出循环
break;
end
[pop1,pop2]=SwapRepeat(tbl,pop1,pop2,crosspoint(:,1),crosspoint(:,2),N);%%执行存在重复的编码问题
end
else
pop1(crosspoint(:,2):crosspoint(:,1))=pop2(crosspoint(:,2):crosspoint(:,1));
pop2(crosspoint(:,2):crosspoint(:,1))=A(1,crosspoint(:,2):crosspoint(:,1));
while 1
tbl = tabulate(pop1(1:N));
if (tbl(:,3)<=(100/N))
break;
end
[pop1,pop2]=SwapRepeat(tbl,pop1,pop2,crosspoint(:,2),crosspoint(:,1),N);
end
end
a=pop1;b=pop2;
end
代码解释：
（1）交换本质：如同C语言中的交换变量：
temp =A
A =B
B =Ttemp
（2）tubelate 函数生成线性表格
SwapRepeat.m （交换函数，为了是将某一个种群中重复的编码去掉）
function [a,b]=SwapRepeat(tbl,pop1,pop2,c1,c2,N)%基因去重
i=100/N;
for k=1:(c1-1) %%从左侧开始找起
if tbl(pop1(k),3)>i %%数重复出现
kk=find(pop1(c1:c2)==pop1(k))+c1-1; %%发现重复数在原本数组中的位置
kkk=pop1(k); %%备份自变量在k时的值
pop1(k)=pop2(kk); %%pop1和pop2
pop2(kk)=kkk; %%pop2
end
end
for k=c2+1:N %%从右侧开始找起
if tbl(pop1(k),3)>i
kk=find(pop1(c1:c2)==pop1(k))+c1-1;
kkk=pop1(k);
pop1(k)=pop2(kk);
pop2(kk)=kkk;
end
end
a=pop1;
b=pop2;
end
代码解释：
上图：简单明了。
主函数调用算子：
%% 交叉crossover
if a>pc
;
else
crosspoint=rand(1,2);
crosspoint=floor(crosspoint*N)+1;
[pop(j,:),pop(j+s/2,:)]=Crossover(pop(j,:),pop(j+s/2,:),crosspoint,N);
end
代码解释：
pc:交叉概率
X = rand( 返回由随机数组成的 sz1,...,szN)sz1×...×szN 数组，其中 sz1,...,szN 指示每个维度的大小。例如：rand(3,4) 返回一个 3×4 的矩阵。（生成一个由介于 0 和 1 之间的均匀分布的随机数组成的 5×5 矩阵）
3.5 变异算子（Mutation.m）
function [a]=Mutation(pop0,N)%变异
crosspoint=rand(1,2); %%随机产生一个1x2的，范围在0-1内的向量Vector
crosspoint=floor(crosspoint*N)+1;
if(crosspoint(:,1)<crosspoint(:,2))
sub=pop0(crosspoint(:,1):crosspoint(:,2));
sub=SwapGene(sub,crosspoint(:,1),crosspoint(:,2));
pop0(crosspoint(:,1):crosspoint(:,2))=sub;
else
sub=pop0(crosspoint(:,2):crosspoint(:,1));
sub=SwapGene(sub,crosspoint(:,2),crosspoint(:,1));
pop0(crosspoint(:,2):crosspoint(:,1))=sub;
end
a=pop0;
end
代码解释：
（1）crosspoint 接收随机变异点
（2）判断两个点是大小，从小到大还是从大到小
使用sub = 截取pop0中相应变异点的值
（3）使用SwapGene库函数交换变异点
（4）替换
图片解释：
其中算子 SwapGene.m
function [a]=SwapGene(sub,c1,c2)%交换
kk=ceil((c2-c1)/2);
kkk=(c2-c1)+2;
for k=1:kk
kkkk=sub(k);
sub(k)=sub(kkk-k);
sub(kkk-k)=kkkk;
end
a=sub;
end
代码解释：之所以kkk = c2-c1 本来数量角度需要加1，但是为了能够表示最后一位数之后的数，就需要加2
上述代码中交换的方式：
传统的穷举交换方式：
变异算子在主函数的调用
%% 变异mutation
if b>pm
;
else
pop(j,:)=Mutation(pop(j,:),N);
pop(j+s/2,:)=Mutation(pop(j+s/2,:),N);
end
代码解释：
pm：变异概率0.1
3.6 迭代所需求的内容：
（1）适应度函数sum
（2）目标函数集合（每代最小值的集合）min_dis
（3）最终迭代完后保留下来的种群的内容写入E_new_new中
（4）每代种群最优编码方式集合 pop_min
（5） E_new_new=[]; 每次迭代都美重新更新
E_new_new=[E_new_new;pop(j,:);pop(j+s/2,:)]; %%每次迭代保留优秀种群写入E_new_new中
end
[individual_fit,sum,min1,min_index]=GroupFit(city_distance,N,E_new_new,s);
%%适应度向量，适应度函数，最小距离，最小距离下标
%%参数：城市距离矩阵，城市数，每代最优种群的几何，种群数
sumS=sum;
pop_fit_aver=[pop_fit_aver;sum]; %%适应度函数
min_dis=[min_dis;min1]; %%每次迭代的最小值的向量集合
E_new_new(:,N+1)=individual_fit; %%目标函数（城市之间的距离）
pop_min=[pop_min;E_new_new(min_index,:)];
if(abs(sumS-sumP)<0.001)%退出条件 %%迭代的条件
break;
end
pop=selection(E_new_new,N,s,c); %%选择算子
end
[a,min_index]=min(min_dis); %%min函数可以求得 该向量min_dis最小值和最小值所在的index
作图：
（1）每代最小值散点图
time1=1:time+1; %%为什么要加1，因为没有迭代前，原始种群也有一个最小值
figure%画平均适应度折线图
plot(time1,min_dis,'k.');
grid on;
title('每代最小值散点图');
xlabel('迭代的次数');
ylabel('最短的距离');
效果图
（2）总适应度折线图
figure%画总适应度折线图
plot(time1,pop_fit_aver);
grid on;
title('总适应度折线图');
xlabel('迭代次数');
ylabel('每代总适应度');
效果图
（3）最优路径图
figure%画最优路径
DrawPath(city_coordinate,pop_min,min_index,N) %%参数：城市坐标，每次迭代最小种群的编码方式，最小在种群index，城市数量
grid on;
title('最优路径图');
xlabel('x');
ylabel('y');
效果图
这里讲一下DrawPath.m
function DrawPath(city_coordinate,E_new_new,min_index,N)%画路径图 %% %%参数：城市坐标，每次迭代最小种群的编码方式，最小在种群index，城市数量
k=E_new_new(min_index,1:N) %%去掉适应度的值
%plot(kkk(:,1),kkk(:,2),'b');%画平均适应度折线图
plot(city_coordinate(:,1),city_coordinate(:,2),'bo');
hold on;
for i=1:N-1
plot([city_coordinate(k(i),1),city_coordinate(k(i+1),1)],[city_coordinate(k(i),2),city_coordinate(k(i+1),2)],'r','LineWidth',2);
test_t=num2str(i);
text(city_coordinate(k(i),1),city_coordinate(k(i),2),test_t);
hold on;
end
test_t=[num2str(N)];
text(city_coordinate(k(N),1),city_coordinate(k(N),2),test_t);
plot([city_coordinate(k(N),1),city_coordinate(k(1),1)],[city_coordinate(k(N),2),city_coordinate(k(1),2)],'r','LineWidth',2)
end
注意点：最后一个城市返回出发点的城市。
plot([city_coordinate(k(N),1),city_coordinate(k(1),1)],[city_coordinate(k(N),2),city_coordinate(k(1),2)],'r','LineWidth',2)
Refrence ：
1.https://blog.csdn.net/qcyfred/article/details/76731706
2.https://www.cnblogs.com/yanshw/p/14749809.html
date：20220601/1:37:31 PM
六一儿童节的礼物，加油！
这篇关于实战1：基于遗传算法解决旅行商问题的MATLAB编程（3）TSP算法编写问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-22[开源]10.3K+ Star！轻量强大的开源运维平台，超赞！
- 2024-11-21Flutter基础教程：新手入门指南
- 2024-11-21Flutter跨平台教程：新手入门详解
- 2024-11-21Flutter跨平台教程：新手入门与实践指南
- 2024-11-21Flutter列表组件教程：初学者指南
- 2024-11-21Flutter列表组件教程：新手入门指南
- 2024-11-21Flutter入门教程：初学者必看指南
- 2024-11-21Flutter入门教程：从零开始的Flutter开发指南
- 2024-11-21Flutter升级教程：新手必读的升级指南
- 2024-11-21Flutter升级教程：轻松掌握Flutter版本更新
