本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com
TSP问题是优化问题中的经典问题，
本文分析如何应用蒙特卡罗算法求解TSP问题，并展示算法求解效果
通过本文，可以进一步感受蒙特卡罗算法的强大之处
本节回顾TSP问题及分析蒙特卡罗算法求解TSP问题的思路
TSP旅行商问题回顾
TSP旅行商问题如下：
有N个城市 ，要求穿过每个城市，最终回到出发城市，
问：寻找一条路径，使旅行总距离最小
该问题无法穷举，因为如果有20个城市，则可选组合为19！种
蒙特卡罗算法求解TSP-算法思路
对于TSP问题，我们可以使用逐个城市决策的方式
即先确定起始城市，然后每次选择期望最优的城市作为下个城市，直到走完所有城市
详细如下：
先初始化出发城市，这里不妨将出发城市初始化为城市A，
由于路径最终是闭环的，所以选择哪个城市作为出发城市都是一样的
然后评估哪个城市能使最终总路径最小，就选择哪个城市作为下个城市
由于还没有确定剩下所有城市的路径，此时没法计算出最终的总路径，
但我们可以用蒙特卡罗法去评估总路径期望，
也即假设选择第j个城市作为下一个城市时，
将剩余城市随机走m次，用这m次的平均总路径作为选择城市j的最终总路径评估
如此反复，直到走完所有城市
蒙特卡罗算法求解TSP - 算法流程
一、初始化选择一个出发城市
二、评估各个城市作为下个城市的代价：
评估城市k的代价的方法：
以城市k作为下个城市，再随机走完剩余城市，走m次
1.如果城市较多时，把m次的平均路程作为城市k的代价
2.如果城市较少时，把m次中最短路程作为城市k的代价
三、选择代价最小的城市作为下个城市
重复二、三，直到走完所有城市
本节提供蒙特卡罗算法求解TSP的代码实现和展示求解结果
蒙特卡罗算法求解TSP-代码实现
在matlab中实现蒙特卡罗法求解TSP问题如下：
%------代码说明：展示蒙特卡罗法求解TSP问题 -----------------
% 来自《老饼讲解神经网络》www.bbbdata.com ,matlab版本：2018a
function MC_TSP()
clc;clear all;close all
rng(999)
global distMat;
cityLoc = [3.64,2.68 ;... %beijing
4.18,1.76 ;... %shanghai
3.71,2.60 ;... %tianjin
1.33,3.30 ;... %wulumuqi
4.20,2.96 ;... %shenyang
3.92,1.82 ;... %nanjing
2.55,1.64 ;... %chengdu
2.37,1.02 ;... %kunming
3.43,2.09 ;... %zhengzhou
3.54,0.70 ;... %xianggang
3.51,1.62 ;... %wuhan
3.44,0.80 ;... %guangzhou
3.24,2.77 ;... %huhehaote
2.38,2.32 ;... %xiling
2.56,2.24 ;... %lanzhou
3.01,2.03 ;... %xian
2.79,2.51 ;... %yinchuan
4.03,1.16 ;... %fuzhou
3.47,0.70 ;... %aomen
1.30,1.69] ; %lasha
distMat = dist(cityLoc') ; % 计算城市距离
N = size(cityLoc,1); % 城市个数
%---------------主流程------------------------------------------
select_city = 1; % 初始化起点城市
res_city = 2:N; % 未走的城市(rest_city)
base_test_num = 200; % 尝试的次数
%-------逐个确定下一个城市------------------
for i=2:N
res_n = length(res_city); % 可选城市个数
res_city_F = zeros(res_n,1); % 初始化各个可选城市的代价(若选该城市为下个城市，走完全程的代价)
test_num = res_n*base_test_num; % 本次抽样的次数
%-------计算选择各个城市的代价---------------------
for j =1:res_n % 计算可选城市的代价
select_city_tmp = [select_city,res_city(j)]; % 添加第j个城市到路径中,作为临时路径
rs_city_tmp = res_city; % 初始化临时剩余城市
rs_city_tmp(j) = []; % 删掉本次选择的城市
% 通过抽样来评估选择了第j个城市后,最终的路径代价
for k = 1:test_num % 假设选择该城市，之后的路线用test_num次随机选择，综合多次采样结果作为选该城市的代价
rand_idx = randperm(length(rs_city_tmp)); % 随机选择剩余的城市
cur_x = [select_city_tmp,rs_city_tmp(rand_idx)]; % 本次的完整城市路径
if (res_n>10) % 如果剩余城市较多时
res_city_F(j) = res_city_F(j) + calF(cur_x)/test_num; % 用平均值估值
else % 如果剩余城市较少,就用抽样中最佳的路径来评估
if(k==1) % 如果第一次抽样
res_city_F(j)= calF(cur_x); % 初始化最佳路径距离
else % 否则
res_city_F(j) = min(res_city_F(j),calF(cur_x)); % 更新最佳路径距离
end
end
end
end
%---------选择代价最小的城市作为下个城市------------------------
[~,select_idx] = min(res_city_F); % 找出哪个城市的代价最低
best_city = res_city(select_idx); % 选择代价最低的城市作为下个城市
select_city = [select_city,best_city]; % 更新已走城市
res_city(select_idx) = []; % 将本次选择的城市移出剩余城市
%----------画图-------------------------------
hold off
plot(cityLoc(:,1),cityLoc(:,2),'o','MarkerEdgeColor','k','MarkerFaceColor','y','MarkerSize',10,'LineWidth',2)
hold on
plot(cityLoc(select_city,1),cityLoc(select_city,2),'LineWidth',2)
drawnow
end
%-----------打印结果---------------------------------------
F = calF(select_city); % 计算最终的路径所需要代价
disp(['城市路径:',num2str(select_city)]) % 打印城市路径
disp(['路径需所距离:',num2str(F)]) % 打印路径所需要的的距离
end
%------------目标函数值计算方法------------------------
function d= calF(x)
global distMat;
d = distMat(x(end),x(1)); % 初始化总距离
for i=1:length(x)-1
d = d + distMat(x(i),x(i+1)); % 累加各个城市之间的距离
end
end运行结果
程序运行结果如下：
可以看到，该方法已经成功地找出了较为合理的路径，说明算法是有效的
编后语
由于没有找到一个非常清晰的蒙特卡罗求解TSP的算法流程或代码
于是笔者就只能按蒙特卡罗的算法思想设计和编写了一下，作为学习者的参考和借鉴
蒙特卡罗是非常强大的思想，小小TSP随便拿捏
End