蚁群优化算法的计算时间分析

近年来，蚁群优化算法成功应用于各种经典NP-难组合优化问题问题和大量工业工程应用问题，蚁群算法的理论研究的必要性和迫切性日显突出。时间复杂度是刻画算法性能的基本指标，本项目分析蚁群算法求解组合优化问题的时间复杂性。构造可供时间复杂性分析的旅行商问题（TSP）、命题逻辑公式的可满足问题（SAT）、顶点覆盖问题等组合优化问题实例，讨论蚁群算法多项式时间和指数时间分界，分析算法中参数和变量的作用，比较各种不同蚁群算法的计算时间，建立蚁群算法时间复杂性分析理论模型、方法和分析框架。本项目突破目前蚁群算法仅仅研究人工布尔函数的局限，分析真实世界组合优化问题的蚁群算法时间复杂性，解决当前蚁群算法理论研究急需的公开性问题，其研究将有助于建立蚁群算法的基础理论。