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

基于遗传算法解决TSP问题摘要题目要求给出环游全国全部省会的最短路径方案是传统的TSP问题本文将图表数据数字化后将其转变成为线性规划问题进而采取遗传算法用Matlab求解出理论上的最短路径与路线图。通过第一问求出的路线顺序结合实际情况求解出实际情况下的最短路径与最短时间。针对第一问首先建立基本TSP模型求出其线性规划方程组用Matlab对地图做出基本处理求出其像素坐标的矩阵。将省会城市初始化为种群数据用遗传算法求解出模型最优解即最短路径大小与旅游城市顺序。针对第二问由于遗传算法求出的是近似最优解以及实际道路情况不可能是直线距离所以理论数据与实际有一定差别。将旅行顺序求解出后需要根据实际道路情况重新求解出最短路径大小并根据题目所给条件求解出最短时间。根据实际情况求得最后的最短路径长度为20402.9公里时间为45天。题目中给出城市转化为图集一共有33个顶点数据较大用Dijkstra算法和Floyd算法虽然答案可能更精确但数据处理量大时间复杂度高。采用遗传算法可以得到近似最优解并且精简了时间复杂度。关键词：最短路径TSP问题线性规划遗传算法问题重述如果从杭州出发要想开车走遍全国所有的省会城市而且在到了每个省会城市以后都必须住一晚第二天早上才能出发安全起见每天开车时间最多在8小时左右车速视实际路况而定一般高速公路可以取平均车速100公里/小时左右不是高速公路平均车速取60公里/小时左右从杭州出发要走遍所有省会城市以后回到杭州开车里程最少需要多少公里？最少需要多少时间？（暂不考虑台湾省）问题分析题目要求求出最短路径与时间是典型的TSP问题即要用最短的总路径走遍所有城市此处需要设立一个二元组并且求出一个点的邻接矩阵。根据经典的TSP模型得出一般的线性规划方程组。解TSP模型的一般算法有Dijkstra算法和Floyd算法由于TSP问题是典型的NP难题其可能路径数目与城市总数目n是呈指数型增长并不适合用以上两种算法。另外常用来解决TSP问题的退火算法受概率和退火过程影响可能运算起来十分缓慢。为了精简时间复杂度故选取了遗传算法将图形数据初始为种群数据进行计算。并且随着种群规模的增大其结果越逼近最优值。对于第二问最短时间的计算按照第一问求出的最优路线行走并且结合实际高速公路分布与走向来计算最短路径的真实值并且统计出高速公路与普通公路的实际数值。题目中给出了车辆在高速公路上行车速度为100km/h普通公路上为60km/h统计出实际数值后计算出总行车时间即可得出最短时间。基本假设题目给出的速度符合实际。无论第一天何时到达第二天均会离开该城市。每天开车时间为8小时左右对于9到10小时内可以开到的城市均算为8小时左右不需要中途休息。开车行程在10小时以后的每天开车八小时即停下并有地方休息。第一问用TSP模型求解时所有城市之间全部算为直线相连。符号说明Z：走遍所有省会城市的最短路径长度C：路网有向图矩阵；：从节点i到节点j的弧∈C；：路段的长度；M：种群个数N：染色基因个数（即城市个数）c：迭代次数Pc：交叉概率Pm：变异概率len：某组解的总距离minlen：该次迭代中的最短距离maxlen：该次迭代中的最长距离m：适应度归一化淘汰加速指数模型建立与求解5.1线性规划的约束条件与目标函数：已设为两城市之间的距离根据TSP问题的一般约束条件可知记为赋权图G=(VE)V为顶点集E为边集各顶点间的距离已知。设目标函数与约束条件：5.2遗传算法前的基本处理将全国城市的经纬度制成表格用excel将其制成散点图方便接下来的数据处理与运算。城市东经北纬城市东经北纬城市东经北纬北京116.4639.92沈阳123.3841.8长沙11328.21天津117.239.13石家庄114.4838.03武汉114.3130.52上海121.4831.22太原112.5337.87广州113.2323.16重庆106.5429.59西宁101.7436.56海口110.3520.02拉萨91.1129.97济南11736.65兰州103.7336.03乌鲁木齐87.6843.77郑州113.6534.76西安108.9534.27银川106.2738.47南京118.7832.04成都104.0630.67呼和浩特111.6540.82合肥117.2731.86贵阳106.7126.57南宁108.3322.84杭州120.1930.26昆明102.7325.04哈尔滨126.6345.75福州119.326.08香港114.122.2长春125.3543.88南昌115.8928.68澳门113.3322.13用基于Java的经纬度坐标与地