Human behaviour in the Euclidean Travelling Salesperson Problem: Computational modelling of heuristics and figural effects

The Travelling Salesperson Problem (TSP) describes a situation where an imaginary individual wishes to visit multiple cities once before returning to his/her own city. This type of problem is known as a nondeterministic polynomial (NP) hard problem, since the factorial number of solutions results in it being impractical to solve using exhaustive processing. Interestingly, when presented as a Euclidean graph (i.e., ETSP), humans identify near optimal solutions almost effortlessly, despite billions of possible tours. In this study, we consider human processing of the ETSP, and introduce the reader to a number of factors that literature proposes as impacting human performance. We hypothesise that: (i) human ETSP activity may be modelled by considering the quotient relationship between node-to-node and node-to-centroid distances; and (ii) consideration of figural effects can optimise automated TSP solution generation. In this paper human processing based heuristics are developed, i.e. replacing the cost function within the nearest neighbour algorithm, to guide node selection. Results showed that the quotient relationship between node-to-node and node-to-centroid distances can be used to closely model average human performance, across a range of ETSP graphs. Interestingly, however, additional consideration of graph figural effects (e.g. distance between boundary points in the convex hull, standard deviation of distances between nodes that make up the convex hull, and number of nodes in the convex hull) results in significantly improved tour costs.     

The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesperson problems

The planar Euclidean version of the traveling salesperson problem requires finding the shortest tour through a two-dimensional array of points. MacGregor and Ormerod (1996) have suggested that people solve such problems by using a global-to-local perceptual organizing process based on the convex hull of the array. We review evidence for and against this idea, before considering an alternative, local-to-global perceptual process, based on the rapid automatic identification of nearest neighbors. We compare these approaches in an experiment in which the effects of number of convex hull points and number of potential intersections on solution performance are measured. Performance worsened with more points on the convex hull and with fewer potential intersections. A measure of response uncertainty was unaffected by the number of convex hull points but increased with fewer potential intersections. We discuss a possible interpretation of these results in terms of a hierarchical solution process based on linking nearest neighbor clusters.     

Global perceptual processing in problem solving: The case of the traveling salesperson

The traveling salesperson problem (TSP) consists of finding the shortest tour around a set of locations and is an important task in computer science and operations research. In four experiments, the relationship between processes implicated in the recognition of good figures and the identification of TSP solutions was investigated. In Experiment 1, a linear relationship was found between participants’ judgments of good figure and the optimality of solutions to TSPs. In Experiment 2, identification performance was shown to be a function of solution optimality and problem orientation. Experiment 3 replicated these findings with a forced-pace method, suggesting that global processing, rather than a local processing strategy involving point-by-point analysis of TSP solutions, is the primary process involved in the derivation of best figures for the presented TSPs. In Experiment 4, the role of global precedence was confirmed using a priming method, in which it was found that short (100 msec) primes facilitated solution identification, relative to no prime or longer primes. Effects of problem type were found in all the experiments, suggesting that local features of some problems may disrupt global processing. The results are discussed in terms of Sanocki’s (1993) global-to-local contingency model. We argue that global perceptual processing may contribute more generally to problem solving and that human performance can complement computational TSP methods.     

Global perceptual processing in problem solving: the case of the traveling salesperson.

The traveling salesperson problem (TSP) consists of finding the shortest tour around a set of locations and is an important task in computer science and operations research. In four experiments, the relationship between processes implicated in the recognition of good figures and the identification of TSP solutions was investigated. In Experiment 1, a linear relationship was found between participants' judgments of good figure and the optimality of solutions to TSPs. In Experiment 2, identification performance was shown to be a function of solution optimality and problem orientation. Experiment 3 replicated these findings with a forced-pace method, suggesting that global processing, rather than a local processing strategy involving point-by-point analysis of TSP solutions, is the primary process involved in the derivation of best figures for the presented TSPs. In Experiment 4, the role of global precedence was confirmed using a priming method, in which it was found that short (100 msec) primes facilitated solution identification, relative to no prime or longer primes. Effects of problem type were found in all the experiments, suggesting that local features of some problems may disrupt global processing. The results are discussed in terms of Sanocki's (1993) global-to-local contingency model. We argue that global perceptual processing may contribute more generally to problem solving and that human performance can complement computational TSP methods.     

The aesthetic appeal of minimal structures: judging the attractiveness of solutions to traveling salesperson problems

