2022年TSP的人工智能求解问题

1、的人工智能求解TSP的人工智能求解问题摘要TSP（Traveling Salesman Problem）问题,又译为旅行商问题,是数学领域闻名问题之一； 假设有一个旅行商要拜望n 个城市,他必需挑选所要走的路径, 路径的限制是每个城市只能拜望一次,而且最终必需要回到原先动身的城市； 路径的挑选目标是要求得的路径路程和为所有路径和之中的最小值； 该问题可简化为一个图论问题：假设有一个图 G=V,E,其中 V 是顶点集, E 是边集,设 D=dij是由全部顶点 i和顶点 j（,）之间的距离所组成的 n*n 距离矩阵,旅行商问题就是求出一条通过全部顶点且每个顶点只通过一次的具有最短距离的回路； 本文

2、主要运用遗传算法, C 语言变成实现对经过的城市进行 Grefenstette编码,交叉和变异,之后对算法进行不断修正循环,得到一个最优解,即是最短距离；1 的人工智能求解问题假设有一个旅行商要拜望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.

3、1 G 1.5 2.9 H 3.4 2.1 I 3.7 3.6 J 2.6 2.5 2 符号说明 V 顶点的集合2 的人工智能求解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 问题分析这

4、可以归结为一个图论问题：给出一个图G=（V,E）,每个边 eijE,且每一个边 e 上都有非负权值 w（e）,查找一个 G的一个回路 C,使得 C不重复过定点 vi（i=1 ,2, n）, 使 C的总权 W（C）=w（e）（其中 eE）最小；3 的人工智能求解可以知道,总的旅程路线为组合数（n-1 ）！/2 ,TSP搜寻空间随着城市数 n 的增加而增大, 一般很难精确地求出其精确的最优解,因此利用遗传算法的思想对旅行商所经过的城市进行编码,将问题空间的数据映射成遗传空间的基因串结构数据；用遗传算法解决 TSP,一个旅程很自然地表示为 n 个城市的排列,但基于二进制编码的交叉和变异操作不能适用,

5、因此利用 Grefenstette 方法对其进行编码,对这些已经编码的数据, 再利用遗传算法常用的单点交叉对路径进行交叉变换,并且利用变异概率对路径进行进一步修正,5 模型建立 5.1 交叉模型的建立5.1.1 城市编码的设计从而得到接近的解；常规的交叉运算和变异运算使群体中产生一些不满意问题约束条件 或者无实际意义的巡回录像, 为了克服这种编码方法的缺点,基于对 各个城市的拜访次序,采纳由 Grefenstette 等提出的一种新的巡回 路线编码方法, 该方法可以使得任意的基因型个体都能够对应一条具 有实际意义的巡回路线,下面对这种新的编码方法进行介绍：对于一个旅行商问题的城市列表 为 T：

6、 T=t1 ,t2 ,t3 , ,ti, t n M,假定各个城市的一个拜访次序规定每拜访完一个城市,就从城市列表 M中将该城市删除,就用第i 个拜访的城市 ti 在全部未拜访的城市列表 M-t 1,t 2, t i-1 中对应位置序号 gi 就可以表示详细拜访哪个城市,如此处理玩 M中的全部4 的人工智能求解的城市；将全部的gi 排列在一起得到一个列表：G=（g1,g2, gn）就可以表示成一条巡回路线,它即为遗传算法的一个个体的基因型；为了便利运算,取 10 个城市：M=A B C D E F G H I J 现在有两条巡回旅行路线：Tx=A D B H F I J G E C Ty=B

7、C A D E J H I F G 依据上述 Grefenstette 以编码为所提出的编码方法,这两条巡回旅行路线可Gx= 1 3 1 5 3 4 4 3 2 1 Gy=2 2 1 1 1 5 3 3 1 1 5.2.2 单点交叉方法旅行商问题对于交叉算子的设计要求是：对于任意两条巡回路线进行交叉操作之后, 都能得到另外两条新的并且具有实际意义的巡回 路线；下面介绍本文即将使用的单点交叉：对于旅行商问题,使用 Grefenstette 等所提出的编码方法来表 示个体时, 个体基因和个体表现型之间具有一一对应的关系,特殊是 它使得经过遗传运算后得到的任意一个基因型个体都能够对应一条 具有实际意

