Santa25 第 14 名 - 自定义模拟退火

大家好，

非常感谢竞赛组织者和所有参与者，让这样有趣的竞赛成为可能！

简而言之，我的解决方案是：

1. 找到最密的树晶格（以二聚体或树对为基本单元）。
2. 使用该晶格构建许多初始解变体。
3. 运行自定义模拟退火（SA）实现来优化边缘，固定正方形边长。
4. 对于在步骤 3) 中找到的解，执行以下操作之一：
   • 如果解有效，逐渐压缩它（减小正方形边长）。
   • 如果解无效，逐渐放松它（增加正方形边长）。

核心 SA 算法运行的视频可以在 这里 找到。

计算资源方面，使用 16 核桌面电脑直到最后一周达到 ~69.43，然后花费 200 美元在 AWS ECS 上加速到 ~69.22 并夺得单人金牌！

然而，有许多实现细节加起来才使其生效，所以我在下面提供更多细节，以防有人感兴趣。

总的来说，很高兴能与大家一起参与！:)

解决方案详情

1) 最密晶格与差分进化

• 最密晶格参数是使用差分进化找到的。晶格是二聚体的平铺（二聚体由两棵树组成，树 1 和树 2）。
• 参数或自由度是 2 个晶格基向量、树 1 的方向和树 2 相对于 NFP 的位置，假设相对于树 1 的方向为 +180 度。
• 最小化的目标是基向量定义的平行四边形的面积。
• 找到的最佳晶格每棵树的面积约为 0.3044。
• 在前几周，我尝试使用差分进化直接获得所有 N 的解：添加正方形边长、晶格全局方向和晶格偏移作为变量，对框内树的数量施加约束，并将目标改为最小化正方形边长。这很容易得到 ~71.x，但显然不是最好的方法，尽管通过这种方式获得的解一直保留到了最后！N=156 (0.3299)。

2) 初始解变化、冻结核心树、低 N 到高 N 方法

• 在最佳晶格中识别出 3 条不同的分离线，并根据不同标准将这些线与框壁对齐（例如，分离对齐的晶格纵横比、允许的壁重叠、到壁的距离）。
• 定义核心树的子形状，在 SA 开始时标记为冻结。
• 初始解的参数都是 N 的函数，包括冻结子形状的参数。
• 冻结子形状参数也依赖于其他初始化参数（例如，正在使用哪条分离线）。
• 大致来说，对于较高的 N，更多的树被冻结且持续时间更长，壁对齐偏差更强，筛选标准更严格，应用的随机抖动更低。
• 对于较低的 N，壁偏差放松，冻结核心更小或不存在，初始解参数更放松。
• 如果有更多时间，我会探索使用不同的最佳晶格作为基础，因为无限平面密度上的微小损失可能会通过允许不同的纵横比来弥补。

3) 自定义 SA 算法

• 由两个顺序锦标赛组成：校准锦标赛，用于寻找最有希望的初始解配置；以及使用这些获胜初始配置作为起点的主锦标赛。
• 每个锦标赛都有多轮，解会被淘汰，直到我们剩下 16 个决赛选手。
• 能量函数是树间面积重叠（二次行为）和壁穿透深度（线性行为）的加权和。发现二次行为可以减少严重的树间堵塞，并取得与树间穿透平方相似的结果和速度。壁碰撞通过线性损失和较高（但不是无限！）的壁项权重被鼓励为零。
• 温度计划遵循 3 个阶段：
  1. 高温阶段，指数衰减（约 10% 的时间）
  2. 临界阶段，线性衰减（甜蜜点，我们花费约 80% 的时间）
  3. 低温细化阶段，恢复指数衰减（约 10% 的时间）
• 临界阶段温度边界是通过目视检查 SA 运行视频确定的，因为仅仅观察能量水平证明是不直观的。定性地说，临界温度是指树偶尔 snapping 并改变解拓扑，但又不是到处都是。
• 移动或状态转换是标准的平移/旋转局部扰动（高斯），以及同时应用于所有树的全局平移/旋转移动。初始解参数影响全局移动的幅度。
• 关键是，局部移动不适用于冻结的树。树会在一段时间后解冻并可以再次局部移动。这大大提高了大 N 的 SA 效率。
• 与 teleport 或“沿外壳流动”移动相比，全局移动在解决长范围不平衡方面更有效。
• 代码是 Python（我知道 :O），但使用 numba/fastmath 进行了大量优化。一些优化包括：
  • 空间哈希用于线性时间碰撞检测。
  • 在昂贵的多边形数学之前进行边界框快速拒绝。
  • 将树分解为 4 个凸子形状以进行快速 SAT 碰撞检测。
  • 在许多地方展开代码以避免循环开销。
  • 一旦发现间隙就停止相交测试。
  • 单次树移动的增量能量更新。
  • 扁平连续的 numpy 数组以最大化 CPU 缓存局部性。
  • 向量化旋转矩阵以避免冗余数学。

4) 压缩和放松 SA 输出

• 此步骤的输入解是来自不同 N 和正方形边长对的主 SA 锦标赛各种运行的决赛选手。
• 使用上述 SA 算法的简单更快变体（具有较低温度和较小移动）来压缩所有有效解并放松无效解。

无效的方法

• 使用复杂 GUI 的手工制作解。
• 基于 JAX GPU 光栅的差分进化，其中离散化太多会导致内存爆炸，太少则没有此问题所需的精度。
• 多晶格初始化：事后看来，这显然是获胜策略，但唉，与我的主要方法相比，无法实现 consistently 更低的分数。
• 还有许多其他方法，这是一个难啃的骨头...

感谢阅读！:)