实验六：遗传算法求解TSP问题实验

1、精品文档实验六：遗传算法求解TSP问题实验一、实验目的熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解 TSP问题的流程并测试主要参数对结果的影响。用遗传算法对 TSP问题进行了求解，熟悉遗传算法地算法流程，证明遗传算法在求解 TSP问题时具有可行性。二、实验内容参考实验系统给出的遗传算法核心代码，用遗传算法求解 TSP的优化问题，分析遗传算法求解不同规模 TSP问题的算法性能。对于同一个 TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。增加 1 种变异策略和 1 种个体选择概率分配策略，比较求解同一 TSP 问题时不同变异策略及不同个体选择分配策略

2、对算法结果的影响。1. 最短路径问题所谓旅行商问题 (Travelling Salesman Problem , TSP)，即最短路径问题，就是在给定的起始点S到终止点 T 的通路集合中， 寻求距离最小的通路，这样的通路成为S 点到 T 点的最短路径。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。遗传算法方。1欢迎下载精品文档法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法， 用遗传算法解决这类问题， 没有太多的约束条件和有关解的限制， 因而可以很快地求出任意两点间的最短路径以及一批次短路径。假设平面上有 n 个点代表 n

3、个城市的位置 , 寻找一条最短的闭合路径 , 使得可以遍历每一个城市恰好一次。 这就是旅行商问题。 旅行商的路线可以看作是对 n 个城市所设计的一个环形 , 或者是对一列 n 个城市的排列。由于对 n 个城市所有可能的遍历数目可达 (n- 1)! 个, 因此解决这个问题需要 0(n!) 的计算时间。假设每个城市和其他任一城市之间都以欧氏距离直接相连。 也就是说 , 城市间距可以满足三角不等式 , 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。2. 遗传算法遗传算法是由美国 J.Holland 教授于 1975 年在他的专著自然界和人工系统的适应性 中首先提出的， 它是一类借鉴

4、生物界自然选择和自然遗传机制的随机化搜索算法。 通过模拟自然选择和自然遗传过程中发生的繁殖、 交叉和基因突变现象， 在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子 ( 选择、交叉和变异 ) 对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 遗传算法在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。其假设常描述为二进制位串，位串的含义依赖于具体应用。搜索合适的假设从若干初始假设的群体集合开始。 当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。每一步，根。2欢迎下载精品文档据给定的

5、适应度评估当前群体的假设， 而后使用概率方法选出适应度最高的假设作为产生下一代的种子。下面介绍几个遗传算法的几个基本概念：（ 1）染色体（ Chromosome）：在使用遗传算法时，需要把问题的解编成一个适合的码子。 这种具有固定结构的符号串既是染色体， 符号串的每一位代表一个基因。 符号串的总位数成为染色体的长度， 一个染色体就代表问题的一个解，每个染色体也被称为一个个体。（ 2）群体（Population ）：每代所产生的染色体总数成为群体，一个群体包含了该问题在这一代的一些解的集合。（ 3）适应度（ Fitness ）：对群体中每个染色体进行编码后，每个个体对应一个具体问题的解， 而每个

6、解对应于一个函数值。 该函数值即适应函数，就是衡量染色体对环境适应度的指标， 也是反映实际问题的目标函数在前一代群体的基础上产生新一代群体的工作成为遗传操作， 基本的遗传操作有：（ 1）选择（Select ）：按一定的概率从上代群体中选择 M对个体作为双亲，直接拷贝到下一代，染色体不发生变化。（2）交叉（ Crossover ）：对于选中进行繁殖的两个染色体X，Y，以X，Y 为双亲作交叉操作，从而产生两个后代X1，Y1.（ 3）变异（ Mutation ）：对于选中的群体中的个体（染色体） ，随机选取某一位进行取反运算，即将该染色体码翻转。用遗传算法求解的过程是根据待解决问题的参数集进行编码，

7、 随机产生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。3欢迎下载精品文档如果满足收敛条件，此种群为最好个体，否则，对产生的新一代群体重新进行选择、交叉、变异操作，循环往复直到满足条件。遗传算法原型：GA(Fitness,Fitness_threshold,p,r,m)Fitness:适应度评分函数 , 为给定假设赋予一个评估分数Fitness_threshold:指定终止判据的阈值p: 群体中包含的假设数量r: 每一步中通过交叉取代群体成员的比例m:变异率初始化群体 :P 随机产生的p 个假设评估 : 对于 P 中的每一个 h, 计算 Fitness(h)当maxFitness(

8、h)<Fitness_threshold,做产生新的一代Ps:(1) 选择 : 用概率方法选择 P 的(1-r)p 个成员加入 Ps. 从 P 中选择假设 hi 的概率用下面公式计算 :(2) 交叉 : 根据上面给出的, 从 P中按概率选择 r(p/2) 对假设 .对于每对假设 <h1，h2>, 应用交叉算子产生两个后代. 把所有的后代加入 Ps(3) 变异 : 使用均匀的概率从 Ps 中选择 m%的成员 . 对于选出的每个成员 , 在它表示中随机选择一个为取反(4) 更新 :P Ps(5) 评估 : 对于 P 中的每个 h 计算 Fitness(h)。4欢迎下载精品文档从