8、义的巡回路线； 这样,就可以用基本遗传算法来求解旅行 商问题,而无需重新去开发一些位置重排序的遗传算子；这时,交叉 运算可以使用通常的单点交叉算子；所谓单点交叉可以懂得为下：5 的人工智能求解仍旧以取前十个城市,以所给出的两条巡回路线 Gx和 Gy为例,取单点交叉操作的交叉点在第 6 个和第 7 个基因座之间,就对 Gx和Gy进行进行交叉操作后可以得到两个新的个体 Gx=（131534|4321）Gy=（221115|3311）单点交叉后 : Gx1=131534|3311 Gy1=221115|4321 Gx1和 Gy1：此时,对其进行解码处理后 , 可以得到两条新的巡回路线Tx1=（A D

9、 B H F I G J C E）Tx2=B C A D E J I H G F 就以这种方法对题目所给的十个城市进行编码和解码；5.2 变异模型的建立遗传算法中的所谓的变异运算, 是指将个体染色体编码串中的某些基因值用该基因座的其他等位基因来替换,从而形成一个新的个体；遗传算法使用交叉算子已经接近或者有助于接近问题的最优解,但是仅仅使用交叉算子无法对搜寻空间的细节进行局部搜寻,使用变异算子来调整个体编码串中的部分基因值,部搜寻才能；就可以提高遗传算法的局本文采纳的是基础位变异（Simple Mutation）中的匀称变异（Uniform Mutation）,使用的是匀称变异算子,类似交叉操作

10、中选择父代的过程,在 rnext-city.=k 【29 】p=p-next; 【30 】return p; 【31 】/* 将种群中个体按代价从小到大排序 */ 【32 】【33 】void SortUnit groupunit_num N-1 轮【34 】 int i,j; 【35 】Unit temp,*p1,*p2; 【36 】forj=1;j=unit_num-1;j+ / 排序总共需进行【37 】 【38 】fori=1;ilengthp2-length / 总长度大的往后排【43 】 【44 】memcpy&temp,p1,sizeofUnit; 【45 】memcpyp1,p2

11、,sizeofUnit; 【46 】memcpyp2,&temp,sizeofUnit; 【47 】/end if 【48 】/end 一轮排序【49 】/end 排序【50 】ifgroup0.length length=0; 【58 】forj=1;jlength+=length_tablep-pathj-1p-pathj; 【61 】 【62 】p-length+=length_tablep-pathcity_num-1p-path0; 【63 】 【64 】/* 生成一个介于两整型数之间的随机整数*/ 9 的人工智能求解【65 】【66 】int RandomIntegerint lo

12、w,int high 【67 】【68 】 【69 】int rand_num; 【70 】double d; 【71 】d=doublerand%100/100.0; /d0&d1 【72 】rand_num=intd*high-low+1+low; 【73 】return rand_num; 【74 】 【75 】/* 输出当代种群中的每个个体 */ 【76 】void Print_optimumUnit groupunit_num,int k 【77 】 【78 】int i,j; 【79 】Unit *p; 【80 】printf 当前第 %d 代： n,k; 【81 】fori=0;

13、i=unit_num-1;i+ 【82 】 【83 】printf 第 %2d 代,个体 %2d ： ,k,i; 【84 】p=&groupi; 【85 】forj=0;jpathj; 【87 】printf 总路径长度为：%d n,p-length; 【88 】 【89 】 【90 】/* 输出最优个体 */ 【91 】void Print_bestoneUnit *bestone 【92 】 【93 】int i; 【94 】Unit *p=bestone; 【95 】printfnn 最优路径为： n; 【96 】fori=0;i,p-pathi; 【98 】printf%d 总路径长度

14、为：%d n,p-path0,p-length; 【99 】/* 交叉 */ 【100 】 void Cross_groupUnit *p1,Unit *p2,Unit *p3 【101 】int i,j,k,Cross_group_point; 【102 】int a,b,c; 【103 】int soncity_num; 【104 】Node *current1,*current2,*current3; 【105 】Node *top1,*top2,*top3; 【106 】Node *p; 【107 】/ 将三个父代路径改为单循环链表【108 】top1=current1=Node *m

15、allocsizeofNode; / 为第一个父代路径生成头一个10 的人工智能求解結点【109 】top1-city=p1-path0; *mallocsizeofNode; / 为其次个父代路径生成头一个【110 】top2=current2=Node 結点【111 】top2-city=p2-path0; *mallocsizeofNode; / 为第三个父代路径生成头一个【112 】top3=current3=Node 結点【113 】top3-city=p3-path0; / 生成三个父代路径的其他結点【114 】fori=1;inext=Node *mallocsizeofNode

