蚁群优化算法的理论研究进展

PDF下载HTML

Title:

Advances in theoretical research of ant colony optimization

作者:

夏小云^1,2, 周育人³

1. 江西理工大学信息工程学院, 江西赣州 341000;
2. 华南理工大学计算机与工程学院, 广东广州 510006;
3. 中山大学数据科学与计算机学院, 广东广州 510006

Author(s):

XIA Xiaoyun^1,2, ZHOU Yuren³

1. School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China;
2. School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China;
3. School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China

关键词:

蚁群优化算法; 理论研究; 组合优化; 收敛性; 时间复杂度; 近似性能

Keywords:

ant colony optimization; theoretical research; combinatorial optimization; convergence; time complexity; approximation performance

分类号:

TP18;TP301.6

DOI:

10.11992/tis.201510002

摘要:

蚁群优化算法的理论研究有助于更好地理解算法的原理以及指导算法应用。回顾了蚁群优化算法的收敛性分析、时间复杂度分析与近似性能分析等理论研究进展,分析了其理论研究的对象从简单的拟布尔函数转为组合优化问题以及实际应用问题。从蚁群算法理论分析方法和研究问题类型2个方面对蚁群算法的理论研究进行综述。介绍了适应值划分、漂移分析等最基本的数学分析工具,对时间复杂性及近似性能等重要问题进行了探讨。总结比较了蚁群算法求解各类问题的性能,指出这些研究能够更加深入了解蚁群算法的运行机制。最后,探讨了目前蚁群算法理论研究中亟待解决的问题,指出引入新的分析工具以及研究更为复杂的算法模型等是值得进一步研究的方向和内容。

Abstract:

Theoretical investigations of the ant colony optimization (ACO) algorithm can help to improve our understanding of the theoretical basis of the algorithm and guide its appropriate application. Theoretical research on ACO has included analyses of early convergence, time complexity, and approximation performance. Investigation objectives have ranged from simple Boolean functions, to combinatorial optimization and practical application problems, to the analysis of NP-hardness problems. In this paper, we survey state-of-the-art theoretical ACO research from two aspects: the most common mathematical techniques and those less common. In addition, we introduce two mathematical analysis tools, including fitness value partitioning and drift analysis, and discuss important ACO issues, including ACO runtime analysis and approximation performance. More specifically, we provide comparative results for ACO’s performance in solving various problems. These studies provide a direction for better understanding the working principles of ACO. Finally, we highlight further research directions, including the introduction of new analytical tools and the study of more complicated algorithmic models.