基于知识库的动态蚁群算法  

Dynamic Ant Colony Algorithm Based on Knowledge Base

作　　者：孙勇[1,2] 李妮[1] 龚光红[1] 韩亮[1] 

机构地区：[1]北京航空航天大学自动化科学与电气工程学院,北京100191 [2]中国兵器科学研究院,北京100089

出　　处：《北京工业大学学报》2012年第3期374-379,共6页Journal of Beijing University of Technology

基　　金：教育部高等学校博士学科点专项科研基金资助项目(20091102120013)

摘　　要：针对蚁群算法收敛速度慢、易陷入局部极值等问题,将其与知识库结合,提出了基于知识库的动态蚁群算法.知识库包括算法知识、规则知识和案例知识,存储了定性或定量的算法参数、参数选择方法和历史数据.基于知识库和问题特性,本算法产生初始状态并动态调整参数,在运行过程中根据赌轮法选择算子并适时引入扰动,在不影响搜索过程随机性的前提下较快地收敛于全局最优值.分别用本算法和其他主流算法解决TSPLIB中的Eil51和CHN144实例,比较优化性能、时间性能和鲁棒性3个指标,结果表明本算法均有明显优势.The ant colony algorithm （ACA） has optimums. Therefore, the characteristics of the algorithm （DACA） based on knowledge base is rule, and case knowledge. The qualitative or the limitation of stagnation and is easy to fall into local algorithm are researched, and a dynamic ant colony proposed. The knowledge base consists of algorithm, quantitative algorithm parameter, parameter choosingmethod, and history data are saved to the knowledge base. DACA generates an initial state, dynamically adjusts the parameter based on the knowledge base and model state, and chooses the parameter through roulette wheel selection. DACA can quickly converge to the global optimization solution without theinfluence of random search process. Eil51 and CHN144 are solved by DACA and other algorithms. Result shows that DACA is the best in optimization performance, time performance, and robustness.

关 键 词：蚁群算法 知识库 动态算法 旅行商问题 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]