作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2024, Vol. 50 ›› Issue (7): 154-163. doi: 10.19678/j.issn.1000-3428.0067039

• 人工智能与模式识别 • 上一篇    下一篇

面向大规模优化问题的精英贡献两阶段动态分组算法

王彬1,*(), 张娇1, 李薇1,2, 王晓帆1, 金海燕1   

  1. 1. 西安理工大学计算机科学与工程学院, 陕西 西安 710048
    2. 西安理工大学陕西省网络计算与安全技术重点实验室, 陕西 西安 710048
  • 收稿日期:2023-02-26 出版日期:2024-07-15 发布日期:2024-04-10
  • 通讯作者: 王彬
  • 基金资助:
    国家自然科学基金(U21A20524); 国家自然科学基金(62272383)

Elite Contribution Based Two-Stage Dynamic Grouping Algorithm for Large-Scale Optimization Problem

Bin WANG1,*(), Jiao ZHANG1, Wei LI1,2, Xiaofan WANG1, Haiyan JIN1   

  1. 1. Faculty of Computer Science and Engineering, Xi'an University of Technology, Xi'an 710048, Shaanxi, China
    2. Shaanxi Key Laboratory for Network Computing and Security Technology, Xi'an University of Technology, Xi'an 710048, Shaanxi, China
  • Received:2023-02-26 Online:2024-07-15 Published:2024-04-10
  • Contact: Bin WANG

摘要:

协同进化框架是解决大规模全局优化问题的有效方法, 设计合理的决策变量分组方法是提高协同进化算法性能的关键, 而利用精英决策变量动态构建精英子组件可以有效提高进化效率, 但在进行大规模优化时, 其可能将无关的变量分配到同一子组件, 从而无法充分利用分组提高协同进化效率。针对该问题, 提出一种精英贡献两阶段动态分组算法(EC-TSDG)。在分组前阶段, 对变量进行随机分组, 评估变量的贡献程度, 从众多变量中寻找精英贡献变量; 在分组后阶段, 利用变量的相关关系寻找与精英决策变量存在相互作用的剩余变量, 并将其合并形成精英子组件, 使得精英子组件内部的变量两两相关, 以此提高变量分组的准确性以及算法的收敛速度, 避免子组件之间的相关干扰。最后, 采用具有外部存档的自适应差分进化算法作为优化器进化各个子组件。在CEC'2013测试集上与其他先进算法进行比较, 实验结果表明, EC-TSDG收敛速度快于对比算法, Friedman检验值为1.43, 平均排序较对比的动态分组算法DCC平均提升36.78%。

关键词: 协同进化, 大规模优化问题, 两阶段动态分组, 贡献信息, 精英子组件

Abstract:

The co-evolution framework is an effective method for solving large-scale global optimization problems. Designing a reasonable decision variable grouping method is key to improving the performance of co-evolution algorithm. Using elite decision variables to dynamically construct elite subcomponents can improve evolutionary efficiency. This paper focuses on the characteristics of inseparable variables in large-scale optimization problems that are difficult to divide. The existing strategy may assign unrelated variables to the same subcomponents of the grouping problem. To address this issue, this paper proposes the Elite Contribution based Two-Stage Dynamic Grouping algorithm(EC-TSDG). First, the variables are randomly grouped in the pre-grouping stage. Subsequently, the contributions of variables are evaluated, and the elite contribution variables are obtained from several variable contributions. Second, in the post-grouping stage, the correlation among the variables is used to determine the remaining variables that interact with the elite decision variables and to merge them to form the elite subcomponent. This enables the variables within the elite subcomponent to correlate in pairs so as to improve the accuracy of variable grouping and convergence speed of the algorithm and to avoid correlation interference between the subcomponents. Finally, an adaptive differential evolution algorithm with an external archive is used as the optimizer for each subcomponent. Compared with other advanced algorithms on the CEC'2013 test set, the proposed algorithm exhibits a faster convergence speed than comparative algorithms. Experimental result show that the Friedman test value of EC-TSDG is 1.43, and its average ranking is 36.78% higher than that of the comparative dynamic grouping algorithm, DCC.

Key words: co-evolution, large-scale optimization problem, two-stage dynamic grouping, contribution information, elite subcomponent