东队解决方案

Woosung 的部分（模因算法）

（我有时间时也会更新其他团队成员的部分。）

在本次比赛中，我研究了一种结合遗传算法（Genetic Algorithm）和模拟退火（Simulated Annealing）的混合方法。

1. 初始种子

我通过重复高密度 2-gram 块模式创建了一个对称的初始种子。

将其旋转 45 度后，我以圆形方式从中心径向生长 (x, y) 坐标。

2. 变异

角落变异

我创建了一个在变异期间扰动角落区域的操作。

基于包围整个多边形的 AABB 矩形，
我随机选择一个角落区域，移除该部分，然后重新填充。

此类变异应用于当前一代的精英个体，并延续到下一代。
我们使用了诸如翻转单个角落的方向、交换两个角落或执行三角落交换等操作。

3. 邻居

邻居操作仅进行非常小的细粒度更改。

我们主要使用：

• (1) 高斯抖动 (Gaussian jitter)
• (2) 垂直翻转 (V-flip)
• (3) 枢轴旋转 (Pivot rotation)
• (4) 组旋转 (Group rotation)。

(3) 环境

我们使用了两种环境：软墙 (Soft Wall) 和硬墙 (Hard Wall)。

(1) 软墙（带刚性旋转）

在软墙设置中，刚性墙放置在左侧和底部，而顶部和右侧区域保持自由，以便在模拟退火下可以自由移动。我们将谜题旋转 90°、180° 和 270°，以便墙壁在每一侧都能同样起作用。我们非常频繁地进行这些刚性旋转——就像滚动一个小面团一样。

(2) 硬墙

在硬墙设置中，侧面是固定的，我们只解决碰撞问题。

在硬墙中，我们借用了 Sparrow 的坐标下降法。由于形状简单，我们直接使用真实重叠面积加上穿透深度，而不是依赖代理。我们没有使用上界进行修剪，而是以一种类似于随机束搜索 (stochastic beam search) 的方式使用遗传算法。

4. GPU / SIMD 加速

我们将树简化为三个三角形和一个四边形（四边形仅使用三个不重叠的轴）。

这种形状简化使我们能够使用 GPU/SIMD 执行大规模并行处理。

5. 结论

起初，我将其视为初始方案设计问题，
所以我专注于种子生长规则并尝试了许多贪婪算法。
我希望我能更多地使用密集网格。

大多数解决方案是在大量计算后偶然发现的。

在最后阶段，我专注于基于 GPU 的并行化。
然而，增加种群大小仅带来了对数级的增益，因此大规模 GPU 并行实验并没有太大影响。

---

Amon 的部分

总的来说，我探索了基于 SA 的优化和使用镶嵌图案生成初始方案。

早期阶段（开始 ~ 12 月中旬）

我的主要重点是编写基础模拟退火 (SA) 代码，观察结果并识别瓶颈。与公共 SA 笔记本的主要区别在于，我实现了一个逻辑来逐渐减少扰动的幅度。

具体来说，我根据当前温度缩放不同转换类型的概率。

• 高温： 求解器允许大幅移动和结构变化，例如垂直翻转和随机树旋转，以探索全局空间。
• 低温： 求解器优先考虑小调整和“压缩”移动（将树向中心移动），这在后期迭代中增加了接受率。

由于在这个阶段公共方案和我自己的镶嵌结构都不强，这种从随机树放置开始的 SA 优化在 N ≈ 120 之前优于图案化解决方案。

中期阶段（12 月中旬 ~ 1 月初）

我们团队的重点转向改进和混合当前可用的解决方案，而不是从头创建。我实现了一个逻辑，通过从 (N+k) 树解决方案中移除 k 棵树来创建 N 棵树的初始解决方案。我主要使用 k = 1, 2。

这使得在较大 N 解决方案中发现的良好局部模式能够“流入”较小的 N 解决方案。树被移除的概率根据其距离中心的距离加权（靠近边缘的树更可能被移除）。这个启发式方法有效，因为通常关闭边界附近产生的间隙比关闭中心的间隙更容易。

结合队友创建的优化启发式方法，这种方法提高了我们在中期阶段的得分。

最终阶段（1 月初 ~ 结束）

到了这个阶段，镶嵌解决方案在较大的 N 上始终优于随机放置。我致力于探索紧密的树镶嵌，并通过从无限网格画布中裁剪方形窗口生成大量“候选”初始解决方案。这是一个两阶段管道：

1. 网格画布创建

此阶段的目的是在镶嵌图案中创建紧密 packed 的树画布。我探索了三种图案：REGULAR（垂直堆叠）、HEXAGONAL（奇数行偏移）和 SHIFT（累积行偏移）。

我通过将其公式化为最大化密度的 6 维优化问题来解决这个问题。参数如下：

• angle：树的基础旋转角度。
• intra_dx, intra_dy：形成单个“模块”的两棵树之间的内部间距。
• inter_dx, inter_dy：网格中相邻模块之间的间距。
• row_offset：应用于行的水平偏移（用于 HEXAGONAL 和 SHIFT 图案）。

我使用嵌套方法优化这些参数：遍历角度和模块配置，然后应用二分查找找到 inter_dx 和 inter_dy 的最紧有效间距。这在各种角度下产生了许多紧密的网格图案。

2. 初始方案裁剪

此阶段的目的是通过裁剪无限网格为特定的 N 创建有效的初始解决方案。

我实现了一个简单的 SA 算法来优化由 (center_x, center_y, side_length, angle) 定义的裁剪窗口。目标函数是裁剪选择的实际密度。我们为每个网格图案保留了前 k 个密集解决方案。这使我们 technically 能够创建无限数量的初始解决方案，这些方案保证具有良好的镶嵌结构。

尽管我能够创建许多候选方案，但大多数最终并没有达到比我们现有最佳解决方案更好的分数， simply because 那些解决方案已经经过了几周的优化。我的遗憾是我无法实现一种 robust 方法将这些刚性镶嵌“嵌入”到正方形的中心，并有效地用随机放置填充剩余的边界使用。