基于分层教学与合作协同进化的大规模高成本离线数据驱动进化优化
《Swarm and Evolutionary Computation》:Large-scale expensive offline data-driven evolutionary optimization via hierarchical teaching and cooperative coevolution
【字体:
大
中
小
】
时间:2026年08月29日
来源:Swarm and Evolutionary Computation 9.6
编辑推荐:
摘要数据驱动进化算法 (DDEAs) 在过去十年中因其解决昂贵优化问题的有效性而受到越来越多的关注。然而,大多数研究集中在小规模问题上,而大规模昂贵优化问题 (LSEOPs) 由于高维搜索空间带来的挑战——通常被称为“维数灾难”——仍未被充分探索。尽管合作协同进化 (CC)
摘要数据驱动进化算法 (DDEAs) 在过去十年中因其解决昂贵优化问题的有效性而受到越来越多的关注。然而,大多数研究集中在小规模问题上,而大规模昂贵优化问题 (LSEOPs) 由于高维搜索空间带来的挑战——通常被称为“维数灾难”——仍未被充分探索。尽管合作协同进化 (CC) 提供了一种减轻该问题的有希望的方法,但其许多高级分组策略需要频繁的真实适应度评估,使其不适合 DDEAs。为了克服这一局限性,我们提出了一种分层教学 - 协同数据驱动进化算法,称为 HTC-DDEA。首先,设计了一种分布感知分组策略,将决策空间划分为具有不同种群多样性水平的多个子空间。然后,开发了一种双阶段搜索机制,根据分组方案动态调整每个子种群的多样性和收敛性,从而在整个优化过程中保持探索与开发之间的适当平衡,并引入了一种新颖的代理建模框架,以实现从局部搜索到全局搜索的平滑过渡。在高达 1000 维问题上的实验以及与最先进 DDEAs 的比较验证了 HTC-DDEA 的有效性。
介绍大规模优化问题 (LSOPs) 在科学和工程领域广泛遇到 [1],其中许多问题本质上是非凸的、不可微的和多模态的。使用数学优化方法求解此类问题要么不切实际,要么效率低下。近年来,受自然进化启发的进化算法 (EAs) [2] 在求解此类优化问题上显示出卓越的性能 [3]。然而,大多数 EAs 的一个常见假设是在优化过程中真实适应度评估 (FEs) 是可行的。当处理大规模昂贵优化问题 (LSEOPs) 时,这一假设不成立,因为目标函数评估成本高或难以建模,使得传统 EAs 难以适用 [4]、[5]。
为了克服 LSEOPs 的这一局限性,开发了离线数据驱动进化算法 (DDEAs) [6]。离线 DDEAs 使用历史数据构建代理模型来近似适应度值,从而减少对真实评估的依赖以解决 LSEOPs。这使得能够以大幅降低的计算成本有效地评估候选解。常见的代理模型包括多项式回归 (PR) [7]、[8],高斯过程 (GP) [9]、[10],支持向量回归 (SVR) [11]、[12],径向基函数网络 (RBFNs) [13]、[14]、[15],以及人工神经网络 (ANNs) [16]、[17]。
虽然离线 DDEAs 通过代理模型减轻了对昂贵真实评估的依赖,在解决 LSEOPs 方面表现出优势,但 LSEOPs 也给离线 DDEAs 带来了新挑战。一方面,随着维度的增长,搜索空间也会指数级扩张 [18],要求 EAs 具有更大的探索能力。例如,在高维多模态问题中,局部最优解的数量通常呈爆炸式增长,而且这些局部最优解可能周围存在广泛的局部区域 [19],这很容易导致 EA 陷入局部解。另一方面,在“维数灾难”下,在可接受的计算成本内构建高质量的代理模型仍然是一个主要挑战。一个相关的现实例子是全网交通信号控制 (TSC) [20] 优化问题,它需要在多个交叉口协调信号定时以提高整体交通效率。评估信号方案依赖于大规模交通仿真,计算成本高昂 [21]。因此,离线 DDEAs 为 TSC 提供了一种有希望的方法。然而,现实世界中的道路网络往往是大型且复杂的交通系统,使得 TSC 成为一个涉及数千甚至更多变量的高维优化问题,从而需要有效的方法来应对上述挑战。
为了应对上述挑战,合作协同进化 (CC) [22] 已被公认为解决 LSEOPs 的有效框架 [23]。其核心原则是分而治之:将高维问题分解为可以独立优化的小型子问题。然后将所有子问题的解组合形成全局解。在 CC 中,分组策略至关重要——有效的分组可以在不影响全局最优解的情况下显著降低优化难度 [24]。理想情况下,强相互作用变量应分配给同一子问题。然而,在离线 DDEAs 中,无法使用真实 FEs 来分析此类相互作用,使得许多高级分组策略不适用。(这些分组方法将在第 2 节中详细说明)。虽然基于代理的分组是可能的,但近似误差使生成的分组不可靠并增加计算开销。因此,离线 DDEAs 中通常采用动态随机分组。然而,动态随机分组可能会破坏之前发现的高质量变量分组,并且难以在优化过程中有效平衡种群探索与开发。
为进一步解决这些挑战,我们提出了一种通过分层教学和合作协同进化的数据驱动进化算法 (HTC-DDEA)。本研究的主要贡献如下。
1. 设计了一种适合离线 DDEAs 的分布感知分组策略。该策略根据当前种群的分布,将全局搜索空间划分为多样性逐渐降低的几个子空间。排名靠前的子空间包含更多样化的子种群,而排名靠后的子空间表现出更好的收敛性。这使得整个优化过程中多样性与收敛性之间的动态平衡成为可能。
2. 提出了一种受教学 - 学习机制启发的双阶段搜索策略。在应用分布感知分组后,优化通过学习阶段和教学阶段进行。在早期阶段,增强多样性的教学有助于保持种群多样性并避免过早收敛。在后期阶段,增强收敛性的教学加速了收敛较差的子种群的收敛。此外,两种教学模式之间的切换点根据问题维度自适应调整,使算法能够更好地适应不同级别的维度并提高最终解的质量。
3. 开发了一种新颖的动态分层协同建模策略。该策略利用分布感知分组将问题分解为低维子空间,为子问题优化训练独立的局部代理模型,并辅以全局代理模型用于选择。这种低维建模方法不仅显著降低了训练成本,而且局部模型固有的近似误差也有助于保持子种群多样性。至关重要的是,子空间数量的逐渐减少以及模型的同步更新确保了优化焦点从局部探索到全局收敛的平滑过渡,同时提高了整体搜索效率。
4. 将提出的 HTC-DDEA 与几个最先进的离线 DDEAs 在高达 1000 维的基准问题上进行了比较。实验结果表明了 HTC-DDEA 的有效性和优越性。
本文其余部分组织如下。第 2 节介绍背景和相关工作。第 3 节详细描述了提出的算法。第 4 节展示了比较实验和分析。最后,第 5 节总结了本文并讨论了未来工作的方向。
章节摘要
合作协同进化
合作协同进化 (CC) 可通过将 LSOPs 分解为多个可以协同优化的子问题来有效解决 LSOPs。在 CC 中,分组策略起着关键作用。迄今为止,关于分组策略的研究主要集中于三类:静态分组、随机分组和基于学习的分组。静态分组是最简单类型的分组策略,因为它将决策变量划分为固定数量的子空间。该方法被提出
框架
提出的 HTC-DDEA 的总体框架如图 1 所示,它由两个主要组件组成:高维全局优化和低维子问题优化。
在全局优化阶段,高维决策空间首先使用随机分组被划分为 K 个独立的 s 维子空间。在每个子空间内,使用原始适应度值 y 作为标签训练 RBFNs。当需要重新分组时,采用分布感知策略
实验结果与分析
实验研究包括三部分。首先,为了评估 HTC-DDEA 的性能,采用了五个广泛用于评估 DDEAs 性能的基准函数,加上 CEC 2013 [43] 测试套件中的 F8 (旋转 Ackley) 和 F12 (旋转 Rastrigin) 函数,将提出的 HTC-DDEA 与五个最先进的离线 DDEAs 进行比较。这些基准函数涵盖了各种特性,如可分性/不可分性,
结论
虽然 CC 的“分而治之”思想被证明在解决 DDEAs 在 LSEOPs 上有限的探索能力方面是有效的,但许多 CC 中开发的效率分组策略依赖真实适应度评估,这在离线 DDEAs 中是不可用的。为了解决这一局限性,我们提出了一种专为离线 DDEAs 设计的分布感知分组策略。该方法将决策空间划分为多个子空间,每个子空间表现出逐渐降低的种群
CRediT 作者贡献声明
Er-chao Li: 写作 – 审阅与编辑,验证,监督,资金获取。WanJi Yuan: 写作 – 原稿,软件,方法论。Li-sen Wei: 写作 – 审阅与编辑,监督。
利益冲突声明
作者声明他们没有已知的竞争性财务利益或个人关系,这些关系可能会影响本文所述的工作。
致谢
本工作部分由国家自然科学基金 (No. 62063019) 和甘肃省自然科学基金 (No. 24JRRA173) 资助。
Er-chao Li|WanJi Yuan|Li-sen Wei
兰州理工大学 自动化与电气工程学院,兰州 730050,中国
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号