Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (7): 2016-2020.DOI: 10.11772/j.issn.1001-9081.2019112006

• Advanced computing • Previous Articles     Next Articles

Solution space dynamic compression strategy for permutation and combination problems

LI Zhanghong, LIANG Xiaolei, TIAN Mengdan, ZHOU Wenfeng   

  1. School of Automobile and Traffic Engineering, Wuhan University of Science and Technology, Wuhan Hubei 430065, China
  • Received:2019-11-26 Revised:2020-01-02 Online:2020-07-10 Published:2020-06-29
  • Supported by:
    This work is partially supported by the Youth Program of National Natural Science Foundation of China (61603280).

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

李章洪, 梁晓磊, 田梦丹, 周文峰   

  1. 武汉科技大学 汽车与交通工程学院, 武汉 430065
  • 通讯作者: 梁晓磊
  • 作者简介:李章洪(1994-),男,湖北利川人,硕士研究生,主要研究方向:智能算法、排列组合问题;梁晓磊(1985-),男,山西长治人,副教授,博士,主要研究方向:智能优化算法、复杂系统建模与仿真;田梦丹(1996-),女,河南焦作人,硕士研究生,主要研究方向:建模仿真、智能优化算法;周文峰(1995-),男,湖北仙桃人,硕士研究生,主要研究方向:智能优化算法。
  • 基金资助:
    国家自然科学基金青年基金资助项目(61603280)。

Abstract: The performance of swarm intelligent algorithms in solving large-scale permutation and combinatorial optimization problems is influenced by the large search space, so a Solution Space Dynamic Compression (SSDC) strategy was proposed to cut down the search space of the algorithms dynamically. In the proposed strategy, two times of initial solutions of the the permutation and combination optimization problem were obtained by the intelligent algorithm firstly. Then the repetitive segments of the two solutions were recognized and merged together. And the new points after merging were taken into the original solution space to perform the compression and update of the solution space. In the next intelligent algorithm solving process, the search was carried out in the compressed feasible space, so as to improve the searching ability of the individuals in the limited space and reduce the searching time cost. Based on five high-dimensional benchmark Travel Salesmen Problems (TSP) and two Vehicle Routing Problems (VRP), the performances of several swarm intelligent algorithms combined with the solution space dynamic compression strategy were tested. The results show that the swarm intelligent algorithms combined with the proposed strategy are superior to the corresponding original algorithms in the search accuracy and stability. It is proved that the solution space dynamic compression strategy can effectively improve the performance of swarm algorithms.

Key words: combinatorial optimization, intelligent algorithm, encoding mode, space reduction, repeat permutation

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

关键词: 组合优化, 智能算法, 编码方式, 空间缩减, 重复排列

CLC Number: