《实验六：遗传算法求解TSP问题实验讲解》由会员分享，可在线阅读，更多相关《实验六：遗传算法求解TSP问题实验讲解（28页珍藏版）》请在金锄头文库上搜索。
1、实验六：遗传算法求解TSP问题实验一、实验目的熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解 函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影 响。用遗传算法对TSP问题进行了求解，熟悉遗传算法地算法流程， 证明遗传算法在求解TSP问题时具有可行性。二、实验内容参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的 优化问题，分析遗传算法求解不同规模TSP问题的算法性能。对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算 法结果的影响。增加1种变异策略和1种个体选择概率分配策略，比较求解同一 TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影 响。
2、1.最短路径问题所谓旅行商问题(Travelling Salesman Problem , TSP),即最短路径问题, 就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通 路，这样的通路成为S点到T点的最短路径。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路 径，还需要知道某个顶点到其他任意顶点间的最短路径。遗传算法方 法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法，用 遗传算法解决这类问题，没有太多的约束条件和有关解的限制，因而 可以很快地求出任意两点间的最短路径以及一批次短路径。假设平面上有n个点代表n个城市的位置，寻找一条最短的闭合路径, 使得可以遍历每一
3、个城市恰好一次。这就是旅行商问题。旅行商的路 线可以看作是对 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， Y 为双亲作交叉操作，从而产生两个后代 X1， Y1.（3）变异（Mutation）：对于选中的群体中的个体（染色体），随机 选取某一位进行取反运算，即将该染色体码翻转。用遗传算法求解的过程是根据待解决问题的参数集进行编码，随机产 生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。 如果满足收敛条件，此种群为最好个体，否则，对产生的新一
7、代群体 重新进行选择、交叉、变异操作，循环往复直到满足条件。遗传算法原型：GA(Fitness,Fitness_threshold,p,r,m)Fitness :适应度评分函数，为给定假设赋予一个评估分数Fitness_threshold:指定终止判据的阈值P：群体中包含的假设数量r:每一步中通过交叉取代群体成员的比例m:变异率初始化群体:P-随机产生的p个假设评估:对于P中的每一个h,计算Fitness(h)当maxFitness(h)Fitness_threshold,做产生新的一代Ps:(1) 选择:用概率方法选择P的(1-r)p个成员加入Ps从P中选择假设 hi的概率用下面公式计算：口
8、rfb J =汀讥JL 耳FLtne-BE(h-j)(2) 交叉:根据上面给出的二，从P中按概率选择r(p/2)对假设对 于每对假设,应用交叉算子产生两个后代把所有的后代加入 Ps变异:使用均匀的概率从Ps中选择m%的成员对于选出的每个 成员，在它表示中随机选择一个为取反(4) 更新:P-Ps评估:对于P中的每个h计算Fitness(h)从P中返回适应度最高的假设3. TSP问题的遗传算法设计与实现对于n个城市的问题，每个个体即每个解的长度为n,用s行,t列的 pop矩阵，表示初始群体，s表示初始群体的个数，t为n+1，矩阵的 每一行的前n个元素表示城市编码，最后一个元素表示这一路径的长 度。
9、城市的位置可以手动输入，使用一个NXN矩阵D存储，D (i, j)代表城市 i 和城市 j 之间的距离。D(i, j)二sqrt(Xi-Xj)42+(Yi-Yj)42)。 在 TSP 的求解中，可以直接用距离总和作为适应度函数。个体的路径 长度越小，所得个体优越，距离的总和越大，适应度越小，进而探讨 求解结果是否最优。选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在 群体中个体适应度评估基础上。这里采用方法是最优保存方法。 本实例中交叉采用部分匹配交叉策略，先随机选取两个交叉点，然后 将两交叉点中间的基因段互换，将互换的基因段以外的部分中与互换 后基因段中元素冲突的用另一父代的相应
10、位置代替，直到没有冲突。变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作 变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则， 仍保留父代染色体。这有助于增加种群的多样性，避免早熟收敛(非 全局最优)。判断结束准则是固定指定了迭代的次数当算法达到迭代次数时，算法 结束，输出当前的最优解。在根据适配值计算并选择的时候，记录下 来的当前最优值，在变异后加入跟新的群体，保证新的迭代循环中 TSP 解越来越好(不会变差)。 在选择的一种操作是拿最优的 K 个替 换最差的 K 个个体，本例是按适配值选择，并使群体数目变少，当每 次变异操作后，产生随机路径补充群体是群体数目不变，再次
11、循环， 一定程度上防止因初始群体的选择问题而陷入局部最优。4. TSP 问题的遗传算法的具体步骤解最短路径的遗传算法如下：Generatep(n);表示程序开始时要首先产生一个群体，群体个数为 nEvaluatep(h);表示计算每个个体适应度，h是种群中的一个个体Repeat roof Generations times連复下面的操作，直到满足条件为止Select p(h) from p(n-1);表示从前一代群体中选择一对双亲，用于交叉、变异操作，P(n)代表第n代群体Crossover and mutation p(n);进行交叉和变异操作Learningp(n);自学习过程Evalua
12、tep(h);计算新生成的种群中每个个体的适应度End;具体流程图如下所示：5遗传算法求解不同规模的TSP问题的算法性能1） 遗传算法执行方式说明：适应度值计算方法：当前路线的路径长度个体选择概率分配方法：适应度比例方法 选择个体方法：轮盘赌选择 交叉类型： PMX 交叉 变异类型: 两点互换变异（2）实验模拟结果：城市个数时间（ms）51692510166301518833202259625241593030289353523940386084540032504375755477466058143655994270643617571417:i10153325303540 iE 60 S657
13、07580城市魏量7 B 5 4 3 2 苣叵盘|:-说卡%图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-45025.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
14、-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-8-4-2 或 3-1-0-9-2-4-8-5-7-6，注意到这是一圈，顺时针 或者逆时针都可以。当种群规模为10，20 时，并没有找到最优解。（2）交叉概率对算法结果的影响实验次数：15种群规模：25最大迭代步数:100变异概率：0.
15、15实验结果：表 1-2交叉概率最好适应度最差适应度平均适应度最优解运行时间0.00128.044736.656732.60029_2_6_0_5_4_8_7-3-13107 3T92600.128.044735.303331.93725-4-8300054873T0.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-92608- 3-1-9-2-6-0-0.327.093531.994129.94285-
