🤖 AI

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

This paper investigates how humans solve Euclidean Traveling Salesman Problems by demonstrating that human-like, near-optimal tours are best modeled not by direct imitation of optimal solutions, but by neural networks pretrained on optimal tours, fine-tuned via reinforcement learning, and decoded through Best-of-N sampling, suggesting that human problem-solving emerges from a combination of supervised learning, reinforcement learning, and test-time search.

Original authors: Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang, Ming Meng

Published 2026-07-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang, Ming Meng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a puzzle where you have to visit a bunch of different locations and return home, but you want to do it in the shortest possible distance. This is a classic brain-teaser known as the Traveling Salesman Problem. It sounds simple, but the math behind it is a nightmare for computers: as you add more locations, the number of possible routes explodes so fast that even the world's most powerful supercomputers can't check every single option to find the absolute best one. Yet, humans are weirdly good at this. We can look at a map of cities and quickly draw a path that is almost as good as the perfect one, even though our brains are tiny and slow compared to a computer. Scientists have long wondered: How do we do it? Are we just guessing, or is there a hidden "algorithm" in our heads that we don't know about? This question sits at the intersection of psychology (how our minds work) and computer science (how we build smart machines). If we can figure out how humans solve these hard puzzles so efficiently, we might be able to build better AI and understand our own thinking better.

This paper dives deep into that mystery by treating human problem-solving like a giant science experiment. The researchers gathered a massive amount of data—over 20 million routes drawn by more than 1,100 people solving 150,000 different city puzzles. They then built computer models to see which ones could best copy how humans think. They tested two main ideas: one where the computer just tries to find the mathematically perfect route (like a robot), and another where the computer learns from examples and then tries to improve itself through trial and error (like a student learning from a teacher and then practicing).

The big surprise? The computer models that tried to be perfect didn't actually look like humans. In fact, the "perfect" routes were too rigid and geometrically precise, missing the little quirks and shortcuts humans naturally take. The models that simply memorized human drawings were better, but they still felt a bit stiff. The real winner was a hybrid approach. The best model first learned from the "perfect" routes to understand the basic rules of geometry, and then it was fine-tuned using a method called reinforcement learning, where it got "rewards" for finding shorter paths. But here is the kicker: this model only looked truly human-like when it was allowed to "think" for a moment before answering. Instead of just picking the first good path it saw, the model generated many possible routes, compared them, and picked the best one. This suggests that human-like intelligence isn't just about having a smart brain; it's about having a smart brain that also knows how to pause, generate a few options, and search through them to find the best fit. The paper suggests that our brains might work the same way: we learn the general shape of a good solution from experience, but when we face a new problem, we do a little bit of mental "searching" to refine our answer.

The researchers found that while humans aren't perfect, our solutions live in a "near-optimal basin." This means our paths are very close to the best possible ones, sharing many of the same structural features, but they have systematic deviations—little imperfections that make them uniquely human. For example, humans tend to be less smooth in their turns and preserve fewer perfect geometric shapes than a computer algorithm designed for perfection. The study explicitly rules out the idea that humans are just using simple, greedy rules (like always picking the closest next city), because those simple strategies performed worse than random guesses. It also suggests that simply copying human drawings isn't enough; the model needs to understand the underlying logic of "good" solutions first.

Ultimately, the paper proposes that human-like solutions emerge from a combination of three things: learning the structure of good solutions from examples (supervised learning), improving that knowledge through feedback (reinforcement learning), and then using a bit of extra computing power at the moment of decision to search for the best option among many (test-time search). This mirrors how modern AI systems are becoming more powerful, not just by getting bigger, but by learning to think harder before they speak. The authors suggest that this "think-then-implement" strategy is likely what allows us to solve these incredibly hard problems so quickly, turning a chaotic mess of possibilities into a neat, efficient path.

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

1. Problem Statement

Combinatorial optimization problems, such as the Euclidean Traveling Salesman Problem (TSP), are computationally hard (NP-hard) yet often solved by humans with near-optimal efficiency under severe time and cognitive constraints. While humans routinely produce tours only ~10% longer than the mathematical optimum, the specific cognitive algorithms and geometric principles underlying this "human-like" performance remain unclear. Existing computational models often rely on either exhaustive search (computationally expensive) or simple heuristics (often suboptimal and failing to capture human structural patterns). The central challenge is to identify a computational framework that not only solves the TSP efficiently but also reproduces the specific geometric signatures and systematic deviations characteristic of human solutions.

2. Methodology

2.1 Large-Scale Behavioral Data Collection (tsp150k)

The authors conducted the largest behavioral experiment on human TSP performance to date, generating the tsp150k dataset.

Participants: 1,107 participants.
Scale: 150,000 unique TSP instances with over 20 million human-generated tours.
Complexity Levels: Five levels based on city count: 10, 12, 15, 19, and 24 cities.
Protocol: Participants solved TSP instances online via a WeChat-integrated platform. Time limits were set to twice the number of cities (e.g., 20s for 10 cities). No feedback on tour length was provided during the task.
Data Density: Each instance received between 92 and 207 human tours (average 139), allowing for robust statistical characterization of human behavior.

2.2 Computational Modeling Framework

The study evaluated a broad hypothesis space of computational models, categorized into search-only methods and hybrid learning-and-search methods.

