【代码】蒙特卡罗算法求解TSP

本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com

TSP问题是优化问题中的经典问题，

本文分析如何应用蒙特卡罗算法求解TSP问题，并展示算法求解效果

通过本文，可以进一步感受蒙特卡罗算法的强大之处

    01. 蒙特卡罗算法求解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的代价
三、选择代价最小的城市作为下个城市                                   
重复二、三，直到走完所有城市   

    02. 蒙特卡罗算法求解TSP-代码实现    

本节提供蒙特卡罗算法求解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