一种用于求解TSP问题的随机最佳插入烟花算法

A randomized best insertion fireworks algorithm for solving TSP problem

TSP问题是一个NP难问题,求解时间随问题规模呈几何级数增长,如何在较短时间内求得更精确的解一直是重要的研究问题。因为烟花算法在求解过程中能够快速收敛,而且能跳出局部最优解,所以基于烟花算法改进了爆炸资源分配的方式,创新性地提出了2个算子:抛弃节点重新插入的爆炸算子和抛弃路径重新插入的变异算子。再使用精英与轮盘赌相结合的烟花选择策略,设计了一种随机最佳插入的烟花算法(RBIFWA)。将该算法与基本烟花算法、混沌烟花算法、离散蝙蝠算法和自适应模拟退火蚁群算法进行比较,结果显示,RBIFWA算法在迭代次数上明显优于其他算法,且算法的解更加接近已知最优解,表明RBIFWA算法在求解TSP问题上具有更加优秀的性能和更高的求解质量。

The TSP problem is an NP-hard problem,and the solution time increases geometrically with the scale of the problem.How to build an accurate solution in a short time is a challenge.Because the firework algorithm can quickly converge in the solution process and can jump out of the local optimal solution,based on the firework algorithm,the resource allocation for explosions is improved,and two operators are innovatively proposed:explosion operator that discards nodes and mutation operator that discards paths.Then,a Randomized Best Insertion Fireworks Algorithm(RBIFWA)is designed by using a fireworks selection strategy combining elite and roulette.RBIFWA are compared with some classical algorithms such as the basic firework algorithm,the chaos firework algorithm,the discrete bat algorithm,and the adaptive simulated annealing ant colony algorithm.The results show that the RBIFWA algorithm is significantly better than other algorithms in the number of iterations,and the accuracy of the algorithm is closer to the known optimal solution.It is proved that the RBIFWA algorithm has better performance and solution quality in solving the TSP problem.