一种改进的蚁群算法及其在最短路径问题中的应用

旅行商问题（TSP）是一个典型的组合优化问题，对其研究具有重大的理论和现实指导意义。然而，随着科技发展以及人类生存空间的不断扩大，问题规模也在逐渐扩大，这使得原始方法已不再适应于此类问题的求解，于是人们提出了许多用于求解复杂优化问题近似解的启发式智能优化算法，蚁群算法就是其中的一种。 蚁群算法是通过模拟自然界中蚂蚁群体的觅食行为而提出的一种新型的智能仿生进化算法。它采用分布式并行计算机制，具有较强的鲁棒性，并易于与其它算法相结合。然而，蚁群算法的搜索时间长、易陷入局部最优，基于这些缺陷，本文提出了一种改进的算法，并围绕其在TSP中的应用进行了深入的研究。本文的主要工作如下： 1.详细地介绍了蚁群算法的研究意义、发展历程、生物学原理以及最短路径问题的基本概念，并给出了蚁群算法求解TSP问题的数学模型和实现步骤。 2.本文针对三个重要的参数：信息素挥发系数ρ，信息素启发式因子α和期望启发式因子β，进行了大量的实验测试，确定了ACS算法参数的最优配置。 3.针对基本蚁群算法的缺陷，本文详细地介绍了两种改进算法，并针对其中一种——蚁群系统（ACS）提出了一种新的改进的蚁群算法：（1）信息素初始值的取法：通过比较任意两个城市之间的距离长度，得到两城市之间的最短距离，并记为lmin=min{dij}，则信息素初始值为τ0=1/n.dij；（2）信息素的更新规则：本文采用对至今最优、最差路径上信息素同时更新的方式；（3）引入Max—Min信息素系统：为了有效地抑制由于最优最差路径上信息素差距的急剧增大而引起的停滞现象，每次信息素更新后，将每条边上的信息量限制在一个范围[τmin,τmax]内。 将改进的蚁群算法用于TSP问题的求解。本文从TSPLIB中选取了十个TSP问题，采用MATLAB进行模拟，首先与蚁群系统所得的结果作比较，证明了改进算法的有效性，接着又与自组织神经网络算法进行了对比，进一步证实了改进算法具有很好的全局寻优性能。例如：将改进算法的运行结果与文献[35]中作者介绍的三种算法（F-W，NCSOM， ASOM）作比较，四种算法的平均相对误差分别为： F-W（10.81464%）、NCSOM（3.2416%）、ASOM（1.74936%）和改进的蚁群算法（0.73188%）。最后，本文运用改进的蚁群算法求解中国实际的最优路径问题，对于中国100个城市的TSP实例，四种算法的比较结果为：F-W（25958千米）、NCSOM（25983千米）、ASOM（25702千米）和改进的蚁群算法（20622.461635千米）。 最后，对全文的研究工作做了总结，并对蚁群算法的前景进行了展望，为今后的研究指明了方向。