基于并行遗传算法的配送路线求解

A Solution to distribution routing of logistics problem Based on Parallel Genetic Algorithm

遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律演化而来的随机化搜索方法,已经成功运用在很多大规模的组合优化问题中。利用如今流行的并行计算机系统,对遗传算法进行并行化,可解决标准遗传算法的速度瓶颈问题。本文在MPI并行环境下,用C++语言实现了粗粒度模型的并行遗传算法。结合并行遗传算法的特点,提出了解决物流配送路线优化的策略以及给出相应的算法过程,并进行了有效验证。通过研究结果表明,与传统遗传算法相比,并行遗传算法提高了运算速度,降低了平均开销时间并且最小总路径值更理想。

Genetic Algorithm is a randomized search method evolved from reference about biosphere＇s evolution rule （genetic mechanisms of survival of the fittest,die out of the inferior） the has been successfully used in many large-scale Combined optimization problems.parallelization to the genetic algorithm based on the popular parallel machine system in present, can solve the problem of speed bottleneck of standard genetic algorithm.In this paper, under MPI, parallel genetic algorithms based on coarse-grained model was realized in this article, which C＋＋ language was used. Combining the characteristics of parallel genetic algorithm, a strategy of optimize the distribution lines of logistics was proposed, the corresponding process of algorithm were also given, and an effective verification was conducted. The results show that parallel genetic algorithm improves the computing speed, reduces the average cost of time and the total-path-shortest is better compared with the traditional genetic algorithm.