技术摘要：受强化学习启发的基于潜在产出的自适应算法切换机制

问题陈述

本工作解决的核心挑战是动态或在线环境中的自适应算法选择（AS）。虽然“没有免费午餐定理”（NFLT）指出没有任何单一算法能在所有问题实例上表现最优，但在特定且不断演变的实例中选择最合适的算法仍然困难。传统的离线选择方法在动态环境（如云计算、机器人技术、流数据）中失效，因为它们依赖于静态特征映射，无法对问题分布的偏移做出反应。相反，现有的在线方法通常基于强化学习（RL）或多臂老虎机，往往依赖于瞬时奖励反馈。这种依赖可能导致反应性、不稳定的行为，以及在性能短暂波动时出现“膝跳反射”式的切换，从而导致次优结果和计算资源的浪费。

方法论

作者提出了一种计算高效的多智能体框架，将**强化学习（RL）概念与遗传算法（GA）**的岛屿模型相结合，以实现稳定、自适应的切换。该系统被构建为一个由半独立“岛屿”组成的群岛，每个岛屿托管一个拥有候选算法库的智能体。

核心组件

1. 岛屿架构：

   • 系统由 $n$ 个岛屿（$I$）组成，每个岛屿包含一个智能体（$\psi_i$）和一个算法库（$Rep_i$）。
   • 岛屿通过**中央接口智能体（CIA）**进行通信，该智能体观察整个群岛的性能，但不强加决策规则。
   • 引入一个特殊的**加拉帕戈斯岛屿（G-Island）**以防止过早收敛。该岛屿通过探索未充分利用的算法并偏离其他岛屿的共识行为，积极促进多样性。

2. 潜在产出（Yielon）机制：

   • 系统不针对单个实例的奖励做出反应，而是将性能历史累积为潜在产出，称为Yielon（$\Upsilon$）。
   • 智能体维护一个Yielory（Yielon 的存储库），作为过去总体性能的内存。
   • 信用归一化： 性能通过基于计算资源（$R$）和时间（$\tau$）的归一化信用（$C_{norm}$）进行衡量，并经过缩放以便在不同异构算法之间进行比较。
   • 挤压因子（$\sigma$）： 计算为滑动窗口（$w$）内归一化信用的平均梯度的“扭矩”。
     • 如果 $\sigma \approx 0$（性能饱和），系统检查当前信用是否超过最小阈值。如果未超过，则触发探索。
     • 如果 $\sigma \neq 0$（性能变化），则根据变化幅度更新 Yielory。

3. 切换动态（利用与探索）：

   • 利用： 只要 Yielory 中包含足够数量的 Yielon（高于阈值 $\Upsilon_{min}$），智能体就会继续使用当前算法，即使性能略有下降。这提供了对抗反射性切换的“惯性”。
   • 内在探索： 如果由于持续的性能不佳导致 Yielon 数量降至 $\Upsilon_{min}$ 以下，智能体将切换到其本地库中的新算法。
   • 外在探索： 如果系统检测到局部最优（性能饱和且 $\sigma \approx 0$）且当前算法次优，智能体将向 CIA 查询所有岛屿中表现最佳的算法（$A_{best}$），并可能切换到该算法。
   • G-Island 的作用： G-Island 旨在即使在其他岛屿稳定时也能强制进行探索，确保系统不会停滞在局部最优解中。

主要贡献

该论文概述了四项主要贡献：

1. 累积潜在产出： 一种机制，能够记住算法的整体性能轨迹，平滑实例特征中的异常波动。
2. 延迟切换： Yielory 充当缓冲区，防止反射性动作，允许算法在改变条件时有时间适应，然后再被丢弃。
3. 通过岛屿模型实现并行性： 使用分布式岛屿促进了并行探索和性能交换，增强了可扩展性。
4. 可扩展性： 该架构支持增加岛屿数量以及算法库中算法的多样性，而不会产生显著的开销。

实验结果

所提出的机制在两个领域进行了评估：封闭世界的排序任务和开放世界的机器人避障任务。

1. 排序算法

• 设置： 三个岛屿针对不同类型的数据（随机大数据、随机小数据、近乎有序数据）测试了快速排序、插入排序和计数排序。
• 发现：
  • 基线（贪婪）： 没有 Yielory 时，智能体基于即时反馈频繁切换算法，往往过早收敛到单一算法（例如计数排序），而不管数据类型如何，导致在其他数据类型上表现次优。
  • 引入 Yielory 后： 潜在产出的引入显著减少了切换次数，同时增加了累积的归一化信用总额。该系统展示了在微小波动期间“坚持”使用某一算法的能力，仅在性能持续下降时才进行切换。
  • G-Island 的影响： G-Island 增加了探索频率，防止整个群岛收敛到局部最优解，尽管这对某些岛屿的总信用带来了边际成本。

2. 机器人避障

• 设置： 四个模拟机器人（岛屿）使用 Q-Learning、SARSA 和 Double-Q-Learning，并配合不同的学习率，在具有静态障碍物的环境中进行导航。
• 发现：
  • Yielory 机制使机器人能够吸收输入的变化，避免过早丢弃学习策略。
  • G-Island 表现出更高的切换率，确保系统继续探索解空间，而其他岛屿则利用稳定的策略。
  • 消融研究证实，移除 G-Island 会减少外在探索，表明系统更依赖于本地算法库，并面临停滞的风险。

意义与主张

作者声称，这项工作提供了一种计算简单但有效的在线算法选择方法，在利用和探索之间取得平衡，同时避免了基于瞬时奖励方法的不稳定性。

• 稳定性： 通过将奖励和惩罚封装为“潜在产出”，系统模拟了过去性能的内存，避免了标准强化学习中常见的“膝跳反射”式反应。
• 多样性： G-Island 的集成解决了“岛屿综合征”（过早收敛到次优解），通过确保搜索过程中的持续多样性。
• 适用性： 结果表明，该方法在静态（排序）和动态（机器人）环境中均具有可行性，突显了其在需要自适应选择的领域（如自动化机器学习（AutoML）和智能控制系统）中的潜在应用。

该论文谦逊地总结道，虽然当前的实现使用了中央接口智能体，但未来的工作可以演变为使用移动智能体和联邦学习的完全去中心化系统，以进一步增强多机器人系统的适应性。