概述

今年的 Santa 挑战赛是一个学习和开发新优化策略的激动人心的机会。感谢我的队友 @danielphalen、@yuchen2066、@veniaminnelin —— 我们需要所有的共同努力才能获得这枚金牌。

我们的基本方法结合了几个想法：

1. 计算在矩形网格中平铺 2 棵树的“最优”规则模式。
2. 修改 Sparrow 以最小化正方形（相对于条形）分数。
3. 实现 C++ 版本的 billiard（如下所述），源自 Gensane 和 Ryckelynck 的论文。
4. 拼接之前的解决方案。

进展

像许多其他人一样，我们开始时计算最好的规则模式。这是通过首先为粗网格的角度和水平/垂直间距计算 2 树平铺的参数来完成的。然后使用 Nelder-Mead 或 Powell 针对特定指标进行优化。早期我们只是计算整行和整列的最佳正方形打包参数。后来，当我们将模式与额外的树结合时，我们可以计算最佳规则平铺（非正方形），当与所需的额外树结合时，它具有特定的边距（比如说从 0.5 到 1.5）。然后可以将这些输入到修改后的 sparrow 中，将固定模式作为一个大形状，额外的树作为自由多边形。

接下来，我们能够针对我们的最佳解决方案反复运行 billiard，以获得 refined（稍微更好）的解决方案，但在布局上没有实质性的不同。我们需要更多的多样性才能达到下一个水平。

我们的最终技术被证明是相当有效的，但可能在比赛中有点太晚了，那就是将 prior 解决方案的片段拼接在一起，然后在它们上运行 sparrow 和 billiard 的组合。

计算“最优”规则模式

这在上面已经描述过了；我们将搜索限制为垂直平移，但正如 @jeroencottaar 指出的那样，使用非垂直模式可以做得更好。对于水平/垂直打包，树的角度为 9.750144 度和 180 度，您可以在无限网格中每棵树获得 .310709 的面积。

修改 Sparrow

与其他团队类似，我们使用 Claude 或 Codex 修改了 sparrow，因为我们不熟悉 Rust。我们发现 sparrow 擅长一次处理大约 50 个对象，但在寻找改进方面开始迅速退化。

1. 调整目标为正方形打包而不是条形打包。
2. 允许解决方案的热启动。
3. 我们发现交换单个树在探索参数空间方面无效，因此我们改变了探索阶段的中断方式，以交换树块、移动树边缘或打乱树簇。

为了适应 50 个对象的限制，我们开始使用合并的树块作为一个大对象，然后在该对象周围打包许多树。此外，我们发现压缩阶段不如我们所能达到的效率高，并依赖于下面描述的 billiard 算法，该算法通常会将边长减少约 0.2%，优于 sparrow 的结果。

Billiard

在 Gensane 和 Ryckelynck 的参考论文中，WithPerturbations 算法（我称之为 Billiard）试图在碰撞前生长最大的正方形。将其转换为固定大小的正方形，您尝试将其打包到最小区域中，我们得到一个如下所示的算法（超参数仅用于说明）：

# 函数 WithPerturbations(C):
从一个配置 C 开始
选择 eps = .1, final_eps = 1e-7
while eps > final_eps:
    C0 = C
    Perturb(C, eps)
    Billiard(C)
    Squeeze(C)
    if C 改进:
        接受 C
        eps = eps*2
    else:
        拒绝 C (设置 C=C0)
        eps = eps/2

Perturb(C,eps) 采取了 3 种不同的形式：

1. 扰动每棵树 eps，然后扩展解决方案以便没有重叠。
2. 简单地按 1+eps 扩展解决方案。
3. 按 1+eps 扩展解决方案，然后扰动每棵树以便没有重叠。

[稍后详述]

Billiard 非常简单：

# 函数 Billiard
eps=start_eps
While (eps > start_eps/100):
    RandomWalking(C, eps)
    if 分数改进:  
        接受 C
        eps=2*eps
    else:
        拒绝 C
        eps=eps/2

RandomWalking 只是随机地可行扰动树：

# 函数 RandomWalking
for i=range(Na):
    选择一个随机树
    扰动它 eps; 如果适合当前边界且不与现有树碰撞则接受

最后 Squeeze() 是一个二分搜索，以在不碰撞的情况下尽可能压缩（将树中心缩放到原点）。

改进

我们对上述 Billiard 使用了两个修改：

1. 我们允许它一次接受和操作一个解决方案列表，而不是单个解决方案，WithPertubations 的每个循环在每个解决方案上同步发生。这允许我们从更多的解决方案开始，然后随着过程的进展逐渐移除得分最差的解决方案，最后以 1 个结束。
2. 有了那个列表添加，我们现在还可以添加能力，有时添加回不总是最好的解决方案——也就是说，而不是扔掉一个更差的解决方案，我们有时可以将其添加到列表中并允许它优化一会儿。有时该解决方案会通过贪婪解决方案并成为赢家。

扩展中的钩挂现象 (Hooking in Expansion)

我们发现，有时您无法在不发生碰撞的情况下将配置扩展少量。经过调查，观察到了这种钩挂现象。考虑这个 2 树排列：

如果您将此配置仅扩展 1.001，您会得到这个：

如图所示发生碰撞。原因是您可以认为树中心的扩展等同于包括树顶点在内的每个点的扩展，随后缩小每棵树以使其恢复到原始大小。扩展不会引起任何碰撞（这只是缩放），但缩小会导致树 0 的分支“钩挂”到树 1 的分支上。

我们解决这个问题的方法是注意到，如果我们将树 0 向前移动 .001/2，碰撞就会解除。这是因为那个钩挂分支距离树的“中心”或 (0,0) 点正好是 0.5。因此，我们能够通过进行此扩展，然后反复将违规树向前移动 eps/2 或 eps/4 直到碰撞消除，来实现 1+eps 的小扩展。这不是万无一失的，但在大多数情况下有效。

这是树 0 向前移动到 .001/2 后的样子：

拼接解决方案

我们最终进入~~疯狂~~更好分数领域的 descent 始于意识到，虽然 billiard 和 sparrow 擅长调整事物，但它们并不擅长获取新解决方案。因此，我们开始通过随机方式从现有的最佳解决方案生成新的起始解决方案：

1. 拼接： 取 N 和 (N-1 或 N-2)；随机旋转两者 0,90,180,270 度，然后将 N 的随机左侧垂直切片拼接到另一个的随机右侧切片，添加或移除足够的树以恰好达到 N。
2. 对称化： 取 N 并取一个随机左侧垂直切片，将其旋转 180 度并合并到右侧，再次调整以获得 N 棵树。

然后我们在新配置上运行 Sparrow 和 Billiard 或仅运行 Billiard，希望获得更好的解决方案。