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

作     者：吴俊斌 吴晟 吴兴蛟 WU Jun-bin;WU Sheng;WU Xing-jiao

作者机构：昆明理工大学信息工程与自动化学院云南昆明650500 华东师范大学计算机科学与技术学院上海200062 

出 版 物：《计算机工程与科学》 (Computer Engineering & Science)

年 卷 期：2020年第42卷第11期

页      码：2080-2087页

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

主 题 词：烟花算法 随机最佳插入 TSP问题 资源分配 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1007-130X.2020.11.022

馆 藏 号：203991779...