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个车辆路径优化问题对融合新策略的多种群智能算法进行测试。实验结果表明融合所提策略的群智能算法在搜索精度和稳定性上均要优于对应的原算法，证明所提解空间动态缩减策略可以有效改善算法的性能。

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