一种改进并行遗传算法解决TSP

Travelling Salesman Problem based on a reformed parallel genetic algorithm

针对旅行商问题(Travelling Salesman Problem,TSP)的遗传算法的大规模操作,需要大量运算时间而且容易造成局部最优解,提出一种并行混合遗传算法。该方法基于MPI并行环境,利用种群中选择、交叉、变异操作的并行化,将种群中个体平均的分配到处理器中进行操作,有效地避免局部最优解的出现和减少算法的运行时间。实验证明该方法相对于简单遗传算法具有更强全局寻优能力以及耗费更少的操作时间。

The operation of the genetic algorithm of Travelling Salesman Problem（TSP） needs lots of time and it is easy to fall into the local optimal solution.In order to avoid the problem ,the parallel compound genetic algorithm is proposed.The method,which avoids the local optimal problem and reduces the time of the operation,makes use of the parallel of the selection,the cross,the variation.The amount of species distributes the average to the CPU for operating in the environment of MPI.The experience proves the time of the operation less than the simple genetic algorithm and strengthens the ability of the global optimal solution.