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

菜单

2.2传统优化算法 6

2.3人工智能优化算法 7

2.4传统优化算法与人工智能优化算法的区别 8

2.5本章小结 8

3蚁群优化算法 9

3.1蚁群优化算法的基本原理 9

3.2蚁群优化算法的研究状况 9

3.3求解旅行商问题建模 10

3.4本章小结 15

4实验结果分析 16

4.1MATLAB仿真 16

4.2枚举法与最大最小蚁群算法仿真的比较 18

4.3不同规模的仿真比较 21

4.4本章小结 30

5结论 31

5.1总结 31

5.2展望 31

附录 32

参考文献 38

致谢 40

1 绪论

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

在科技技术迅速发展的时代中，计算机已经成为人类前进步伐中不可缺少的一部分。但是在实际问题中，有些问题是模糊不定的，人类无法利用精确的算法在多项式时间内计算出准确的答案，称之为组合优化（NP）问题。随着所研究问题的规模扩大，其复杂度就会成指数上升，在现有的条件下无法解决。旅行商问题就是经典的NP问题。

旅行商问题（Traveling Salesman Problem），被称为旅行推销问题[1]，简称TSP问题。是指推销员在按照一定的顺序的情况下，如何选择最短路径，合理运用时间并且节省经济，访问N个城市，且每个城市仅能被访问一次，最终回到起点城市。

TSP问题历史悠久。早在1759年，欧拉研究的骑士环游问题，其实就是最早的旅行商问题特例。当时，在国际象棋棋盘的64个方格中，棋手在选择落棋的方格时，每个方格都要被选择过而且只能选择一次，64个方格都被选到过，最终回到起始方格。

美国的兰德公司（Research and Development, RAND）在1948年提出TSP问题，由于该公司的声誉以及知名度，使得这一问题引起了大众的关注。在1959年，Dantzigd等人提出了最早的旅行商问题的数学规划，描述了在物流中，TPS问题就是一个物流配送公司，如何确定最短的路径来将n个客户的订单送往每一个地方，且不能重复，最终回到初始地点。

2010年10月25号，英国伦敦大学皇家霍洛韦学院通过蜜蜂采蜜成功破解了旅行商问题。在研究过程中，无论他们如何变换花的位置，蜜蜂都能很快地寻找到最短路径。尽管蜜蜂的大脑只有菜籽的大小，但他不依靠电脑就能很快的找到解决方案，这对人类今后的研究提供了不可或缺的帮助。

现如今，人类对于旅行商问题的研究依旧如此热衷，这更有利于解决一些实际问题。比如：校园班车接送孩子的问题，考虑如何将行驶路径变得最短，节省行驶时间，减少汽车尾气的排放量，解决道路拥挤问题；城市管道铺设问题，如何减少管道的数量，使成本最小；邮局收集邮件的问题，即如何节省工作人员的时间，又便利于民等。因此，旅行商问题将会不断发展着。

1.2 研究状态及成果

旅行商问题大多集中在启发式解法上。启发式算法是在已有的经验或者能够直观的前提下，解决优化问题得出可行解。在1993年，Bodin将启发式算法分为三种，每种都有个各自的解法。第一种是途程建构法，可以用最近邻点法、节省法或插入法来解决从距离矩阵中产生的一个近似的最优路径。具体的来说，就是旅行商未出发前，相关人员根据已有的经验或者技术拟定最优路径。第二种解法是途程改善法，先人为规定一个可行的路径，然后在通过不断的改进，直到不能再进行改进为止。最后一种解法是前两种解法的集合，称之为合成启发法。合成启发法更有助于提高寻找最优路径的效率。通过途程建构法先产生一个起始的路径，然后利用途径改善法不断的优化已有的路径，直到为最优路径。