基于遗传算法解决TSP 问题
摘要
题目要求给出环游全国全部省会的最短路径方案，是传统的TSP 问题，本文将图表数据数字化后，将其转变成为线性规划问题，进而采取遗传算法用Matlab 求解出理论上的最短路径与路线图。通过第一问求出的路线顺序结合实际情况求解出实际情况下的最短路径与最短时间。
针对第一问，首先建立基本TSP 模型，求出其线性规划方程组，用Matlab 对地图做出基本处理，求出其像素坐标的矩阵。将省会城市初始化为种群数据，用遗传算法求解出模型最优解，即最短路径大小与旅游城市顺序。
针对第二问，由于遗传算法求出的是近似最优解，以及实际道路情况不可能是直线距离，所以理论数据与实际有一定差别。将旅行顺序求解出后，需要根据实际道路情况重新求解出最短路径大小，并根据题目所给条件求解出最短时间。 根据实际情况，求得最后的最短路径长度为20402.9公里，时间为45天。
题目中给出城市转化为图集，一共有33个顶点，数据较大，用Dijkstra 算法和Floyd 算法虽然答案可能更精确，但数据处理量大，时间复杂度高。采用遗传算法可以得到近似最优解，并且精简了时间复杂度。
关键词： 最短路径 TSP问题 线性规划 遗传算法
一、问题重述
如果从杭州出发，要想开车走遍全国所有的省会城市，而且在到了每个省会城市以后都必须住一晚，第二天早上才能出发，安全起见每天开车时间最多在8小时左右，车速视实际路况而定，一般高速公路可以取平均车速100公里/小时左右，不是高速公路平均车速取60公里/小时左右，从杭州出发要走遍所有省会城市以后回到杭州，开车里程最少需要多少公里？最少需要多少时间？（暂不考虑台湾省）
二、问题分析
题目要求求出最短路径与时间是典型的TSP 问题，即要用最短的总路径走遍所有城市，此处需要设立一个二元组(V (G ), E (G )) ，并且求出一个点的邻接矩阵。根据经典的TSP 模型，得出一般的线性规划方程组。解TSP 模型的一般算法有Dijkstra 算法和Floyd 算法，由于TSP 问题是典型的NP 难题，其可能路径数目与城市总数目n 是呈指数型增长，并不适合用以上两种算法。另外常用来解决TSP 问题的退火算法受概率和退火过程影响，可能运算起来十分缓慢。为了精简时间复杂度，故选取了遗传算法将图形数据初始为种群数据进行计算。并且随着
种群规模的增大，其结果越逼近最优值。
对于第二问，最短时间的计算，按照第一问求出的最优路线行走，并且结合实际高速公路分布与走向来计算最短路径的真实值，并且统计出高速公路与普通公路的实际数值。题目中给出了车辆在高速公路上行车速度为100km/h，普通公路上为60km/h，统计出实际数值后，计算出总行车时间即可得出最短时间。
三、基本假设
1. 题目给出的速度符合实际。
2. 无论第一天何时到达，第二天均会离开该城市。
3. 每天开车时间为8小时左右，对于9到10小时内可以开到的城市均算为8小时左右，不需要中途休息。
4. 开车行程在10小时以后的，每天开车八小时即停下并有地方休息。 5. 第一问用TSP 模型求解时，所有城市之间全部算为直线相连。
四、符号说明
Z ： 走遍所有省会城市的最短路径长度 C ： 路网有向图矩阵；
c ij ：从节点i 到节点j 的弧，c ij ∈C ； d ij ：路段c ij 的长度； M ： 种群个数
N ： 染色基因个数（即城市个数） c ： 迭代次数 Pc ： 交叉概率 Pm ： 变异概率 len ： 某组解的总距离 minlen ：该次迭代中的最短距离 maxlen ：该次迭代中的最长距离 m ： 适应度归一化淘汰加速指数
五、模型建立与求解
5.1线性规划的约束条件与目标函数：
已设d ij 为两城市之间的距离，根据TSP 问题的一般约束条件可知，记为赋权图G=(V,E)，V 为顶点集，E 为边集，各顶点间的距离d ij 已知。设
....... 若(i , j ) 在回路路径上⎧0，
x ij =⎨
....... 其他⎩1，
目标函数与约束条件： mixZ =
∑∑d
i =1j =1
n n
ij ij
x
⎧n
⎪∑x ij =1, i ∈V ⎪j =1⎪n
⎪x ij =1, j ∈V s . t ⎨∑i =1⎪
⎪∑∑x ij ≤S -1, ∀S ∈V , 2≤S ≤n -1⎪i ∈S j ∈S
⎪x ij ∈{0, 1}⎩
5.2遗传算法前的基本处理
将全国城市的经纬度制成表格，用excel 将其制成散点图，方便接下来的数
用基于Java 的经纬度坐标与地图容器像素坐标转换器，求出33个省会城市的像素坐标如下：
1. 西藏 2. 云南 3. 四川 4. 青海 5. 宁夏 6. 甘肃 7. 内蒙古 8. 黑龙江 9. 吉林 10. 辽宁 11. 北京 12 天津 13. 河北 14. 山东 15. 河南 16. 山西 17. 陕西 18. 安徽 19. 江苏 20. 上海 21. 浙江 22. 江西 23. 湖北 24. 湖南 25, 贵州 26. 广西 27. 广东 28. 福建 29. 海南 30. 澳门 31. 香港 32. 重庆 33. 新疆 像素坐标如下：
Columns 1 through 11
100 187 201 187 221 202 258 352 346 336 290 211 265 214 158 142 165 121 66 85 106 127 Columns 12 through 22
297 278 296 274 265 239 302 316 334 325 293 135 147 158 177 148 182 203 199 206 215 233 Columns 23 through 33
280 271 221 233 275 322 250 277 286 220 104 216 238 253 287 285 254 315 293 290 226 77
5.3遗传算法求解最优值
1. 程序初始化
程序首先读入 33 个省会城市坐标，计算任意两个城市的距离； 设置遗传算法控制参数。
clear all;clc;clf;
load('testdata.mat'); nlen=length(x1); xy=[x1;y1]';
n = 500; %种群数目
C = 5000; %进化迭代次数
m=2; %适应度归一化淘汰加速指数，取值不宜太大 alpha=0.8; %淘汰保护指数，范围0~1，为1时关闭保护 a = meshgrid(1:nlen); %生成 n x n矩阵
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),nlen,nlen); %计算城市距离矩阵
遗传算法对求解问题本身是一无所知的，这里采用随机生成初始化种群，如 下：
[N,NN]=size(dmat);
farm=zeros(n,N); %用于存储种群 for i=1:n
farm(i,:)=randperm(N); %随机生成初始化种群 end
2 计算适应度
本程序目标函数为经过 33 省会的总距离，适应度与目标函数的正相关，取 值范围 0~1，适应度计算公式为：
len -min len
fit =(1-) m
max len -min len +0. 001
3.4 变异操作
采用变异操作解 决同一问题。算法核心思路是，在每次迭代中，解的个体随机按 4 个为 1 组，每组中只保留最优解，然后对此最优解进行左右翻转、交换、向前移位三种变异操作，生成三个新个体，再参与下次迭代。整个算法不需要计算归一化适应度。在此算法中，每次迭代淘汰率固定为 75%，三种变异操作覆盖面比较广，直 接以最短距离为适应函数，省去每次适应度的计算。初始值种群数目设为 500， 进化迭代次数为 5000，寻得最优解为 1295.72。
5.4算法求解结果
图一 散点图最优表示
图二 仿真图表示
5.4根据实际情况的求解答案
路线：
杭州——上海——南京——合肥——武汉——南昌——长沙——重庆——成都——西安——郑州——济南——天津——沈阳——长春——哈尔滨——北京——石家庄——太原——呼和浩特——银川——兰州——西宁——乌鲁木齐——拉萨——昆明——贵阳——南宁——海口——澳门——广州——香港——福州——杭州
最终的最优解，最短路径长度为20402.9公里，时间为45天。
六、模型评价
本文采用MATLAB 实现遗传算法求解TSP 问题，对结果进行了分析。遗传算法是一种智能优化算法。该模型最大的缺点是，求出的不是最优解，而是近似最优解。同时，在做该模型时，是通过经纬度计算，算出的距离接近于两地直线距离。而真实情况中，大部分公路都不是笔直的，而是弯弯曲曲的，因此该模型求解答案与真实值有差距。同时，建最短时间模型过程中，忽略了很多客观的不定因素，比如天气问题等，会使正常计划受到一定的影响。还有驶入高速前的一段公路上的速度也被近似看成高速车速。但是本模型用区域性划分和动态分析法解决游遍全国的省会城市、直辖市、香港、澳门，相对于传统的动态规划解法，达到了省时、简便的效果，大大降低了计算的复杂性。我们还需再靠近实际情况，再精确该模型，减少误差。
七、参考文献
[1]铁菊红，彭辉：一种改进的基于高斯分布拟合的提取标志点像素坐标方法。Computer and Modernization，2008（4）。
[2]解晨，韦雄亦：模拟退火算法和遗传算法的比较与思考。电脑知识与技术，2013,9（19）。
[3]王勇：用遗传算法求解中国旅行商问题。哈尔滨商业大学学报：自然科学版，2005（4）。
[4]刘英：遗传算法中适应度函数的研究。兰州工业高等专科学校学报，2006.9，vol13（3）。
[5]周凯，宋全军，邬学军：数学建模竞赛与提高，图与网络模型。
[6] 王剑文，戴光明，谢柏桥，张全元。求解 TSP 问题算法综述[J]。计算机 工程与科学.2008(02)。
八、附录
基于Java 的经纬度坐标与地图容器像素坐标转换器
经纬度坐标与地图容器像素坐标相互转换
地图经纬度坐标：(鼠标左键在地图上单击获取经纬度坐标)
X： Y：
地图容器像素坐标：
X： Y：
变异法核心代码
for p = 4:4:pop_size
rtes = pop(rand_pair(p-3:p),:);
dists = total_dist(rand_pair(p-3:p));
[ignore,idx] = min(dists);
best_of_4_rte = rtes(idx,:);
ins_pts = sort(ceil(n*rand(1,2))); %生成 1x2 每一列元素
%按照升序排列矩阵
I = ins_pts(1);
J = ins_pts(2);
for k = 1:4 %保留最佳个体，繁殖三个新个体
tmp_pop(k,:) = best_of_4_rte;
switch k
case 2 %左右翻转
tmp_pop(k,I:J) = fliplr(tmp_pop(k,I:J));
case 3 %交换
tmp_pop(k,[I J]) = tmp_pop(k,[J I]);
case 4 %向前移动一位
tmp_pop(k,I:J) = tmp_pop(k,[I+1:J I]);
otherwise
end
end
new_pop(p-3:p,:) = tmp_pop;
end
pop = new_pop;
基于遗传算法解决TSP 问题
摘要
题目要求给出环游全国全部省会的最短路径方案，是传统的TSP 问题，本文将图表数据数字化后，将其转变成为线性规划问题，进而采取遗传算法用Matlab 求解出理论上的最短路径与路线图。通过第一问求出的路线顺序结合实际情况求解出实际情况下的最短路径与最短时间。
针对第一问，首先建立基本TSP 模型，求出其线性规划方程组，用Matlab 对地图做出基本处理，求出其像素坐标的矩阵。将省会城市初始化为种群数据，用遗传算法求解出模型最优解，即最短路径大小与旅游城市顺序。
针对第二问，由于遗传算法求出的是近似最优解，以及实际道路情况不可能是直线距离，所以理论数据与实际有一定差别。将旅行顺序求解出后，需要根据实际道路情况重新求解出最短路径大小，并根据题目所给条件求解出最短时间。 根据实际情况，求得最后的最短路径长度为20402.9公里，时间为45天。
题目中给出城市转化为图集，一共有33个顶点，数据较大，用Dijkstra 算法和Floyd 算法虽然答案可能更精确，但数据处理量大，时间复杂度高。采用遗传算法可以得到近似最优解，并且精简了时间复杂度。
关键词： 最短路径 TSP问题 线性规划 遗传算法
一、问题重述
如果从杭州出发，要想开车走遍全国所有的省会城市，而且在到了每个省会城市以后都必须住一晚，第二天早上才能出发，安全起见每天开车时间最多在8小时左右，车速视实际路况而定，一般高速公路可以取平均车速100公里/小时左右，不是高速公路平均车速取60公里/小时左右，从杭州出发要走遍所有省会城市以后回到杭州，开车里程最少需要多少公里？最少需要多少时间？（暂不考虑台湾省）
二、问题分析
题目要求求出最短路径与时间是典型的TSP 问题，即要用最短的总路径走遍所有城市，此处需要设立一个二元组(V (G ), E (G )) ，并且求出一个点的邻接矩阵。根据经典的TSP 模型，得出一般的线性规划方程组。解TSP 模型的一般算法有Dijkstra 算法和Floyd 算法，由于TSP 问题是典型的NP 难题，其可能路径数目与城市总数目n 是呈指数型增长，并不适合用以上两种算法。另外常用来解决TSP 问题的退火算法受概率和退火过程影响，可能运算起来十分缓慢。为了精简时间复杂度，故选取了遗传算法将图形数据初始为种群数据进行计算。并且随着
种群规模的增大，其结果越逼近最优值。
对于第二问，最短时间的计算，按照第一问求出的最优路线行走，并且结合实际高速公路分布与走向来计算最短路径的真实值，并且统计出高速公路与普通公路的实际数值。题目中给出了车辆在高速公路上行车速度为100km/h，普通公路上为60km/h，统计出实际数值后，计算出总行车时间即可得出最短时间。
三、基本假设
1. 题目给出的速度符合实际。
2. 无论第一天何时到达，第二天均会离开该城市。
3. 每天开车时间为8小时左右，对于9到10小时内可以开到的城市均算为8小时左右，不需要中途休息。
4. 开车行程在10小时以后的，每天开车八小时即停下并有地方休息。 5. 第一问用TSP 模型求解时，所有城市之间全部算为直线相连。
四、符号说明
Z ： 走遍所有省会城市的最短路径长度 C ： 路网有向图矩阵；
c ij ：从节点i 到节点j 的弧，c ij ∈C ； d ij ：路段c ij 的长度； M ： 种群个数
N ： 染色基因个数（即城市个数） c ： 迭代次数 Pc ： 交叉概率 Pm ： 变异概率 len ： 某组解的总距离 minlen ：该次迭代中的最短距离 maxlen ：该次迭代中的最长距离 m ： 适应度归一化淘汰加速指数
五、模型建立与求解
5.1线性规划的约束条件与目标函数：
已设d ij 为两城市之间的距离，根据TSP 问题的一般约束条件可知，记为赋权图G=(V,E)，V 为顶点集，E 为边集，各顶点间的距离d ij 已知。设
....... 若(i , j ) 在回路路径上⎧0，
x ij =⎨
....... 其他⎩1，
目标函数与约束条件： mixZ =
∑∑d
i =1j =1
n n
ij ij
x
⎧n
⎪∑x ij =1, i ∈V ⎪j =1⎪n
⎪x ij =1, j ∈V s . t ⎨∑i =1⎪
⎪∑∑x ij ≤S -1, ∀S ∈V , 2≤S ≤n -1⎪i ∈S j ∈S
⎪x ij ∈{0, 1}⎩
5.2遗传算法前的基本处理
将全国城市的经纬度制成表格，用excel 将其制成散点图，方便接下来的数
用基于Java 的经纬度坐标与地图容器像素坐标转换器，求出33个省会城市的像素坐标如下：
1. 西藏 2. 云南 3. 四川 4. 青海 5. 宁夏 6. 甘肃 7. 内蒙古 8. 黑龙江 9. 吉林 10. 辽宁 11. 北京 12 天津 13. 河北 14. 山东 15. 河南 16. 山西 17. 陕西 18. 安徽 19. 江苏 20. 上海 21. 浙江 22. 江西 23. 湖北 24. 湖南 25, 贵州 26. 广西 27. 广东 28. 福建 29. 海南 30. 澳门 31. 香港 32. 重庆 33. 新疆 像素坐标如下：
Columns 1 through 11
100 187 201 187 221 202 258 352 346 336 290 211 265 214 158 142 165 121 66 85 106 127 Columns 12 through 22
297 278 296 274 265 239 302 316 334 325 293 135 147 158 177 148 182 203 199 206 215 233 Columns 23 through 33
280 271 221 233 275 322 250 277 286 220 104 216 238 253 287 285 254 315 293 290 226 77
5.3遗传算法求解最优值
1. 程序初始化
程序首先读入 33 个省会城市坐标，计算任意两个城市的距离； 设置遗传算法控制参数。
clear all;clc;clf;
load('testdata.mat'); nlen=length(x1); xy=[x1;y1]';
n = 500; %种群数目
C = 5000; %进化迭代次数
m=2; %适应度归一化淘汰加速指数，取值不宜太大 alpha=0.8; %淘汰保护指数，范围0~1，为1时关闭保护 a = meshgrid(1:nlen); %生成 n x n矩阵
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),nlen,nlen); %计算城市距离矩阵
遗传算法对求解问题本身是一无所知的，这里采用随机生成初始化种群，如 下：
[N,NN]=size(dmat);
farm=zeros(n,N); %用于存储种群 for i=1:n
farm(i,:)=randperm(N); %随机生成初始化种群 end
2 计算适应度
本程序目标函数为经过 33 省会的总距离，适应度与目标函数的正相关，取 值范围 0~1，适应度计算公式为：
len -min len
fit =(1-) m
max len -min len +0. 001
3.4 变异操作
采用变异操作解 决同一问题。算法核心思路是，在每次迭代中，解的个体随机按 4 个为 1 组，每组中只保留最优解，然后对此最优解进行左右翻转、交换、向前移位三种变异操作，生成三个新个体，再参与下次迭代。整个算法不需要计算归一化适应度。在此算法中，每次迭代淘汰率固定为 75%，三种变异操作覆盖面比较广，直 接以最短距离为适应函数，省去每次适应度的计算。初始值种群数目设为 500， 进化迭代次数为 5000，寻得最优解为 1295.72。
5.4算法求解结果
图一 散点图最优表示
图二 仿真图表示
5.4根据实际情况的求解答案
路线：
杭州——上海——南京——合肥——武汉——南昌——长沙——重庆——成都——西安——郑州——济南——天津——沈阳——长春——哈尔滨——北京——石家庄——太原——呼和浩特——银川——兰州——西宁——乌鲁木齐——拉萨——昆明——贵阳——南宁——海口——澳门——广州——香港——福州——杭州
最终的最优解，最短路径长度为20402.9公里，时间为45天。
六、模型评价
本文采用MATLAB 实现遗传算法求解TSP 问题，对结果进行了分析。遗传算法是一种智能优化算法。该模型最大的缺点是，求出的不是最优解，而是近似最优解。同时，在做该模型时，是通过经纬度计算，算出的距离接近于两地直线距离。而真实情况中，大部分公路都不是笔直的，而是弯弯曲曲的，因此该模型求解答案与真实值有差距。同时，建最短时间模型过程中，忽略了很多客观的不定因素，比如天气问题等，会使正常计划受到一定的影响。还有驶入高速前的一段公路上的速度也被近似看成高速车速。但是本模型用区域性划分和动态分析法解决游遍全国的省会城市、直辖市、香港、澳门，相对于传统的动态规划解法，达到了省时、简便的效果，大大降低了计算的复杂性。我们还需再靠近实际情况，再精确该模型，减少误差。
七、参考文献
[1]铁菊红，彭辉：一种改进的基于高斯分布拟合的提取标志点像素坐标方法。Computer and Modernization，2008（4）。
[2]解晨，韦雄亦：模拟退火算法和遗传算法的比较与思考。电脑知识与技术，2013,9（19）。
[3]王勇：用遗传算法求解中国旅行商问题。哈尔滨商业大学学报：自然科学版，2005（4）。
[4]刘英：遗传算法中适应度函数的研究。兰州工业高等专科学校学报，2006.9，vol13（3）。
[5]周凯，宋全军，邬学军：数学建模竞赛与提高，图与网络模型。
[6] 王剑文，戴光明，谢柏桥，张全元。求解 TSP 问题算法综述[J]。计算机 工程与科学.2008(02)。
八、附录
基于Java 的经纬度坐标与地图容器像素坐标转换器
经纬度坐标与地图容器像素坐标相互转换
地图经纬度坐标：(鼠标左键在地图上单击获取经纬度坐标)
X： Y：
地图容器像素坐标：
X： Y：
变异法核心代码
for p = 4:4:pop_size
rtes = pop(rand_pair(p-3:p),:);
dists = total_dist(rand_pair(p-3:p));
[ignore,idx] = min(dists);
best_of_4_rte = rtes(idx,:);
ins_pts = sort(ceil(n*rand(1,2))); %生成 1x2 每一列元素
%按照升序排列矩阵
I = ins_pts(1);
J = ins_pts(2);
for k = 1:4 %保留最佳个体，繁殖三个新个体
tmp_pop(k,:) = best_of_4_rte;
switch k
case 2 %左右翻转
tmp_pop(k,I:J) = fliplr(tmp_pop(k,I:J));
case 3 %交换
tmp_pop(k,[I J]) = tmp_pop(k,[J I]);
case 4 %向前移动一位
tmp_pop(k,I:J) = tmp_pop(k,[I+1:J I]);
otherwise
end
end
new_pop(p-3:p,:) = tmp_pop;
end
pop = new_pop;