基于遗传算法解决TSP问题 - 图文

基于遗传算法解决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： 路网有向图矩阵；

cij：从节点i到节点j的弧，cij∈C； dij：路段cij的长度； M： 种群个数

N： 染色基因个数（即城市个数） c： 迭代次数 Pc： 交叉概率 Pm： 变异概率 len： 某组解的总距离 minlen：该次迭代中的最短距离 maxlen：该次迭代中的最长距离 m： 适应度归一化淘汰加速指数

五、模型建立与求解

5.1线性规划的约束条件与目标函数：

已设dij为两城市之间的距离，根据TSP问题的一般约束条件可知，记为赋权图G=(V,E)，V为顶点集，E为边集，各顶点间的距离dij已知。设

.......若(i,j)在回路路径上?0， xij??.......其他?1，

目标函数与约束条件： mixZ???di?1j?1nnijij

x?n??xij?1,i?V?j?1?n?xij?1,j?Vs.t??i?1????xij?S?1,?S?V,2?S?n?1?i?Sj?S?xij??0,1??5.2遗传算法前的基本处理

将全国城市的经纬度制成表格，用excel将其制成散点图，方便接下来的数

据处理与运算。 城市 东经 北纬 城市 东经 北纬 城市 东经 北京 116.46 39.92 沈阳 123.38 41.8 长沙 113 天津 117.2 39.13 石家庄 114.48 38.03 武汉 114.31 上海 121.48 31.22 太原 112.53 37.87 广州 113.23 重庆 106.54 29.59 西宁 101.74 36.56 海口 110.35 拉萨 91.11 29.97 济南 117 36.65 兰州 103.73 乌鲁木齐 87.68 43.77 郑州 113.65 34.76 西安 108.95 银川 106.27 38.47 南京 118.78 32.04 成都 104.06 呼和浩特 111.65 40.82 合肥 117.27 31.86 贵阳 106.71 南宁 108.33 22.84 杭州 120.19 30.26 昆明 102.73 哈尔滨 126.63 45.75 福州 119.3 26.08 香港 114.1 北纬 28.21 30.52 23.16 20.02 36.03 34.27 30.67 26.57 25.04 22.2 长春 125.35 43.88 南昌 115.89 28.68 澳门 113.33 22.13

用基于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?minlenfit?(1?)m

maxlen?minlen?0.001

3.4 变异操作

采用变异操作解 决同一问题。算法核心思路是，在每次迭代中，解的个体随机按 4 个为 1 组，每组中只保留最优解，然后对此最优解进行左右翻转、交换、向前移位三种变异操作，生成三个新个体，再参与下次迭代。整个算法不需要计算归一化适应度。在此算法中，每次迭代淘汰率固定为 75%，三种变异操作覆盖面比较广，直 接以最短距离为适应函数，省去每次适应度的计算。初始值种群数目设为 500， 进化迭代次数为 5000，寻得最优解为 1295.72。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库基于遗传算法解决TSP问题 - 图文在线全文阅读。