改进的麻雀搜索算法及其求解旅行商问题

Improved Sparrow Search Algorithm and Its Application in TSP

旅行商问题(TSP)是经典的NP难问题,对该问题的研究从未停止,也得到了很多的近似求解算法,但每一种算法都各有特色,正因如此,对旅行商问题总有新的算法在提出.麻雀算法是新近提出的算法,本文对麻雀搜索算法(SSA)的原理、搜索策略以及算法的基本流程进行研究分析,针对SSA搜索接近全局最优时,种群的多样性减少,容易陷入局部最优等问题提出一种改进的麻雀搜索算法(ISSA).使用6个标准测试函数与基本SSA以及其他群体智能算法进行仿真实验,测试ISSA的性能.最后应用ISSA对旅行商问题进行求解.实验表明,改进的麻雀搜索算法的能够改善麻雀搜索算法的缺点,提升寻优能力,并且验证了其求解旅行商问题的可行性与优越性.

The traveling salesman problem(TSP)is a classical NP-hard problem.The research on it has never stopped,and a lot of approximate solving algorithms have been obtained.However,each algorithm has its own characteristics,and thus new algorithms are proposed frequently for TSP,such as the sparrow algorithm developed recently.This work studies and analyzes the principle,search strategy,and basic process of the sparrow search algorithm(SSA).When the search by SSA approaches the global optimum,the diversity of the population decreases and it is easy to fall into the local optimum.Given this,the work proposes an improved sparrow search algorithm(ISSA).Six standard test functions,the basic SSA,and other swarm intelligence algorithms are employed in simulation experiments to test the performance of ISSA.Finally,ISSA is used to solve the TSP.Experiments show the effectiveness of ISSA in improving the shortcomings of SSA and enhancing the optimization ability and verify the feasibility and superiority of ISSA in TSP solving.