基于云计算的城市路网最短路径遗传算法求解

摘要

Aiming at the heavy calculation load existing in the solution to the shortest path in urban road networks, this paper proposes a parallel genetic algorithm based on MapReduce in light of analysis of the features and short-comings of genetic algorithm,and has validated the effectiveness of this algorithm based on Changchun Citys data of road network features. Experimental results show that the proposed algorithm based on MapReduce is of faster convergence rate and shorter running time in comparison with the traditional genetic one;and that the inter-node communication load increases as parallel nodes increase,so that proper selection of node number plays a key role in enhancing the operation efficiency.%针对城市路网最短路径求解过程中计算量庞大的问题，在分析遗传算法特征和缺陷的基础上，提出了基于MapReduce的并行遗传算法，并以长春市路网特征数据为基础验证了该算法的有效性。实验结果表明：基于MapReduce的并行遗传算法较传统遗传算法收敛速度快，运行时间短；随着并行节点数的增加，节点间的通信负荷加重，因此恰当地选择节点数尤为重要，合适的节点数可以提高运行效率。