Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search
Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang, Ming Meng
cs.AI
2026-07-27
用 1107 人、15 万道旅行商问题的近 2100 万条解,研究发现人类路线落在近最优的几何盆地但带稳定偏差,Pointer Network 靠最优解加强化学习复现了这种「人味」。
旅行商问题(TSP)是经典的 NP-hard 组合优化:给定一堆点,找一条访问所有点又回到起点的最短路线。算法要靠精确求解器 Concorde 或启发式搜索,人在毫秒级就能画出一条很不错的路线,而且似乎不依赖穷举。这种「人比算法快又准」的能力从何而来,一直是认知科学和 AI 交叉处的谜题。
这篇要回答两个问题:人类的 TSP 解到底「人」在哪里,能不能用一个学习模型把这种人类策略学出来。
团队收集了 1107 名被试在 15 万道欧氏 TSP 实例上的解,合计约 2080 万条路线(平均每题 139 条人类解)。实例规模从 10 个城市到 24 个城市。
建模用的是 Pointer Network,一种带注意力机制、按位置「指点」输出顺序的循环网络。训练策略分四档:只在最优解上做监督学习(poptimal)、纯强化学习(pRL)、最优解监督预训练再 RL 微调(poptimal+RL)、以及在人类解上监督学习(phuman)。推理时再叠加三种解码:贪心、束搜索(beam search,B=100)、Best-of-N 采样(N=1/10/100)。作为对照,他们还跑了一批纯搜索基线:精确的 Concorde、最近邻、凸包最廉价插入、最大内角、弹性网。
关键是不只比谁更短,而是比谁更像人:作者定义了一个「类人几何指标」,看路线的平滑度、2-opt 局部最优性、凸包边界保持等几何特征与人类解的吻合度。
人类路线确实近乎最优但不是最优:最优差距随规模从 10 城的 6.2% 涨到 24 城的 11.0%,而每个人最好的那条路线距最优只差 0.3%。换句话说,人类落在一个近最优的几何盆地,但不是精确命中那个最优点。
人类有一致的偏差:比最优路线更不光滑、2-opt 局部最优性更低、凸包边界保持更弱。这些偏差稳定可复现,正是「人味」的来源。
在不用人类数据训练的模型里,poptimal+RL 配 Best-of-100 采样最像人,类人几何指标的 Pearson 相关达到 0.583。拿它和搜索基线比类人程度(满分 1.0):Concorde 只有 0.592,弹性网 0.593,而该模型 0.600,纯最近邻只有 0.447。用人类解监督的 phuman 配束搜索达到 0.600,被视为经验上限。
一个反直觉的发现:纯 RL 模型(pRL)的几何分布「过度集中」,对测试时的搜索反而不敏感;而监督加 RL 的模型更愿意通过 Best-of-N 采样收敛到人类所在的近最优区域。
| 方法 | 类人程度 |
| 最近邻 | 0.447 |
| Concorde(精确) | 0.592 |
| 弹性网 | 0.593 |
| poptimal+RL, Best-of-100 | 0.600 |
对做组合优化和学习的人,这篇的价值是它把「最优」和「类人」拆开了:一个能找最优解的模型未必像人,一个像人的模型未必最优。人靠的大概是一套带稳定偏差的几何启发式,不是穷举,这套启发式可以被神经网络学出来。这给「用人类认知策略改进搜索算法」留下了一个具体的入口。
对从业者要清醒的是,这是 10 到 24 个城市的小规模,直接搬到上千节点的物流问题上是另一回事。
作者自己承认几处。人在真实生活里不可能像监督训练那样大规模观察到最优解,那么人类解的范本从哪来,这篇没有给出认知层面的解释。网络容量有限,仍会把不可忽略的概率分给那些既不最优也不像人的候选路线。测试时的搜索还可以试更复杂的(如 MCMC),这篇没覆盖。
读下来还有一个方法上的张力:类人程度这套指标是作者自己定义的,phuman 在它上面天然占优(在人类解上训、再用人类指标评),把它当经验上限看可以,但不能当成一个干净的对照。