2。2  遗传算法 8

2。2。1  遗传算法的描述 8

2。2。2  遗传算法的基本概念 8

2。2。3 遗传算法流程 9

2。3。3  遗传算法流程图 10

第三章 遗传算法求解 TSP 问题 11

3。1  遗传算法的基本要素 11

3。2  初始种群的生成 12

3。2 选择算子 12

3。3  交叉操作 12

3。4  变异操作 13

4。5 TSP 问题解决流程图 15

第四章 仿真实验 16

4。1  程序初始化 16

4。1。1 生成初始种群 17

4。2  实验一 算法有效性验证 18

4。3  实验二 寻找最优遗传算子 21

4。4  实验三 多例子验证程序的普适性 22

4。5  实验四 第二种遗传算子选择实验比较 26

4。6  实验总结： 28

结语 29

致谢 30

参考文献 31

第一章 绪论

1。1  研究背景

现实生活中，如何合理建设合理高效的交通道路以减少交通拥堵，怎样合理规划路 径以减少运营成本，怎么铺设网络节点更好的让信息流动，是一个困扰很多领域的问题。

这些问题都是组合优化问题中的一种。有效解决这些组合优化问题能够给人类生活 带来巨大的便利。旅行商问题是指一个商人在许多城市之中的从一个城市出发，每个城 市走且仅走一遍。显然旅行商问题就是一个典型的组合优化问题，它的解空间规模将随 着城市规模的增大呈指数型增大。论文网

所以研究旅行商问题的解决方法，以此可以推广到其他组合优化问题。并利用该方 法解决一些实际问题。

因此，寻找一个可实现并且高效率的解决方法具有重要意义。因为，这不仅可以解 决众多现实中的问题，还可以在成本节约，以及提高工作效率上提供可观 的改进。 1。2  遗传算法发展历史

20 世纪七十年代，美国密歇根大学学者 J。Holland 通过研究总结创立了遗传算法， 算法理论基础是生物学上的物竞天择，适者生存，以此来搜寻所求问题的最优解。在

《Adaption in Natural and Artificial Systems》发布后，遗传算法逐渐被学者应用到各个领 域之中，而由 J。Holland 提出的遗传算法被称为简单遗传算法（SGA）1。 遗传算法是模拟生物学进化物竞天择适者生存优胜劣汰的生物进化法则的数学模型。通 过交叉变异与选择在组合优化问题的解空间中搜索最优解2。遗传算法是将生物种群的 所有个体编码，并通过交叉变异选择的手段构成算法的基本操作模式。参数的程序化， 如何设置初始种群，如何选择适应度函数，一串操作流程，遗传算子的设定组成遗传算 法的核心内容3。旅行商问题是一个 NP 完全问题，从理论上讲，这些问题都是可以通 过枚举的方式找出最优解但是，旅行商问题却会随着城市个数的增加解空间将会指数型 增大，所以枚举法一般是不可行的。由于对于这种旅行行商问题，他的可行解的数量 会随着目的地的变大变得巨大。