一种求解TSP问题的多种群并行遗传算法

A Multi-Group Parallel Genetic Algorithm for TSP

遗传算法是一种基于自然群体遗传机制的有效搜索算法,由于它在搜索空间中同时考虑许多点,减少了收敛于局部极值的可能,也增加了处理的并行性。因此可以利用并行遗传算法研究典型的TSP问题的求解。提出一种有效的多种群并行算法求解旅行商(TSP)问题,应用多种群遗传并行进化的思想,并在种群之间进行遗传信息交流,以解决经典遗传的收敛到局部最优值问题。仿真实验结果表明,方法在解的精度上以及解的质量上优于经典的遗传算法。

Genetic algorithm is an effective search algorithm based on the natural genetic mechanism.Because it takes into account a number of points,so it may reduce the convergence in the local minimum,and will increase the parallel processing.So the parallel genetic algorithm can be used to solve typical TSP problem.This paper presents an effective multi-group parallel algorithm for solving traveling salesman（TSP） problem.By using parallel genetic evolution,and making genetic information exchange between populations,the classical convergence problem will be solved.The experimental results show that the accuracy and quality of the method are better than that of the classical algorithms.