蚁群算法的鞅过程及收敛性分析  

The martingale process of the ant colony algorithm and its convergence analysis

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

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

出　　处：《华中科技大学学报（自然科学版）》2013年第S1期89-91,共3页Journal of Huazhong University of Science and Technology(Natural Science Edition)

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

摘　　要：给出了一类基于GBAS/tdlb策略改进蚁群算法的收敛性分析.证明了转移路径向量列是状态有限的马尔可夫链,通过分析代价函数值序列的条件期望,证明代价函数值序列是非负下鞅.算法首次发现最优解时的迭代次数是一个停时,证明了代价函数值序列的期望有限,进一步从代价函数值序列的停止过程得出算法在有限步内以概率1收敛.收敛性分析为探讨蚁群算法与其他仿生优化算法的融合奠定一定的理论基础.An improved ant colony algorithm based on GBAS/tdlb strategy was given and its convergence was analyzed.It is proved that vector sequence of the transition path was a Markov chain with finite states.By analyzing the conditional expectation of cost function sequence,that the cost function sequence was non-negative submartingale was proved.Then the number of iterations finding optimal solutions firstly was a stopping time.And that the expectation value of cost function sequence was finite was proved.Further,by using the stopping process of the cost function sequence,it was concluded that the algorithm converges within a finite number of iterations with probability 1.Convergence analysis explore a new method for the further study of the ant colony algorithm,and makes some theoretical foundations for other bionic optimization algorithms.

关 键 词：蚁群算法 鞅过程 停时 收敛性分析 马尔可夫链 

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