Ormerod and Chronicle (1999) reported that optimal solutions to traveling salesperson problems were judged to be aesthetically more pleasing than poorer solutions and that solutions with more convex hull nodes were rated as better figures. To test these conclusions, solution regularity and the number of potential intersections were held constant, whereas solution optimality, the number of internal nodes, and the number of nearest neighbors in each solution were varied factorially. The results did not support the view that the convex hull is an important determinant of figural attractiveness. Also, in contrast to the findings of Ormerod and Chronicle, there were consistent individual differences. Participants appeared to be divided as to whether the most attractive figure enclosed a given area within a perimeter of minimum or maximum length. It is concluded that future research in this area cannot afford to focus exclusively on group performance measures.     

Human performance on visually presented Traveling Salesman problems

Little research has been carried out on human performance in optimization problems, such as the Traveling Salesman problem (TSP). Studies by Polivanova (1974, Voprosy Psikhologii, 4, 41–51) and by MacGregor and Ormerod (1996, Perception & Psychophysics, 58, 527–539) suggest that: (1) the complexity of solutions to visually presented TSPs depends on the number of points on the convex hull; and (2) the perception of optimal structure is an innate tendency of the visual system, not subject to individual differences. Results are reported from two experiments. In the first, measures of the total length and completion speed of pathways, and a measure of path uncertainty were compared with optimal solutions produced by an elastic net algorithm and by several heuristic methods. Performance was also compared under instructions to draw the shortest or the most attractive pathway. In the second, various measures of performance were compared with scores on Raven's advanced progressive matrices (APM). The number of points on the convex hull did not determine the relative optimality of solutions, although both this factor and the total number of points influenced solution speed and path uncertainty. Subjects' solutions showed appreciable individual differences, which had a strong correlation with APM scores. The relation between perceptual organization and the process of solving visually presented TSPs is briefly discussed, as is the potential of optimization for providing a conceptual framework for the study of intelligence. Received: 28 December 1998 / Accepted: 20 January 2000     

Spatial and contextual factors in human performance on the travelling salesperson problem

The travelling salesperson problem (TSP) provides a realistic and practical example of a visuo-spatial problem-solving task. In previous research, we have found that the quality of solutions produced by human participants for small TSPs compares well with solutions from a range of computer algorithms. We have proposed that the ability of participants to find solutions reflects the natural properties of human perception, solutions being found through global perceptual processing of the problem array to extract a best figure from the TSP points. In this paper, we extend the study of human performance on the task in order to understand further how human abilities are utilised in solving real-world TSPs. The results of experiment 1 show that high levels of solution quality are maintained in solving larger TSPs than had been investigated previously with human participants, and that the presence of an implied real-world context in the problems has no effect upon performance. Experiment 2 demonstrated that the presence of regularity in the point layout of a TSP can facilitate performance. This was confirmed in experiment 3, where effects of the internality of point clusters were also found. All three experiments were consistent with a global, perceptually based approach to the problem by participants. We suggest that the role of perceptual processing in spatial problem-solving is an important area for further research in both theoretical and applied domains.     

Human performance on the traveling salesman problem

Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.     

Perceived optimality of competing solutions to the Euclidean travelling salesperson problem

The Travelling Salesperson Problem (TSP) is a nondeterministic-polynomial hard (NP-hard) combinatorial problem that occurs in a wide range of industrial domains, including logistics, route finding, and computer wiring. Interestingly, despite the problem’s inherent computational difficulty, when presented in Euclidean space (ETSP), human participants can produce close-to-optimal solutions in near-linear time. However, when asked to compare and select the most optimum solution from a set of pre-defined competing solution options, participants can struggle. In this study we investigate this paradox by asking participants to compare four closed-loop Euclidean TSP solutions, in order to determine which solution they perceived to have the most optimal tour cost. We hypothesise that the extracted geometric properties have an effect on stimulus selection in a discrimination task (selection or no selection). Accordingly, we extracted four geometric properties from competing stimuli in order to create a perceptual activation function. Predictive analytics demonstrated that a classification model could identify the most optimal solution 97% of the time using the perceptual activation scores alone, yet human participants only correctly determined the most optimal solution 47% of the time. Mixed-effects models suggest that ‘likelihood of stimulus selection’ can be modelled as a function of the weighted coefficients of competing perceptual activation scores within each trial; however only a small amount of the variance is explained by these perceptual activation scores. Finally, a drift–diffusion model was used to create a theoretical framework of how likelihood of stimulus selection is influenced by competing perceptual activators. Our study highlights a novel way of extracting and analysing the importance of geometric properties that influence ETSP discrimination tasks, and links this analysis to human behaviour when discriminating between competing ETSP solutions.     

