带固定半径近邻搜索3-opt的离散烟花算法求解旅行商问题

Discrete fireworks algorithm with fixed radius nearest-neighbor search 3-opt for travelling salesman problem

传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题。针对旅行商问题的特点,提出一种带固定半径近邻搜索3-opt的离散烟花算法。该算法基于基本烟花算法进行离散化改进,采用整数编码的路径表示方法来表示旅行商问题的解,对爆炸算子、高斯变异算子进行离散化操作策略设计。为了使算法具有较好的局部搜索能力,提出固定半径近邻搜索3-opt策略来提高算法精度和收敛速度,同时采用不检测标志策略提高算法效率。实验结果表明:该算法能有效地求解旅行商问题,其离散烟花算子在全局收敛能力、收敛精度、求解时间和稳定性等方面均优于传统烟花算子;基准测试算例的最优解平均误差率仅为0.002%,优于对比算法。

The traditional fireworks algorithm has slow convergence speed and low precision when solving large-scale discrete problems.Aiming at the characteristics of travelling salesman problem,this paper proposed a discrete fireworks algorithm with fixed radius nearest-neighbor search 3-opt.It discretized and improved the proposed algorithm based on the basic fireworks algorithm,where adopted the integer coding path representation method to represent the solution of the travelling salesman problem,as well as designed the explosion operator and the Gauss mutation operator of the algorithm for discretization solution.To enhance local search ability of the algorithm,the algorithm proposed implements 3-opt local search to strengthen search ability of the algorithm,and introduced the fixed radius of neighbor search and don’t-look-bits strategy to improve the efficiency of the algorithm.The experiments indicate that the proposed algorithm solves travelling salesman problem effectively.The discrete fireworks operator proposed is superior to the traditional fireworks operator in global convergence ability,convergence accuracy,solution time and stability.The average costs of the solutions of the algorithms for all benchmark instances probed have an overall deviation in only 0.002%from those of the best known solutions,which is lower than those of all comparing algorithms.