面向进制转换和克隆进化的帝国竞争改进算法

doi:10.3778/j.issn.1002-8331.2112-0416

摘要/Abstract

摘要： 帝国竞争算法（imperialist competitive algorithm，ICA）是一种被广泛应用于求解各类理论与实践问题的随机搜索智能优化算法，但它收敛过快的特性令其容易在求解复杂问题时陷入局部最优，故对ICA进行有针对性的改进十分必要。引入二进制转换和克隆进化机制，为算法的进化种群提供新的上升通道和进化模式，帮助进化种群跳出局部最优，从而提出了一种改进的帝国竞争算法（decimal-binary conversion and clonal evolution oriented improved imperialist competitive algorithm，DCCE-IICA）。此外，为修正经典ICA早熟导致的算法过早结束和群体多样性快速降低的缺陷，DCCE-IICA还辅以帝国分裂和出界点替换策略，以确保进制转化和克隆进化机制在改进算法执行中充分发挥区域深度探索和平衡资源分配的初衷。随后，经典函数测试集、CEC2017测试集及CEC2020测试集被用于检验DCCE-IICA在多个维度下对不同类型复杂问题的寻优能力。选取分别在经典函数测试集、CEC2017测试集和CEC2020测试集中表现优异的共14种典型算法，与DCCE-IICA进行实验结果比较。实验结果显示DCCE-IICA引入的改进机制在大多数情况下能够稳定且高效地提升算法性能，使得算法同时具备较好的收敛速度、收敛精度和求解鲁棒性。

关键词: 进制转换, 克隆进化, 帝国竞争算法, 帝国分裂, 出界点替换, CEC2017, CEC2020

Abstract: The imperialist competitive algorithm（ICA） is a random search intelligent optimization algorithm that is widely used to solve various theoretical and practical problems. However, it is liable to fall into a local optimum while solving complex problems because of its characteristics of fast convergence. Consequently, it is necessary to make targeted improvements on ICA. This paper introduces a clonal evolution mechanism in the context of decimal-binary conversion to provide a new ascending channel and evolutionary pattern for the algorithm’s evolutionary population, and it aims at helping the population jump out of the local optimum. Accordingly, the decimal-binary conversion and clonal evolution oriented improved imperialist competitive algorithm（DCCE-IICA） is proposed tentatively. In addition, to cope with the premature and the rapid reduction of population diversity caused by the excessively fast convergence, the DCCE-IICA is also supplemented by the empire split and the new out-of-bounds replacement strategy to help the decimal-binary conversion and clone evolution mechanism to fully play their roles of regional in-depth exploration and balanced resource allocation in the execution of the improved algorithm. Subsequently, a total of 14 kinds of intelligent optimization algorithms that are performed well in the classic function test set, CEC2017 test set and CEC2020 test set are selected to compare the experimental results with DCCE-IICA. The computational experiments and contrastive analysis show that the improved mechanisms introduced in DCCE-IICA can improve the algorithm performance stably and efficiently in most instances, and make the algorithm have good convergence speed, convergence accuracy and solution stability simultaneously.

Key words: decimal-binary conversion, clonal evolution, imperialist competitive algorithm, empire split, out-of-bounds replacement, CEC2017, CEC2020

李斌, 黄起彬. 面向进制转换和克隆进化的帝国竞争改进算法[J]. 计算机工程与应用, 2022, 58(5): 208-224.

LI Bin, HUANG Qibin. Decimal-Binary Conversion and Clonal Evolution Oriented Improved Imperialist Competitive Algorithm[J]. Computer Engineering and Applications, 2022, 58(5): 208-224.

参考文献