9、P中返回适应度最高的假设3. TSP 问题的遗传算法设计与实现对于 n 个城市的问题，每个个体即每个解的长度为n，用 s 行, t列的 pop 矩阵，表示初始群体， s 表示初始群体的个数， t 为 n+1，矩阵的每一行的前 n 个元素表示城市编码， 最后一个元素表示这一路径的长度。城市的位置可以手动输入，使用一个 N×N 矩阵 D 存储， D（ i ， j ） 代 表城 市i和城市j之间 的 距 离。D（ i ， j ）=sqrt( （Xi-Xj ）.2+(Yi-Yj).2)。在 TSP的求解中，可以直接用距离总和作为适应度函数。 个体的路径长度越小，所得个体优越，距离的总和越大，

10、适应度越小，进而探讨求解结果是否最优。选择就是从群体中选择优胜个体、 淘汰劣质个体的操作， 它是建立在群体中个体适应度评估基础上。这里采用方法是最优保存方法。本实例中交叉采用部分匹配交叉策略， 先随机选取两个交叉点， 然后将两交叉点中间的基因段互换， 将互换的基因段以外的部分中与互换后基因段中元素冲突的用另一父代的相应位置代替，直到没有冲突。变异操作是以变异概率 Pm对群体中个体串某些基因位上的基因值作变动，若变异后子代的适应度值更加优异， 则保留子代染色体， 否则，仍保留父代染色体。这有助于增加种群的多样性，避免早熟收敛（非全局最优）。判断结束准则是固定指定了迭代的次数当算法达到迭代次数时，

11、 算法结束，输出当前的最优解。在根据适配值计算并选择的时候，记录下来的当前最优值，在变异后加入跟新的群体，保证新的迭代循环中。5欢迎下载精品文档TSP解越来越好（不会变差） 。 在选择的一种操作是拿最优的K 个替换最差的 K个个体，本例是按适配值选择，并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不变，再次循环，一定程度上防止因初始群体的选择问题而陷入局部最优。4. TSP 问题的遗传算法的具体步骤解最短路径的遗传算法如下：Generatep(n); 表示程序开始时要首先产生一个群体， 群体个数为 nEvaluatep(h); 表示计算每个个体适应度， h 是种群中的一个个

12、体Repeat roof Generations times;重复下面的操作，直到满足条件为止Select p(h) from p(n-1);表示从前一代群体中选择一对双亲，用于交叉、变异操作， P(n) 代表第 n 代群体Crossover and mutation p(n);进行交叉和变异操作Learningp(n);自学习过程Evaluatep(h);计算新生成的种群中每个个体的适应度End;具体流程图如下所示：。6欢迎下载精品文档流程图5. 遗传算法求解不同规模的 TSP问题的算法性能（1） 遗传算法执行方式说明：适应度值计算方法：当前路线的路径长度个体选择概率分配方法：适应度比例方法

13、选择个体方法：轮盘赌选择交叉类型： PMX交叉变异类型 :两点互换变异（2）实验模拟结果：城市个数时间（ ms）51692510166301518833。7欢迎下载精品文档202259625241593030289353523940386084540032504375755477466058143655994270643617571417图 1-1（3）分析由图 1-1 可知，遗传算法执行时间随着TSP问题规模的增大而增大，并且大致为线性增长。8欢迎下载精品文档五、不同参数下的计算结果对比（ 1）种群规模对算法结果的影响实验次数： 10最大迭代步数 :100交叉概率： 0.85变异概率： 0.

14、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.16520-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-

15、6-7如 表1-1所 示 ， 显 然 最 短 路 径 为25.1652m, 最 优 路 径 为1-0-9-1-3-6-7-5-8-4-2或 3-1-0-9-2-4-8-5-7-6，注意到这是一圈，顺时针或者逆时针都可以。当种群规模为10，20 时，并没有找到最。9欢迎下载精品文档优解。（ 2）交叉概率对算法结果的影响实验次数： 15种群规模： 25最大迭代步数 :100变异概率： 0.15实验结果：表 1-2交叉概最好适应最差适应平均适应运行时率度度度最优解间9-2-6-0-5-4-8-0.00128.044736.656732.60027-3-13107-8-3-1-9-2-6-0.0127

