基于Hama并行蚁群算法模型及TSP应用研究

来源：交通运输系统工程与信息杂志2016年第3期北京时间：

作者：马继辉，余明捷，陈鑫杰，宋翠颖，杨扬

单位：北京交通大学交通运输学院，北京100044

摘要：Hama 是建立在Hadoop 上的分布式并行计算模型，基于BSP (Bulk Synchronous Parallel, BSP)计算技术的开放式并行计算平台，它的主要功能是支持并行及大数据的科学计算.目前改进传统启发式算法，移植到Hama平台提高算法效率是研究热点之一.蚁群算法是适应性极强的启发式算法，应用广泛，但由于蚁群中个体的随机性，解的收敛速度与解的多样性、稳定性之间存在矛盾.而该矛盾可通过将蚁群算法并行化得到缓解，算法求解性能因此得到提升.本文在Hama 平台上，选择以信息素矩阵进行交互的策略，建立了并行蚁群算法模型，并通过该模型求解多种规模下的旅行商问题.实验表明，本文提出的并行蚁群算法模型可行，并能有效地提高算法性能.

关键词：信息技术,蚁群算法,Hama,并行,TSP,共享信息素矩阵

基金资助：科技部“863”项目/ Ministry of Science and Technology 863 Plan（2015AA124103）.