智能算法在tsp中的应用研究.doc

智能算法在TSP中的应用研究
摘要:TSP问题,即旅行商问题,是一个典型的组合优化问题,实际应用中非常广泛,近几年对于此问题的求解提出了很多方法,例如:遗传算法,蚁群算法,模拟退火算法,爬山法,粒子群算法等等。本文通过对遗传算法以及蚁群算法的重点介绍,并且应用于求解TSP问题。主要工作有:
(1)概述了旅行商问题的定义、数学模型。
(2)概述了旅行商问题的研究背景、研究现状、目的、意义及本文的主要工作,阐述了遗传算法和蚁群算法以及其特点、基础理论以及其研究现状。
(3)介绍了遗传算法和蚁群算法的数学模型,以及处理TSP问题的步骤,分别用遗传算法和蚁群算法对十个城市进行组合优化处理。
关键词:TSP,遗传算法,蚁群算法,组合优化
Intelligent algorithm in the application of the TSP
Abstract: TSP, the traveling salesman problem, is a binatorial optimization problem, a wide range of practical applications in recent years to solve this problem for many methods proposed, For example: ic algorithm, ant colony algorithms, simulated annealing, hill climbing method, Particle swarm optimization, etc. Based on the ic algorithm and focus on the ant colony algorithm, and used to solve TSP. Main tasks are:
(1) An overview of the traveling salesman problem definition, mathematical model
(2) Overview of the traveling salesman problem of background, status, purpose, meaning and major tasks of this paper to explain the ic algorithm and ant colony algorithm and its characteristics, the basic theory and its research status.
(3) Describes the ic algorithm and mathematical model of ant colony algorithm, as well as steps to deal with TSP problems, respectively, the ic algorithm and ant colony optimization of the ten bined treatment.
Keywords: TSP, ic algorithms, ant colony algorithm, combinatorial optimization
目录
1 绪论 1
研究背景 1
课题研究背景及意义 1
课题的国内外研究状况 2
研究内容 3
本课题要研究的问题 3
旅行商问题的定义及数学模型 3
拟采用的研究手段 4
2 遗传算法 8
8
遗传算法的设计 8
8
9
9
11
13
14
仿真实验分析 14
3 蚁群算法 17
蚁群算法的起源与发展 17
18
蚁群行为的描述 18
蚁群算法的数学模型 19
蚁群算法的具体实现步骤 21
仿真实验分析 21
22
4 总结 25
附录. 遗传算法以及蚁群算法解决TSP问题的程序: 26
参考文献 39
1 绪论
研究背景
课题研究背景及意义
随着人们生活水平的提高,旅游越来越成为一种时尚,旅游者和旅行社都希望通过合理的旅游线路来达到满足最大化,成本最小化的目的。一条成功的旅游线路能为旅游者提供一次特定时空序列、心