16、.093534.994332.14950-5-42607-3-1-9-2-6-0-0.128.044735.303331.93725-4-83000-5-4-8-7-3-1-0.1528.044734.117531.21839-2-62703-1-9-2-6-5-0-0.228.710833.951230.90354-7-82801-3-7-8-4-5-0-0.2528.044735.162330.74566-2-9260。10欢迎下载精品文档8-3-1-9-2-6-0-0.327.093531.994129.94285-4-72909-1-3-8-7-4-5-0.3527.093532.80

17、8530.99450-6-22701-3-8-7-4-5-0-0.427.093532.531330.15346-2-92798-3-1-9-2-6-0-0.4527.093533.201430.17575-4-74565-0-2-6-9-1-3-0.528.093433.630730.90268-7-46631-9-2-6-0-5-4-0.5527.093533.523329.13047-8-35203-1-9-2-6-0-5-0.627.093533.251230.78364-7-85465-4-8-7-3-1-9-0.6528.044733.700330.93712-6-05969-1-

18、3-8-7-4-5-0.727.093532.092729.95020-6-25710-5-4-8-7-3-1-0.7528.044732.448830.36999-2-65597-4-5-0-6-2-9-0.827.093532.155129.93821-3-83580.8527.093534.539930.35945-0-6-2-9-1-3-360。11欢迎下载精品文档8-7-46-0-5-4-7-8-3-0.927.093532.627330.691-9-23756-2-9-1-3-8-7-0.9527.093532.467229.9194-5-0476（注 : 红色表示非最优解）在该情

19、况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。（ 3）变异概率对算法结果的影响实验次数： 10种群规模： 25最大迭代步数 :100交叉概率： 0.85实验结果：表 1-3变异概最好适应最差适应平均适应运行时率度度度最优解间0-6-2-1-9-3-8-70.00129.471734.73232.4911-4-52458-4-5-0-2-6-9-10.0129.044634.659132.3714-3-72745-0-2-6-9-1-3-80.128.093434.01130.9417-7-4250。12欢迎下载精品文档6-0-5-4-7-8-3-10.1527.093532.09330

20、.2568-9-22468-7-4-5-0-6-2-90.227.093532.234930.3144-1-32824-5-0-6-2-9-1-30.2527.093532.71830.1572-8-72450-5-4-7-8-3-1-90.327.093532.448830.2854-2-62521-3-8-7-4-5-0-60.3527.093533.316730.7748-2-92662-0-5-4-8-7-3-10.429.044634.370531.3041-9-63622-6-0-5-4-7-8-30.4527.093531.37429.6816-1-94382-9-1-3-8-7

21、-4-50.527.093532.375230.2211-0-64311-3-8-7-4-5-0-60.5527.093533.381930.6623-2-94921-3-8-7-4-5-0-20.628.093433.251230.36-6-94173-1-9-2-6-0-5-40.6527.093532.749130.0201-7-84340.728.710832.423830.7851-3-8-7-4-0-5-6432。13欢迎下载精品文档-2-91-9-2-6-0-5-4-70.7527.093531.892830.2451-8-34759-1-3-8-7-4-5-00.828.093

22、431.613530.3471-2-63272-9-1-3-7-8-4-00.8529.66233.239231.1585-5-63140-5-4-8-7-3-1-90.928.044732.038730.4152-2-63969-1-3-7-8-4-5-00.9528.044731.303630.0067-6-2436又表 1-3 可知，当变异概率过大或过低都将导致无法得到最优解。注：（2）（3）的实验数据与（ 1）的实验数据不同，详见附录。六、不同变异策略和个体选择概率分配策略对算法结果的影响（ 1）两点互换变异与插入变异的比较：试验次数（ CASNUM）：10城市数 (POINTCNT)

23、:10种群规模 (POPSIZE)：100最大迭代步数 (GENERATIONS):100。14欢迎下载精品文档交叉概率 (PC)：0.85变异概率 (PM):0.15选择个体方法：轮盘赌选择交叉类型： PMX交叉个体选择概率分配方法：适应度比例方法a. 变异类型 :两点互换变异表 1-4 两点互换变异程序结果最好适应最差适应平均适应运行时序号度度度最优解间6-2-0-5-4-7-8-3-128.093430.422929.08911-911994-5-0-6-2-9-1-3-227.093531.141728.98418-716780-5-4-7-8-3-1-9-327.093530.422

