基于MapReduce的改进蚁群算法在TSP中的应用  

APPLICATION OF IMPROVED ANT COLONY ALGORITHM IN TSP BASED ON MAPREDUCE

作　　者：何广才[1] 周根宝[1] 

机构地区：[1]内蒙古农业大学计算机信息与工程学院,呼和浩特010018

出　　处：《内蒙古农业大学学报（自然科学版）》2015年第5期125-132,共8页Journal of Inner Mongolia Agricultural University(Natural Science Edition)

基　　金：内蒙古自然科学基金(200408020110)

摘　　要：针对基本蚁群算法在处理中等规模TSP问题上存在着收敛速度慢、停滞和易出现结果早熟等现象,提出了1种云计算环境下将双倍体免疫算法与蚁群算法相结合的策略,并在MapReduce计算模型上实施。该策略通过混沌扰动原理对蚁群算法中调节参数α设计动态变化和全局参数ρ进行自适应调节,在免疫算法中融合双倍体免疫机制形成双倍体免疫算法,并将疫苗的思想引入到蚁群算法中,使结合的新算法具有蚁群算法的自适应反馈机理,收敛速度快和免疫算法维持种群多样性,防止种群退化等特性,目的是改进的蚁群算法能加快搜索的速度、避免陷入局部最优解和更好的寻找到较优的路径结果,最终将其部署在Hadoop云计算平台上运行。仿真实验结果表明,融合后的新算法与双倍体免疫算法和蚁群算法相比较,既提高了运行的速度和空间的搜索效率,同时又进一步改善了路径的寻优结果,新算法在解决多结点的TSP问题上,证明了MapReduce计算模型的并行高效性。In view of the basic ant colony algorithm in handling medium-sized TSP problems prescents slow convergence speed,stagnation and prone to result premature phenomenon etc. For this case put forward a cloud computing environment by combining the immune algorithm with ant colony algorithm strategy,and implementation in MapReduce computing model. The strategy in the ant colony algorithm by chaotic perturbation theory to alpha parameter of design of dynamic change and adaptively adjust the global parameterρ,fusion diploid immune mechanisms in the immune algorithm to form a diploid immune algorithm,and introduces the ideas of the vaccine to the ant colony algorithm,making the combinative new algorithm with the adaptive feedback mechanism,fast convergence rate of ant colony algorithm and immune algorithm to keep population diversity,prevent the degradation of population characteristics,the purpose is to accelebrate the search speed and avoid falling into local optimal solution and find the path results in improved ant colony algorithm is better and better,eventually to be deployed in a Hadoop cloud computing platform to run. Simulation results show that,compared the fusion of the new algorithm with immune algorithm and ant colony algorithm,not only improves the operation speed and space search efficiency,and further improve the path optimization results,the new algorithm in TSP problem of solving many nodes,to be proved the more efficience of parallel MapReduce computing model.

关 键 词：蚁群算法 TSP MAPREDUCE 双倍体免疫算法 HADOOP 

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