1、实验六遗传算法求解TSP问题实验讲解实验六：遗传算法求解TSP问题实验一、 实验目的 熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影 响。用遗传算法对TSP问题进行了求解，熟悉遗传算法地算法流程， 证明遗传算法在求解TSP问题时具有可行性。二、 实验内容参考实验系统给出的遗传算法核心代码，用遗传算法求解 TSP的 优化问题，分析遗传算法求解不同规模 TSP问题的算法性能。对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算 法结果的影响。增加 1 种变异策略和 1 种个体选择概率分配策略，比较求解同一 TSP 问题时
2、不同变异策略及不同个体选择分配策略对算法结果的影 响。1.最短路径问题所谓旅行商问题（Travelling Salesman Problem , TSJP即最短路径问题， 就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通 路，这样的通路成为S点到T点的最短路径。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路 径，还需要知道某个顶点到其他任意顶点间的最短路径。 遗传算法方 法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法， 用 遗传算法解决这类问题， 没有太多的约束条件和有关解的限制， 因而 可以很快地求出任意两点间的最短路径以及一批次短路径。 假设平面上有 n
3、个点代表 n 个城市的位置 , 寻找一条最短的闭合路径 , 使得可以遍历每一个城市恰好一次。 这就是旅行商问题。 旅行商的路 线可以看作是对 n 个城市所设计的一个环形 , 或者是对一列 n 个城市 的排列。由于对 n 个城市所有可能的遍历数目可达 (n- 1)!个 , 因此解 决这个问题需要0(n!)的计算时间。假设每个城市和其他任一城市之 间都以欧氏距离直接相连。 也就是说 , 城市间距可以满足三角不等式 , 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接 距离。2.遗传算法遗传算法是由美国J.Holland教授于1975年在他的专著自然界和人 工系统的适应性 中首先提出的，
4、它是一类借鉴生物界自然选择和自 然遗传机制的随机化搜索算法。 通过模拟自然选择和自然遗传过程中 发生的繁殖、交叉和基因突变现象， 在每次迭代中都保留一组候选解， 并按某种指标从解群中选取较优的个体，利用遗传算子 (选择、交叉 和变异 )对这些个体进行组合，产生新一代的候选解群，重复此过程， 直到满足某种收敛指标为止。 遗传算法在本质上是一种不依赖具体问 题的直接搜索方法， 是一种求解问题的高效并行全局搜索方法。 其假 设常描述为二进制位串， 位串的含义依赖于具体应用。 搜索合适的假 设从若干初始假设的群体集合开始。 当前种群成员通过模仿生物进化 的方式来产生下一代群体，如随机变异和交叉。每一步
5、，根据给定的 适应度评估当前群体的假设， 而后使用概率方法选出适应度最高的假 设作为产生下一代的种子。下面介绍几个遗传算法的几个基本概念：（1） 染色体（Chromosome）:在使用遗传算法时，需要把问题的解 编成一个适合的码子。 这种具有固定结构的符号串既是染色体， 符号 串的每一位代表一个基因。 符号串的总位数成为染色体的长度， 一个 染色体就代表问题的一个解，每个染色体也被称为一个个体。（2） 群体（Population）:每代所产生的染色体总数成为群体，一个 群体包含了该问题在这一代的一些解的集合。（3） 适应度（Fitness）:对群体中每个染色体进行编码后，每个个体 对应一个具体
6、问题的解， 而每个解对应于一个函数值。 该函数值即适 应函数， 就是衡量染色体对环境适应度的指标， 也是反映实际问题的 目标函数 在前一代群体的基础上产生新一代群体的工作成为遗传操作， 基本的 遗传操作有：（1） 选择（Select）:按一定的概率从上代群体中选择 M对个体作为 双亲，直接拷贝到下一代，染色体不发生变化。（2） 交叉（Crossover）:对于选中进行繁殖的两个染色体 X，Y,以X， 丫为双亲作交叉操作，从而产生两个后代 X1, Y1.（ 3）变异（ Mutation ） 对于选中的群体中的个体（染色体） ，随机 选取某一位进行取反运算，即将该染色体码翻转。用遗传算法求解的过程
7、是根据待解决问题的参数集进行编码， 随机产 生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。 如果满足收敛条件，此种群为最好个体，否则，对产生的新一代群体 重新进行选择、交叉、变异操作，循环往复直到满足条件。遗传算法原型GA(Fit ness,Fit ness_threshold,p,r,m)Fitness适应度评分函数，为给定假设赋予一个评估分数Fit ness_threshold指定终止判据的阈值p:群体中包含的假设数量r:每一步中通过交叉取代群体成员的比例m:变异率初始化群体：P-随机产生的p个假设评估:对于P中的每一个h,计算Fitness(h)当maxFit ness(h
8、)Fit ness_threshold 做产生新的一代Ps:(1)选择:用概率方法选择P的(1-r)p个成员加入Ps从P中选择假设 hi的概率用下面公式计算(2)交叉:根据上面给出的：，从P中按概率选择r(p/2)对假设.对于每对假设,应用交叉算子产生两个后代把所有的后代加入Ps(3)变异:使用均匀的概率从Ps中选择m%的成员.对于选出的每个 成员,在它表示中随机选择一个为取反(4)更新:P Ps(5)评估:对于P中的每个h计算Fitness(h)从P中返回适应度最高的假设3.TSP问题的遗传算法设计与实现对于n个城市的问题，每个个体即每个解的长度为 n,用s行，t列的 pop矩阵，表示初始群
9、体，s表示初始群体的个数，t为n+1,矩阵的 每一行的前 n 个元素表示城市编码， 最后一个元素表示这一路径的长 度。城市的位置可以手动输入，使用一个 NX N矩阵D存储，D (i,j)代表城市i和城市j之间的距离。D(i,j)二sqrt(Xi-Xj)八2+(Yi-Yj)“2。 在TSP的求解中，可以直接用距离总和作为适应度函数。 个体的路径 长度越小，所得个体优越，距离的总和越大，适应度越小，进而探讨 求解结果是否最优。选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在 群体中个体适应度评估基础上。这里采用方法是最优保存方法。本实例中交叉采用部分匹配交叉策略， 先随机选取两个交叉点
10、，然后 将两交叉点中间的基因段互换，将互换的基因段以外的部分中与互换 后基因段中元素冲突的用另一父代的相应位置代替，直到没有冲突。变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作 变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则， 仍保留父代染色体。这有助于增加种群的多样性，避免早熟收敛(非 全局最优)。判断结束准则是固定指定了迭代的次数当算法达到迭代次数时， 算法结束，输出当前的最优解。在根据适配值计算并选择的时候，记录下 来的当前最优值，在变异后加入跟新的群体，保证新的迭代循环中TSP解越来越好(不会变差)。在选择的一种操作是拿最优的 K个替 换最差的K个个体，本例
11、是按适配值选择，并使群体数目变少，当每 次变异操作后，产生随机路径补充群体是群体数目不变，再次循环， 一定程度上防止因初始群体的选择问题而陷入局部最优。4.TSP问题的遗传算法的具体步骤解最短路径的遗传算法如下:Gen eratep (n);表示程序开始时要首先产生一个群体，群体个数为nEvaluatep(h);表示计算每个个体适应度，h是种群中的一个个体Repeat roof Ge nerati ons times重复下面的操作，直到满足条件为止Select p(h) from p(n-1)表示从前一代群体中选择一对双亲，用于交叉、 变异操作，P(n)代表第n代群体Crossover and
12、 mutati on p(n)进行交叉和变异操作Learni ngp( n);自学习过程Evaluatep(h)计算新生成的种群中每个个体的适应度End;流程图5遗传算法求解不同规模的TSP问题的算法性能(1)遗传算法执行方式说明：适应度值计算方法：当前路线的路径长度个体选择概率分配方法：适应度比例方法选择个体方法：轮盘赌选择交叉类型：PMX交叉变异类型：两点互换变异(2)实验模拟结果：城市个数时间(ms)51692510166301518833202259625241593030289353523940386084540032504375755477466058143655994270643
13、617571417 I L i i i i 0 6 IQ t5 20 25 30 35 40 J5 50 5S 60 65 ?D 75 BQ坡市孰罩图1-1(3)分析由图1-1可知，遗传算法执行时间随着 TSP问题规模的增大而增 大，并且大致为线性增长。五、不同参数下的计算结果对比(1)种群规模对算法结果的影响 实验次数：10最大迭代步数：100交叉概率：0.85变异概率：0.15表1-1种群规模适应度值最优路径1025.2644-5-8-7-6-3-1-0-9-22026.34282-9-1-0-3-6-7-5-8-43025.16521-3-6-7-5-8-4-2-9-05025.1652
14、0-1-3-6-7-5-8-4-2-98025.16529-0-1-3-6-7-5-8-4-210025.16521-0-9-2-4-8-5-7-6-315025.16525-8-4-2-9-0-1-3-6-720025.16521-3-6-7-5-8-4-2-9-025025.16523-1-0-9-2-4-8-5-7-630025.16525-8-4-2-9-0-1-3-6-7如表1-1所示，显然最短路径为25.1652m,最优路径为1-0-9-1-3-6-7-5-842或 3-1-0-9-2-4-8-5-7-6,注意到这是一圈，顺时针 或者逆时针都可以。当种群规模为 10, 20时，并没
15、有找到最优解。（2）交叉概率对算法结果的影响实验次数：15种群规模：25最大迭代步数：100变异概率：0.15实验结果：表1-2交叉概率最好适应度最差适应度平均适应度最优解运行时间0.00128.044736.656732.60029-2-6-0-5-4-87-3-13100.0127.093534.994332.14957-8-3-1-9-2-60-5-42600.128.044735.303331.93727-3-1-9-2-6-05-4-83000.1528.044734.117531.21830-548-7-3-19-2-62700.228.710833.951230.90353-1-
16、9-2-6-5-04-7-82800.2528.044735.162330.74561-3-7-8-4-5-06-2-92600.327.093531.994129.94288-3-1-9-2-6-05-4-72900.3527.093532.808530.99459-1-3-8-7-4-50-6-22700.427.093532.531330.15341-3-8-7-4-5-06-2-92790.4527.093533.201430.17578-3-1-9-2-6-05-4-74560.528.093433.630730.90265-0-2-6-9-1-38-7-46630.5527.093
17、533.523329.13041-9-2-6-0-5-47-8-35200.627.093533.251230.78363-1-9-2-6-0-5-5464-7-80.6528.044733.700330.9371548-7-3-1-92-6-05960.727.093532.092729.95029-1-3-8-7-4-50-6-25710.7528.044732.448830.36990-5-4-8-7-3-19-2-65590.827.093532.155129.93827-4-5-0-6-2-91-3-83580.8527.093534.539930.35945-0-6-2-9-1-3
18、8-7-43600.927.093532.627330.696-0-5-4-7-8-31-9-23750.9527.093532.467229.9196-2-9-1-3-8-74-5-0476(注:红色表示非最优解)在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解(3)变异概率对算法结果的影响实验次数：10种群规模：25最大迭代步数：100交叉概率：0.85实验结果:表1-3变异概率最好适应度最差适应度平均适应度最优解运行时间0.00129.471734.73232.49110-6-2-1-9-3-8-7-4-52450.0129.044634.659132.37148-4-5-0-
19、2-6-9-1-3-72740.128.093434.01130.94175-0-2-6-9-1-3-8-7-42500.1527.093532.09330.25686-0-5-4-7-8-3-1-9-22460.227.093532.234930.31448-7-4-5-0-6-2-9-1-32820.2527.093532.71830.15724-5-0-6-2-9-1-3-8-72450.327.093532.448830.28540-5-4-7-8-3-1-9-2-62520.3527.093533.316730.77481-3-8-7-4-5-0-6-2-92660.429.0446
20、34.370531.30412-0-5-4-8-7-3-1-9-63620.4527.093531.37429.68162-6-0-5-4-7-8-3438-1-90.527.093532.375230.22112-9-1-3-8-745-0-64310.5527.093533.381930.66231-3-8-7-4-5-0-6-2-94920.628.093433.251230.361-3-8-7-4-5-0-2-6-94170.6527.093532.749130.02013-1-9-2-6-0-5-4-7-84340.728.710832.423830.7851-3-8-7-4-0-5
21、-6-2-94320.7527.093531.892830.24511-9-2-6-0-5-4-7-8-34750.828.093431.613530.34719-1-3-8-7-4-5-0-2-63270.8529.66233.239231.15852-9-1-3-7-8-4-0-5-63140.928.044732.038730.41520-5-4-8-7-3-1-9-2-63960.9528.044731.303630.00679-1-3-7-8-4-5-0-6-2436又表1-3可知，当变异概率过大或过低都将导致无法得到最优解注：(2) (3)的实验数据与(1)的实验数据不同，详见附录
22、六、不同变异策略和个体选择概率分配策略对算法结果的影响(1)两点互换变异与插入变异的比较：试验次数(CASNUM)： 10城市数(POINTCNT):10种群规模(POPSIZE)： 100最大迭代步数(GENERATIONS):。交叉概率(PC)： 0.85变异概率(PM):0.15选择个体方法：轮盘赌选择交叉类型：PMX交叉个体选择概率分配方法：适应度比例方法a.变异类型：两点互换变异表1-4两点互换变异程序结果序号最好适应度最差适应度平均适应度最优解运行时间128.093430.422929.08916-2-0-547-8-31-91199227.093531.141728.98414-
23、5-0-6-2-9-1-3-16788-7327.093530.422829.06040-547-8-3-1-92-61940427.093530.370328.87871-3-8-7-4-5-0-62-91756527.093531.061929.07553-1-9-2-6-0-5-47-81885627.093531.158929.39422-6-0-5-4-7-8-31-91936728.044731.061929.76486-2-9-1-3-7-8-45-01772829.044631.347529.84154-5-0-2-6-9-1-37-81980927.093530.614329
24、.0590-6-2-9-1-3-8-74-519401027.093530.558529.08119-2-6-0-5-4-7-83-118721127.093531.017129.42640-5-4-7-8-3-1-92-615171227.093531.303629.24141-9-2-6-0-5-4-78-315411327.093532.025529.07890-6-2-9-1-3-8-74-515171427.093531.51628.89060-6-2-9-1-3-8-74-513451527.093530.422829.02266-0-547-8-3-19-213771627.09
25、3530.408128.90810-6-2-9-1-3-8-74-518531727.093530.408129.33167-8-3-1-9-2-6-05-415221827.093530.020328.52431-3-8-7-4-5-0-62-916011928.044731.140429.5672-9-1-3-7-8-4-50-616092027.093531.141729.53597-4-5-0-6-2-9-13-81311平均值27.336130.878229.18771657b.变异类型：插入变异表1-5插入变异程序结果最好适应最差适平均适运行序号度应度应度最优解时间31.47528
26、.8452-6-0-547-8-3-1127.093533-9138828.9165-0-6-2-9-1-3-8-7227.093529.6628-4135529.6631-9-2-6-0-5-4-7-8327.0935128.902-3163730.52429.5114-5-0-6-2-9-1-3-7428.044719-8116431.05729.4682-6-0-5-4-7-8-3-1527.093552-9124528.5542-6-0-5-4-7-8-3-1627.093529.6626-9122230.8203-1-9-2-6-0-5-4-8728.0447529.748-7114
27、830.52429.3901-9-2-6-0-5-4-7-8827.093517-3174228.6870-6-2-9-1-3-8-7-4927.093530.4238-5206430.4085-0-6-2-9-1-3-8-71027.0935128.72-4151829.3284-5-0-6-2-9-1-3-81127.093531.3742-712401227.093530.52328.5541-3-8-7-4-5-0-6-212044-930.82029.0500-6-2-9-1-3-8-7-41327.093558-5173431.11729.5900-547-8-3-1-9-21427.093575-6153229.1904-5
