内容发布更新时间 : 2025/4/2 2:44:30星期一 下面是文章的全部内容请认真阅读。

遗传算法解决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，则该串参加交叉操作，如此选出参加交叉的一组后，随机配对。

（2） 对每一对，产生[1，m]间的随机数以确定交叉的位置。 第六步 变异

如变异概率为Pm，则可能变异的位数的期望值为Pm ×m×M，每一位以等概率变异。具体为对每一串中的每一位产生[0，1]间的随机数r，若r

如新个体数达到M个，则已形成一个新群体，转向第三步；否则转向第四步继续遗传操作。直到找到使适应值最大的个体或达到最大进化代数为止。 由于选择概率是由适应值决定的，即适应值大的染色体入选概率也较大，使选择起到\择优汰劣\的作用。交叉使染色体交换信息，结合选择规则，使优秀信息得以保存，不良信息被遗弃。变异是基因中得某一位发生突变，以达到产生确实有实质性差异的新品种。遗传算法虽是一种随机算法，但它是有导向的，它所使用的\按概率随机选择\方法是在有方向的搜索方法中的一种工具。正是这种独特的搜索方法，使遗传算法自然地避开了其它最优化算法常遇到的局部最小陷阱。

遗传算法的优点：

1. 与问题领域无关切快速随机的搜索能力。

2. 搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较，robust. 3. 搜索使用评价函数启发，过程简单 4. 使用概率机制进行迭代，具有随机性。 5. 具有可扩展性，容易与其他算法结合。

遗传算法的缺点：

1、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,

2、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.

3、没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精