基于MapReduce的动态自适应蚁群算法设计与实现

Design and implementation of dynamically adaptive ant colony optimization based on MapReduce

针对基本蚁群算法(ACO)在处理中等规模旅行商问题(TSP)上消耗时间过长的问题,提出一种基于MapReduce的动态自适应蚁群算法(MDACO)。该算法在信息素更新策略方面动态地调整信息素挥发系数,使蚁群能够自适应地寻找较优的路径结果,而且采用MapReduce计算模型将蚁群算法中循环迭代部分并行化,最终将其部署在Hadoop云计算平台上运行。当TSP节点数为150及以上时,该算法比基本蚁群算法的运行时间平均减少43.2%,路径寻优结果也得到进一步改善。仿真结果表明,该算法在保证问题求解质量以及提高求解速度方面具有优越性。

When dealing with medium-scale Traveling Salesman Problem （ TSP ） , the basic Ant Colony Optimization （ ACO） would consume a long time. To solve the problem, a Dynamically adaptive Ant Colony Optimization based on MapReduce （ MDACO） was proposed. In order to make the ant group adaptive to search the best path, this algorithm dynamically adjusted the volatilization coefficient in pheromone update strategy, it also used the parallel calculation model of MapReduce to parallel the loop iteration part of ACO and eventually deployed it on the Hadoop cloud computing platform. When the number of TSP nodes was greater than 150, the experimental results show that the running time of MDACO could be increased by 43. 2% than the basic ACO, and it also improved the path optimization results. The simulation results show that the MDACO is more efficient in guaranteeing the quality of problem solution and running speed.