基于改进的遗传算法求解TSP问题

摘要

遗传算法是模拟自然环境中生物的遗传和进化过程而形成的一种优化算法。遗传算法具有全局搜索能力、隐并行性、鲁棒性、操作简单等特点，常被用于解决一些传统优化方法难以解决的问题。由于其不受搜索空间的限制性假设的约束，尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程，从而使它的应用范围极为广泛，并且已在众多领域得到了实际应用。
　　旅行商问题（TSP）是一个典型的组合优化问题，由于其NP完全性，一直作为衡量算法优劣的经典实例，受到广大研究者的青睐。
　　本文以改进遗传算法为依托，以求解TSP问题为着眼点，探讨解决经典TSP问题的有效途径。基于此提出了两种基于适应度比例选择的改进策略。实验结果表明，本文提出的两种改进方法能够有效提高解的准确性，并具有更好的收敛性。

目录

声明

1 引言

1.1 研究背景及意义

1.2 国内外研究现状

1.3 本文主要工作

1.4 本文组织结构

2 遗传算法概述

2.1 遗传算法基本思想

2.2 遗传算法的特点

2.3 遗传算法的几个基本概念

2.4 遗传算法的具体实现

2.5基础遗传算法操作步骤

2.6 基础遗传算法小结

3 旅行商问题（TSP）

3.1 旅行商问题（TSP）定义

3.2 旅行商问题（TSP）的求解

3.3 小结

4 基于改进轮盘赌遗传算子选择方式的遗传算法求解TSP问题

4.1 传统遗传算法求解旅行商（TSP）问题

4.2 改进的遗传算法求解TSP问题

5 实验分析及结论

5.1 MATLAB下的路径图对比（以bayg29、att48为例）

5.2 实验结果比较分析

5.3 结论

6 结束语

6.1 本文工作总结

6.2 研究展望

致谢

参考文献

作 者 简 介