下载文档原格式
智能优化实验报告基于遗传算法的TSP问题求解研究一、问题描述1、TSP问题的概述旅行商问题 (Traveling Salesman Problem，简称 TSP) 是一个经典的组合化问题。
它可以描述为：一个商品推销员要去若干个城市推销商品，从一个城出发需要经过所有城市后回到出发地，应如何选择行进路线以使总行程短。
从图论的角度看，该问题实质是在一个带权完全无向图中找一个权值最的小回路。
在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。
旅行商问题也是经典的组合数学的问题，生活中随处可见这类组合数学问题。
例如，计算下列赛制下的总的比赛次数:n个球队比赛，每队只和其他队比赛一次。
在纸上画一个网络，用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，一笔画出网络图。
一个邮递员从邮局出发，要走完他所管辖的街道，他应该选择什么样的路径，这就是著名的“中国邮递员问题”。
一个通调网络怎样布局最节省?美国的贝尔实验室和IBM公司都有世界一流的组合数学家在研究这个问题，这个问题直接关系到巨大的经济利益。
库房和运输的管理也是典型的组合数学问题，怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取。
上述的这些例子中，其中一部分就和旅行商问题有关系。
2、TSP问题研究意义解决旅行商问题有着极其重要的理论和现实意义。
从理论层面来讲，解TSP不仅为其他算法提供了思想方法平台，使这些算法广泛地应用于各种组合优化问题；而且经常被用来测试算法的优劣，如模拟退火算法、禁忌搜索、神经网络、进化算法等，都可用旅行商问题来测试。
从实际应用层面来讲，旅行商问题作为一个理想化的问题，尽管多数的研究成果不是为了直接的应用，但却被广泛地转化为许多组合优化问题，最直接的就是其在交通、物流和大规模生产中的应用。
3、TSP问题的解决TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。
![[物流管理]TSP旅行商问题（TravelingSalemanProblem）](https://img.taocdn.com/s1/m/7b6b1127b80d6c85ec3a87c24028915f804d84c0.png)
TSP旅行商问题（Traveling Saleman Problem）什么是旅行商问题旅行商问题（Traveling Saleman Problem，TSP）是VRP的特例，由于Gaery[1]已证明TSP 问题是NP难题，因此，VRP也属于NP难题。
旅行商问题（TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。
最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。
TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。
如何确定最短路线。
TSP问题最简单的求解方法是枚举法。
它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。
可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。
求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。
旅行商问题的历史旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。
TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP 成为一个知名且流行的问题。
旅行商问题的解法旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。
Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：1、途程建构法（Tour Construction Procedures）从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：1）最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。
旅行商问题旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。
最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。
目录目录旅行商问题 (1)目录 (1)1.简介 (1)2．研究历史 (2)3.问题解法 (2)4.解法思路 (2)途程建构法 (2)途程改善法 (2)合成启发法 (3)5.研究进展 (3)6.问题分析 (3)1.简介“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。
规则虽然简单，但在地点数目增多后求解却极为复杂。
以42个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。
多年来全球数学家绞尽脑汁，试图找到一个高效的算法。
TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。
如何确定最短路线。
TSP问题最简单的求解方法是枚举法。
它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。
可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。
求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。
2．研究历史旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。
TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。
3 旅行商问题3.1 旅行商问题概述3.1.1 旅行商问题的定义和数学模型① 定义旅行商问题(Traveling Salesman Problem ，简记TSP)是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现己归入所谓的NP 完全问题类，经典提法为：有一货物推销员要去若干个城市推销货物，从城市1出发，经其余各城市一次，然后回到城市1，问选择怎样的行走路线，才能使总行程最短（各城市间距离为己知）。
该问题在图论的意义下就是所谓的最小Hamilton 圈问题，由于在许多领域中都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。
遗憾的是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。
若设城市数目为n 时，那么组合路径数则为(n-1)!。
很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。
假设现在城市的数目增为20个，组合路径数则为(20-1)! ，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。
尽管现在计算机的计算速度大大提高，而且已有一些指数级的算法可精确地求解旅行商问题，但随着它们在大规模问题上的组合爆炸，人们退而求其次，转向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。
② 数学模型设(,)G V E =为赋权图，{1,2,}V n ="为顶点集，E 为边集，各顶点间距离为ij c ，已知(0,,,)ij ij c c i j V >=+∞∈，并设则旅行商问题的数学模型可写成如下的线性规划形式：ij ij i jMinZ c x ≠=∑1,(,)0,ij i j x ⎧=⎨⎩边在最优路线上其它,1,1,.1,{0,1},ij j i ij i jij i j S ij x i V x j V s t x K K V x i j V ≠≠∈⎧=∈⎪⎪=∈⎪⎨⎪≤−⊂⎪⎪∈∈⎩∑∑∑这里，K 为V 的所有非空子集，K 为集合K 中所含图G 的顶点个数。
TSP问题求解旅行商问题(traveling saleman problem,简称tsp)：已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。
如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，…,n)。
若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为：min l=σd(t(i),t(i+1))（i=1,…,n）旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。
一．遗传算法：初始化过程：用v1,v2,v3,…,vn代表所选n个城市。
定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。
适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)).评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).^(i-1) 。
旅行商问题
TSP,Travelling salesman problem
问题描述：
给定一系列点，以及各点之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。
问题实质：
哈密尔顿回路问题
NP完全问题
解决方法：
早期方法：分支定界法，线性规划法，动态规划法
近代方法：遗传算法，模拟退火法，蚁群算法，禁忌搜索算法，贪心算法，神经网络算法
空间数结构术语：
问题状态：在解空间树中的每一个结点确定所求问题的一个问题状态
状态空间：由根结点到其它结点的所有路径则确定了这个问题的状态空间解状态：表示一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组
答案状态：表示一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解
问题求解：
1.暴力求解：
运用枚举的思想，复杂度为O(n！)。
tsp问题旅⾏商问题(tsp问题)就是⼀个经销商从n个城市中的某⼀城市出发，不重复的⾛完其余的n-1个城市并回原出发点，求所有可能路径单中⾛出路径长度最短的⼀条。
本题假设旅⾏商从第⼀个城市出发。
解法:dfs+回溯#include <iostream>using namespace std;#define NUM 100int n;//图G的顶点数int m;//图G的边数int a[NUM][NUM];//图G的邻接矩阵int x[NUM] = {0}; //当前解int bestx[NUM];//最优解int cc = 0; //当前费⽤int bestc = 0; //当前最优值int NoEdge = -1; //⽆边标记int Visited[100];//访问标志int num = 0;int FirstArc(int t){for(int i = 1; i <= m; i++)if(a[t][i] != NoEdge)return i;return 0;}int NextArc(int t, int w){for(int p = w + 1; p <= m; p++)if(a[t][p] != NoEdge)return p;return 0;}void dfs(int t){int l, i;Visited[t] = 1;if(num == m && a[t][1] != NoEdge){if(cc + a[t][1] < bestc){bestc = cc + a[t][1];for(int s = 0; s < m; s++)bestx[s] = x[s];}}else{for(i = FirstArc(t); i != 0; i = NextArc(t, i))if(!Visited[i] && a[t][i] != NoEdge)if(cc + a[t][i] < bestc) //剪枝{x[num++] = i;cc += a[t][i];dfs(i);cc -= a[t][i];Visited[i] = 0;num--;}}}void tsp(int t){for(int i = 1; i <= m; i++)Visited[i] = 0;//保存第⼀个节点x[num++] = t;Visited[t] = 1;for(int q = FirstArc(t); q != 0; q = NextArc(t, q)) if(a[t][q] != NoEdge && !Visited[q]){x[num++] = q;cc += a[t][q];dfs(q);cc -= a[t][q]; //回溯Visited[q] = 0;num--;}}int main(){int s, e, t;scanf("%d%d", &m, &n);//初始化邻接矩阵for(int i = 1; i <= m; i++)for(int j = 1; j <= m; j++)a[i][j] = NoEdge; //表⽰两个节点不相连 for(int i = 1; i <= n; i++){scanf("%d%d%d", &s, &e, &t);a[s][e] = t;a[e][s] = t;}//初始化变量bestc = 1000;tsp(1);for(int i = 0; i < m; i++)printf("%d ", bestx[i]);printf("\nbestc=%d\n", bestc);return 0;}/*1 2 201 4 41 3 62 3 52 4 103 4 15*/。
