TSP的人工智能求解问题

《TSP的人工智能求解问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ＴＳＰ的人工智能求解TSP的人工智能求解问题摘要TSP（TravelingSalesmanProblem）问题，又译为旅行商问题，是数学领域著名问题之一。假设有一个旅行商要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后必须要回到原来出发的城市。路径的选择目标是要求得的路径路程和为所有路径和之中的最小值。该问题可简化为一个图论问题：假设有一个图G=(V,E)，其中V是顶点集，E是边集，设D=(dij)是由所有顶点i和顶点j（ｉ，ｊ＝１，２．．．．ｎ）之间的距离所组成的n*n距离矩阵，旅行商

2、问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。本文主要运用遗传算法，C语言变成实现对经过的城市进行Grefenstette编码，交叉和变异，之后对算法进行不断修正循环，得到一个最优解，即是最短距离。19ＴＳＰ的人工智能求解１问题假设有一个旅行商要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后必须要回到原来出发的城市。路径的选择目标是要求所得的路径路程为所有路径之中的最小值。本文中，给出具体的10个城市的坐标，利用遗传算法的思想对该问题进行具体求解。10个城市TSP

3、坐标如下：城市XYA5.21.5B4.23.6C4.72.8D4.12.2E0.93.8F4.76.119ＴＳＰ的人工智能求解G1.52.9H3.42.1I3.73.6J2.62.52符号说明V顶点的集合C过所有定点且最后回到起点的圈（不重复）vi第i个城市的标号，i=1，2，…10E所有边的集合eijvi到vj的边wijvi到vj距离Tx巡回路线G巡回路线城市列表gi在访问中第n个被访问的城市W圈C的权值Pm变异概率F适应度函数19ＴＳＰ的人工智能求解3模型假设1假设n取10已经足够大2假设变异概率以及适应度函数准确3

4、在交叉运算和变异运算中没有产生不满足约束条件或无实际意义的巡回路线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的增加而增大，一般很难精确地求出其精确的最优解，因此利用遗传算法的思想对旅行商所经过的城市进行编码，将问题空间的数据映射成遗传空间的

5、基因串结构数据。用遗传算法解决TSP，一个旅程很自然地表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用，因此利用Grefenstette方法对其进行编码，对这些已经编码的数据，再利用遗传算法常用的单点交叉对路径进行交叉变19ＴＳＰ的人工智能求解换，并且利用变异概率对路径进行进一步修正，从而得到接近的解。5模型建立5.1交叉模型的建立5.1.1城市编码的设计常规的交叉运算和变异运算使群体中产生一些不满足问题约束条件或者无实际意义的巡回录像，为了克服这种编码方法的缺点，基于对各个城市的访问顺序，采用由Grefe

6、nstette等提出的一种新的巡回路线编码方法，该方法可以使得任意的基因型个体都能够对应一条具有实际意义的巡回路线，下面对这种新的编码方法进行介绍：对于一个旅行商问题的城市列表M，假定各个城市的一个访问顺序为T：T=(t1,t2,t3,…,ti,…tn)规定每访问完一个城市，就从城市列表M中将该城市删除，则用第i个访问的城市ti在所有未访问的城市列表M-{t1,t2,…ti-1}中对应位置序号gi就可以表示具体访问哪个城市，如此处理玩M中的所有的城市。将所有的gi排列在一起得到一个列表：G=（g1,g2,…gn）就可以表

7、示成一条巡回路线，它即为遗传算法的一个个体的基因型。为了方便运算，取10个城市：M=(ABCDEFGHIJ)19ＴＳＰ的人工智能求解现在有两条巡回旅行路线：Tx=(ADBHFIJGEC)Ty=(BCADEJHIFG)按照上述Grefenstette所提出的编码方法，这两条巡回旅行路线可以编码为Gx=(1315344321)Gy=(2211153311)5.2.2单点交叉方法旅行商问题对于交叉算子的设计要求是：对于任意两条巡回路线进行交叉操作之后，都能得到另外两条新的并且具有实际意义的巡回路线。下面介绍本文即将使用的单点交

8、叉：对于旅行商问题，使用Grefenstette等所提出的编码方法来表示个体时，个体基因和个体表现型之间具有一一对应的关系，特别是它使得经过遗传运算后得到的任意一个基因型个体都能够对应一条具有实际意义的巡回路线。这样，就可以用基本遗传算法来求解旅行商问题，而无需重新去开发一些位置重排序的遗传算子。这时，交叉运算可以使