16、; 【117 】【118 】current1=current1-next; / 链接第一个父代路径头尾结点【119 】current1-city=p1-pathi; 【120 】current2-next=Node *mallocsizeofNode; 【121 】current2=current2-next; 【122 】current2-city=p2-pathi; 【123 】current3-next=Node *mallocsizeofNode; 【124 】current3=current3-next; 【125 】current3-city=p3-pathi; 【126 】 【1

17、27 】current1-next=top1; 【128 】current2-next=top2; / 链接其次个父代路径头尾结点【129 】current3-next=top3; / 链接第三个父代路径头尾结点【130 】Cross_group_point=RandomInteger0,city_num-1; / 三交换启示交叉【131 】whileCross_group_point- / 将最优点存入son 【132 】current1=current1-next; 【133 】current2=search_sontop2,current1-next-city; 【134 】curren

18、t3=search_sontop3,current1-next-city; 【135 】fori=0;inext-city; 【138 】p=current1-next; / 从第一个父代路径链表中删除该最优点【139 】current1-next=p-next; / 从其次个父代路径链表中删除该最【140 】freep; 【141 】p=current2-next; 优点【142 】current2-next=p-next; / 从第三个父代路径链表中删除该最【143 】freep; 【144 】p=current3-next; 优点【145 】current3-next=p-next; 【

19、146 】freep; 11 的人工智能求解【147 】ifi=9break; / 比较最短踞离后,将三条父代路径【148 】a=length_tablesonicurrent1-next-city; 【149 】b=length_tablesonicurrent2-next-city; 【150 】c=length_tablesonicurrent3-next-city; 【151 】ifa=b&anext-city; 【153 】current3=search_soncurrent3,current1-next-city; 【154 】 【155 】else ifb=a&bnext-cit

20、y; 【157 】current3=search_soncurrent3,current2-next-city; 【158 】 【159 】else ifc=a&cnext-city; 【161 】current2=search_soncurrent2,current3-next-city; 【162 】 【163 】memcpyp1-path,son,sizeofp1-path; / 生成第一个子代路径【164 】Cross_group_point=RandomInteger0,city_num-1; / 生成其次个子代路径【165 】fork=0,i=Cross_group_point;i

21、pathk+=soni; 【167 】fori=0;ipathk+=soni; 【169 】Cross_group_point=RandomInteger0,city_num-1; / 生成第三个子代路径【170 】fork=0,i=Cross_group_point;ipathk+=soni; 【172 】fori=0;ipathk+=soni; 、【174 】Calculate_lengthp1; / 运算子代 p1 路径的总长度【175 】Calculate_lengthp2; / 运算子代 p2 路径的总长度【176 】Calculate_lengthp3; / 运算子代 p3 路径的

22、总长度【177 】 【178 】 /* 变异 */ 【179 】 void Varation_groupUnit *group,int gen_num 【180 】 【181 】int flag,i,j,k,temp; / 在进化后期,增大变异概率【182 】Unit *p; 【183 】flag=gen_num50.3*100*pv:100*pv; 【184 】whileflag- / 确定发生变异的个体【185 】 【186 】i=RandomInteger0,unit_num-1; 【187 】j=RandomInteger0,city_num-1; / 确定发生变异的位【188 】k=

23、RandomInteger0,city_num-1; / 变异【189 】p=&groupi; 12 的人工智能求解【190 】 temp=p-pathj; / 重新运算变异后路径的总长度【191 】p-pathj=p-pathk; 【192 】p-pathk=temp; 【193 】Calculate_lengthp; 【194 】【195 】 【196 】 /* 初始化最优值 */ 【197 】 void Initial_bestoneUnit *bestone 【198 】 【199 】bestone-length=RAND_MAX; 【200 】 【201 】 /* 初始化种群 */

24、【202 】 void Initial_groupUnit *group 【203 】 【204 】int i,j,k; 【205 】Unit *p; 【206 】fori=0;i=unit_num-1;i+ / 初始化种群里的 100 个个体【207 】 【208 】p=group+i; /p 指向种群的第 i 个个体【209 】forj=0;jpathj=RandomInteger0,city_num-1; 【213 】else 【214 】 【215 】p-pathj=RandomInteger0,city_num-1; 【216 】whilekpathj=p-pathk 【219 】 【220 】p-pathj=RandomInteger0,city_num-1; 【221 】k=0; 【222 】 【223 】else k+; 【224 】/end while 【225 】 【226 】/end for / 初始化路径【227 】Calculate_lengthp; / 运算该路径的总长度【228 】/end for / 初