基于ICS算法的旅行商问题研究

Research on Traveling Salesman Problem Based on ICS Algorithm

旅行商问题(Traveling Salesman Problem, TSP)是一个NP问题。为了能够获得最优的路径长度以及降低运行时间,文章使用改进的布谷鸟算法(Improved Cuckoo Search, ICS)进行旅行商问题的优化。首先阐述了TSP问题的定义,其次采用布谷鸟算法(Cuckoo Search, CS)进行优化:使用混沌映射进行种群初始化,提高种群多样性;利用量化正交交叉算子对每一次迭代后的个体进行筛选,保证了算法解的质量。仿真实验中与ACO、PSO和CS对比,该文算法在TSP的最优路径和最短时间方面具有一定的效果。

Traveling Salesman Problem(TSP)is a NP problem.In order to obtain the optimal path length and reduce running time,this paper uses the improved Cuckoo search(ICS)algorithm to optimize the traveling salesman problem.Firstly,the definition of the TSP problem is explained,and then the Cuckoo search(CS)algorithm is used for optimization:chaos mapping is used for population initialization to improve population diversity;the quantization orthogonal crossover operator is used to screen the individuals after each iteration,ensuring the quality of the algorithm solution.Compared with ACO,PSO,and CS in simulation experiments,the proposed algorithm in this paper has certain effectiveness in terms of optimal path and shortest time of TSP.