文档介绍：工程硕士学位论文
混合遗传算法和模拟退火算法
在 TSP 中的应用研究
作 者 姓 名 刘 锦
工 程 领 域 计 算 机 技 术
校 内 指 导 教 师 文 贵 华 教 授
校 外 指 导 教 师 李 建 权 高 级 工 程 师
所 在 学 院 计 算 机 科 学 与 工 程 学 院
论 文 提 交 日 期
Applied Research of Hybrid Genetic Algorithm
and Simulated Annealing Algorithm in
Traveling Salesman Problem
A Dissertation Submitted for the Degree of Master
Candidate：Liu Jin
Supervisor：Prof. Wen Gui Hua
South China University of Technology
Guangzhou, China
分类号： 学校代号：10561
学 号 ：201020206230
华南理工大学硕士学位论文
混合遗传算法和模拟退火算法
在 TSP 中的应用研究
作者姓名： 刘锦 申请学位级别：工程硕士
工程领域名称： 计算机技术
校内指导教师姓名、职称：文贵华 教授 校外指导教师姓名、职称：李建权 高级工程师
论文形式： 产品研发 工程设计 应用研究 √ 工程/项目管理 调研报告
研究方向： 计算机应用技术
论文提交日期： 2014 年 5 月 1 日 论文答辩日期： 2014 年 6 月 7 日
学位授予单位： 华南理工大学 学位授予日期： 年 月 日
答辩委员会成员：
主席： 韩国强
委员： 文贵华 陆璐 徐红云 高昭昇
摘要
本文从现有的求解 TSP 的算法入手，介绍了几种常见算法的主要思想。研究表明，
遗传算法和模拟退火算法在解决 TSP 的过程中表现出了一定的优势，并且在实际问题的
求解中得到了广泛的应用。本文针对这两种算法进行了深入研究并编程实现，发现了基
于全局搜索的遗传算法和基于局部搜索的模拟退火算法在求解 TSP 上的不足。于是在这
两种算法的基础上，分别提出了两种算法的改进方法，并验证了改进后算法的有效性。
同时基于两种改进算法，提出了一种混合遗传模拟退火算法，用于求解旅行商问题。首
先，混合算法采用混合方法产生初始种群，提高了初始群体的质量，增大了搜索到最优
解的概率。另一方面，算法通过海选择优的方式，充分发挥了优秀基因的特性，大大减
少了遗传的代数，提高了收敛速度，并有效防止种群早熟现象，避免陷入局域最优解；
最后，算法通过模拟退火过程，提升了获得更优解的概率，并对路径进行优化处理，使
得到的解尽可能更优。相比单一的遗传算法或模拟退火算法求解，该混合算法在实例中
表现出了更优异的可行性和有效性。
关键词：旅行商问题；遗传算法；模拟退火算法；路径优化
I
Abstract
This paper introduces the main ideas of the several comm