Linear Proposal Operators and Stochastic Search Geometry in SOMA and Differential Evolution

想象一下，你正试图在一个充满丘陵、凸起和隐藏坑洞的广阔且雾气缭绕的山谷中寻找最低点。你看不见完整的地图，也没有一个指向“下”方的指南针。这就是计算机在尝试解决“黑盒”优化问题时的日常工作。为了实现这一目标，科学家们使用了一种被称为进化算法的特殊程序。把它们想象成数字生态系统，其中一群虚拟探险家（一个“种群”）在四处游走。他们并不只是随机行走；他们会互相学习。有些探险家是“领导者”（那些目前找到了最佳位置的人），而其他人则尝试向他们移动，或者将自己的路径与其他探险家的路径混合，以观察是否能找到更好的位置。两个著名的探险队被称为 SOMA（自组织迁移算法）和 差分进化算法（DE）。它们已经存在很久了，但通常也被视为“黑盒”本身：我们知道它们有效，但并不总是理解其探险家移动的具体几何步骤。

这篇由 Vojtěch Novák 和 Ivan Zelinka 撰写的论文，决定拆解这些黑盒，观察内部的齿轮。作者并没有观察整个混乱的探险家移动、疲劳和被替换的过程，而是将“移动”部分与“判断”部分分离开来。他们发现，这些算法提出新步骤的方式实际上比看起来要简单得多，也更具数学性。他们发现，即使整个系统感觉很混乱，你也可以使用直线和简单的数学公式（线性算子）来描述这些探险家的运动。通过理解这种隐藏的几何结构，他们能够构建出更聪明的新型探险家，这些探险家准确地知道该跳多远以及向哪个方向跳，从而能更好地找到山谷的底部。

“提议”与“评判”的魔力

想象你在玩一个游戏，你必须猜一个 0 到 100 之间的秘密数字。你有一群朋友在帮助你。在旧的方法中，整个过程是一片模糊：一个朋友提出了一个数字，你检查它是否正确，如果它太高了，你可能会改变它，然后你决定谁留在游戏中。很难解释为什么一个朋友提出了特定的数字。

本文的作者意识到，这里实际上有两个截然不同的步骤，并且应该将它们分开处理：

1. 提议（“如果……会怎样”）： 一个朋友根据他们所在的位置和他们最好的朋友所在的位置，提出了一个新的数字。这一步纯粹是几何性的。它就像是在地图上画一条线。
2. 选择（“评判者”）： 你查看这个建议，并决定：“这是否比我们现有的更好？”这一步取决于具体的问题（“适应度”），并且是复杂且非线性的。

本文的一个重大突破在于证明了对于 SOMA 和差分进化算法，提议步骤实际上是一条笔直、干净的线。尽管整个游戏感觉很复杂，但生成一个候选位置的行为仅仅是一个简单的数学运算：取当前位置，观察领导者，并沿着一条直线移动一段距离。

跳跃的几何学

作者使用了一个聪明的技巧来证明这一点。他们将“迁移者”（移动中的探险家）和“领导者”（最好的探险家）想象为空间中的两个点。他们证明了新位置并不是某种神奇、不可预测的跳跃。它恰好是一个线性变换。

可以这样想：如果你站在点 A，而你的领导者在点 B，算法并不仅仅是“猜测”该去哪里。它在您和领导者之间画一条直线。然后，它在直线上选取一个点。

• 插值（Interpolation）： 它可能会选择你和领导者中间的一个点。
• 投影（Projection）： 它可能会选择正好位于领导者位置的点。
• 超调（Overshooting）： 它可能会选择一个落在领导者之后的点，仿佛它跑得太快，需要检查领导者背后的情况。

论文显示，这种运动受几个简单的旋钮控制：

• 路径参数 ($t$)： 我们沿着这条线走多远？
• 掩码（PRT 或 CR）： 这就像一副墨镜，遮挡了你观察某些方向的视线。如果掩码说“不要向北移动”，那么探险家只会向东、向南或向西移动。这创造了一种“稀疏”的运动，其中只有某些坐标会同时发生变化。

通过将掩码视为随机硬币投掷（伯努利分布），作者可以计算出探险家的平均行为。他们找到了诸如以下内容的公式：

• 平均而言，探险家会跳多远？
• 跳跃中存在多少“扩散”或不确定性？
• 探险家实际会向多少个方向（维度）移动？

