计算机应用

作者：杨云亭, 王鹏

单位：1.中国科学院 成都计算机应用研究所，成都 6100412.中国科学院大学，北京 1000493.西南民族大学 计算机科学与技术学院，成都 610225

关键词：自由粒子,动态搜索,优化算法,组合优化,旅行商问题,波函数

基金：国家自然科学基金资助项目(60702075)。

针对目前元启发式算法在求解组合优化问题中的旅行商问题（TSP）时求解缓慢的问题，受量子理论中波函数的启发提出一种多尺度自适应的量子自由粒子优化算法。首先，在可行域中随机初始化表示城市序列的粒子，作为初始的搜索中心；然后，以每个粒子为中心进行当前尺度下的均匀分布函数的采样，并交换采样位置上的城市编号产生新解；最后，根据新解相较上一次迭代中最优解的优劣进行搜索尺度的自适应调整，并在不同的尺度下进行迭代搜索直到满足算法结束条件。将该算法和混合粒子群优化（HPSO）算法、模拟退火(SA)算法、遗传算法(GA)和蚁群优化算法应用在TSP上进行性能测试，实验结果表明自由粒子模型算法适合求解组合优化问题，在TSP数据集上相比目前较优算法在求解速度上平均提升50%以上。

来源：2020年第5期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第5期