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

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