Search-Only Baselines:
- Exact: Concorde (branch-and-cut) for optimal solutions.
- Heuristics: Nearest Neighbor, Convex Hull Cheapest Insertion, Largest Interior Angle.
- Relaxation: Elastic Net (gradient descent on a deformable ring).
Neural Network Models (Pointer Networks):
The authors utilized Pointer Networks (RNNs with attention-based pointing mechanisms) to define probability distributions over valid tours. Four distinct training regimes were tested:
1. $p_{optimal}$ : Supervised learning on optimal tours (Concorde solutions).
2. $p_{RL}$ : Reinforcement Learning (RL) using negative Euclidean tour length as the reward.
3. $p_{optimal+RL}$ : Supervised pretraining on optimal tours followed by RL fine-tuning.
4. $p_{human}$ : Supervised learning directly on human tours (serving as an empirical upper bound).
Decoding Strategies:
To generate tours from the trained policies, three search strategies were applied:
1. Greedy Decoding: Myopic selection of the most probable next city.
2. Beam Search: Heuristic approximation of the most probable complete sequence.
3. Best-of- $N$ Sampling: Randomly sampling $N$ complete tours and selecting the shortest one.

2.3 Evaluation Metrics

Model performance was assessed on a held-out test set (50,000 instances) using five pairwise similarity metrics comparing model tours to human tours:

Edge Overlap Ratio (EOR): Proportion of shared edges.
Longest Common Substring (LCS): Length of the longest shared consecutive city sequence.
Levenshtein Distance (LD): Minimum edits to transform one tour to another.
Fréchet Distance (FD): Spatial separation between corresponding points in traversal order.
Kendall's $\tau$ : Rank correlation of visiting orders.

Geometric Analysis: Eight specific geometric features (e.g., smoothness, turning-angle entropy, convex-hull preservation, 2-opt optimality) were extracted to characterize the "geometric basin" of human solutions.

3. Key Results

3.1 Human Performance Characteristics

Human tours are near-optimal but exhibit systematic deviations, occupying a "near-optimal geometric basin."
Humans spend significantly more time deliberating at the initial position, suggesting a "think-then-implement" strategy.
After ignoring previously visited cities, human next-city choices stabilize at a high level of local optimality.

3.2 Model Performance Comparison

Search-Only Models: Optimal tours (Concorde) and Elastic Net outperformed simple heuristics and a random human baseline, achieving high similarity to human tours. However, they failed to capture specific human sub-optimality signatures (e.g., lower smoothness and weaker convex-hull preservation than the mathematical optimum).
Pure Supervised Learning ( $p_{human}$ ): The model trained directly on human tours with Beam Search achieved the highest overall alignment (Aggregate Score: 0.600), establishing the empirical upper bound.
The Best Generalizable Model ( $p_{optimal+RL}$ ): Among models not trained on human data, the PointerNet pretrained on optimal tours and fine-tuned with RL, decoded via Best-of- $N$ sampling ( $N=100$ ), achieved the strongest human-likeness (Aggregate Score: 0.600).
- This model closely matched the geometric features of human tours (Pearson's $r = 0.583$ across eight features) and achieved the lowest Mean Absolute Error (MAE = 0.021).
- It successfully reproduced characteristic human sub-optimality (e.g., non-perfect convex-hull preservation) that pure optimal solvers missed.

3.3 Geometric Basin Analysis

Human tours are distinct from pure optimal tours; they exhibit lower smoothness and lower 2-opt local optimality.
$p_{optimal}$ models converge too quickly to the optimal geometric region, missing human deviations.
$p_{RL}$ models become over-concentrated on a narrow set of high-reward tours, lacking the diversity required for test-time search to find human-like variations.
$p_{optimal+RL}$ strikes a balance: supervised pretraining provides broad support for geometrically near-optimal tours, while RL fine-tuning biases the distribution toward shorter paths without eliminating diversity. This allows Best-of- $N$ sampling to converge to a region that aligns with human behavior.

4. Key Contributions

tsp150k Dataset: The creation of a massive, high-quality dataset comprising 150,000 TSP instances and 20+ million human tours, enabling systematic characterization of human behavior.
Identification of Human-Like Mechanisms: Demonstrating that human-like solutions are not merely imitations of optimal tours but emerge from a specific combination of structured supervised learning (acquiring geometric knowledge), reinforcement learning (optimizing for efficiency), and test-time search (Best-of- $N$ sampling).
Geometric Characterization: Defining a "geometric basin" for human solutions, showing that humans share structural properties with optimal solutions while preserving systematic deviations (e.g., in smoothness and convex-hull preservation) that standard heuristics and pure optimal solvers fail to capture.
Cognitive Modeling Framework: Proposing that human problem-solving in combinatorial spaces can be modeled as a two-stage process: acquiring structural knowledge from high-quality examples (imitation) and refining via feedback (RL), followed by deliberation (search) at test time.

5. Significance and Claims

The paper claims that human-like performance in combinatorial optimization arises not from fixed, hand-crafted heuristics, but from a computational architecture that integrates learning and search. Specifically:

Learning-Search Synergy: The most accurate model of human behavior is not a direct imitation of human data, but a model trained on optimal data, refined by RL, and decoded with search. This suggests humans may acquire broad geometric knowledge through exposure to high-quality examples and refine these representations through experience-based feedback.
Role of Test-Time Compute: The study highlights that "test-time compute" (e.g., Best-of- $N$ sampling) is a critical, often overlooked component of cognitive modeling. It allows a static neural network to generate human-like variability in solution quality without modifying its weights, paralleling mechanisms like chain-of-thought reasoning in large language models.
Generalizability: The findings suggest that the "bitter lesson" of AI—relying on learning and computation rather than fixed heuristics—applies to human cognition. Human solutions to complex problems may reflect a cognitive analogue of general-purpose methods that learn from experience and exploit computation through search.

The authors modestly note that while their model reproduces human geometries without direct training on human tours, the source of the "optimal demonstrations" for human supervised learning remains an open question, potentially involving curriculum learning from simpler instances.