求解排列组合问题的解空间动态缩减策略

作者：李章洪; 梁晓磊^*; 田梦丹; 周文峰

来源：计算机应用, 2020, 40(07): 2016-2020.

DOI：10.11772/j.issn.1001-9081.2019112006

• 组合优化
• 智能算法
• 编码方式
• 空间缩减
• 重复排列

针对一般群智能算法求解大规模排列组合问题时搜索空间大从而影响群体搜索效率的问题,提出了一种解空间动态缩减(SSDC)策略,以动态减少算法搜索空间。该策略中,首先通过智能算法对排列组合优化问题两次初步求解,对获得的两个解中重复的片段进行识别和融合,将融合成的新节点代入原解空间进行解空间缩小更新;而后在下一次智能算法求解的过程中,对缩小的可行空间进行搜索,从而提升个体在有限空间内的搜索效率,降低搜索时间成本。基于5个高维标准旅行商问题(TSP)和2个车辆路径优化问题对融合新策略的多种群智能算法进行测试。实验结果表明融合所提策略的群智能算法在搜索精度和稳定性上均要优于对应的原算法,证明所提解空间动态缩减策略可以有效改善算法的性能。

• 单位
  武汉科技大学