遗传算法解决TSP问题
姓名:
学号: 专业:
问题描叙
TSP问题即路径最短路径问题,从任意起点出发(或者固定起点),依次经 过所有城市,一个城市只能进入和出去一次,所有城市必须经过一次,经过终点 再到起点,从中寻找距离最短的通路。
通过距离矩阵可以得到城市之间的相互距离,从距离矩阵中的到距离最短路 径,解决TSP问题的算法很多,如模拟退火算法,禁忌搜索算法,遗传算法等 等,每个算法都有自己的优缺点,遗传算法收敛性好,计算时间少,但是得到的 是次优解,得不到最有解。
算法设计
遗传算法属于进化算法的一种,它通过模仿自然界的选择与遗传的机理来寻 找最优解.遗传算法有三个基本算子:选择、交叉和变异。
数值方法求解这一问题的主要手段是迭代运算。 一般的迭代方法容易陷入局 部极小的陷阱而出现\死循环\现象,使迭代无法进行。遗传算法很好地克服了这 个缺点,是一种全局优化算法。
生物在漫长的进化过程中,从低等生物一直发展到高等生物,可以说是一个绝妙 的优化过程。这是自然环境选择的结果。人们研究生物进化现象,总结出进化过 程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到 启发,提出了遗传算法。算法中称遗传的生物体为个体,个体对环境的适应程度 用适应值(fitness)表示。适应值取决于个体的染色体,在算法中染色体常用一 串数字表示,数字串中的一位对应一个基因。 一定数量的个体组成一个群体。 对 所有个体进行选择、交叉和变异等操作,生成新的群体,称为新一代遗传算法计 算程序的流程可以表示如下: 第一步准备工作
(1) 选择合适的编码方案,将变量(特征)转换为染色体(数字串,串长为m)。 通常用二进制编码。
(2) 选择合适的参数,包括群体大小(个体数 M )、交叉概率PC和变异概率 Pm。
(3) 确定适应值函数f (x)。f(x)应为正值。
第二步 形成一个初始群体(含M个个体)。在边坡滑裂面搜索问题中,取已分 析的可能滑裂面组作为初始群体。
第三步 对每一染色体(串)计算其适应值fi,同时计算群体的总适应值 。 第四步选
择
计算每一串的选择概率Pi=fi/F及累计概率。选择一般通过模拟旋转滚花轮 (roulette,其上按Pi大小分成大小不等的扇形区)的算法进行。旋转
M次即可
选出M个串来。在计算机上实现的步骤是:产生[0, 1]间随机数r,若r (1) 对每串产生[0, 1]间随机数,若r>pc,贝U该串参加交叉操作,如此选出参 加交叉的一组后,随机配对。 (2) 对每一对,产生[1,m]间的随机数以确定交叉的位置。 第六步变异 如变异概率为Pm,则可能变异的位数的期望值为 Pm XmXM,每一位以等概率 变异。具体为对每一串中的每一位产生[0,1]间的随机数r,若r 如新个体数达到M个,则已形成一个新群体,转向第三步;否则转向第四 步继续遗传操作。直到找到使适应值最大的个体或达到最大进化代数为止。 由于选择概率是由适应值决定的,即适应值大的染色体入选概率也较大, 使选择 起到\择优汰劣\的作用。交叉使染色体交换信息,结合选择规则,使优秀信息得 以保存,不良信息被遗弃。变异是基因中得某一位发生突变, 以达到产生确实有 实质性差异的新品种。遗传算法虽是一种随机算法,但它是有导向的,它所使用 的\按概率随机选择\方法是在有方向的搜索方法中的一种工具。 正是这种独特的 搜索方法,使遗传算法自然地避开了其它最优化算法常遇到的局部最小陷阱。 遗传算法的优点: 1. 与问题领域无关切快速随机的搜索能力。 2. 搜索从群体出发,具有潜在的并行性,可以进行多个个体的同时比较,robust. 3. 搜索使用评价函数启发,过程简单 4. 使用概率机制进行迭代,具有随机性。 5. 具有可扩展性,容易与其他算法结合。 遗传算法的缺点: 1、 遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之 后还需要对问题进行解码, 2、 另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的 选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.
遗传算法解决TSP问题
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)