基本蚁群算法的A.S.收敛性研究  

Research on the A.S.Convergence Properties of Basic Ant Colony Algorithm

作　　者：段海滨[1] 王道波[2] 于秀芬[3] 

机构地区：[1]北京航空航天大学自动化科学与电气工程学院,北京100083 [2]南京航空航天大学自动化学院,江苏南京210016 [3]中国科学院空间科学与应用研究中心,北京100080

出　　处：《应用基础与工程科学学报》2006年第2期297-301,共5页Journal of Basic Science and Engineering

基　　金：国家自然科学基金资助项目;江苏省"333"工程基金(JS200204)重点资助项目

摘　　要：蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化算法,虽然该算法已经在众多组合优化领域中得到广泛应用,但是对其收敛性尤其是A.S.(A lmost Surely)收敛性问题的研究还存在很多空白.本文在介绍蚁群算法基本原理的基础上,以Markov链和离散鞅作为研究工具,对基本蚁群算法的A.S.收敛性问题进行了理论证明,把最优解集序列转变为下鞅序列来考察残留信息素轨迹向量的收敛性,随后提出了基本蚁群算法首达时间的定义,并对基本蚁群算法首次到达时间的期望值进行了理论分析.Ant colony algorithm is a novel category of bionic meta-heuristic algorithm. Although ant colony algorithm for the heuristic solution of combinational optimization problems enjoy a rapidly growing popularity, but little is known about its convergence properties, especially its A. S. （almost surely） convergence properties. In this paper, we are concerned specifically with the A.S. convergence properties of the basic ant colony algorithm. Based on the introduction of the principle of basic ant colony algorithm, theoretical proof for the A.S. convergence properties of the basic ant colony algorithm is conducted by using Markov chains and martingale. The convergence properties of the pheromone trail vector is studied by changing the optimum solution set sequence into the submartingale sequence. Finally, the definition of the fir st passage time for the basic ant colony algorithm is proposed. Meanwhile, the theoretical analysis for the expected values of the first passage time is also performed in this paper.

关 键 词：蚁群算法 信息素 A.S.收敛性 MARKOV链 离散鞅 首达时间 

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