基于某遗传算法解决TSP问题.doc

《基于某遗传算法解决TSP问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于遗传算法解决TSP问题摘要题目要求给出环游全国全部省会的最短路径方案，是传统的TSP问题，本文将图表数据数字化后，将其转变成为线性规划问题，进而采取遗传算法用Matlab求解出理论上的最短路径与路线图。通过第一问求出的路线顺序结合实际情况求解出实际情况下的最短路径与最短时间。针对第一问，首先建立基本TSP模型，求出其线性规划方程组，用Matlab对地图做出基本处理，求出其像素坐标的矩阵。将省会城市初始化为种群数据，用遗传算法求解出模型最优解，即最短路径大小与旅游城市顺序。针对第二问，由于遗传算法求出的是近似最优解，以及实际道路情况不可能是直线距离，所以理论数据与实际有一定差

2、别。将旅行顺序求解出后，需要根据实际道路情况重新求解出最短路径大小，并根据题目所给条件求解出最短时间。根据实际情况，求得最后的最短路径长度为20402.9公里，时间为45天。题目中给出城市转化为图集，一共有33个顶点，数据较大，用Dijkstra算法和Floyd算法虽然答案可能更精确，但数据处理量大，时间复杂度高。采用遗传算法可以得到近似最优解，并且精简了时间复杂度。关键词：最短路径TSP问题线性规划遗传算法一、问题重述如果从出发，要想开车走遍全国所有的省会城市，而且在到了每个省会城市以后都必须住一晚，第二天早上才能出发，安全起见每天开车时间最多在8小时左右，车速视实际路况而定

3、，一般高速公路可以取平均车速100公里/小时左右，不是高速公路平均车速取60公里/小时左右，从出发要走遍所有省会城市以后回到，开车里程最少需要多少公里？最少需要多少时间？（暂不考虑省）二、问题分析题目要求求出最短路径与时间是典型的TSP问题，即要用最短的总路径走遍所有城市，此处需要设立一个二元组，并且求出一个点的邻接矩阵。根据经典的TSP模型，得出一般的线性规划方程组。解TSP模型的一般算法有Dijkstra算法和Floyd算法，由于TSP问题是典型的NP难题，其可能路径数目与城市总数目n是呈指数型增长，并不适合用以上两种算法。另外常用来解决TSP问题的退火算法受概率和退火过程

4、影响，可能运算起来十分缓慢。为了精简时间复杂度，故选取了遗传算法将图形数据初始为种群数据进行计算。并且随着种群规模的增大，其结果越逼近最优值。对于第二问，最短时间的计算，按照第一问求出的最优路线行走，并且结合实际高速公路分布与走向来计算最短路径的真实值，并且统计出高速公路与普通公路的实际数值。题目中给出了车辆在高速公路上行车速度为100km/h，普通公路上为60km/h，统计出实际数值后，计算出总行车时间即可得出最短时间。一、基本假设1.题目给出的速度符合实际。2.无论第一天何时到达，第二天均会离开该城市。3.每天开车时间为8小时左右，对于9到10小时可以开到的城市均算为8小时

5、左右，不需要中途休息。4.开车行程在10小时以后的，每天开车八小时即停下并有地方休息。5.第一问用TSP模型求解时，所有城市之间全部算为直线相连。四、符号说明Z：走遍所有省会城市的最短路径长度C：路网有向图矩阵；：从节点i到节点j的弧，∈C；：路段的长度；M：种群个数N：染色基因个数（即城市个数）c：迭代次数Pc：交叉概率Pm：变异概率len：某组解的总距离minlen：该次迭代中的最短距离maxlen：该次迭代中的最长距离m：适应度归一化淘汰加速指数四、模型建立与求解5.1线性规划的约束条件与目标函数：已设为两城市之间的距离，根据TSP问题的一般约束条件可知，记为赋权图G=(

6、V,E)，V为顶点集，E为边集，各顶点间的距离已知。设目标函数与约束条件：5.2遗传算法前的基本处理将全国城市的经纬度制成表格，用excel将其制成散点图，方便接下来的数据处理与运算。城市东经北纬城市东经北纬城市东经北纬116.4639.92123.3841.811328.21117.239.13114.4838.03114.3130.52121.4831.22112.5337.87113.2323.16106.5429.59101.7436.56110.3520.0291.1129.9711736.65103.7336.03乌鲁木齐87.6843.77113.6534.761

7、08.9534.27106.2738.47118.7832.04104.0630.67呼和浩特111.6540.82117.2731.86106.7126.57108.3322.84120.1930.26102.7325.04126.6345.75119.326.08114.122.2125.3543.88115.8928.68澳门113.3322.13用基于Java的经纬度坐标与地图容器像素坐标转换器，求出33个省会城市的像素坐标如下：1.2.3.4.5.6.7.8.9.10.11.121