|
|||||
|
|
| 基本蚁群算法的A.S.收敛性研究 | |
| 引用本文： | 段海滨,王道波,于秀芬.基本蚁群算法的A.S.收敛性研究[J].应用基础与工程科学学报,2006,14(2):297-301. |
| 作者姓名： | 段海滨 王道波 于秀芬 |
| 作者单位： | 1. 北京航空航天大学自动化科学与电气工程学院,北京,100083 2. 南京航空航天大学自动化学院,江苏,南京,210016 3. 中国科学院空间科学与应用研究中心,北京,100080 |
| 基金项目： | 国家自然科学基金;江苏省333新世纪科学技术带头人培养工程 |
| 摘 要： | 蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化算法，虽然该算法已经在众多组合优化领域中得到广泛应用，但是对其收敛性尤其是A．S．（AlmostSurely）收敛性问题的研究还存在很多空白．本文在介绍蚁群算法基本原理的基础上，以Markov链和离散鞅作为研究工具，对基本蚁群算法的A．S．收敛性问题进行了理论证明，把最优解集序列转变为下鞅序列来考察残留信息素轨迹向量的收敛性，随后提出了基本蚁群算法首达时间的定义，并对基本蚁群算法首次到达时间的期望值进行了理论分析． |
| 关 键 词： | 蚁群算法 信息素 A.S.收敛性 Markov链 离散鞅 首达时间 |
| 文章编号： | 1005-0930(2006)02-0297-05 |
| 收稿时间： | 06 3 2005 12:00AM |
| 修稿时间： | 03 3 2006 12:00AM |
Research on the A. S. Convergence Properties of Basic Ant Colony Algorithm |
|
| DUAN Haibin,WANG Daobo,YU Xiufen.Research on the A. S. Convergence Properties of Basic Ant Colony Algorithm[J].Journal of Basic Science and Engineering,2006,14(2):297-301. | |
| Authors: | DUAN Haibin WANG Daobo YU Xiufen |
| Institution: | 1. School of Automation Science and Electrical Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China; 2. College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China; 3. Center for Space Science and Applied Research, Chinese Academy of Sciences, Beijing 100080, China |
| Abstract: | 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. |
| Keywords: | ant colony algorithm pheromone A S convergence properties Markov chains martingale first passage time |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |