本站原创文章，转载请说明来自《老饼讲解-深度学习》www.bbbdata.com
TSP问题（Traveling Salesman Problem）是一个经典的组合优化问题，它旅行商如何走完所有城市才能最短
本文讲解TSP问题的描述，并展示TSP问题的特点、数学表示方式，并展示一个求解TSP问题的代码示例
通过本文，可以快速了解TSP问题是什么，有什么特点，以及求解TSP问题的常用方法，以及如何求解TSP问题
本节介绍TSP旅行商问题是什么，以及它的特点
TSP旅行商问题
TSP（Traveling Salesman Problem，旅行销售商)问题如下：
现有N个城市 ，旅行商需求穿过每个城市，最终回到出发城市
则旅行商问题为：如何寻找一条路径，使旅行总距离最小
TSP问题的数学表述
假设有5个城市，用矩阵D表示城市之间的距离
代表第i个城市到第j个城市的距离
路径X可以表示为序列形式：
它代表先到城市1，再到城市5，再到3.....最后由4回到1
而总距离就是按这顺序行走的总距离
使用以上表示 ，则旅行商TSP问题可以理解为：求一 个1到N的组合X,令总距离F最小
✍️TSP问题的经典性
TSP问题有两个特有的经典特点
1. 不能穷举
它的解空间是非常大的，这就不能用一般的穷举法来寻找最优解
如果有N个城市，那么就会有(N-1)！个解，N=15时，(15-1)!就约等于871亿
2. x与f(x)的非纯数学性
它的目标函数 和解 而更倾向于一系列描述性计算
而不是一般问题那样具有严格的数值表达式，这导致它不能用梯度下降一类的算法来求解
本节展示用智能算法求解TSP问题的一个例子
TSP问题的求解方法
TSP问题的求解方法往往使用智能优化算法求解，例如模拟退火、遗传算法、蚁群算法等
这类智能优化算法以启发式搜索为核心，可以求得TSP问题的优秀解
用模拟退火算法求解TSP问题的代码实现如下：
%代码说明：模拟退火求解TSP旅行商问题
%来自《老饼讲解神经网络》www.bbbdata.com ,matlab版本：2018a
clc;clear all;close all
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); % 城市个数
rng(888) % 为方便复现结果,设定随机种子
x = randperm(N); % 随机初始化解
E = distMat(x(end),x(1)); % 初始化解的能量
for i=1:length(x)-1
E = E+ distMat(x(i),x(i+1)); % 累加各个城市之间的距离
end
%---------温度初始化可用此方法(取N次邻域能量差均值的10倍)-------------
dE = 0; % 计算平均能量差
try_cn = 20; % 尝试次数
for k = 1:try_cn
pair = randperm(N); % 随机生成要交换的两个位置
new_x = x; % 将旧解copy过来
new_x([pair(1),pair(2)])= new_x([pair(2),pair(1)]); % 将选择的两个位置进行交换
new_E = distMat(new_x(end),new_x(1)); % 初始化新解的能量
for i = 1:length(x)-1
new_E = new_E+ distMat(new_x(i),new_x(i+1)); % 累加各个城市之间的距离
end
dE = dE+ abs(E-new_E)/try_cn; % 更新平均能量差
end
teamp = dE*10 ; % 温度初始化
%-------------外循环-------------------------
for t=1:100
minE = E; % 记录本轮的最小能量
maxE = E; % 记录本轮的最大能量
%--------内循环-----------------------
for k =1:500
pair = randperm(N); % 随机生成要交换的两个位置
new_x = x; % 将旧解copy过来
new_x([pair(1),pair(2)])= new_x([pair(2),pair(1)]); % 将选择的两个位置进行交换
new_E = distMat(new_x(end),new_x(1)); % 初始化新解的能量
for i = 1:length(x)-1
new_E = new_E+ distMat(new_x(i),new_x(i+1)); % 累加各个城市之间的距离
end
%--------按概率接受新解-------------------
if(exp((E-new_E)/teamp)>rand()) % 如果接受新解
x = new_x; % 更新解
E = new_E; % 更新能量
minE = min(E,minE); % 更新本轮的最小能量
maxE = max(E,maxE); % 更新本轮的最大能量
end
end
disp(['第',num2str(t),'轮:E=',num2str(E),',teamp:',num2str(teamp)]) % 打印当前温度与能量
disp([' minE=',num2str(minE),',maxE:',num2str(maxE)]) % 打印最小最大能量
hold off
plot(cityLoc(:,1),cityLoc(:,2),'o','MarkerEdgeColor','k','MarkerFaceColor','y','MarkerSize',10,'LineWidth',2)
hold on
plot(cityLoc([x,x(1)],1),cityLoc([x,x(1)],2))
drawnow
%--------降温，并检查是否退出循环--------
teamp = teamp*0.9; % 降温
if((maxE-minE)/maxE<0.001) % 如果最优最差解并没太大差异
break % 退出循环
end
end运行结果如下：
可以看到，本例中共有20个城市，路径的组合有(20-1)！种 ，是非常庞大的
但经模拟退火求解，可以看到，在有限的步数内，已经能自动找到一条不错的路径了
好了，以上就是TSP旅行商问题的介绍，以及它的求解示例了~
End
