🤖 AI

Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search

本文通过研究发现，人类解决欧几里得旅行商问题的方式并非通过直接模仿最优解，而是通过在最优路径上进行预训练、经由强化学习微调并利用 Best-of-N 采样进行解码的神经网络来建模类人且近乎最优的路径，这表明人类的问题解决能力源于监督学习、强化学习与测试时搜索的结合。

原作者： Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang, Ming Meng

发布于 2026-07-28

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang, Ming Meng

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试解决一个谜题：你必须访问许多不同的地点，然后回到家，但你想用最短的距离完成这一切。这是一个被称为“旅行商问题”（Traveling Salesman Problem）的经典脑力挑战。这听起来很简单，但其背后的数学逻辑对计算机来说简直是一场噩梦：随着地点数量的增加，可能路径的数量会爆炸式增长，以至于即使是世界上最强大的超级计算机也无法检查每一个选项来找到绝对最优的路径。然而，人类在这方面却异常擅长。我们可以看着一张城市地图，迅速画出一条几乎接近完美路径的路线，尽管我们的大脑与计算机相比既微小又缓慢。科学家们长期以来一直在思考：我们究竟是如何做到的？我们是在瞎猜，还是大脑中隐藏着某种我们尚未察觉的“算法”？这个问题处于心理学（研究我们的思维如何运作）与计算机科学（研究我们如何构建智能机器）的交汇点。如果我们能弄清楚人类是如何如此高效地解决这些难题的，我们或许就能构建出更好的人工智能，并更好地理解我们自身的思维。

这篇论文通过将人类解决问题的过程视为一场巨大的科学实验，深入探讨了这个谜团。研究人员收集了海量数据——超过 1,100 人在解决 150,000 个不同城市谜题过程中绘制的 2,000 多万条路径。随后，他们构建了计算机模型，以观察哪些模型能最好地模仿人类的思维方式。他们测试了两个主要思路：一种是计算机仅仅尝试寻找数学上的完美路径（像机器人一样）；另一种是计算机通过实例进行学习，然后通过试错法进行自我改进（像一个通过老师学习并随后进行练习的学生）。

大惊喜在于：那些试图追求完美的计算机模型实际上并不像人类。事实上，“完美”的路径过于僵硬且具有几何精确性，缺失了人类自然采取的那些小巧思和捷径。那些仅仅模仿人类绘图的模型表现较好，但仍然显得有些生硬。真正的赢家是一种混合方法。表现最好的模型首先从“完美”路径中学习，以理解基本的几何规则，然后利用一种称为“强化学习”的方法进行微调，即通过寻找更短路径来获得“奖励”。但关键在于：只有当模型被允许在回答前先“思考”片刻时，它才会表现得真正像人。模型并不是直接选择看到的第一个好路径，而是生成许多可能的路径，进行比较，然后选出最好的那一个。这表明，类人智能不仅仅关乎拥有一个聪明的头脑；还在于拥有一个懂得如何停顿、生成几个选项并搜索它们以找到最合适方案的聪明头脑。该论文指出，我们的大脑可能也是这样运作的：我们从经验中学习优秀解的总体轮廓，但在面对新问题时，我们会进行一些细微的心理“搜索”来完善答案。

研究人员发现，虽然人类并不完美，但我们的解决方案存在于一个“近优盆地”（near-optimal basin）中。这意味着我们的路径非常接近最优路径，拥有许多相同的结构特征，但也存在系统性的偏差——即那些使之具有独特人性特征的小瑕率。例如，人类在转弯时往往不够平滑，且保留的完美几何形状比旨在追求完美的计算机算法要少。这项研究明确排除了人类只是在使用简单的“贪婪规则”（例如总是选择最近的下一个城市）的可能性，因为这些简单的策略表现甚至不如随机猜测。它还表明，仅仅模仿人类的绘图是不够的；模型首先需要理解“优良”解的底层逻辑。

