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.     

Global vs. local information processing in visual/spatial problem solving: The case of traveling salesman problem

Human visual/spatial problem solving often requires both global and local information to be processed. But the relationship between those two kinds of information and the way in which they interact with one another during problem solving has not been thoroughly discussed. In the particular setting of solving the traveling salesman problem (TSP), we investigated into the relative roles of global and local information processing. An experiment was conducted to measure the importance of global information and the possible constraints of global information processing on search. A model was built to simulate human TSP performance and was used to investigate further the relationship between global information processing and local information processing. Our model was compared with the human data we collected and with other models of human TSP solving.     

A comparison of human performance in figural and navigational versions of the traveling salesman problem

Performance on a typical pen-and-paper (figural) version of the Traveling Salesman Problem was compared to performance on a room-sized navigational version of the same task. Nine configurations were designed to examine the use of the nearest-neighbor (NN), cluster approach, and convex-hull strategies. Performance decreased with an increasing number of nodes internal to the hull, and improved when the NN strategy produced the optimal path. There was no overall difference in performance between figural and navigational task modalities. However, there was an interaction between modality and configuration, with evidence that participants relied more heavily on the NN strategy in the figural condition. Our results suggest that participants employed similar, but not identical, strategies when solving figural and navigational versions of the problem. Surprisingly, there was no evidence that participants favored global strategies in the figural version and local strategies in the navigational version.     

Route selection by rats and humans in a navigational traveling salesman problem

Spatial cognition is typically examined in non-human animals from the perspective of learning and memory. For this reason, spatial tasks are often constrained by the time necessary for training or the capacity of the animal’s short-term memory. A spatial task with limited learning and memory demands could allow for more efficient study of some aspects of spatial cognition. The traveling salesman problem (TSP), used to study human visuospatial problem solving, is a simple task with modifiable learning and memory requirements. In the current study, humans and rats were characterized in a navigational version of the TSP. Subjects visited each of 10 baited targets in any sequence from a set starting location. Unlike similar experiments, the roles of learning and memory were purposely minimized; all targets were perceptually available, no distracters were used, and each configuration was tested only once. The task yielded a variety of behavioral measures, including target revisits and omissions, route length, and frequency of transitions between each pair of targets. Both humans and rats consistently chose routes that were more efficient than chance, but less efficient than optimal, and generally less efficient than routes produced by the nearest-neighbor strategy. We conclude that the TSP is a useful and flexible task for the study of spatial cognition in human and non-human animals.     

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.     

Applications of combinatorial programming to data analysis: The traveling salesman and related problems

The Traveling Salesman and similar combinatorial programming tasks encountered in operations research are discussed as possible data analysis models in psychology, for example, in developmental scaling, Guttman scaling, profile smoothing, and data array clustering. In addition, a short overview of the various computational approaches from this area of combinatorial optimization is included.The research of the first author was supported by a research grant SOC-75-07860 from the National Science Foundation.     

The importance of the convex hull for human performance on the traveling salesman problem: a comment on MacGregor and Ormerod (1996)

MacGregor and Ormerod (1996) have presented results purporting to show that human performance on visually presented traveling salesman problems, as indexed by a measure of response uncertainty, is strongly determined by the number of points in the stimulus array falling inside the convex hull, as distinct from the total number of points. It is argued that this conclusion is artifactually determined by their constrained procedure for stimulus construction, and, even if true, would be limited to arrays with fewer than around 50 points.     

A hierarchical bayesian model of human decision-making on an optimal stopping problem

We consider human performance on an optimal stopping problem where people are presented with a list of numbers independently chosen from a uniform distribution. People are told how many numbers are in the list, and how they were chosen. People are then shown the numbers one at a time, and are instructed to choose the maximum, subject to the constraint that they must choose a number at the time it is presented, and any choice below the maximum is incorrect. We present empirical evidence that suggests people use threshold-based models to make decisions, choosing the first currently maximal number that exceeds a fixed threshold for that position in the list. We then develop a hierarchical generative account of this model family, and use Bayesian methods to learn about the parameters of the generative process, making inferences about the threshold decision models people use. We discuss the interesting aspects of human performance on the task, including the lack of learning, and the presence of large individual differences, and consider the possibility of extending the modeling framework to account for individual differences. We also use the modeling results to discuss the merits of hierarchical, generative and Bayesian models of cognitive processes more generally.     

A hierarchical process-dissociation model

In fitting the process-dissociation model (L. L. Jacoby, 1991) to observed data, researchers aggregate outcomes across participant, items, or both. T. Curran and D. L. Hintzman (1995) demonstrated how biases from aggregation may lead to artifactual support for the model. The authors develop a hierarchical process-dissociation model that does not require aggregation for analysis. Most importantly, the Curran and Hintzman critique does not hold for this model. Model analysis provides for support of process dissociation--selective influence holds, and there is a dissociation in correlation patterns among participants and items. Items that are better recollected also elicit higher automatic activation. There is no correlation, however, across participants; that is, participants with higher recollection have no increased tendency toward automatic activation. The critique of aggregation is not limited to process dissociation. Aggregation distorts analysis in many nonlinear models, including signal detection, multinomial processing tree models, and strength models. Hierarchical modeling serves as a general solution for accurately fitting these psychological-processing models to data.     

Indclas: A three-way hierarchical classes model

A three-way three-mode extension of De Boeck and Rosenberg's (1988) two-way two-mode hierarchical classes model is presented for the analysis of individual differences in binary object × attribute arrays. In line with the two-way hierarchical classes model, the three-way extension represents both the association relation among the three modes and the set-theoretical relations among the elements of each model. An algorithm for fitting the model is presented and evaluated in a simulation study. The model is illustrated with data on psychiatric diagnosis. Finally, the relation between the model and extant models for three-way data is discussed.The research reported in this paper was partially supported by NATO (Grant CRG.921321 to Iven Van Mechelen and Seymour Rosenberg).     

