第三名解决方案：定制化的麻雀算法

将归纳偏置构建到麻雀算法中并生成优质种子解以获得第三名

前言

首先，我要向组织本次比赛的 Kaggle 团队表示由衷的感谢。这是我们参加过的最有趣的 Santa 比赛之一。此外，热烈祝贺所有参赛者，特别是 @jeroencottaar 获得的个人冠军。最后，我要感谢所有的队友，没有他们就不可能取得这一成就：@zidmie, @khahuras, @delporterobbe 和 @olehugnivenko。

简介

我们解决方案的示意图如下所示。它包含以下主要组件，我们将在随后进行深入讨论：

• 矩形组合：通过较小的矩形解生成大型 N 的优质方形解
• 重度修改版的 Sparrow（麻雀）算法：支持热启动，直接优化方形目标，提高数值精度，并引入多个新超参数来控制优化行为（Rust 编写）
• 非常快的 C++ 模拟退火（SA）和“推挤”过程：用于轻微扰动和压缩方形解（每个 N 的最后一步）
• 无缝工作流程：充分利用团队合作和分布式计算资源

矩形组合

在比赛早期，我们通过组合优化的矩形取得了强劲的结果。我们使用晶格生成和带有不同条带高度的 vanilla Sparrow 算法，生成了一个具有不同纵横比的大型矩形带库。

然后递归地组合该库中的矩形以形成更大的矩形和正方形。虽然我们最终的結果都不是直接由该算法生成的，但这些解为后续步骤提供了宝贵的种子。

下面是矩形组合算法输出的示例（已应用了一些后处理）。注意，绿色和蓝色区域中的矩形本身又是其他矩形的组合。

作为一个有趣的巧合，如果我们绘制出生成的矩形的最小和最大尺寸，似乎会出现鸟类（麻雀？）的形状！

仅应用此算法，可以达到大约 70.0 的分数。

模拟退火 + 压缩

早期，我们将比赛前几天公开发布的一个 SA 笔记本翻译成 C++ 并添加了多线程支持。Oleh 在 2026 年 1 月加入我们要团队，他使用的是另一个公开的 SA 算法笔记本并翻译成了 C++。

SA 算法的概要伪代码如下：

初始化当前布局和最佳布局
计算初始边界正方形大小
设置温度 T = T_start

进行多次迭代：
  随机选择一个树
  提议一个小的随机移动 (dx, dy) 和旋转 (dθ)
  如果移动后的树与其他树重叠：拒绝

  计算新的边界正方形大小（目标）
  Δ = 新分数 − 当前分数

  如果 Δ < 0:
    接受移动
  否则:
    以概率 exp(−Δ / T) 接受移动

  如果接受:
    更新当前布局
    如果有所改进则更新最佳布局

  逐渐降低 T

此外，我们实现了一个简单但最初有效的后处理算法，模拟摇晃装有这些多边形的托盘。这也是用 C++ 实现的。

这个推挤算法的概要伪代码如下：

重复直到没有改进：
  对于每个预定义的推挤方向（例如 左 + 下，右 + 上）：
    对于递减的步长：
      对于每棵树：
        当树可以在推挤方向上轻微移动（并稍微旋转）
        且不发生碰撞或边界违规时：
          接受移动

    如果结果布局具有更小的边界正方形：
      接受它

通过将矩形组合器与这些算法结合（用于后处理我们库中的矩形以及组合器的中间和最终解），可以达到大约 69.50 的分数。

扩展麻雀算法

虽然我们很早就开始使用“ vanilla"版本的 sparrow（感谢 @jern97 和 @tonywauters）算法来为我们的矩形库创建矩形，但我们从未深入探索过它。1 月份，Oleh 加入了我们的团队，他主要致力于扩展该实现，构建几个针对我们特定问题的归纳偏置。

直接优化正方形

Sparrow 的目标被修改为同时最小化宽度和高度，而不是在保持高度固定的情况下最小化宽度。将 Sparrow 的目标与比赛指标对齐是第一个自然的扩展。

允许传递初始解供 Sparrow 开始（热启动）

我们扩展了 Sparrow 以接受初始解，允许它从先前获得的布局进行热启动。这使我们能够用矩形组合算法产生的多样化解来播种 Sparrow。

在求解器中强制对称性（4 向和 2 向对称）

为了显著减少搜索空间，我们强制实施了对称约束。对于可被 2 和 4 整除的 N 值，分别支持 2 向和 4 向对称。虽然最终解中剩下的对称性很少，但这种方法帮助 Sparrow 在优化早期收敛到强大的种子解。

方向偏置以强制晶格状结构

为了减少旋转噪声并稳定全局结构，我们应用了软方向偏置，鼓励项目与主导布局轴对齐。对于旋转为 θ 的放置，惩罚为：

其中 w 是 orientation_bias_weight（超参数），θ* 是固定的目标 orientation_bias_angle（超参数），Δ 是模 180°的最小角度差。

通过设置 B(c) 使惩罚具有中心感知：

其中 r 是到容器中心的归一化距离，b = orientation_bias_center_boost（超参数），p = orientation_bias_center_power（超参数），在中心强制更强的对齐，而在边缘附近约束较软。偏置强度在优化过程中自适应（改进时增长，否则衰减，并在压缩开始时重新缩放）。

生成和踢出种子解

除了由我们的矩形组合算法生成的种子外，我们还实现了下采样和上采样例程，以从其他 N 值的解生成初始 Sparrow 解。下面是一个如何上采样的简单示例。我们基本上随机添加一棵树，然后让 sparrow 智能地插入它。

比赛后期的大部分精力都花在调整这些超参数以及仔细选择目标 N 和要下采样或上采样的 N 值上，通常通过目视检查来指导。

在运行 Sparrow 之前，初始解会被“踢出”以帮助跳出局部最优，方法是应用全局旋转（将整个解旋转几度）和缩放（将所有 (x, y) 坐标乘以略大于 1 的因子）。

团队合作

构思和平衡工作负载分配是 Kaggle 团队设置中的主要挑战，尤其是在需要无情优化以充分利用可用计算资源的比赛中。考虑到不同的背景 and 时区，我们采用了一个简单高效的协作方案：

• Kaggle 笔记本（启用互联网），自动提交每个新发现的单个 N 的改进作为一次提交（感谢 Kaggle 允许每天提交 100 次）
• 直接从这些笔记本向 Slack 报告分数和参数，以便进一步分析和讨论

以下是当发现改进时由我们的 slackbot 发布的消息示例：

通过这种工作流程，所有团队成员都可以 24/7 连续运行多个笔记本，只需最少的努力，同时使用他们的本地机器。合并改进和分发新想法既快速又简单。

额外图表（杂项）

下图显示了每个 n 的分数和边长：

每个解的中值角度似乎显示出明显的模式。最优解倾向于具有晶格结构的树，角度在 22-24 度和 202-204 度左右。

大语言模型 (LLMs)

如果不提及在本次比赛中使用 AI 工具，那将是不诚实的。虽然所有核心想法都源自团队（否则不可能获得金牌），但 AI 工具在支持任务方面 proved 有价值。特别是，它们帮助将 Python 原型翻译成高效的 C++ 实现，并协助修改 Sparrow Rust 代码库（大多数团队成员不熟悉该语言），使得上述扩展的实施变得显著更容易。

我们的解决方案

请欣赏我们要最终解决方案的视频：https://www.youtube.com/shorts/Ru8dcAfGb-E