Movement characteristics support a role for dead reckoning in organizing exploratory behavior

Rat exploration is an organized series of trips. Each exploratory trip involves an outward tour from the refuge followed by a return to the refuge. A tour consists of a sequence of progressions with variable direction and speed concatenated by stops, whereas the return consists of a single direct progression. We have argued that processing self-movement information generated on the tour allows a rat to plot the return to the refuge. This claim has been supported by observing consistent differences between tour and return segments independent of ambient cue availability; however, this distinction was based on differences in movement characteristics derived from multiple progressions and stops on the tour and the single progression on the return. The present study examines movement characteristics of the tour and return progressions under novel-dark and light conditions. Three novel characteristics of progressions were identified: (1) linear speeds and path curvature of exploratory trips are negatively correlated, (2) tour progression maximum linear speed and temporal pacing varies as a function of travel distance, and (3) return progression movement characteristics are qualitatively different from tour progressions of comparable length. These observations support a role for dead reckoning in organizing exploratory behavior.     

The traveling salesman problem: A hierarchical model

Our review of prior literature on spatial information processing in perception, attention, and memory indicates that these cognitive functions involve similar mechanisms based on a hierarchical architecture. The present study extends the application of hierarchical models to the area of problem solving. First, we report results of an experiment in which human subjects were tested on a Euclidean traveling salesman problem (TSP) with 6 to 30 cities. The subject's solutions were either optimal or near-optimal in length and were produced in a time that was, on average, a linear function of the number of cities. Next, the performance of the subjects is compared with that of five representative artificial intelligence and operations research algorithms, that produce approximate solutions for Euclidean problems. None of these algorithms was found to be an adequate psychological model. Finally, we present a new algorithm for solving the TSP, which is based on a hierarchical pyramid architecture. The performance of this new algorithm is quite similar to the performance of the subjects.     

It looks easy! Heuristics for combinatorial optimization problems

Human performance on instances of computationally intractable optimization problems, such as the travelling salesperson problem (TSP), can be excellent. We have proposed a boundary-following heuristic to account for this finding. We report three experiments with TSPs where the capacity to employ this heuristic was varied. In Experiment 1, participants free to use the heuristic produced solutions significantly closer to optimal than did those prevented from doing so. Experiments 2 and 3 together replicated this finding in larger problems and demonstrated that a potential confound had no effect. In all three experiments, performance was closely matched by a boundary-following model. The results implicate global rather than purely local processes. Humans may have access to simple, perceptually based, heuristics that are suited to some combinatorial optimization tasks.     

It looks easy! Heuristics for combinatorial optimization problems

Human performance on instances of computationally intractable optimization problems, such as the travelling salesperson problem (TSP), can be excellent. We have proposed a boundary-following heuristic to account for this finding. We report three experiments with TSPs where the capacity to employ this heuristic was varied. In Experiment 1, participants free to use the heuristic produced solutions significantly closer to optimal than did those prevented from doing so. Experiments 2 and 3 together replicated this finding in larger problems and demonstrated that a potential confound had no effect. In all three experiments, performance was closely matched by a boundary-following model. The results implicate global rather than purely local processes. Humans may have access to simple, perceptually based, heuristics that are suited to some combinatorial optimization tasks.     

Google and the mind: predicting fluency with PageRank

Human memory and Internet search engines face a shared computational problem, needing to retrieve stored pieces of information in response to a query. We explored whether they employ similar solutions, testing whether we could predict human performance on a fluency task using PageRank, a component of the Google search engine. In this task, people were shown a letter of the alphabet and asked to name the first word beginning with that letter that came to mind. We show that PageRank, computed on a semantic network constructed from word-association data, outperformed word frequency and the number of words for which a word is named as an associate as a predictor of the words that people produced in this task. We identify two simple process models that could support this apparent correspondence between human memory and Internet search, and relate our results to previous rational models of memory.     

New Spirituality and Social Engagement

New spirituality has often been accused of being egocentric and thus lacking incentives for social engagement. The discussion on this subject is tangled because authors differ in specifying who they are writing about and what the criticism is. After seeking an adequate demarcation of the target group (people involved in new spirituality), we established a concept of social engagement that distinguishes between behavior that is and that is not driven by egocentric motivation. Using measures based on this conceptual model, we surveyed a representative sample of the Dutch population. We found that on most measures people involved in new spirituality are less socially engaged than affiliated or traditionally religious people but more engaged than “secular” people. However, they are more committed to organizations for environmental protection, peace, or animal rights than others. Overall, demographic factors—especially education, age, and gender—are stronger predictors for social engagement than religious and spiritual beliefs, experiences, or practices. The most important spirituality variable that predicts some social engagement measures is connectedness with self, others, and nature.     

