Hybrid Beetle Antennae Search Algorithm For Traveling Salesman Problem

Traveling salesman problem(TSP)is a classical combinatorial optimization problem.It is widely used in PCB drilling,genome sequencing,aircraft routing and crystal structure analysis.Traveling salesman problem is also a NP hard problem,which plays an important role in operational research and theoretical computer science.Therefore,solving TSP has important theoretical research value and engineering application background.It has become one of the research hotspots in combinatorial optimization.TSP is a NP hard problem,and its exact algorithm has been eliminated.Many researchers at home and abroad use swarm intelligence optimization algorithm to study TSP,and have achieved fruitful results.Because swarm intelligence optimization algorithm belongs to approximate algorithm,there are still some shortcomings when using swarm intelligence optimization algorithm to solve TSP,such as poor convergence and easy to fall into local optimization.In order to solve the traveling salesman problem more effectively,this paper mainly does the following work:Firstly,the beetle antennae search algorithm(BASA)is improved to make it suitable for the TSP.The main improvements include the determination of city number and city order suitable for solving TSP,and the calculation of fitness value suitable for solving TSP.Using a single beetle and a group of beetle to calculate the TSPLIB example,the improved BASA falls into the local optimum and has been stagnation,and the calculation results are far from the actual recognized optimal value.In the next work,we consider the improvement of BASA itself and the fusion of other algorithms and BASA to propose improved BASA to solve the TSP better.Secondly,the BASA based on inversion mutation is proposed to solve TSP.The fitness scaling selection in genetic algorithm,inversion mutation and Monte Carlo rule in simulated annealing algorithm are organically integrated into the framework of the BASA to proposed BASA based on inversion mutation.Three different initialization methods of beetle population are used to ensure the diversity of the population.The adaptive step size and multi-directional motion of the beetle are introduced to improve the search ability of the algorithm.The results of BASA based on inversion mutation for solving TSP are compared with those of the three algorithms of the three journal articles,which show that the proposed algorithm is feasible and effective.In the end,the BASA based on quantum mechanics idea is proposed to solve the TSP.The proposed algorithm uses quantum coding for each beetle,and uses quantum register to encode the sequence of visiting the city,so as to ensure the diversity of the population.The quantum gate is used to drive each beetle to move in a better direction,which improves the Breadth search ability of the algorithm.The experimental results of solving TSP show that the proposed algorithm is feasible and effective.