大规模组合优化问题蚁群算法应用研究

摘要

蚁群算法作为一种新型的模拟进化算法，是由意大利学者MacroDorigo等最早提出，它在解决组合优化问题方面效果显著。但是蚁群算法在求解大规模组合优化问题时其求解速度过慢，为了将蚁群算法成功的引入大规模组合优化问题的解决当中，本文在深入的探讨了组合优化问题和蚁群系统的基础上，结合了基本蚁群算法解决大规模组合优化问题的缺点，给出了如何运用蚁群算法解决大规模组合优化问题的策略以及相应的算法。 由于基本蚁群算法鲁棒性很强可以很容易和别的算法结合，所以改进后的算法运用了数据聚类，规则集挖掘，遗传算法等知识。为了解决蚁群算法求解大规模TSP问题时速度较慢的缺点，本文提出了几点改进措施，首先，利用遗传算法对蚁群的参数进行了进化，得到了较为理想的参数配置，该参数配置可以针对问题规模的大小对参数进行合理配置，而合理配置的蚁群算法参数有利于算法运行速度的提高和得到较优的运行结果。其次，利用聚类算法对所给问题进行聚类得到几个规模较小的子问题，对每个子问题分配参数，然后并行运算，同时针对聚类算法的波动性进行了一定的探讨。其三，针对蚁群算法中当循环进行到一定程度的时候，在局部内可能已经存在的局部最优路径，可以通过分类算法将这些局部内的最优路径找出来，归并为一个城市，并且利用模式学习不断的分析判断求解得到的局部最优路径是否出现在全局最优路径终，由此可以避免大量的重复计算，进而减少收敛时间。其四，利用信息熵作为判断算法结束的条件，改变原有的利用迭代次数最为结束条件的方法。 通过选取TSPLIB95中几个经典的TSP问题作为实例进行模拟测试，该算法对于大规模优化组合问题有一定的解决能力。

目录

郑重声明

摘要

第一章绪论

第二章大规模组合优化问题

第三章蚁群系统(ACS)

第四章运用蚁群算法中求解大规模TSP问题

第五章实验结果分析

第六章结束语

致谢

参考文献

附录1