论文部分内容阅读
蚁群优化算法(ant colony optimization, ACO)由意大利学者Marco Dorigo, VManiezzo ,A. Colorni于1992年首先提出,是基于蚂蚁群体觅食过程中沿着最短路径行进的这种生物学行为发展起来的一类群智能优化方法。在解决传统优化方法难以奏效的具有NP-hard特性的组合优化问题中利用该算法取得了令人鼓舞的效果,因而受到了学术界以及工业界的广泛关注。目前,蚁群优化算法已经成为计算智能方法中的一个重要分支,成为当下蓬勃发展的热点研究课题之一。蚁群优化算法的理论研究相对滞后,特别是算法的参数选择和收敛性证明方面还有待于进一步研究。虽然,该研究方法处于研究的初级阶段,但是一些研究成果已经显示出蚁群系统在求解复杂优化问题方面的优越性。目前,蚁群系统己成功应用于求解旅行商问题(Traveling salesman problem TSP)、二次分配问题(QAP)和job-shop调度问题,取得了很好的实验效果。TSP(Travelling Salesman Problem)也称作货郎担或巡回售货员问题,在运筹学、管理科学及工程实际中具有广泛的用途。TSP问题是组合优化中的著名难题,一直受到人们的极大关注。由于其NP难题性质,至今尚未完全解决。本文的主要工作如下:1.对蚁群算法的基本理论以及在TSP问题中的应用进行了较为深入和系统的研究。介绍了蚁群算法的基本原理、特点、构成和算法的实现方法。2.基本蚁群算法由于存在搜索时间长,易陷入局部最优解等突出缺点,使得求解效果不是很好。针对这些缺陷,提出了利用改进的蚁群算法求解TSP问题。改进主要在参数的初始化、状态转移概率的选择策略以及信息素更新方法的改进三个方面。①对于一个初始的TSP,首先考虑对其进行预处理。在利用蚂蚁算法求解问题之前,先用近邻法构造一个初始游历,并计算信息素初值。②利用Dorigo M等提出的Ant-Q Systems算法,采用确定性和随机性选择相结合的选择策略,并在搜索过程中动态调整状态转移概率。③信息素更新采用在线单步更新信息素及离线全局更新信息素相结合的方法,即在蚂蚁巡游过程中在线单步更新信息素以及在本次迭代结束时离线全局更新信息素。将以上三步算法的改进结合起来,用MATLAB模拟,选取了TSPLIB中的十个TSP问题进行实验,并与用基本蚁群算法做的结果以及现在应用比较广泛的遗传算法的结果做了比较。然后运用改进的蚁群算法对以中国100城市为代表的中国旅行商问题进行了数值模拟并与用基本蚁群算法做的结果以及神经网络算法求解的结果做了比较。结果表明虽然运行时间变长了,但改进后的蚁群算法在全局搜索最优解能力上要好很多,在稳定性和收敛性方面也有了较大提高。最后对全文的研究工作进行了总结,并展望了蚁群算法进一步还要研究的课题。