TSP的人工智能求解..doc

TSP的人工智能求解问题 摘要 TSP（Traveling Salesman Problem）问题，又译为旅行商问题，是数学领域著名问题之一。假设有一个旅行商要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后必须要回到原来出发的城市。路径的选择目标是要求得的路径路程和为所有路径和之中的最小值。该问题可简化为一个图论问题：假设有一个图G=(V,E)，其中V是顶点集，E是边集，设D=(dij)是由所有顶点i和顶点j（ｉ，ｊ＝１，２．．．．ｎ）之间的距离所组成的n*n距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。本文主要运用遗传算法，C语言变成实现对经过的城市进行Grefenstette编码，交叉和变异，之后对算法进行不断修正循环，得到一个最优解，即是最短距离。 关键字：TSP 图论 遗传算法 Grefenstette C 交叉 变异 １问题的重述 1.1背景 TSP（Traveling Salesman Problem）问题，又译为旅行商问题，是一个比较古老的问题，最早可以追溯到1759年Euler提出的骑士旅行问题。1984年，由美国兰德公司推动，TSP成为近代组合优化领域的一个经典难题。应该说，TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题，它已经被证明属于NP难题。 很多实际应用问题，例如印制电路板的钻孔路线方案、连锁店的货物配送录像等，经过简化处理后，均可以建模为旅行商问题，因而对旅行商问题的求解方法的研究也具有重要的应用价值。此外，研究求解旅行上问题的遗传算法，对促进遗传算法本身的发展也具有重要的意义。 1.2问题 假设有一个旅行商要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后必须要回到原来出发的城市。路径的选择目标是要求所得的路径路程为所有路径之中的最小值。 本文中，给出具体的10个城市的坐标，利用遗传算法的思想对该问题进行具体求解。10个城市TSP坐标如下： 城市 X Y A 5.2 1.5 B 4.2 3.6 C 4.7 2.8 D 4.1 2.2 E 0.9 3.8 F 4.7 6.1 G 1.5 2.9 H 3.4 2.1 I 3.7 3.6 J 2.6 2.5 2符号说明 V 顶点的集合 C 过所有定点且最后回到起点的圈（不重复） vi 第i个城市的标号， i=1，2，…10 E 所有边的集合 eij vi到vj 的边 wij vi到 vj 距离 Tx 巡回路线 G 巡回路线城市列表 gi 在访问中第n个被访问的城市 W 圈C的权值 Pm 变异概率 F 适应度函数 3模型假设 1 假设n取10已经足够大 2 假设变异概率以及适应度函数准确 3 在交叉运算和变异运算中没有产生不满足约束条件或无实际意义 的巡回路线 4 设随机选取的r准确 4问题分析 这可以归结为一个图论问题：给出一个图G=（V，E），每个边eij∈E，且每一个边e上都有非负权值w（e），寻找一个G的一个回路C，使得C不重复过定点vi（i=1，2，…n）,使C的总权W（C）=∑w（e）（其中e∈E）最小。 我们可以知道，总的旅程路线为组合数（n-1）！/2 ，TSP有哪些信誉好的足球投注网站空间随着城市数n的增加而增大，我们一般很难精确地求出其精确的最优解，因此我们利用遗传算法的思想对旅行商所经过的城市进行编码，将问题空间的数据映射成遗传空间的基因串结构数据。用遗传算法解决TSP，一个旅程很自然地表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用，因此我们利用Grefenstette方法对其进行编码，对这些已经编码的数据，我们再利用遗传算法常用的单点交叉对路径进行交叉变换，并且利用变异概率对路径进行进一步修正，从而得到接近的解。 5模型建立 5.1 交叉模型的建立 5.1.1城市编码的设计 常规的交叉运算和变异运算使群体中产生一些不满足问题约束条件或者无实际意义的巡回录像，为了克服这种编码方法的缺点，基于对各个城市的访问顺序，我们采用由Grefenstette等提出的一种新的巡回路线编码方法，该方法可以使得任意的基因型个体都能够对应一条具有实际意义的巡回路线，下面对这种新的编码方法进行介绍： 对于一个旅行商问题的城市列表M，假定各个城市的一个访问顺序为T： T=(t1 ,t2 ,t3 ,…,ti,…tn) 规定每访问完一个城市，就从城市列表M中将该城市删除，则用第i个访问的城市ti在所有未访问的城市列表M-{t1,t2,…ti-