基于分层搜索的蚁群算法及收敛性分析  

ANT COLONY ALGORITHM BASED ON HIERARCHICAL SEARCH AND ITS CONVERGENCE ANALYSIS

作　　者：刘锴[1] 游晓明[1] 刘升[2] 

机构地区：[1]上海工程技术大学电子电气工程学院,上海201620 [2]上海工程技术大学管理学院,上海201620

出　　处：《计算机应用与软件》2016年第2期208-211,共4页Computer Applications and Software

基　　金：国家自然科学基金项目(61075115);上海市教委科研创新重点项目(12ZZ185);上海市学科专业建设项目(XKCZ1212)

摘　　要：针对蚁群算法容易陷入局部最优的问题,提出一种新的解决连续空间优化的蚁群分层搜索算法。该算法将蚁群搜索空间逐层分割,用信息素分布函数给出了基于分层结点的信息素分布方法。定义了适用于连续域的信息素局部更新、全局更新、状态转移规则,其中局部更新算子能够通过选取合适的参数来增加解的多样性。实验结果表明,相比传统算法,该算法全局搜索能力强,求解精度更高。该算法能达到连续域问题的理论最优值,通过下鞅的停时理论证明了算法以概率1收敛。For ant colony algorithm easily falling into local optimum, we proposed a novel ant colony hierarchical search algorithm for solving continuous space optimisation. The algorithm partitions the ant colony search space hierarchically, and presents a hierarchical nodes- based pheromone distribution approach with pheromone distribution function. We defined the rules of pheromone local update, global update and state transition suitable for continuous domains, in which the local update operator could increase the diversity of solutions by selecting the appropriate parameters. Experimental results showed that comparing with traditional ant colony algorithms, the ant colony hierarchical search algorithm had stronger global search capability and higher solution accuracy. It could achieve the theoretical optimum of continuous domains problem. Moreover, by using the stopping theory of submartingale, it was concluded that the algorithm converges with probability 1.

关 键 词：蚁群算法 连续空间优化 分层搜索 下鞅 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]