基于蚁群算法的TSP研究与实现文献综述
2020-04-14 05:04
| 1、目的及意义 1.1 研究目的及意义 在计算机自动控制领域中, 控制和优化始终是两个重要问题。使用计算机进行控制和优化本质上都表现为对信息的某种处理。随着问题规模的日益庞大, 特性上的非线性及不确定性等使得难以建立精确的“数学模型”。人们从生命科学和仿生学中受到启发, 提出了许多智能优化方法, 为解决复杂优化问题(NP- hard 问题) 提供了新途径。 蚁群算法(Ant Colony Algorithm, ACA) 是Dorigo M等人于1991年提出的。经观察发现, 蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。在运动过程中, 蚂蚁能够在它所经过的路径上留下该种信息素, 而且能够感知信息素的浓度, 并以此指导自己的运动方向 。蚁群的集体行为表现出一种信息正反馈现象: 某一路径上走过的蚂蚁越多, 则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。它充分利用了生物蚁群通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性。同时，该算法还被用于求解二次指派问题以及多维背包问题等，显示了其适用于组合优化问题求解的优越特征。 蚁群算法应用于静态组合优化问题, 其典型代表有旅行商问题( TSP) 、二次分配问题(QAP) 、车间调度问题、车辆路径问题等。在动态优化问题中的应用主要集中在通讯网络方面。这主要是由于网络优化问题的特殊性, 如分布计算, 随机动态性, 以及异步的网络状态更新等。例如将蚁群算法应用于QOS组播路由问题上, 就得到了优于模拟退火(SA)和遗传算法(GA)的效果。蚁群优化算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域获得成功的应用，其中最成功的是在组合优化问题中的应用。 蚁群算法作为智能计算领域的一个重要分支，该算法具有很大的应用前景，并且还在不断地创新和发展。蚁群算法虽然存在诸多优点，但它还存在着收敛速度慢，收敛精度不高，易陷入局部最优等缺点，需要研究人员不断地去完善和发展该算法的理论，以提升该算法的实际性能，使其更好地服务于应用领域。 1.2 国内外研究现状 1991年，意大利学者Dorigo M等人提出了蚁群算法，并成功的解决了旅行商问题（TSP）。1995年，Gambardella L M和Dorigo M提出了Ant-Q算法，建立了AS和Q-learning的联系。1956年，Dorigo M等人在《IEEE Transactions on System,Man,and Cybernetics-Part B》上发表了“Ant system:optimization by a colony of cooperating agents”一文，全面系统的描述了蚁群算法的基本原理。1996年，Dorigo M,Maniezzo V等人又提出了蚁群系统（Ant Colony System, ACS).通过不断地改进，带精英策略的蚂蚁系统，最大-最小蚂蚁系统（Max-Min Ant System,ACS)等相继诞生。1998年10月，第一届蚁群算法国际研讨会（ANTS）在比利时布鲁塞尔举办，为蚁群算法的快速发展奠定了基础。1999年，Dorigo M等人把先前各种蚁群算法归结到一个统一的框架之中，并给出了抽象，规范的算法描述，称之为蚁群优化算法。后来Gutjahr W J在一些学术报告和论文中对一些问题进行了假设，并因此为前提，证明了蚁群算法的收敛性，有力地推动了蚁群算法的发展和应用。《IEEE Transactions on Evolutionary Computation》在2002年出版了蚁群算法特刊。2004年，Dorigo M和Stutzle出版了一本关于蚁群算法的书《Ant Colony Optimization》。2015年Joao Batista Queiroz Zuliani等人把蚁群优化算法和遗传算法结合起来，并成功运用到目标拓扑优化中，达到了很好的实验效果。2016年1月，Pawan Kuman Tiwari等人把“懒蚂蚁”应用到蚁群算法中，实验结果表明“懒蚂蚁”既降低了算法复杂度，又提高了算法性能。 |
2. 研究的基本内容与方案
{title}2、研究（设计）的基本内容、目标、拟采用的技术方案及措施
2.1 主要内容
2.1.1 TSP问题的简单描述
TSP问题（Traveling Salesman Problem），即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
2.1.2 蚁群算法的基本原理
蚂蚁在运动过程中会通过在路上释放一种特殊的分泌物——信息素来寻找路径。当它碰到一个还没有走过的路口时就随机选择一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口时，选择信息量较大的路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路径上的信息量却随时间逐渐减少，最终整个蚁群会找出最优路径。
2.1.3 蚁群算法求解TSP的流程
（1）参数初始化。令时间t=0，循环次数NC=0，设置最大循环次数NCmax ，将m只蚂蚁置于n个城市上，令每条边上的（i,j）初始化信息量τij(t)=const，其中const表示常量，且初始时刻Δτij(0)=0；
（2）循环次数NC = NC 1；
（3）蚂蚁的禁忌表索引号k=1；
（4）蚂蚁数目k=k 1；
（5）蚂蚁个体根据状态转移概率公式计算的概率Pkij(t)选择城市j；
（6）修改禁忌表指针，即选择好后将蚂蚁移动到新的城市，并把该城市移动到该蚂蚁个体的禁忌表中；
（7）若集合C中的城市未遍历完，即klt;m，则跳转到第（4）步，否则继续往下一步执行；
（8）根据信息素更新机制更新每条路径上的信息量τij(t n)；
（9）若满足结束条件，即循环次数NCgt;=NCmax, 则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第（2）步。
注：上述步骤中要用到该算法数学模型中两个重要的机制（如下），其中将涉及到几个关键参数。
1.路径选择机制:
2-1
2.信息素更新机制:
2-2，2-3
系统流程图如下图所示：
2.2 预期目标
通过研究和分析各种蚁群算法模型，掌握蚁群算法的基本原理和实现步骤，并在MATLAB环境中进行仿真，分析蚁群算法中各关键参数对算法性能的影响。
针对TSP问题，掌握经典算法的基本思想和解决方法，并应用性能优异的蚁群算法得出旅行商问题的最佳解。
3. 参考文献4、参考文献
[1] Ying-Hua Huang; Carola A. Blazquez. Solving
the Feeder Vehicle Routing Problem Using Ant Colony Optimization[J]. Computers
amp; Industrial Engineering. 2018, 46(10):649 - 654
[2] Jingfa Liu; Jun Liu;. Blazquez. Applying
multi-objective ant colony optimization algorithm for solving the unequal area
facility layout problems[J]. Applied Soft Computing Journal. 2018, (74):
167-189
[3] Shupeng Gao ; Jiaqi Zhong ; Yali Cui. A
novel pheromone initialization strategy of ACO algorithms for solving TSP[C]. 2017
13th International Conference on Natural Computation, Fuzzy Systems and
Knowledge Discovery (ICNC-FSKD). 243 - 248
[4] 李根; 李航. 基于蚁群算法的最优路径规划及参数研究[J]. 中国科技论文. 2018,
13(16):1909-1914
[5] 马振. 改进蚁群算法及其在TSP中的应用研究[D]. 青岛理工大学. 2016
