自适应的并行蚁群算法  

Adaptive Parallel Ant Colony Algorithm

作　　者：陈崚[1,2] 章春芳[1] 

机构地区：[1]扬州大学信息工程学院计算机系 [2]南京大学计算机软件新技术国家重点实验室,江苏南京210093

出　　处：《小型微型计算机系统》2006年第9期1695-1699,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60473012)资助;国家科技攻关基金项目(2003BA614A-14)资助;江苏省自然科(BK20005047)资助;南京大学软件新技术国家重点实验室开放基金资助

摘　　要：本文根据影响并行蚁群算法性能的关键因素,提出了一种自适应的并行蚁群算法.首先提出了基于适应度和基于距离选择的两种不同的信息交流策略,使得各处理机自适应地选择与之进行信息交换的处理机,然后采用自适应的更新策略进行信息素的更新.为了增强该算法的搜索能力,还根据解的多样性给出了自适应地调节处理机之间的信息交流周期的方法.在M PP处理机深腾1800上对TSP问题的实验结果表明了该算法在保证有效的加速比的同时,具有很好的收敛性.An adaptive parallel ant colony algorithm is presented by considering the critical factors influencing the parallelization of the ant colony algorithm. Two different strategies for information exchange between processors are proposed： selecting the partner processor based on the fitness and on the distance. These strategies enable each processor to choose the partner proces- sor to communicate and update the pheromone adaptively. In order to increase the ability of optimization and to avoid early convergence, we also propose a method of adjusting the iteration interval adaptively according to the diversity of the solutions. These techniques are tested on the traveling salesman problem using the massive parallel processors （MPP） Shengteng1800. Experimental results show that our algorithm can converge very quickly and has high speedup.

关 键 词：蚁群优化算法 并行 多样性 旅行商问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]