他们甚至发现，“掩码”（墨镜）并不仅仅是随机地阻挡方向；它创造了一种特定的不确定性形状。如果掩码概率较低，探险家会在极少数方向上移动。如果概率较高，他们会在许多方向上移动。最“混乱”（方差最高）的运动发生在掩码设置为 50% 时，而不是在完全打开或完全关闭时。

构建更好的探险家：新的变体

一旦作者理解了运动背后的数学原理，他们并没有止步于理论。他们利用这些公式构建了三个改进版的 SOMA 算法。

1. 几何控制 SOMA (GC-SOMA)：
   与其猜测要在多少个方向上移动，这个版本允许用户说：“我希望探险家正好在 5 个方向上移动”或者“我希望探险家到达领导者位置的 90% 处”。算法随后使用数学公式来计算实现该特定几何目标所需的精确设置（掩码概率和路径长度）。这就像告诉一辆车：“正好行驶 50 英里”，然后汽车的计算机计算出需要踩多久油门。

2. 旋转感知 SOMA (RA-SOMA)：
   标准算法沿着网格线（北、南、东、西）移动。但如果山谷是倾斜的呢？如果最佳路径是斜向的呢？标准算法会陷入困境，因为它被困在沿直线网格移动。RA-SOMA 观察整个探险家群体，找出他们所在的山谷的“形状”，并旋转其运动以匹配该形状。这就像一个徒步旅行者停止沿网格行走，而是因为意识到山是倾斜的，转而斜向上坡行走。这使得算法在解决棘手的、扭曲的问题时表现得更好。

3. iL-SHOMA-RA：
   这是一个结合了旋转技巧和其他智能特征的“加强版”。它会记住哪些移动效果良好（成功历史），并在接近解决方案时逐渐减少探险家的数量（种群缩减）。这就像一支搜救队，开始时有 100 人，但随着他们接近宝藏，他们送走大部分人，只留下最好的侦察兵，而这些侦察兵现在正朝着完美的路径行走。

结果：它们真的有效吗？

作者在包含 24 个不同形状和难度的“山谷”（称为 BBOB 基准测试）的著名集合上测试了这些新的探险家。他们将自己与原始 SOMA 以及一些最好的差分进化算法（如 iL-SHADE）进行了比较。

结果非常明确：

• 原始版本落败： 标准的、未经修改的 SOMA 通常是表现最差的。它速度慢，且经常陷入困境。
• 新版本表现强劲： 所有三个新版本（GC-SOMA、RA-SOMA 和 iL-SHOMA-RA）都比原始版本好得多。
• 旋转是关键： 旋转感知版本在低维问题（如 5 或 10 个变量）中表现最为出色。它在某些情况下击败了最好的差分进化算法。这证明了使“倾斜”运动以匹配问题形状是一个巨大的优势。
• 预算很重要： “加强版”（iL-SHOMA-RA）在计算机时间有限（低“预算”）时特别有效。它能快速找到良好的解决方案。
• 并非万能灵药： 然而，论文谨慎地指出，这些新方法并没有赢得所有比赛。在极高维度（20 个变量）或某些类型的特定问题上，成熟的差分进化算法仍然更好。这些新方法并不是解决所有优化问题的“终极方案”，但相比旧的 SOMA，它们是一个巨大的进步。

为什么这很重要

这篇论文之所以重要，是因为它改变了我们看待这些算法的方式。长期以来，我们将它们视为神秘的黑盒。这篇论文打开了盒子，让我们看到了内部的齿轮。它证明了这些算法的“运动”部分实际上是一个简单的线性数学运算。

通过理解几何结构，我们可以停止猜测，开始设计。我们可以告诉算法它应该如何移动，而不是仅仅希望随机设置能奏效。作者表明，通过控制跳跃的“形状”（几何），我们可以使这些算法更加高效。

论文总结道，虽然这些新方法是一个巨大的进步，但故事尚未结束。最好的算法取决于具体的问题、变量的数量以及你拥有的时间。但现在，我们已经拥有了一张地图和指南针，可以为未来的探险家构建更优秀的工具。作者建议，未来我们应该研究这些几何思想如何在更复杂、更有噪声或有约束的环境中发挥作用，但就目前而言，他们已成功地将混乱的搜索转变为一次精准的、受数学引导的旅程。