Abstract：The imperialist competitive algorithm is a swarm intelligence optimization algorithm with strong local search ability, but excessive local search will lead to the loss of diversity and fall into local optimum. Aiming at this problem, an Imperialist Competitive Algorithm based on Multiple Search Strategy (MSSICA) was proposed. The country was defined as a feasible solution and the kingdoms were defined as four mechanisms of combinatorial artificial chromosome with different characteristics. The block mechanism was used to retain the dominant solution fragment during search and differentiated mechanisms of combinatorial artificial chromosome was used for different empires to search the effective and feasible solution information of different solution spaces. When it come to the local optimum, the multiple search strategy was used to inject a uniformly distributed feasible solution to replace a less advantageous solution to enhance the diversity. Experimental results show that the multiple search strategy can effectively improve diversity of the imperialist competitive algorithm and improve the quality and stability of the solution.
[1] GOLDBERG D E, LINGLE R, Jr. Alleles, Loci, and the traveling salesman problem[C]//Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale:L. Erlbaum Associates Inc., 1985:154-159. [2] ISMKHAN H, ZAMANIFAR K. Developing improved greedy crossover to solve symmetric traveling salesman problem[EB/OL].[2018-10-10]. https://arxiv.org/ftp/arxiv/papers/1209/1209.5339.pdf. [3] 袁豪. 旅行商问题的研究与应用[D]. 南京:南京邮电大学, 2017:5-6. (YUAN H. Research and application of traveling salesman problem[D]. Nanjing:Nanjing University of Posts and Telecommunications, 2017:5-6.) [4] ARSHAD S, YANG S. A hybrid genetic algorithm and inver over approach for the travelling salesman problem[C]//Proceedings of the 2010 IEEE Congress on Evolutionary Computation. Piscataway:IEEE, 2010:1-8. [5] 王艳, 王秋萍, 王晓峰. 基于改进萤火虫算法求解旅行商问题[J]. 计算机系统应用, 2018, 27(8):219-225. (WANG Y, WANG Q P, WANG X F. Solving traveling salesman problem based on improved firefly algorithm[J]. Computer Systems & Applications, 2018, 27(8):219-225.) [6] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598):671-680. [7] ATASHPAZ-GARGARI E, LUCAS C. Imperialist competitive algorithm:an algorithm for optimization inspired by imperialistic competition[C]//Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway:IEEE, 2007:4661-4666. [8] 李明, 雷德明. 基于新型帝国竞争算法的高维多目标柔性作业车间调度[J].控制理论与应用, 2019, 36(6):893-901. (LI M, LEI D M. Novel imperialist competitive algorithm for many-objective flexible job shop scheduling[J]. Control Theory and Applications, 2019, 36(6):893-901.) [9] KAVEH A, TALATAHARI S. Optimum design of skeletal structures using imperialist competitive algorithm[J]. Computers & Structures, 2010, 88(21):1220-1229. [10] FOROUHARFARD S, ZANDIEH M. An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems[J]. The International Journal of Advanced Manufacturing Technology, 2010, 51(9/10/11/12):1179-1193. [11] 孟洪潮. 多策略改进的混合帝国竞争算法[J]. 价值工程, 2018, 37(14):193-195. (MENG H C. Improved imperialist competitive algorithm based on quantum behavior[J]. Value Engineering, 2018, 37(14):193-195.) [12] CHANG P, HUANG W, WU J, et al. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International Journal of Production Economics, 2013, 141(1):45-55. [13] CHEN M H, CHEN S H, CHANG P C. Imperial competitive algorithm with policy learning for the traveling salesman problem[J]. Soft Computing, 2017, 12(7):1863-1875. [14] HUANG W H, CHANG P C, WANG L C, et al. A fast block-based evolutional algorithm for combinatorial problems[J]. International Journal of Computer, Electrical, Automation, Control and Information Engineering, 2012, 6(7):889-895. [15] PASTI R, de CASTRO L N. A neuro-immune network for solving the traveling salesman problem[C]//Proceedings of the 2006 IEEE International Joint Conference on Neural Networks. Piscataway:IEEE, 2006:3760-3766. [16] SOMHOM S, MODARES A, ENKAWA T. A self-organizing model for the travelling salesman problem[J]. Journal of the Operational Research Society, 1997, 48(9):919-928.
2019, Vol. 39 