A model of human performance on the traveling salesperson problem

A computational model is proposed of how humans solve the traveling salesperson problem (TSP). Tests of the model are reported, using human performance measures from a variety of 10-, 20-, 40-, and 60-node problems, a single 48-node problem, and a single 100-node problem. The model provided a range of solutions that approximated the range of human solutions and conformed closely to quantitative and qualitative characteristics of human performance. The minimum path lengths of subjects and model deviated by average absolute values of 0.0%, 0.9%, 2.4%, 1.4%, 3.5%, and 0.02% for the 10-, 20-, 40-, 48-, 60-, and 100-node problems, respectively. Because the model produces a range of solutions, rather than a single solution, it may find better solutions than some conventional heuristic algorithms for solving TSPs, and comparative results are reported that support this suggestion.     

Risk and Prisoner's Dilemma: A Reinterpretation of Coombs' Re‐parameterization

We propose a model to measure risk in a prisoner's dilemma based on Coombs' (1973) re‐parameterization of the game as an individual risk decision‐making task that chooses between a gamble of cooperation and another gamble of defection. Specifically, we propose an index, r, to represent the risk associated with cooperation relative to defection. In conjunction with Rapoport's (1967) index of cooperation (K), our formulation of risk allows us to construct games that vary in risk (as indexed by r) while controlling for cooperativeness (as indexed by K). Following utility analysis that models risk seeking as a convex utility function and risk averse as a concave function, we predict that risk‐seeking people cooperate more in games that the cooperation choice is more risky, whereas risk‐averse people cooperate more in games that the cooperation choice is less risky. In the three studies that we varied game parameters, used different measures of risk orientation and prosocial orientation and used different experimental procedures, we found robust results supporting our predictions. Theoretical analysis of our formulation further suggests that risk and cooperativeness of a prisoner's dilemma game is not entirely independent. Games that have a higher cooperativeness index are necessarily more risky. Copyright © 2011 John Wiley & Sons, Ltd.     

Early computation of contour curvature and part structure: evidence from holes

We used holes to study unilateral border ownership and in particular the information carried by the sign of the curvature along the contour (ie the difference between convex and concave regions). When people perceive a hole, its shape has a reversed curvature polarity (ie a changed sign of curvature) compared to the same region perceived as an object. Bertamini (2001 Perception 30 1295-1310), and Bertamini and Croucher (2003 Cognition 87 33-54) suggested and found evidence to support the hypothesis that, because convex regions are perceived as parts, positional information is more readily available for convex regions. Therefore a change is predicted when a given region is perceived as either a hole or a figure. We confirm that finding in this study, using holes defined by binocular disparity. We conclude that a change from figure to hole always reverses the encoding of curvature polarity. In turn, polarity obligatorily affects perceived part structure and the processing of position.     

Effects of Solution Elicitation Aids and Need for Cognition on the Generation of Solutions to Ill-Structured Problems

Numerous techniques have been proposed to assist problem solvers in the solution generation process. We empirically examined the effectiveness of a solution elicitation technique based on the presentation of problem objectives and also examined whether the technique was effective across individual differences in need for cognition (NC). We found that when two conflicting objectives were presented successively, more solutions, more categories of solutions, and more effective solutions were generated than when the same two objectives were presented simultaneously or not at all. However, the results indicated that effective solutions may be more efficiently generated by considering objectives simultaneously. Need for cognition was positively related to measures of divergent thinking, and the presentation of objectives was particularly effective as a solution elicitation aid for individuals with low NC. Implications for creative problem-solving research and practice are discussed.     

Change blindness blindness: beliefs about the roles of intention and scene complexity in change detection

Observers have difficulty detecting visual changes. However, they are unaware of this inability, suggesting that people do not have an accurate understanding of visual processes. We explored whether this error is related to participants' beliefs about the roles of intention and scene complexity in detecting changes. In Experiment 1 participants had a higher failure rate for detecting changes in an incidental change detection task than an intentional change detection task. This effect of intention was greatest for complex scenes. However, participants predicted equal levels of change detection for both types of changes across scene complexity. In Experiment 2, emphasizing the differences between intentional and incidental tasks allowed participants to make predictions that were less inaccurate. In Experiment 3, using more sensitive measures and accounting for individual differences did not further improve predictions. These findings suggest that adults do not fully understand the role of intention and scene complexity in change detection.