最终，这篇论文提出，类人解的产生源于三者的结合：从实例中学习优秀解的结构（监督学习）、通过反馈改进该知识（强化学习），以及在决策时刻利用额外的计算能力在众多选项中搜索最佳选项（测试时搜索）。这反映了现代人工智能系统变得更加强大的方式——不仅是通过规模变大，更是通过学会如何在开口说话前进行更深入的思考。作者认为，这种“先思考后执行”的策略很可能就是使我们能够如此快速地解决这些极其困难的问题，将混乱的可能性转化为一条整洁、高效路径的原因。

技术摘要：通过学习与搜索理解组合优化中的类人解法

1. 问题陈述

组合优化问题（如欧几里得旅行商问题，TSP）在计算上是极难的（NP-hard），但在严苛的时间和认知约束下，人类通常能以接近最优的效率解决这些问题。虽然人类生成的路径长度通常仅比数学最优解长约 10%，但支撑这种“类人”表现的具体认知算法和几何原理仍不明确。现有的计算模型要么依赖于穷举搜索（计算成本高昂），要么依赖于简单的启发式算法（通常表现欠佳，且无法捕捉人类的结构化模式）。核心挑战在于寻找一种计算框架，该框架不仅能高效解决 TSP，还能重现人类解法中特有的几何特征和系统性偏差。

2. 研究方法

2.1 大规模行为数据采集 (tsp150k)

作者进行了迄今为止规模最大的关于人类 TSP 表现的行为实验，生成了 tsp150k 数据集。

参与者： 1,107 名参与者。
规模： 150,000 个独特的 TSP 实例，包含超过 2,000 万条人类生成的路径。
复杂度等级： 基于城市数量分为五个等级：10、12、15、19 和 24 个城市。
实验协议： 参与者通过一个集成微信的平台在线解决 TSP 实例。时间限制设定为城市数量的两倍（例如，10 个城市为 20 秒）。任务过程中不提供路径长度的反馈。
数据密度： 每个实例接收到 92 至 207 条人类路径（平均 139 条），从而实现了对人类行为的稳健统计表征。

2.2 计算建模框架

本研究评估了一个广泛的假设空间模型，将其分为仅搜索方法和学习与搜索混合方法。

仅搜索基准模型：
- 精确解法： Concorde (branch-and-cut) 用于获取最优解。
- 启发式算法： 最近邻算法 (Nearest Neighbor)、凸包最便宜插入法 (Convex Hull Cheapest Insertion)、最大内角法 (Largest Interior Angle)。
- 松弛法： 弹性网 (Elastic Net)（在可变形环上进行梯度下降）。
神经网络模型 (Pointer Networks)：
作者利用指针网络（带有注意力机制的 RNN）来定义有效路径的概率分布。测试了四种不同的训练方案：
1. $p_{optimal}$ ： 在最优路径（Concorde 解）上的监督学习。
2. $p_{RL}$ ： 强化学习 (RL)，使用负的欧几里得路径长度作为奖励。
3. $p_{optimal+RL}$ ： 在最优路径上进行监督预训练，随后进行 RL 微调。
4. $p_{human}$ ： 直接在人类路径上进行监督学习（作为经验上限）。
解码策略：
为了从训练好的策略中生成路径，应用了三种搜索策略：
1. 贪婪解码 (Greedy Decoding)： 启发式地选择概率最大的下一个城市。
2. 束搜索 (Beam Search)： 对最可能的完整序列进行启发式近似。
3. Best-of- $N$ 采样： 随机采样 $N$ 条完整的路径并从中选择最短的一条。

2.3 评估指标

模型性能在留出的测试集（50,000 个实例）上进行评估，通过五种两两相似度指标将模型路径与人类路径进行比较：

