基于改进萤火虫算法求解旅行商问题

鉴于TSP问题是古老的组合优化难题,而萤火虫算法在求解函数优化问题中表现出优良的性能,因此,本文利用改进的萤火虫算法求解TSP问题.首先,在分析了旅行商问题的特点后,采用整数编码的方式来表示萤火虫的位置.然后,在标准萤火虫算法的位置更新过程中引入了对数递减的惯性权重来影响萤火虫的迭代过程,同时结合了遗传算法中的选择,交叉,变异以及进化逆转操作来提高每一次迭代中种群的多样性及种群的搜索能力,并将改进的算法解决TSP问题.最后,通过Matlab仿真实验表明改进的算法在求解TSP问题时具有更好收敛速度和优化效果.

Solving Traveling Salesman Problem Based on Improved Firefly Algorithm

Traveling Salesman Problem (TSP) is an oldest combinatorial optimization problem, and Firefly Algorithm (FA) shows excellent performance to complicated function optimization. Hence, in this study, we used improved FA to solve TSP. Firstly, after the characteristics of TSP are analyzed, and the method of integer encoding is adopted to set the position of fireflies. Then, the logarithmic adjustment factor is introduced in the standard FA. Meanwhile, we combine the crossover, mutation, and reverse operation in Genetic Algorithm (GA) to improve the population diversity and search ability of each iteration, and it is applied to solve TSP. Finally, the numerical experiments show that the proposed algorithm has faster convergence speed and optimization effect.