People Efficiently Explore the Solution Space of the Computationally Intractable Traveling Salesman Problem to Find Near-Optimal Tours
Authors:
Open Access
- 29 July 2010
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 5 (7) , e11685
Abstract
Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: (1) only a small portion of instances of such problems are actually hard, and (2) successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesman Problem (TSP). Participants were provided feedback on the cost of their solutions and were allowed unlimited solution attempts (trials). We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings. More importantly, we found that participants modified their current better solutions in such a way that edges belonging to the optimal solution (“good” edges) were significantly more likely to stay than other edges (“bad” edges), a hallmark of structural exploitation. We found, however, that more trials harmed the participants' ability to tell good from bad edges, suggesting that after too many trials the participants “ran out of ideas.” In sum, we provide the first demonstration of significant performance improvement on the TSP under repetition and feedback and evidence that human problem-solving may exploit the structure of hard problems paralleling behavior of state-of-the-art heuristics.Keywords
This publication has 37 references indexed in Scilit:
- Structure Learning in Human Sequential Decision-MakingPLOS Computational Biology, 2010
- Structure learning in actionBehavioural Brain Research, 2010
- Theory-based Bayesian models of inductive learning and reasoningTrends in Cognitive Sciences, 2006
- The aesthetic appeal of minimal structures: Judging the attractiveness of solutions to traveling salesperson problemsPerception & Psychophysics, 2006
- The importance of the convex hull for human performance on the traveling salesman problem: A comment on MacGregor and Ormerod (1996)Perception & Psychophysics, 2000
- Searching for backbones — an efficient parallel algorithm for the traveling salesman problemComputer Physics Communications, 1996
- Optimization by Simulated AnnealingScience, 1983
- A man-machine approach toward solving the traveling salesman problemCommunications of the ACM, 1971
- The Role of Time and Energy in Food PreferenceThe American Naturalist, 1966
- A Behavioral Model of Rational ChoiceThe Quarterly Journal of Economics, 1955