基于蚁群算法的中国旅行商问题研究

摘要中国旅行商问题是一个典型的组合优化方面的难题，事实上生活中很多问题都可以直接转化为旅行商问题，比如交通调度问题、邮路选择问题、网络通信问题等。

本论文简单介绍了一些传统优化算法和人工智能优化算法，着重讲述了采用蚁群优化算法处理旅行商问题。蚁群优化算法是一种新颖的仿生进化类算法，它具有诸如健壮性、正反馈性、并行性，并且容易与其它方法融合的优点等。蚁群算法作为一种启发式算法已经成功地应用于旅行商问题，但是在求解过程中其收敛性差，容易陷入局部最优，所以本文运用最大最小蚁群算法来解决旅行商问题。在信息素更新时，提出了一种新的信息素的更新方式，同时限制信息素的大小，避免出现搜索停滞的现象。根据生物对环境敏感的变化原理，将启发式信息线性递减，以及对参数、实现自适应调整，以此来提高寻优效率。

本论文通过MATLAB对最大最小蚂蚁算法进行仿真测试，最终结果显示了用该算法解决旅行商问题的优点。49291

该论文有图17幅，表10个，参考文献30篇。

毕业论文关键词：旅行商问题蚁群优化算法最大最小蚁群优化算法信息素

The Research of Chinese Traveling Salesman Problem Based on Ant Colony Algorithm

Abstract Chinese traveling salesman is a typical problem of combinatorial optimization. In reality ,a lot of problems can be translate into traveling salesman problem directly, such as the traffic scheduling problem, the routing problem as well as the network communication problem.

In this paper, some traditional optimization algorithms and artificial intelligence optimization algorithms have been simply introduced, with a focus on the usage of ant colony optimization algorithm in solving traveling salesman problems. Ant colony optimization algorithm is a novel bionic evolutionary algorithm, it has advantages such as robustness, positive feedback and parallelism, and it can merge with other methods easily. Ant colony algorithm has been successfully applied to the traveling salesman problem as a kind of heuristic algorithm. However, this method has a poor convergence and may fall into local optimum easily in the process of solving the problems. So this article use maximum minimum ant colony algorithm to solve traveling salesman problems. When the pheromone updates, we proposes a new mode of the pheromone update, and limit the size of the pheromone at the same time, avoiding the stagnation of the search. According to the principle that biological is sensitive to environmental changes, human make the heuristic information decrease linearly and realize the adaptive adjustment of the parameters 、 ,in order to improve the efficiency of optimization.

This paper uses MATLAB simulation test to carry out the maximum minimum ant algorithm. Finally it shows the advantages of the optimization algorithm in solving traveling salesman problems.

The paper has 17 pictures , 10 tables, 30 references.

Key Words: traveling salesman problem ant colony optimization algorithm maximum minimum ant colony optimization algorithm pheromone

摘要 I

Abstract II

目录 IV

1 绪论 1

1.1 旅行商问题的背景及发展 1

1.2 研究状态及成果 2

1.3 论文的构成及研究内容 3

2 解决旅行商问题的基本方法 5

2.1 中国旅行商问题的分析基于蚁群算法的中国旅行商问题研究:http://www.youerw.com/zidonghua/lunwen_52249.html