神经网络-一篇入门

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

作者 : 老饼 发表日期 : 2023-05-30 02:22:40 更新日期 : 2023-11-20 18:14:17
本站原创文章,转载请说明来自《老饼讲解-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 






联系老饼