[1] KAVEH A，BAKHSHPOORI T.Water evaporation optimization：a novel physically inspired optimization algorithm[J].Computers & Structures，2016，167：69-85.
[2] HOLLAND J H.Adaptation in natural and artificial systems：an introductory analysis with applications to biology，control，and artificial intelligence[M].[S.l.]：MIT Press，1992：211.
[3] BEYER H G，SCHWEFEL H P.Evolution strategies-a comprehensive introduction[J].Natural Computing，2002，1（1）：3-52.
[4] WEI Z L，HUANG C Q，WANG X F，et al.Nuclear reaction optimization：a novel and powerful physics-based algorithm for global optimization[J].IEEE Access，2019，7：66084-66109.
[5] TAHANI M，BABAYAN N.Flow regime algorithm（FRA）：a physics-based meta-heuristics algorithm[J].Knowledge and Information Systems，2019，60（2）：1001-1038.
[6] DORIGO M，MANIEZZO V，COLORNI A.Ant system：optimization by a colony of cooperating agents[J].IEEE Trans Syst Man Cybernet，Part B：Cybernet，1996，26（1）：29-41.
[7] KENNEDY J，EBERHART R.Particle swarm optimization[C]//Proceedings of ICNN’95-International Conference on Neural Networks，1995：1942-1948.
[8] 周蓉，李俊，王浩.基于灰狼优化的反向学习粒子群算法[J].计算机工程与应用，2020，56（7）：48-56.
ZHOU R，LI J，WANG H.Reverse learning particle swarm optimization based on grey wolf optimization[J].Computer Engineering and Applications，2020，56（7）：48-56.
[9] 张德惠，游晓明，刘升.融合猫群算法的动态分组蚁群算法[J].计算机科学与探索，2020，14（5）：880-891.
ZHANG D H，YOU X M，LIU S.Dynamic grouping ant colony algorithm combined with cat swarm optimization[J].Journal of Frontiers of Computer Science and Technology，2020，14（5）：880-891.
[10] 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-4667.
[11] KAVEH A，RAHMANI P，ESLAMLOU A D.An efficient hybrid approach based on Harris Hawks optimization and imperialist competitive algorithm for structural optimization[J].Engineering with Computers，2021：1-29.
[12] PIRHADI S，MAGHOOLI K，MOTEGHAED N Y，et al.Biomarker discovery by imperialist competitive algorithm in mass spectrometry data for ovarian cancer prediction[J].Journal of Medical Signals and Sensors，2021，11（2）：108-119.
[13] 彭政，崔雪，王恒，等.考虑储能和需求侧响应的微网光伏消纳能力研究[J].电力系统保护与控制，2017，45（22）：63-69.
PENG Z，CUI X，WANG H，et al.Research on the accommodation of photovoltaic power considering storage system and demand response in microgrid[J].Power System Protection and Control，2017，45（22）：63-69.
[14] TAO X R，LI J Q，HAN Y Y，et al.Discrete imperialist competitive algorithm for the resource-constrained hybrid flowshop problem[J].Journal of Industrial and Production Engineering，2020，37（7）：345-359.
[15] FATHY A，REZK H.Parameter estimation of photovoltaic system using imperialist competitive algorithm[J].Renewable Energy，2017，111：307-320.
[16] 裴小兵，于秀燕，王尚磊.混合帝国竞争算法求解旅行商问题[J].浙江大学学报（工学版），2019，53（10）：2003-2012.
PEI X B，YU X Y，WANG S L.Solution of traveling salesman problem by hybrid imperialist competitive algorithm[J].Journal of Zhejiang University（Engineering Science），2019，53（10）：2003-2012.
[17] BAHRAMI H，FAEZ K，ABDECHIRI M.Imperialist competitive algorithm using chaos theory for optimization（CICA）[C]//Proceedings of the 12th International Conference on Computer Modelling and Simulation.Piscataway：IEEE，2010：98-103.
[18] ARDEH M A，MENHAJ M B，ESMAILIAN E，et al.EXPLICA：an explorative imperialist competitive algorithm based on the notion of explorers with an expansive retention policy[J].Applied Soft Computing，2017，54：74-92.
[19] KORHAN G，?CLAL G，KADIR T.ICA-RD：the regional domination policy for imperialist competitive algorithm from imperialism to internationalism[J].Arabian Journal for Science and Engineering，2020：1-61.
[20] XU S，WANG Y，LU P.Improved imperialist competitive algorithm with mutation operator for continuous optimization problems[J].Neural Computing and Applications，2017，28（7）：1667-1682.
[21] HEIDARI A A，MIRJALILI S，FARIS H，et al.Harris hawks optimization：algorithm and applications[J].Future Generation Computer Systems，2019，97：849-872.
[22] DEB K，AGRAWAL R B.Simulated binary crossover for continuous search space[J].Complex Systems，1995，9（2）：115-148.
[23] CASTRO D，ZUBEN V.Learning and optimization using the clonal selection principle[J].IEEE Transactions on Evolutionary Computation，2002，6（3）：239-251.
[24] 郭婉青.帝国竞争算法的研究与改进[D].福州：福州大学，2014.
GUO W Q，Research and improvement of empire competition algorithm[D].Fuzhou：Fuzhou University，2014.
[25] AWAD H N，ALI Z M，LIANG J J，et al.Problem definitions and evaluation criteria for the CEC 2017 special session and competition on single objective real-parameter numerical optimization[R].Singapore：Nanyang Technological University，2016.
[26] YUE T C，PRICE V K，SUGANTHAN N P，et al.Problem definitions and evaluation criteria for the CEC 2020 special session and competition on single objective bound constrained numerical optimization[R].Zhengzhou，China：Zhengzhou University.Computational Intelligence Laboratory，2019.
[27] PAN L Q，XU W T，LI L H，et al.Adaptive simulated binary crossover for rotated multi-objective optimization[J].Swarm and Evolutionary Computation，2021，60：100759.
[28] LIN J J，HUANG S C，JIAU M K.An evolutionary multiobjective carpool algorithm using set-based operator based on simulated binary crossover[J].IEEE Transactions on Cybernetics，2018，49（9）：3432-3442.
[29] JIANG Q Y，WANG L，HEI X H，et al.MOEA/D-ARA+SBX：a new multi-objective evolutionary algorithm based on decomposition with artificial raindrop algorithm and simulated binary crossover[J].Knowledge-Based Systems，2016，107：197-218.
[30] LIN J L，CHOC W，CHUANH C.Imperialist competitive algorithms with perturbed moves for global optimization[J].Applied Mechanics and Materials，2013：3135-3139.
[31] 毛清华，张强.融合柯西变异和反向学习的改进麻雀算法[J].计算机科学与探索，2021，15（6）：1155-1164.
MAO Q H，ZHANG Q.Improved sparrow algorithm combining Cauchy mutation and opposition-based learning[J].Journal of Frontiers of Computer Science and Technology，2021，15（6）：1155-1164.
[32] 黄光球，陆秋琴.具脉冲出生和季节性捕杀的种群系统优化算法[J].计算机科学与探索，2021，15（10）：2002-2014.
HUANG G Q，LU Q Q.Population system optimization algorithm with impulsive birth and seasonal killing[J].Journal of Frontiers of Computer Science and Technology，2021，15（10）：2002-2014.
[33] WANG X，HAN T，ZHAO H.An estimation of distribution algorithm with multi-leader search[J].IEEE Access，2020，8：37383-37405.
[34] 王贵林，李斌.受春秋战国史实启发的帝国竞争改进算法[J].计算机应用，2021，41（2）：470-478.
WANG G L，LI B.Improved imperialist competitive algorithm inspired by historical facts of Spring and Autumn Period[J].Journal of Computer Applications，2021，41（2）：470-478.
[35] STANOVOV V，AKHMEDOVA S，SEMENKIN E.LSHADE algorithm with rank-based selective pressure strategy for solving CEC 2017 benchmark problems[C]//
2018 IEEE Congress on Evolutionary Computation（CEC），2018.
[36] MOHAMED A W，HADI A A，FATTOUH A M，et al.LSHADE with semi-parameter adaptation hybrid with CMA-ES for solving CEC 2017 benchmark problems[C]//2017 IEEE Congress on Evolutionary Computation（CEC），2017：145-152.
[37] BREST J，MAU?EC M S，BO?KOVI? B.Single objective real-parameter optimization：algorithm jSO[C]//2017 IEEE Congress on Evolutionary Computation（CEC），2017：1311-1318.
[38] BIEDRZYCKI R.A version of IPOP-CMA-ES algorithm with midpoint for CEC 2017 single objective bound constrained problems[C]//2017 IEEE Congress on Evolutionary Computation（CEC），2017：1489-1494.
[39] TANGHERLONI A，RUNDO L，NOBILE M S.Proactive particles in swarm optimization：a settings-free algorithm for real-parameter single objective optimization problems[C]//2017 IEEE Congress on Evolutionary Computation（CEC），2017：1940-1947.
[40] MAHARANA D，KOMMADATH R，KOTECHA P.Dynamic Yin-Yang pair optimization and its performance on single objective real parameter problems of CEC 2017[C]//2017 IEEE Congress on Evolutionary Computation（CEC），2017：2390-2396.
[41] WILCOXON F.Individual comparisons by ranking methods[J].Biometrics Bulletin，1945，1（6）：80-83.
[42] VE?EK N，MERNIK M，?REPIN?EK M.A chess rating system for evolutionary algorithms：a new method for the comparison and ranking of evolutionary algorithms[J].Information Sciences，2014，277：656-679.
[43] SALGOTRA R，SINGH U，SAHA S，et al.Improving cuckoo search：incorporating changes for CEC 2017 and CEC 2020 Benchmark Problems[C]//2020 IEEE Congress on Evolutionary Computation（CEC），2020.
[44] STANOVOV V，AKHMEDOVA S，SEMENKIN E.Ranked archive differential evolution with selective pressure for CEC 2020 numerical optimization[C]//2020 IEEE Congress on Evolutionary Computation（CEC），2020.
[45] MOHAMED A K，HADI A A，MOHAMED A W.Generalized adaptive differential evolution algorithm for solving CEC 2020 benchmark problems[C]//2020 2nd Novel Intelligent and Leading Emerging Sciences Conference（NILES），2020：391-396.
[46] BOLUFé-R?HLER A，CHEN S.A multi-population exploration-only exploitation-only hybrid on CEC-2020 single objective bound constrained problems[C]//2020 IEEE Congress on Evolutionary Computation（CEC），2020.
[47] MOHAMED A W，HADI A A，MOHAMED A K，et al.Evaluating the performance of adaptive gaining sharing knowledge based algorithm on CEC 2020 benchmark problems[C]//2020 IEEE Congress on Evolutionary Computation（CEC），2020.
[48] SALLAM K M，ELSAYED S M，CHAKRABORTTY R K，et al.Improved multi-operator differential evolution algorithm for solving unconstrained problems[C]//2020 IEEE Congress on Evolutionary Computation（CEC），2020.