本科毕业设计说明书（论文）
图。
第 27 页 共 32 页
初始种群为100的模块。遗传代数为200，交叉率为0.9、变异率为0.01的运行
图3.4初始种群为100的算法运行图
初始种群为100的模块。遗传代数为200，交叉率为0.9、变异率为0.01获得最优解得截图。
图3.5 初始种群为100算法运行结果图
本科毕业设计说明书（论文）
4 混合遗传算法的展望
第 28 页 共 32 页
随着遗传算法的发展，为了提高遗传算法的质量和效率，人们把它与其他算法相结合，产生许多混合遗传算法。大大提高了算法质量和效率。更好的解决了许多实际问题。
（1）模拟退火遗传算法：
模拟退火算法的基本思路就是通过模拟高温物体退火过程的方式来找到优化问题的全局最优解。从统计物理学的观点看，随着物体温度的不断降低，物质的能量将不断的接近一个很低的状态，最后达到某种平衡状态。遗传算法的局部搜索能力并不是很好，但是整体的搜索能力比较突出；而模拟退火算法却相反，它具有出色的局部搜索能力，并能防止陷入局部最优解，但它却对整个搜索空间的了解不多，不便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运算效率不高。但如果将遗传算法和模拟退火算法相结合，互相取长补短，则有可能开发出性能优良的新的全局搜索算法。
（2）免疫遗传算法：
人工免疫算法受生物免疫系统原理的启发，针对求解问题特征进行人工疫苗接种，可充分利用问题本身的信息，和遗传算法结合时，遗传算法的全局搜索能力及免疫算法的局部优化相配合，可大大提高搜索效率。我们可以通过注射疫苗的方法来减少遗传操作的盲目性，加强遗传算法收敛性能，多次的测试结果证明了该改进方法的有效性。
（3）小生境遗传算法：
生物学上，小生境指在特定环境中的一种组织功能，它将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表，组成一个新种群，再在同一种群中以及不同种群之间进行杂交、变异，产生新一代个体群，同时采用“预选择”机制或排挤机制或共享机制完成选择操作。“解空间”中峰周围的子空间中的个体具有相对独立生长繁衍的特性。常用的小生境遗传算法大多在对群体进行选择操作前，计算个体之间的海明距离，如小于事先设定值，则对“适应值”低的个体处以罚函数，降低其适应值。这样可以保护解的多样性，也可以避免大量重复的解充斥整个解空间。用小生境思想来实现遗传算法的选择操作，使遗传算法的全局寻优能力得到了明显提高。
本科毕业设计说明书（论文）
（4）模糊遗传算法：
第 29 页 共 32 页
模糊遗传算法，即融合模糊优化设计思想的遗传算法，它把模糊优化和遗传算法优化结合起来，构成一种混合优化的设计方法。其目的是利用模糊优化设计的优点，克服一般遗传算法优化设计存在的不足，从而使得系统的优化设计更灵活、方便，取得好的设计效果。首先，在模糊遗传算法中引入“论域”的概念。在这里，“论域”即指用隶属函数来表示遗传算法的优化过程中所采用的约束条件的区间范围。用隶属函数来表示遗传算法的约束条件，以使约束条件能够更容易得到表达，又能够保证遗传子代的选择中能够拥有更广泛的群体组成。其次，在模糊遗传算法中，采用权变理论中的以变应变的思想。模糊遗传算法运用模糊控制的思想来自适应改变遗传算法的种群规模、交叉概率、变异概率、适应度函数以及控制策略等。
（5）混沌遗传算法：
混沌是自然界广泛存在的一种非线性现象，它充分体现了系统的复杂性。混沌运动具有类似随机变量的杂乱表现，具有随机性；“混沌”能在一定范围内按其自身特性不重复地历经所有状态，具有遍历性；初值条件极其微弱的变化会引起混沌系统行为的巨大变化，具有对初始条件的极度敏感性。混沌运动的上述性质作为避免陷入局部极小的优化搜索机制，恰好可以弥补遗传算法易陷入局部最优、收敛速度慢的缺陷。可以利用混沌的遍历性产生初始种群，也可以运用混沌的遍历性对优良个体进行变异操作，混沌遗传算法增强了遗传算法的全局寻优能力。
（6）量子遗传算法：
量子遗传算法是量子计算思想与遗传算法结合的产物。与遗传算法类似，它也是一个产生—检验的过程，但其实现同标准遗传算法不一样。在表达方式上，量子遗传算法将量子的态矢量表述引入染色体编码；在演化机制上，它利用量子门实现染色体演化。这些区别，使得量子遗传算法表现出比标准遗传算法更好的种群多样性、更强的全局搜索能力和更快的收敛速度。还有其他的算法已被引入到遗传算法中来（如禁忌—并行 ，分层），在此，就不再过多介绍。遗传算法与其他算法和理论的结合已经成为改进遗传算法的一个非常有效的手段。
随着人们对遗传算法研究的不断深入，可以预见，会有更多更好的理论和方法被引入到遗传算法中来。相信通过遗传算法与其他算法的结合以及自身实现方式的不断改进，在不久的未来，遗传算法的质量和效率都会有一个飞的提高。
本科毕业设计说明书（论文）
第 30 页 共 32 页
结 论
本文通过遗传算法求解TSP问题，成功获得了全局最优解。综上所述，在求解的过程中遗传算法能够收敛到某一稳定的“最优解”。在求解的质量和优化效率上都表现出了比较突出的能力。
针对具体TSP问题，遗传算法的几个关键参数都有它自己的适合值，种群大小、交叉率、变异率、遗传代数都从一定程度上影响着算法的效率和质量。如种群大小影响了种群的多样性，过少会导致算法陷入局部最优，而找不到全局最优解，过多大大的增加算法的计算量，增大机器开销，算法效率低下，针对10个城市的例子，初始种群应选50到200。交叉操作是产生新个体的主要操作，交叉率决定了算法的收敛速度，过大可能会破坏种群中较优的个体，过小怎会降低产生新个体的速度从而导致算法效率低下。本算法中应取0.7到0.9为宜。变异操作时产生新一代种群的辅助操作，它主要用来改善遗传算法的局部搜索能力，维持群体多样性防止局部收敛。取值较大，虽然能帮助群体产生较多的新个体，但同时也可能破坏较好的个体，所以要配合最优保存策略，但是也会增加机器开销。取值过小的话，变异操作产生新个体的能力和抑制局部收敛的能力都会降低，本算法应取0.01到0.1为宜。
在整个编写过程中，我认为一个最大的问题是：很难保证个体的完整结构。从父代到子代的交叉过程中，保留了部分父代的绝对访问顺序，但是它更多地产生了父代巡回路线中所没有的本分新路线，从而致使整个算法的遗传性状不是好很。也许以后会找到更好的交叉和变异规则，帮助遗传算在性状遗传上获得更好的效果。
本科毕业设计说明书（论文）
第 31 页 共 32 页
致 谢
大学四年的学习即将结束，在此首先感谢所有曾经教导过我的老师。 同时本文能成功完成，要感谢我的导师：朱保平老师。在整个毕业设计的过程中给了我巨大的帮助。是在他的帮助下，我的论文才得以良好的完成。在此，再次感谢,所有南京理工大学的老师,感谢他们这四年来给予了我巨大帮助。
本科毕业设计说明书（论文）
参 考 文 献
第 32 页 共 32 页
[1] Garey MR, Johnson Ds. A guide to the Theory of NP Completeness[J].
Computers and Intractability,1979,3(5):23-26
[2] 高经维,张煦,李峰,赵晖.求解TSP 问题的遗传算法实现[J].计算机时代,2004 ,2:19-21.
[3] 邓娟,陈莘萌.一种基于最大相似性的TSP 问题求解算法[J].计算机工
程,2004,30(17):1-2,11.
[4] 谢胜利,张燕姑,李广. 基于遗传算法的旅行商问题求解[J ].温州师范学院
学报(自然科学版),2002,,23 (3):7-10.
[5] 李华昌,谢淑兰,易忠胜. 遗传算法的原理与应用[J]. 矿冶,北京矿冶研究
总院1005-7854(2005)01-0087–04
[6] Holland J H. Adaptation in Natural and artificial Systems[M]. Ann
Arbor: The University of Michigan Press ,1975. [7] Cong Peisheng, Li Tonghua.Numeric genetic algorithm [J]. Anal , Chem. Acta,1994,293:191-203.
[8] 王辉.用遗传算法求解TSP问题[J].计算机与现代化,2009,7:12-16 [9] 周明,孙树栋.遗传算法原理及应用[M].国防工业出版社.1999. [10] 张文修,梁怡.遗传算法数学基础[M].西安交通大学出版社.2003.
[11] 张辉,赵正德,杨立朝,赵郁亮.TSP问题的算法与应用的研究[J].计算机应
用与软件,2009,26(4):274-276.
[12] 陈国良,等.遗传算法及其应用.北京:人民邮电出版社,1995
[13] 刘勇等.非数值并行算法（二）--遗传算法[M].北京:科学出版社，1995. [14] Sushil J.Louis.Genetic Algorithm for TSP[OL]. http://www.cs. unr .edu/～sushil/ papers/ conference/
[15] 谢胜利,等.求解TSP问题的一种改进的遗传算法[J].计算机工程与应
用,2002(8):58-245