```html

第 11 名解决方案

概述

我的解决方案基于软约束模拟退火（Soft-Constraint Simulated Annealing）结合晶格势（Lattice Potentials）。

我使用元启发式框架（锦标赛选择）管理并行执行，从大量的候选方案中生成精英解。为了进一步优化这些解，我应用了巨正则盆地跳跃（Grand Canonical Basin Hopping）策略，对源自 N、N+1 和 N-1 配置的初始解进行再加热处理。

注意：虽然其中一些策略灵感来源于统计物理学，但在这里它们是作为启发式方法应用的，从学术角度来看可能并不严格严谨。

核心优化引擎

本节详细介绍了单次模拟退火（SA）运行的逻辑。它是元启发式框架内的基本执行单元。

基础求解器：软约束模拟退火

我实现了一个标准的模拟退火（SA），带有软约束，允许粒子之间以及粒子与容器之间发生重叠。我没有降低温度，而是通过增加惩罚权重 lambda 来对系统进行退火。

允许重叠预计会使搜索更高效，因为它使求解器能够更容易地在能量景观上的不同局部极小值之间移动。

容器大小是固定的，并在外部赋予适当的值。换句话说，求解器不是直接探索盒子大小，而是在“可行性模式”下运行，搜索对于给定的边长 L 是否存在零重叠配置。

后处理抛光工具：NPT 系综

由于仅使用基础求解器实际上很难完全消除重叠，我开发了一个单独的抛光工具来生成用于提交的“合法”解。

该工具使用具有可变盒子大小的 NPT 系综，包含体积膨胀和收缩移动。惩罚 lambda 逐渐增加，直到所有重叠都被消除。

晶格势

对于较大的 N，有序结构显然更优越。然而，使用简单的 SA 通常会导致无序的“玻璃态”，无论计算时间多长。我通过在基础求解器中引入晶格势来解决这个问题，以迫使粒子进入有序排列。

该晶格势在 lambda 调度中途被关闭，以允许配置适应容器边界。

晶格势基于二聚体晶格。我使用 SA 优化了两个粒子的相对位置和角度以及基本平移矢量，以最大化无限系统中的密度。这些预计算参数随后被加载并由基础求解器使用。

此外，对于像 N=156 这样粒子整齐地适应晶格网格的情况，我通过在有限系统内对晶格参数和网格尺寸进行退火，单独生成了初始解。

元启发式框架

由于多模态景观和强烈的初始解依赖性，单次 SA 运行似乎会在 70.0 左右达到平稳期。为了解决这个问题，我利用了由元启发式框架管理的大量计算资源以实现高效扩展。

锦标赛选择

为了有效地探索巨大的搜索空间，我采用了大规模并行策略。我同时运行了多达数千个 SA 实例。退火调度（增加 lambda）被分为多代（例如 50 代）。

种群大小在每一代呈指数级减少，幸存者根据其惩罚分数进行选择。

为了在有限的计算预算内最大化起始点的多样性，我使用了以下策略：在早期阶段为每个代理分配较少的迭代次数，随着种群减少而增加迭代次数。这种方法可能平衡了初始配置的多样性与整体搜索质量。

巨正则盆地跳跃

最佳解使用我称为巨正则盆地跳跃的策略不断细化。

• 盆地跳跃：为了改进 N 的配置，将当前最佳解用作初始解，从中等 λ 重新启动 SA。此过程在无限循环中重复以逃离局部极小值。
• 巨正则方法：在最后阶段，我利用来自 N+1（移除一个随机粒子）和 N-1（添加一个随机粒子）的配置作为 N 的种子。受物理学中粒子数波动的巨正则系综启发，该策略使分数从 69.30x 显著提高到了 69.10x。

多样性维护（3 谱系法）

通过巨正则方法的成功，我意识到初始解多样性的至关重要性。由于构建复杂解池的时间有限，因此实施了一种简化的"3 谱系法”来维持多样性。系统不是跟踪单个最佳解，而是为每个 N 跟踪三个独立的谱系：

1. N 的当前最佳配置。
2. 源自 N+1 的最佳配置。
3. 源自 N-1 的最佳配置。

新的细化运行从这三个谱系中随机选择一个种子。

其他方法与尝试

以下是我尝试过的一些其他方法。它们不是我的主要关注点，但在某些情况下仍然有效。

副本交换 (Replica Exchange)

副本交换是统计物理学中一种常见且强大的方法，所以我在比赛早期就尝试了它。我预计它在 N <= 30 时会很有效，因为有序配置并不总是最好的。

然而，最终只有少数结果（如 N=18）来自此方法。很难说是参数调整的问题，还是该方法 simply 不适合这个问题。

种群退火 (Population Annealing)

我尝试了一种基于种群退火的启发式方法，在每一步使用加权重采样。虽然它在更多情况下比副本交换有效，但对于这个问题，锦标赛选择通常表现更好。尚不清楚这是由于实现问题还是问题本身的原因。

注意：锦标赛选择的灵感来自这种方法的逻辑。

进一步改进的想法

为了更好地在巨正则盆地跳跃中保持多样性，可以探索以下想法：

• 解池化：维护来自锦标赛选择（或任何方法）的次优解池，并将它们用作初始配置的种子。
• 拓扑多样性：不仅仅比较分数，而是使用拓扑差异的定量度量来优先保留池中的多样化解。
• SA 风格的池管理：不使用爬山方法（如 3 谱系法），而是对池使用 SA 风格的接受。在不同池之间变化温度可以进一步促进多样性。

通过演化整个解池环境而不仅仅是单个最佳解，可能实现一个“开放式”的改进过程——随着更多计算能力的加入，其性能可以继续扩展，而不是过早达到平稳期。

附录

计算资源

随着比赛的进行，我增加了计算资源。最大配置如下：

• Google Cloud Platform 上的 2× C4A（每个 72 核）
• Oracle Cloud Infrastructure 上的 2× Ampere A1（每个 80 核）

总成本：< $2,000

生成式 AI 使用情况

我使用 Codex CLI 编写了本次比赛的全部源代码。此外，Gemini 3.0 Pro 用于头脑风暴、生成想法和研究现有文献。

引用公共解决方案

虽然我主要开发自己的解决方案，但我发现在比赛的最后阶段合并公共解决方案显著提高了我的分数（大约提高了 0.01）。

受影响的 N：2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 131, 132, 154, 180, 181, 182

特别是加粗的值，代表了我的求解器无法达到的重要改进。

统计数据

总分：69.106266

我附上了一个 PDF 文件，记录了我所有的最终配置 (11thPlaceConfigurations.pdf)。如果您感兴趣，请查看！

```