模拟退火与蚁群混合并行算法解旅行商问题

求解TSP问题的智能优化算法主要包括蚁群算法和模拟退火算法等,这些算法求解TSP问题的速度比传统的精确求解算法有很大改进,但在问题的求解空间逐渐增加时,串行执行速度往往还是无法满足人们的需求.针对此问题,研究了蚁群算法、模拟退火算法以及两者的混合算法的并行实现方法,建立了PC机群实验平台,基于MPI环境对蚁群算法、模拟退火算法以及混合算法的并行算法进行了测试.根据理论研究和实际测试的结果,比较了并行算法和传统串行算法的性能差异,总结了利用PC机群系统求解旅行商问题的并行求解的可行性,得出了关于并行效率等方面的一些有意义的结论.

Using Ant Colony Algorithm and Simulated Annealing Parallel Algorithm to Solve Traveling Salesman Problem

The intelligent optimization algorithms for solving TSP mainly include ant colony algorithm and simulated annealing,etc. These algorithms have significant advantages and run faster than traditional exact algorithms. But,the speed is often impossible to meet people's need as the scale of TSP increase gradually. For the problem. this paper discussed the parallel methods to implement the ant colony algorithm,the simulated annealing and the hybrid algorithm,established a cluster of PCs system,and tested the parallel algorithms in MPI. Based on the theoretic and practical study, the performance differences between parallel algorithms and traditional algorithms were analyzed,the feasibility of proceeding parallel algorithm to solve TSP in cluster of PCs was discussed and some meaningful conclusions about parallel efficiency were achieved