Improved Fireworks Algorithm For Solving Travel Salesman Problems

Traveling salesman problems are essentially a combinatorial optimization problem and has an important place in computer science and operations research as well as in engineering applications.Small-scale traveling salesman problems can be solved directly by exact algorithms,while for large-scale traveling salesman problems heuristic algorithms are required.Traditional heuristic algorithms still have some limitations in solving large-scale traveling salesman problems,such as insufficient convergence accuracy and tendency to fall into local optimal solution.The main purpose of this paper is to solve traveling salesman problems and its derivative problems more efficiently.For the single traveling salesman problem,an improved fireworks algorithm for gene fragment selection is proposed in this paper to solve the problem of low convergence accuracy of the traditional fireworks algorithm.The algorithm generates the initial population by the nearest neighbor algorithm and selects the next generation population by the "elite strategy-no put-back roulette";the explosion operator is discretized and the fireworks individuals are optimized by the minimum incremental deletion insertion operation.An improved fireworks algorithm for gene fragment selection to solve the single traveling salesman problem is obtained by applying the idea of adaptive probability acceptance of neighborhood solutions with simulated annealing and using inverse variation instead of Gaussian variation to select the optimal few fireworks for gene fragment selection strategy.The improved algorithm is validated by experimental data.For the multi-traveling salesman problem,this paper takes the discrete fireworks algorithm as the framework and organically integrates four variation operations(gene random insertion,gene fragment right shift,gene fragment left shift,and gene fragment flip)in the uniparental genetic algorithm as the explosion operator to increase the diversity of the population.Elite selection strategy for populations.This article optimizes the variation operator,proposes a local optimization strategy for variable neighborhood search and applies it to the firework algorithm.Finally,the algorithm is used to perform simulation experiments on several cases.