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.
[1] 于莹莹, 陈燕, 李桃迎. 改进的遗传算法求解旅行商问题[J]. 控制与决策,2014,29(8):1483-1488. (YU Y Y,CHEN Y,LI T Y. Improved genetic algorithm for solving TSP[J]. Control and Decision,2014,29(8):1483-1488.) [2] 何庆, 吴意乐, 徐同伟. 改进遗传模拟退火算法在TSP优化中的应用[J]. 控制与决策,2018,33(2):219-225. (HE Q,WU Y L, XU T W. Application of improved genetic simulated annealing algorithm in TSP optimization[J]. Control and Decision,2018,33(2):219-225.) [3] 胡云清. 求解VRP的混沌模拟退火萤火虫算法[J]. 包装工程, 2017,38(7):216-221. (HU Y Q. A chaotic simulated annealing glowworm algorithm for solving VRP problem[J]. Packaging Engineering,2017,38(7):216-221.) [4] 周永权, 黄正新. 求解TSP的人工萤火虫群优化算法[J]. 控制与决策,2012,27(12):1816-1821. (ZHOU Y Q,HUANG Z X. Artificial glowworm swarm optimization algorithm for solving TSP[J]. Control and Decision,2012,27(12):1816-1821.) [5] 吴新杰, 王静文, 黄国兴, 等. 一种求解旅行商问题的改进蛙跳算法[J]. 小型微型计算系统,2015,36(5):1078-1081. (WU X J,WANG J W,HUANG G X,et al. Improved shuffled frog leaping algorithm for solving the traveling salesman problems[J]. Journal of Chinese Computer Systems,2015,36(5):1078-1081.) [6] 王艳, 王秋萍, 王晓峰. 基于改进萤火虫算法求解旅行商问题[J]. 计算机系统应用,2018,27(8):219-225. (WANG Y, WANG Q P,WANG X F. Solving travel salesman problem based on improved firefly algorithm[J]. Computer Systems and Applications,2018,27(8):219-225.) [7] 蔡延光, 陈厚仁, 戚远航. 混沌烟花算法求解旅行商问题[J]. 计算机科学,2019,46(6A):85-88. (CAI Y G,CHEN H R,QI Y H. Chaotic fireworks algorithm for solving travelling salesman problem[J]. Computer Science,2019,46(6A):85-88.) [8] 冯志雨, 游晓明, 刘升. 分层递进的改进聚类蚁群算法解决TSP[J]. 计算机科学与探索,2019,13(8):1280-1294. (FENG Z Y, YOU X M,LIU S. Hierarchical progressive improved ant colony clustering algorithm to solve TSP problem[J]. Journal of Frontiers of Computer Science and Technology,2019,13(8):1280-1294.) [9] 饶卫振, 王新华, 金淳, 等. 一类求解TSP构建型算法的通用改进策略[J]. 中国科学:信息科学,2015,45(8):1060-1079.(RAO W Z,WANG X H,JIN C,et al. On the universal strategy for improving a certain type of construction heuristic for the traveling salesman problem[J]. SCIENTIA SINICA Informationis,2015,45(8):1060-1079.) [10] 许凯波, 鲁海燕, 程毕芸, 等. 求解TSP的改进信息素二次更新与局部优化蚁群算法[J]. 计算机应用, 2017,37(6):1686-1691.(XU K B,LU H Y,CHENG B Y,et al. Ant colony optimization algorithm based on improved pheromones double updating and local optimization for solving TSP[J]. Journal of Computer Applications,2017,37(6):1686-1691.) [11] 程毕芸, 鲁海燕, 徐向平, 等. 求解旅行商问题的该进局部搜索混沌离散粒子群优化算法[J]. 计算机应用,2016,36(1):138-142, 149.(CHENG B Y,LU H Y,XU X P,et al. Improved localsearch-based chaotic discrete particle swarm optimization algorithm for solving traveling salesman problem[J]. Journal of Computer Applications,2016,36(1):138-142,149.) [12] 程毕芸, 鲁海燕, 黄洋, 等. 求解TSP的自适应优秀系数粒子群优化算法[J]. 计算机应用,2017,37(3):750-754,781. (CHENG B Y,LU H Y,HUANG Y,et al. Particle swarm optimization algorithm based on self-adaptive excellence coefficients for solving traveling salesman problem[J]. Journal of Computer Applications,2017,37(3):750-754,781.) [13] 李擎, 张超, 陈鹏, 等. 一种基于粒子群参数优化的改进蚁群算法[J]. 控制与决策,2013,28(6):873-878.(LI Q,ZHANG C, CHEN P,et al. Improved ant colony optimization algorithm based on particle swarm optimization[J]. Control and Decision,2013, 28(6):873-878.) [14] WHITLEY D,HAINS D,HOWE A. A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover[C]//Proceedings of the 2010 International Conference on Parallel Problem Solving from Nature,LNCS 6238. Berlin:Springer,2010:566-575. [15] MARINAKI M,MARINAKIS Y. A glowworm swarm optimization algorithm for the vehicle routing problem with stochastic demands[J]. Expert Systems with Applications,2016,46:145-163.
2020, Vol. 40 
