改进细菌觅食算法在TSP问题中的应用

Improvement of Bacterial Foraging Algorithm in TSP Problem

在解决旅行商问题(TSP)时,细菌觅食算法因其并行搜索和易跳出局部最优解的优点在众多算法中脱颖而出,但仍存在收敛速度慢、搜索精度不够高等缺点,为改进以上缺陷,对其种群数量、趋化和迁徙过程进行了优化。首先用较大初始种群数目保证算法的求解精度,接着合理调控求解过程中的细菌数量,减少不必要的计算以提高求解速度,然后为趋化过程引入局部搜索能力较强的2-opt算法提高局部搜索的精度,最后结合Prim算法和连续出度法改进迁徙算子提高其全局搜索能力。在Matlab中对TSPLIB数据进行仿真后,结果表明改进算法比基本细菌觅食算法、差分算法和蚁群算法具有更好的收敛效果和求解精度,体现了该算法的有效性和可靠性。

This paper optimizes its population,chemotaxis and migration process.Firstly,uses enough initial population size to ensure the accuracy of the algorithm.Secondly,regulates the number of bacteria in the solution process reasonably,reducing unnecessary calculations to increase the solution speed.Thirdly,this paper introduces 2-opt algorithm with strong local search capability in chemotaxis process.Finally,uses Prim algorithm and continuous output method in migration operator to improve the global search ability.