论文部分内容阅读
20世纪90年代初,意大利学者Dorigo M等人受到大自然中蚂蚁觅食行为的启发,提出了蚁群算法,它是继模拟退火算法、遗传算法等启发式搜索算法之后出现的一种新的启发式搜索算法,具有较强的鲁棒性、正反馈、分布式计算和易于与其他方法结合等优点。它已经被应用到许多组合优化问题中,取得了令人鼓舞的效果。作为群智能和计算智能的重要分支之一,蚁群优化算法的研究引起了越来越多学者的关注。旅行商问题(Traveling Salesman Problem,简称TSP)是近代组合优化领域的一个典型难题,现实生活中的很多问题都可以转化为TSP问题,如邮路问题、电路板钻孔问题、交通调度问题和网络通迅问题等,这些问题可以直接转化为TSP问题或者本身就是TSP问题的原型。TSP问题己经成为并将继续成为测试组合优化新算法的标准问题。因此,对TSP问题的研究具有重要的理论意义和实际应用价值,这就促使人们长期以来不断地探索并积累了大量的研究算法。本文主要工作是在蚁群优化算法实验性分析的基础上,提出了一种改进的蚁群算法来解决TSP问题,以克服先前蚁群优化算法的一些不足。它是一种基于最小生成树的自适应蚁群优化算法。提出该算法用来解决TSP问题是受启发于以下事实:在一般TSP问题中,最短路径回路包含最小生成树中70%-80%的路径,也就是说,最小生成树的边将很可能出现在TSP问题的最优路径中。它利用最小生成树和最优路径之间的关系限制蚂蚁在每个城市的搜寻范围来优化搜索策略,通过引入一个自适应概率来更好地发挥最小生成树在TSP问题路径寻优中的作用。在这个基础上,另外增加了两个策略:一是加入了最大最小蚂蚁中的信息素限定规则,即将每条边上的信息素限制在一个范围内来抑制由于最短路径和最长路径信息素差距加剧引起的停滞现象;二是在每次迭代的最后阶段,加入一个局部搜索,通过对当前最优解进行局部调整来优化改进解,以提高解的计算精度。最后,通过在VC++环境下实现改进的蚁群算法程序,验证了改进后的蚁群算法的可行性以及改进后的蚁群算法求解TSP问题的高效性。对TSP数据库中具体城市数据进行的计算机实验仿真结果表明,该算法能够比先前的蚁群算法达到更好的效果和更高的效率。