计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 182-190.doi: 10.11896/jsjkx.201200012
潘燕娜, 冯翔, 虞慧群
PAN Yan-na, FENG Xiang, YU Hui-qun
摘要: 合作协同优化是目前针对大规模优化问题的最有前景的算法之一,该算法通过分而治之策略划分子问题,以进行协同进化。不同的子问题根据演化状态的不同对整体改善的贡献大小也不一致,因此均匀分配计算资源会造成浪费。针对上述问题,提出一种新颖的基于自适应资源分配池策略和基于竞争的群优化集成的竞争合作群协同优化算法。首先,考虑到子问题的不平衡性,将子问题对整体目标改善的动态贡献作为分配计算资源的标准;其次,为了更好地适应子问题演化状态,不固定资源分配单元,而是利用池模型进行自适应分配,并且在相同子问题连续迭代中避免重复评估个体,以节省计算资源;然后,将上述策略与基于竞争的群协同优化算法进行集成,设计了一种新的竞争合作群协同优化;最后,将该算法与其他5种算法在CEC 2010和CEC 2013套件的35个基准函数上进行比较,验证了算法的有效性。
中图分类号:
[1]BELLMAN R E.Dynamic Programming (Dover Books onMathematics)[M].MIT Press,1957. [2]BERGH F V D,ENGELBRECHT A P.A Cooperative Ap-proach to Particle Swarm Optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):225-239. [3]POTTER M A,JONG K A D.A cooperative coevolutionary approach to function optimization[J].Third Parallel Problem Solving Form Nature,1994,866(1):249-257. [4]POTTER M A,JONG K A D.Cooperative Coevolution:An Architecture for Evolving Coadapted Subcomponents[J].Evolutionary Computation,2014,8(1):1-29. [5]MA X,LI X,ZHANG Q,et al.A Survey on Cooperative Co-Evolutionary Algorithms[J].IEEE Transactions on Evolutio-nary Computation,2019,23(3):421-441. [6]FOGARTY J S,SMITH J,FOGARTY T C.An adaptive poly-parental recombination strategy[M]//Evolutionary Computing.Berlin:Springer,1995. [7]YANG Z,TANG K,YAO X.Multilevel cooperative coevolution for large scale optimization[C]//Evolutionary Computation.IEEE,2008. [8]YANG Z,TANG K,YAO X.Large scale evolutionary optimization using cooperative coevolution[J].Information Ences,2014,178(15):2985-2999. [9]MEI Y,OMIDVAR M N,LI X,et al.A Competitive Divide-and-Conquer Algorithm for Unconstrained Large-Scale Black-Box Optimization[J].ACM Transactions on Mathematical Software (TOMS),2016,42(2):13.1-13.24. [10]OMIDVAR M N,YANG M,MEI Y,et al.DG2:a faster and more accurate differential grouping for large-scale black-box optimization[J].IEEE Transactions on Evolutionary Computation,2019,21(6):929-942. [11]LIU Y,YAO X,ZHAO Q,et al.Scaling Up Fast Evolutionary Programming with Cooperative Coevolution[C]//Congress on Evolutionary Computation.IEEE,2001. [12]OMIDVAR M N,LI X,YAO X.Smart use of computational resources based on contribution for cooperative co-evolutionary algorithms[C]//Genetic and Evolutionary Computation Confe-rence.2011:1115-1122. [13]MOHAMMAD N O,BORHAN K,LI X D,et al.CBCC3-Acontribution-based cooperative co-evolutionary algorithm with improved exploration/exploitation balance[C]//IEEE Congress on Evolutionary Computation.IEEE,2016. [14]YANG M,OMIDVAR M N,LI C,et al.Efficient Resource Allocation in Cooperative Co-Evolution for Large-Scale Global Optimization[J].IEEE Transactions on Evolutionary Computation,2017(4):1-1. [15]BERGH F V D,ENGELBRECHT A P.Cooperative learning in neural networks using particle swarm optimizers[J].South African Computer Journal,2000,26:84-90. [16]WEICKER K,WEICKER N.On the Improvement of Coevolutionary Optimizers by Learning Variable Interdependencies[C]//Proceedings of the 1999 Congress on Evolutionary Computation(CEC 99).IEEE,2002. [17]CHEN W,WEISE T,YANG Z,et al.Large-Scale Global Optimization Using Cooperative Coevolution with Variable Interaction Learning[C]//International Conference on Parallel Problem Solving from Nature.Berlin:Springer,2010:300-309. [18]OMIDVAR M N,LI X,YAO X.Cooperative Co-evolution with delta grouping for large scale non-separable function optimization[C]//Evolutionary Computation.IEEE,2011. [19]SUN Y,KIRLEY M,HALGAMUGE S K.Extended Differen-tial Grouping for Large Scale Global Optimization with Direct and Indirect Variable Interactions[C]//Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation.2015:313-320. [20]LI X,YAO X.Cooperatively Coevolving Particle Swarms forLarge Scale Optimization[J].Evolutionary Computation,IEEE Transactions on,2012,16(2):210-224. [21]HANSEN N,OSTERMEIER A.Completely Derandomized Self-Adaptation in Evolution Strategies[J].Evolutionary Computation,2001,9(2):159-195. [22]LIU J,TANG K.Scaling Up Covariance Matrix Adaptation Evolution Strategy Using Cooperative Coevolution[C]//International Conference on Intelligent Data Engineering & Automated Learning.Berlin:Springer,2013. [23]SHI Y,TENG H,LI Z Q.Cooperative Co-evolutionary Differential Evolution for Function Optimization[C]//Advances in Na-tural Computation,First International Conference,ICNC 2005.2005. [24]YANG Z,TANG K,YAO X.Self-adaptive differential evolutionwith neighborhood search[C]//Evolutionary Computation.IEEE,2010. [25]ZHANG J,SANDERSON A C.JADE:Adaptive DifferentialEvolution With Optional External Archive[J].IEEE Transactions on Evolutionary Computation,2009,13(5):945-958. [26]TANG L,DONG Y,LIU J.Differential Evolution With an Individual-Dependent Mechanism[J].IEEE Transactions on Evolutionary Computation,2015,19(4):560-574. [27]TANABE R,FUKUNAGA A.Success-history based parameter adaptation for differential evolution[C]//2013 IEEE Congress on Evolutionary Computation (CEC).IEEE,2013. [28]HU X M,HE F L,CHEN W N,et al.Cooperation coevolution with fast interdependency identification for large scale optimization[J].Information Ences,2016,381:142-160. [29]REN Z,LIANG Y,ZHANG A,et al.Boosting CooperativeCoevolution for Large Scale Optimization With a Fine-Grained Computation Resource Allocation Strategy[J].IEEE Transactions on Cybernetics,2019,49(12):4180-4193. [30]CHENG R,JIN Y.A Competitive Swarm Optimizer for LargeScale Optimization[J].IEEE Transactions on Cybernetics,2015,45(2):191-204. [31]LIU W,ZHOU Y,LI B,et al.Cooperative Co-evolution with Soft Grouping for Large Scale Global Optimization[C]//2019 IEEE Congress on Evolutionary Computation (CEC).IEEE,2019. |
[1] | 唐枫, 冯翔, 虞慧群. 基于自适应知识迁移与资源分配的多任务协同优化算法 Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation 计算机科学, 2022, 49(7): 254-262. https://doi.org/10.11896/jsjkx.210600184 |
[2] | 徐旭, 钱丽萍, 吴远. 基于移动边缘计算的区块链计算资源分配和收益分享研究 Computation Resource Allocation and Revenue Sharing Based on Mobile Edge Computing for Blockchain 计算机科学, 2021, 48(11): 124-132. https://doi.org/10.11896/jsjkx.201100205 |
[3] | 陈晋音, 熊晖, 郑海斌. 基于粒子群算法的支持向量机的参数优化 Parameters Optimization for SVM Based on Particle Swarm Algorithm 计算机科学, 2018, 45(6): 197-203. https://doi.org/10.11896/j.issn.1002-137X.2018.06.035 |
[4] | 周雅兰,徐 志. 多变异策略的自适应差分演化算法 Self-adaptive Differential Evolution with Multi-mutation Strategies 计算机科学, 2015, 42(6): 247-250. https://doi.org/10.11896/j.issn.1002-137X.2015.06.052 |
[5] | 艾浩军,龚素文,袁远明. 基于多目标演化算法的云计算虚拟机分配策略研究 Research of Cloud Computing Virtual Machine Allocated Strategy on Multi-objective Evolutionary Algorithm 计算机科学, 2014, 41(6): 48-53. https://doi.org/10.11896/j.issn.1002-137X.2014.06.010 |
[6] | 周雅兰,朱耀辉,张军. 具有学习机制的离散差分演化算法 Discrete Differential Evolution with Learning Mechanism 计算机科学, 2011, 38(7): 225-227. |
[7] | 王磊,王维平,杨峰,朱一凡. 认知演化算法 Cognition Evolutionary Algorithm 计算机科学, 2010, 37(9): 198-204. |
[8] | 赵凤强,徐毅,李广强. 基于岛屿群体模型的多目标演化算法研究 Research on Multi-objective Evolutionary Algorithm Based on Island Model 计算机科学, 2010, 37(12): 190-192. |
[9] | 王媛妮,边馥苓. 基于演化算法的带故障约束空间聚类分析 Clustering Based on Evolutionary Algorithm in the Presence of Obstacles 计算机科学, 2009, 36(12): 197-198. |
[10] | 吴圣宁 李思昆. 嵌入式处理器寄存器分配的一种混合演化算法 计算机科学, 2007, 34(8): 278-280. |
[11] | 李景治 康立山 方宁. 一个约束可满足性问题的演化算法求解 计算机科学, 2004, 31(4): 137-139. |
[12] | 覃俊 康立山 陈毓屏. 一种新的求解多峰函数优化问题的动态演化算法 计算机科学, 2004, 31(3): 134-136. |
[13] | 周永华 毛宗源. 基于混合杂交与间歇变异的约束优化演化算法 计算机科学, 2003, 30(9): 35-38. |
[14] | 高汉平 唐立山 陈毓屏. 求解非线性规划问题的一种新演化算法 计算机科学, 2002, 29(9): 30-32. |
[15] | 何峰 康立山 陈毓屏. 一种具有个体学习能力的演化算法 计算机科学, 2002, 29(10): 64-66. |
|