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

作者：许智宏; 宋勃; 郭艳艳

来源：河北工业大学学报, 2010, (02): 48-51.

DOI：10.14081/j.cnki.hgdxb.2010.02.024

• 旅行商问题
• 模拟退火算法
• 蚁群算法
• 混合算法
• 并行计算 TSP
• simulated annealing algorithm
• ant colony algorithm
• hybrid algorithm
• parallel computing

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

• 出版日期2010
• 单位河北工业大学