面向TSP问题的改进信息素启发因子蚁群算法研究

Research on Improved Pheromone Heuristic Factor Ant Colony Algorithm for TSP Problem

针对蚁群算法解决TSP问题时容易陷入局部最优的问题,提出一种采用自适应改变信息素启发因子和模拟退火扰动机制的方法。首先,在算法搜索初期阶段采用较小的信息素启发因子,以增强个体搜索过程中选择路径的随机性。其次,当算法首次陷入局部最优时,通过自适应增大信息素启发因子的方法加强局部搜索能力。最后,在蚁群算法搜索后期阶段,借鉴模拟退火算法原理,通过在全局最优解上加入随机扰动的方式,加强算法跳出局部最优的能力。仿真结果表明,针对不同规模的TSP问题,改进的蚁群算法精度至少提高3%。

For the problem that the ant colony algorithm is easy to fall into local optimum when solving the TSP problem,a method using adaptive change of pheromone heuristic factor and simulated annealing perturbation mechanism is proposed.Firstly,a smaller pheromone heuristic factor is used in the initial stage of algorithm search to enhance the randomness of path selection during individual search.Secondly,the local search capability is enhanced by adaptively increasing the pheromone heuristic factor when the algorithm falls into a local optimum for the first time.Finally,in the later stage of the ant colony algorithm search,the ability of the algorithm to jump out of the local optimum is enhanced by adding a random perturbation to the global optimum solution by drawing on the principle of simulated annealing algorithm.The simulation results show that the accuracy of the improved ant colony algorithm is improved by at least 3%for different sizes of TSP problems.