CAJ | 학술논문

针对城市路网最短路径求解过程中计算量庞大的问题，在分析遗传算法特征和缺陷的基础上，提出了基于MapReduce的并行遗传算法，并以长春市路网特征数据为基础验证了该算法的有效性。实验结果表明：基于MapReduce的并行遗传算法较传统遗传算法收敛速度快，运行时间短；随着并行节点数的增加，节点间的通信负荷加重，因此恰当地选择节点数尤为重要，合适的节点数可以提高运行效率。
침대성시로망최단로경구해과정중계산량방대적문제，재분석유전산법특정화결함적기출상，제출료기우MapReduce적병행유전산법，병이장춘시로망특정수거위기출험증료해산법적유효성。실험결과표명：기우MapReduce적병행유전산법교전통유전산법수렴속도쾌，운행시간단；수착병행절점수적증가，절점간적통신부하가중，인차흡당지선택절점수우위중요，합괄적절점수가이제고운행효솔。
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.