Never cross the path of a traveling salesman: The neural network generation of Halstead-Reitan trail making tests

The Halstead-Reitan Trail Making Test (TMT) is one of the most widely used neuropsychological instruments for the assessment of brain damage. Despite its usefulness, however, the TMT has two major disadvantages. It has not been constructed in a principled manner that would facilitate systematic investigation, and there is no established procedure for generating equivalent, but stochastically different, test forms. The reason is that the generation of self-avoiding TMT pathways resembles the finding of near-optimal solutions to the Euclidean Traveling Salesman Problem (TSP) and constitutes a computational problem that is NP-complete. This article describes a practical approach to the problem of generating stochastically different test forms. This approach employs anelastic net neural network to generate TMT forms based on self-avoiding, near-optimal paths, and closed circuits. The usefulness and limitations of this solution are discussed briefly in relation to alternative and complementary problems and procedures.     

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.     

A hierarchical model of temporal perception

Temporal perception comprises subjective phenomena such as simultaneity, successiveness, temporal order, subjective present, temporal continuity and subjective duration. These elementary temporal experiences are hierarchically related to each other. Functional system states with a duration of 30 ms are implemented by neuronal oscillations and they provide a mechanism to define successiveness. These system states are also responsible for the identification of basic events. For a sequential representation of several events time tags are allocated, resulting in an ordinal representation of such events. A mechanism of temporal integration binds successive events into perceptual units of 3 s duration. Such temporal integration, which is automatic and presemantic, is also operative in movement control and other cognitive activities. Because of the omnipresence of this integration mechanism it is used for a pragmatic definition of the subjective present. Temporal continuity is the result of a semantic connection between successive integration intervals. Subjective duration is known to depend on mental load and attentional demand, high load resulting in long time estimates. In the hierarchical model proposed, system states of 30 ms and integration intervals of 3 s, together with a memory store, provide an explanatory neuro-cognitive machinery for differential subjective duration.     

The conjunctive model of hierarchical classes

This paper describes the conjunctive counterpart of De Boeck and Rosenberg's hierarchical classes model. Both the original model and its conjunctive counterpart represent the set-theoretical structure of a two-way two-mode binary matrix. However, unlike the original model, the new model represents the row-column association as a conjunctive function of a set of hypothetical binary variables. The conjunctive nature of the new model further implies that it may represent some conjunctive higher order dependencies among rows and columns. The substantive significance of the conjunctive model is illustrated with empirical applications. Finally, it is shown how conjunctive and disjunctive hierarchical classes models relate to Galois lattices, and how hierarchical classes analysis can be useful to construct lattice models of empirical data.The research reported in this paper was supported by NATO (Grant CRG.921321 to Iven Van Mechelen and Seymour Rosenberg) and by the Research Fund of Katholieke Universiteit Leuven (Grants PDM92/19 and POR93/3 to Iven Van Mechelen; Grants OT89/9 and F91/56 to Paul De Boeck).     

A set-theoretical approach to the problem of hierarchical clustering

A set-theoretical formalization is developed for the problem of generating hierarchically organized collections of subsets, or to use a phrase common in the applied substantive literature, for the problem of hierarchical clustering. A number of terms are introduced to characterize those clustering methods that attempt to limit the size of the overlap between each pair of subsets constructed at a specific “compactness” level. Several examples, motivated primarily by graph theory, are discussed briefly to illustrate the various set-theoretical concepts presented.     

The comorbidities of adolescent problem behaviors: A latent class model

The correlations and comorbidities of a series of adolescent problem behaviors were studied in a sample of 739 New Zealand 15-year-olds. This analysis revealed the presence of strong comorbidities between different problem behaviors. The data were modeled using methods of unrestricted latent class analysis and this suggested that the best fitting model to describe the data was one which assumed that adolescent problem behaviors were described by four general classes of children. While the same general four-class model applied to males and females, there were marked gender differences in the rates of problems. Specifically, the predominant problem behaviors in females were those relating to an accelerated transition to adulthood marked by early sexual activity, alcohol abuse, and cannabis use whereas the predominant problems for boys were related to antisocial and law-breaking behaviors. Rates of children with no problems (85%) and with multiple problems (3%) were similar for boys and girls.This research was funded by grants from the Health Research Council of New Zealand, the Canterbury Medical Research Foundation, and the National Child Health Research Foundation.     

Predictive joint-action model: A hierarchical predictive approach to human cooperation

Research in a number of related fields has recently begun to focus on the perceptual, cognitive, and motor workings of cooperative behavior. There appears to be enough coherence in these efforts to refer to the study of the mechanisms underlying human cooperative behavior as the field of joint-action (Knoblich, Butterfill, & Sebanz, 2011; Sebanz, Bekkering, & Knoblich, 2006). Yet, the development of theory in this field has not kept pace with the proliferation of research findings. We propose a hierarchical predictive framework for the study of joint-action that we call the predictive joint-action model (PJAM). The presentation of this theoretical framework is organized into three sections. In the first section, we summarize hierarchical predictive principles and discuss their application to joint-action. In the second section, we juxtapose PJAM’s assumptions with empirical evidence from the current literature on joint-action. In the third section, we discuss the overall success of the hierarchical predictive approach to account for the burgeoning empirical literature on joint-action research. Finally, we consider the model’s capacity to generate novel and testable hypotheses about joint-action. This is done with the larger goal of uncovering the empirical and theoretical pieces that are still missing in a comprehensive understanding of joint action.