边重叠率 (EOR)： 共享边的比例。
最长公共子串 (LCS)： 最长的连续城市序列的长度。
编辑距离 (Levenshtein Distance, LD)： 将一条路径转换为另一条路径所需的最小编辑次数。
Fréchet 距离 (FD)： 遍历顺序中对应点之间的空间分离度。
肯德尔 $\tau$ 系数 (Kendall's $\tau$ )： 访问顺序的秩相关性。

几何分析： 提取了八个特定的几何特征（如平滑度、转角熵、凸包保持度、2-opt 最优性等），用以表征人类解法的“几何盆地”。

3. 关键结果

3.1 人类表现特征

人类路径接近最优，但存在系统性偏差，占据了一个“近优几何盆地”。
人类在初始位置会花费显著更多的时间进行思考，表明存在一种“先思考后执行”的策略。
在忽略已访问城市后，人类对下一个城市的选择在局部最优性方面趋于稳定。

3.2 模型性能比较

仅搜索模型： 最优路径（Concorde）和弹性网的表现优于简单的启发式算法和随机人类基准，与人类路径具有高度相似性。然而，它们未能捕捉到特定的类人次优特征（例如，其平滑度和凸包保持度弱于人类）。
纯监督学习 ( $p_{human}$ )： 使用束搜索并直接在人类路径上训练的模型实现了最高的整体对齐度（聚合得分：0.600），建立了经验上限。
最佳泛化模型 ( $p_{optimal+RL}$ )： 在非人类数据训练的模型中，在最优路径上预训练并通过 RL 微调的 PointerNet，结合 Best-of- $N$ 采样 ( $N=100$ )，实现了最强的类人性（聚合得分：0.600）。
- 该模型紧密匹配了人类路径的几何特征（八个特征的 Pearson 相关系数 $r = 0.583$ ），并实现了最低的平均绝对误差 (MAE = 0.021)。
- 它成功重现了人类特有的次优特征（如非完美的凸包保持），而纯最优求解器则忽略了这一点。

3.3 几何盆地分析

人类路径与纯最优路径截然不同；它们表现出较低的平滑度和较低的 2-opt 局部最优性。
$p_{optimal}$ 模型过快地收敛到最优几何区域，错失了人类的偏差。
$p_{RL}$ 模型过于集中在极少数高奖励路径上，缺乏进行测试时搜索所需的多样性。
$p_{optimal+RL}$ 达到了平衡：监督预训练提供了对几何近优路径的广泛支持，而 RL 微调则将分布偏向更短的路径，同时并未消除多样性。这使得 Best-of- $N$ 采样能够收敛到与人类行为一致的区域。

4. 核心贡献

tsp150k 数据集： 创建了一个大规模、高质量的数据集，包含 150,000 个 TSP 实例和 2,000 万条以上的人类路径，使系统性表征人类行为成为可能。
识别类人机制： 证明了类人解法并非仅仅是对最优路径的模仿，而是源于结构化监督学习（获取几何知识）、强化学习（优化效率）与测试时搜索（Best-of- $N$ 采样）的特定结合。
几何表征： 定义了人类解法的“几何盆地”，表明人类解法在共享最优解结构属性的同时，保留了系统性的偏差（如在平滑度和凸包保持度方面的偏差），而标准的启发式算法和纯最优求解器无法捕捉这些特征。
认知建模框架： 提出人类在组合空间中的问题解决过程可以被建模为一个两阶段过程：从高质量示例中获取结构化知识（模仿），通过反馈进行精炼（RL），随后在测试时进行决策（搜索）。

5. 意义与主张

本文声称，组合优化中的类人表现并非源于固定的、手工设计的启发式算法，而是源于一种整合了学习与搜索的计算架构。具体而言：

学习-搜索协同作用： 最准确的人类行为模型并非直接模仿人类数据，而是通过在最优数据上训练、经由 RL 精炼并使用搜索进行解码的模型。这表明人类可能通过接触高质量示例来获取广泛的几何知识，并通过基于经验的反馈来精炼这些表示。
测试时计算的作用： 研究强调，“测试时计算”（如 Best-of- $N$ 采样）是认知建模中一个关键且常被忽视的组成部分。它允许静态神经网络生成具有人类多样性的解法质量，而不必修改其权重，这与大型语言模型中的思维链（chain-of-thought）推理机制相类似。
泛化性： 研究结果表明，AI 的“苦涩教训”（即依赖学习和计算而非固定启发式算法）同样适用于人类认知。人类对复杂问题的解法可能反映了一种通用方法的认知模拟，即通过学习经验并利用搜索来发挥计算能力。

作者也谦虚地指出，尽管他们的模型无需直接在人类路径上训练即可重现人类几何特征，但人类监督学习的“最优演示”来源仍是一个开放性问题，可能涉及从更简单实例进行的课程学习。