一种基于域密度的蚁群系统(AS)改进算法及结果解析  

An improved AS algorithm and result analyzing based on domain and its density

作　　者：林建兵[1] 陈智雄[2] 姚国祥 

机构地区：[1]莆田学院信息工程学院,福建莆田351100 [2]莆田学院数学学院,福建莆田351100 [3]莆阳网络系统公司,福建莆田351100

出　　处：《武汉大学学报（工学版）》2016年第4期627-634,共8页Engineering Journal of Wuhan University

基　　金：国家自然科学基金(编号:61373140);福建省科技厅重大项目(编号:2012H1009)

摘　　要：针对蚁群算法在求解类似TSP问题时,所涉及图的节点分布在总体上具有显著差异的情况,定义域和密度的概念,在此基础上提出具有域和密度特征的AS改进算法DDACO.对DDACO算法的基本原理和策略进行了介绍,通过判断节点是否位于优先域,进而对信息素和下一节点的选择概率进行处理,以改进AS算法.对DDACO算法的具体构建过程进行了详细地描述,利用实例数据对算法构建的过程进行了说明.最后分别对DDACO和AS求解TSP问题分别进行实验测试,分析了测试结果差别的原因.测试的最终结果表明,DDACO在解决具有显著节点密度差异和节点规模比较大时和AS算法相比在时间和收敛性上具有明显的优势.The distributing characteristics of nodes in a graph in which the ant system（AS）deals with in the travelling salesman problem（TSP）,can be have apparent difference;in order to suit for the situation,this article first studies the distributing characteristics of nodes in graph,then defines the concepts of nearby-domain and density,in the basis of nearby-domain and density,the article puts forward the domaindensity ant colony optimization（DDACO）algorithm.The basic strategy of DDACO is described and the detail process of constructing the algorithm is introduced.Finally,this article makes some simulation experiments for TSP with DDACO and AS.The results show that the DDACO is more effective than AS when the relating graphs have significant difference of density and a large number of nodes.

关 键 词：TSP 蚁群系统(AS) 域 密度 DDACO 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]