24、829.06042-619401-3-8-7-4-5-0-6-427.093530.370328.87872-917563-1-9-2-6-0-5-4-527.093531.061929.07557-818852-6-0-5-4-7-8-3-627.093531.158929.39421-91936728.044731.061929.76486-2-9-1-3-7-8-4-1772。15欢迎下载精品文档5-04-5-0-2-6-9-1-3-829.044631.347529.84157-819800-6-2-9-1-3-8-7-927.093530.614329.0594-519409-2-6

25、-0-5-4-7-8-1027.093530.558529.08113-118720-5-4-7-8-3-1-9-1127.093531.017129.42642-615171-9-2-6-0-5-4-7-1227.093531.303629.24148-315410-6-2-9-1-3-8-7-1327.093532.025529.07894-515170-6-2-9-1-3-8-7-1427.093531.51628.89064-513456-0-5-4-7-8-3-1-1527.093530.422829.02269-213770-6-2-9-1-3-8-7-1627.093530.40

26、8128.90814-518537-8-3-1-9-2-6-0-1727.093530.408129.33165-415221-3-8-7-4-5-0-6-1827.093530.020328.52432-91601。16欢迎下载精品文档2-9-1-3-7-8-4-5-1928.044731.140429.5670-616097-4-5-0-6-2-9-1-2027.093531.141729.53593-81311平均值27.336130.878229.18771657b. 变异类型 :插入变异表 1-5 插入变异程序结果最好适应最差适平均适运行序号度应度应度最优解时间31.47528.84

27、52-6-0-5-4-7-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-91245。17欢迎下载精品文档28.5542-6-0-5-4-7-8-3-1627.093529.6626-9122230.8203-1-9-2-6-0-5-4-8728.044752

28、9.748-7114830.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.328 4-5-0-6-2-9-1-3-81127.093531.3742-7124028.554 1-3-8-7-4-5-0-6-21227.093530.5234-9120430.82029.0500-6-2-9-1-3-8-7-41327.093558-5173431.11729.5900-5-4-

29、7-8-3-1-9-21427.093575-6153229.190 4-5-0-6-2-9-1-3-81527.093530.5234-7148330.40828.8065-0-6-2-9-1-3-8-71627.093511-412821727.093531.76329.4596-0-5-4-7-8-3-1-91485。18欢迎下载精品文档91-231.15829.1614-5-0-6-2-9-1-3-81827.093594-7160130.40828.5972-6-0-5-4-7-8-3-11927.093514-9150730.61428.8033-1-9-2-6-0-5-4-720

30、27.093536-8123430.64629.064平均值27析：两点互换变异 20 次模拟中， 4 次得到非最优解；而插入变异只有2 次；插入变异的最好适应度平均值比两点互换变异小0.14755 ，最差适应度平均值和总的适应度平均值都比两点互换下，并且在 Release 下，运行时间前者比后者快 218.3ms。可见在该条件下（交叉概率，变异概率，种群规模等） ，插入变异比两点互换变异的算法效果要好。（2）个体选择分配策略试验次数（ CASNUM）：10城市数 (POINTCNT):10种群规模 (POPSIZE)：100最大迭代步数 (GENERATIONS):

31、100。19欢迎下载精品文档交叉概率 (PC)：0.85变异概率 (PM):0.15选择个体方法：轮盘赌选择交叉类型： PMX交叉变异类型 :两点互换变异a. 个体选择概率分配方法：适应度比例方法同表 1-4b. 个体选择概率分配方法：非线性排序方式表 1-6 非线性排序方式程序结果最好适最差适平均适应运行时序号应度应度度最优解间1-9-2-6-0-5-4-7-127.093532.172130.09048-38244-5-0-6-2-9-1-3-228.044731.29729.99797-88652-0-5-4-7-8-3-1-328.093432.168330.56019-68953-1

32、-9-2-6-0-5-4-427.093532.097330.34727-81067527.093531.51629.85314-5-0-6-2-9-1-3-887。20欢迎下载精品文档8-75-0-6-2-9-1-3-8-627.093531.40829.46377-47273-1-9-2-6-0-5-4-727.093531.374229.94767-86510-5-4-7-8-1-3-9-829.523131.800930.55432-69010-5-4-7-8-3-1-9-927.093532.714730.3912-67499-3-1-8-7-4-5-0-1029.523131.568830.23856-28403-7-8-4-5-0-6-2-1128.044731.763930.26179-110441-3-7-8-4-5-0-6-1228.044731.630830.32672-97320-5-4-7-8-3-1-9-1327.093531.568829