《工程结构反理论》课程设计分析.doc

《工程结构反分析理论》 课程设计 题目：旅行商问题的遗传算法解答 专业： 姓名： 指导教师： 学号： 日期：2015年月日 目录 1 旅行商问题概述 3 1.1 旅行商问题简介 3 1.2 旅行商问题的研究意义 3 1.3 旅行商问题的数学模型 3 1.4 旅行商问题的解法 4 2 遗传算法概述 5 2.1遗传算法简介 5 2.2 遗传算法的特点 5 2.3遗传算法的运算过程 6 3 遗传算法求解旅行商问题的研究及MATLAB程序设计 6 3.1初始化群体 7 3.2 个体适应度计算 7 3.3 比例选择操作 7 3.4 交叉操作 9 3.5 变异操作 10 4.结果评价 10 5.结语 11  1 旅行商问题概述 1.1 旅行商问题简介 旅行商问题(Trvaeling salesman Porblem,简称TSP)是威廉·哈密尔顿爵士和英国数学家克克曼(T.P.Kirkman)于19世纪初提出的一个数学问题。这是一个典型的NP完全性问题。其简单描述为：已知n个城市之间的相互距离,现有一旅行商要遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发的城市。应如何选择巡回路径，以使其旅行路线的总长度最短。 1.2 旅行商问题的研究意义 TSP是最有代表性的优化组合问题之一,它的应用已逐步渗透到交通运输、电路板线路设计以及物流配送等领域。在大规模生产过程中,寻找最短路径能有效地降低成本,减少交通费用，节约时间，充分利用有限的资源。这类问题的解决还可以延伸到其他行业中去,如运输业、后勤服务业等。然而,由于TSP会产生组合爆炸的问题,因此寻找切实可行的简化求解方法就成为问题的关键。 1.3 旅行商问题的数学模型 从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。假设有一个图G=（V，E），其中V是顶点集，E是边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸。 G=（V，E）为一个带权图，V=｛1，2，…,n｝为顶点集，E=｛eij=(i,j)|i,j∈V，i≠j｝为边集。dij(i,j∈V，i≠j)为顶点i到顶点j的距离，其中dij＞0且dij≠∞，同时dij=dji(i,j∈V),则经典TSP（Classical TSP,CTSP）的数学模型为： （1） （2） （3） （4） （5） 其中xij为决策变量，xij=1表示商人行走的路线包括从城市i到城市j的路径，xij=0表示商人没有选择这条路径。公式（1）为目标函数，求经过所有顶点的回路的最小距离；公式（3）要求商人从城市i出来只有一次；公式（4）要求商人走入城市i只有一次；公式（2）-（4）限定回路上每个顶点仅有一条入边和一条出边，即每个城市只经过一次。|S|为图S的顶点数，K是V的全部非空子集，|K|是集合K中包含图G的全部顶点个数。公式（5）限定在回路中不出现子回路。模型实质上是在一个带权图中求一条Hamilton回路。若对所有i,j,k∈V，不等式均成立，则称该问题是满足三角不等式的。 1.4 旅行商问题的解法 人们在考虑解决这个问题时,一般首先想到的最原始的一种方法就是:列出每一条可供选择的路线(即对给定的城市进行排列组合),计算出每条路线的总里程,最后从中选出一条最短的路线假设现在给定的4个城市分别为A、B、C和D,各城市之间的距离为己知数(如图1所示)。我们可以通过一个组合的状态空间图来表示所有的组合(如图2所示)。从图中不难看出,可供选择的路线共有6条,从中很快可以选出一条总距离最短的路线。由此推算,若设城市数目为n时,那么组合路径数则为(n一1)！。很显然，当城市数目不多时要找到最短距离的路线并不难,但随着城市数目的不断增大,组合路线数将呈指数级数规律急剧增长,以至达到无法计算的地步,这就是所谓的“组合爆炸问题”。 多年来对于求解TSP问题出现了很多传统方法，早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法和动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式