Abstracts
Individual Differences in Problem Solving and Intelligence
Author: Nick Burns
Affiliation:University of Adelaide
Studies of human problem solving have traditionally used deterministic tasks
that require the execution of a systematic series of steps to reach a rational
and optimal solution. Most real-world problems, however, are characterised
by uncertainty, the need to consider an enormous number of variables and possible
courses of action at each stage in solving the problem, and the need to optimise
the solution subject to multiple interacting constraints. There are reliable
individual differences in people’s abilities to solve such realistic
problems. It also seems likely that people’s ability to solve these difficult
problems reflects, or depends on, their intelligence. We report on a study
of N = 101 adults who completed a series of visual optimisation problems (Travelling
Salesperson, Minimum Spanning Tree, and Generalised Steiner Tree problems),
as well as a cognitive optimisation problem (a version of the Secretary problem).
We also characterised these individuals along three relevant and important
cognitive abilities dimensions, fluid ability, visuo-spatial ability, and cognitive
processing speed. Modelling of covariance structures indicated that performance
on both types of optimisation problems relies on general intelligence and raises
the possibility that they can be used to assess intelligence.
Optimizing and “pessimizing” – human performance with instructional variants of the traveling salesperson problem
Author: Edward P. Chronicle
Affiliation: University of Hawaii at Manoa
The two-dimensional Traveling Salesperson Problem (TSP) requires finding the
shortest tour through n locations. Untrained adults are adept at the
task, and reliably outperform simple construction algorithms for n ≤ 60.
Performance may stem from a specific, inherent ability. Alternatively, it may
reflect general spatial intelligence, whether inherent or acquired. If the
latter holds, then people should be equally adept at finding longest tours.
I report two experiments in which human ability to find shortest and longest
tours was examined. In Experiment 1, tour lengths were 6.02% above the minimal
for short tours, and 16.23% below the maximal for long tours, with short tour
performance significantly superior to long, t(18)=4.30, p<.001. Experiment
2 replicated Experiment 1, and also examined whether humans could perform at
the equivalent level to that of construction algorithms when finding longest
tours. Full data will be available by the time of the meeting. These results
are consistent with the hypothesis of a specific, inherent ability to find
short routes, and I will offer some suggestions as to possible origins of this
ability.
Human interaction in solving hard practical optimization problems
Author: Richard W. Eglese
Affiliation: Lancaster University, UK
In the field of Operational Research, there are many practical management
situations where a mathematical model may be constructed in the form of an
optimization model. Many of these models require excessive computing time and
resources to produce a guaranteed optimal solution. Heuristic methods are often
devised for these hard practical optimization problems to deliver a good, though
not necessarily optimal solution, within the computing time available. A key
question is whether devising an approach that involves human judgement as part
of the solution process is an effective strategy for producing good solutions.
This issue is illustrated using a case study concerning the planning of vehicle
routes for a winter gritting operation. In this case, a comparison is made
of the quality of the solution achieved by allowing human interaction in the
solution process compared to a simple heuristic, showing that significant benefits
may be obtained from this approach. Further reasons are given and discussed
for making use of human interaction in solving hard practical optimization
problems and finally some issues for future research in this area are outlined.
Approximating TSP solutions with Graph Pyramids
Authors: Walter G. Kropatsch and Yll Haxhimusa
Affiliation: Vienna University of Technology
The travelling salesperson (TSP) problem consists in finding the shortest
tour through n cities. The locations of these cities determine the solution
and the difficulty of finding it. There are configurations where a trivial
closest neighbor connecting algorithm finds the optimal solution. Pyramid solution
strategies convert a TSP problem with a large number of cities into successively
smaller problems with similar layout and solution until the number of cities
is small enough to seek the optimal solution. Expanding this solution to the
lower levels of the pyramid approximates the solution. A dual graph pyramid
adapts its structure to the data. A version of Boruvca's minimal spanning tree
construction will be applied to the solution of the TSP problem. Inserting
further cities along the optimal tour does not change its length. This increases
the size of a given TSP problem into a large class where the trivial algorithm
finds the original optimal solution. This may be of interest for two reasons:
1) It allows the generation of a large variety of new problems with a known
optimal solution. 2) The difficulty of a given TSP problem could be related
with the density of cities along the optimal tour.
A generative model of human performance on an optimal stopping problem
Author: Michael D. Lee
Affiliation: University of Adelaide, Australia
We consider human performance on an optimal stopping problem where people
are presented with a list numbers independently chosen from a bounded 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 number that exceeds a fixed threshold
for that position in the list. We then develop a generative account of this
model family, and use Bayesian and Minimum Description Length methods -- including
model averaging, model selection and 'entropification' methods -- to learn
about the parameters of the generative process, and make inferences about the
threshold decision models people use. Finally, we consider a framework for
modelling the clear individual differences in the data, and discuss the possibility
of modelling group decision-making on a modified version of the optimal stopping
task.
Solution performance and heuristics in closed and open versions of 2D Euclidean TSPs
Author: James N. MacGregor
Affiliation: University of Victoria, Canada
We report the results of several previously published experiments and one
new experiment comparing optimization performance on closed tours versus open
paths. One experiment used instances with 12 nodes having either one or six
interior nodes. The results indicated more optimal solutions on closed tours
than on open paths, but differences were more pronounced for the one than for
the six interior node instances. A second experiment using 15 node instances
with 9 interior nodes failed to find a significant difference between closed
and open versions, while a third, using 15 node instances with 4 interior nodes,
again found closed tour performance to be superior. A fourth experiment, using
20 node problems with 0, 5, 10 and 15 interior points, found results similar
to the first experiment, that the superiority of performance on closed versions
was greater for fewer interior points. Overall, the results indicate that performance
on closed tours degrades with increasing numbers of interior points, while
performance on open paths does not. We discuss implications of the results
for human heuristics for solving both closed and open versions.
Human solutions to the capacitated vehicle routing problem
Authors: Tom Ormerod & Simon Slavin
Affiliation: Lancaster University, UK
The capacitated vehicle routing problem (CVRP) presents an important example
of NP-complete optimization problems, partly because it subsumes travelling
sales problems as a special case, but also because of its practical significance
to delivery and distribution planning. The CVRPs studied here consist of a
set of nodes presented in a 2D Euclidean plane: deliveries must be made to
meet different demands from nodes using a finite number of capacity-limited
vehicles. We present the results of a series of preliminary studies that examine
human-drawn solutions to CVRPs of between 30 and 60 nodes. The studies compare
human performance against known optimum solutions, and also examine the effects
of visual display of node demand size and training manipulations on improvement
to human solutions.
Adaptive pyramid model for the traveling salesman problem
Author: Pizlo, Z., Stefanov, E., Saalweachter, J., Haxhimusa, Y. & Kropatsch,
W.G.
Affiliation: Purdue University and Vienna Univ. of Technology
We will present a pyramid model, which provides near-optimal solutions to
the Euclidean-TSP in time that is a low-degree polynomial function of the problem
size. In this model hierarchical clustering of cities is first performed by
using an adaptive method. Specifically, after computing a weighted average
I(x,y) of city positions, the algorithm finds the borders between clusters
as argmin_x{argmax_y[I(x,y)]} or argmin_y{argmax_x[I(x,y)]}. This process is
performed recursively in a coarse-to-fine direction. The solution tour is then
produced by a sequence of coarse-to-fine approximations, during which the model
has a high-resolution access to the problem representation only within a small
area, simulating the non-uniform distribution of visual acuity across the visual
field. The tour is produced by simulated movements of the eyes. Computational
complexity of the new model is between N and N^2. The model was applied to
TSP problems of size 6, 10, 20 and 50 and its performance was fitted to that
of five subjects by using one free parameter representing the extent of local
search. Computational efficiency of the model was then tested using problems
with sizes between 50 and 1000 cities.
Understanding human sequential decision making under uncertainty using ideal observer analysis
Author: Brian J. Stankiewicz
Affiliation: University of Texas, Austin
Most human decisions are made with a certain amount of uncertainty about the
true state of the environment and with noisy actions and observations. For
example, in medical diagnosis and treatment, a patient will present a collection
of symptoms in which the doctor must interpret and generate a hypothesis about
the true malady (uncertainty about the true state of the patient). Given these
initial observations and the hypotheses that the doctor generated, he/she needs
to decide what actions to do. These actions can be gathering more information
from the patient (e.g., tests) or prescribing a specific treatment. Furthermore
the doctor must weigh the costs and benefits of each of these actions. Once
the doctor has decided on the appropriate action the doctor will receive new
information that will aid in updating his current belief about the true malady
of the patient. The doctor will cycle through this observe, belief update,
generate action cycle until the task is completed. We are studying human sequential
decision making with uncertainty behavior by studying human performance in
problems that are structurally similar to the medical diagnosis problem using
a Seek-and-Destroy task and a human navigation when lost task. In both of these
studies we compare the human observer to the ideal observer using Partially
Observable Markov Decision Process (POMDP). We have worked to isolate the cognitive
limitation that are preventing subjects from become optimal decision makers.
In summary we have evidence that the cognitive limitation is in the subject's
ability to integrate the actions and observations into an accurate belief state
about the environment.
Implementing The Tractable-Design Cycle: Definitions and Techniques
Author: Ulrike Stege
Affiliation: University of Victoria, Canada
In her talk, I. van Rooij proposed to utilize a tractable-design cycle in
the computational modeling of human optimization behavior. To implement this
cycle we need the following two ingredients: (1) a definition of tractability,
and (2) techniques for assessing tractability. In this talk I discuss two proposals
for defining tractability. The first definition derives from classical complexity
theory and defines tractability as polynomial-time computability.
On this account NP-hard computations are considered intractable. The second
definition derives from parameterized complexity theory and defines tractability
as polynomial-time computability for small parameters ranges, called fixed-parameter
tractability.
On this account NP-hard computation may be tractable for small parameter ranges,
even if the input size is large. I will argue that, for our purpose, the second
definition improves upon the first. Subsequently, I review a set of rather
simple techniques to perform (in)tractability tests and provide examples of
how these techniques can be used in the analysis and improvement of existing
models of human optimization.
Understanding Human Optimization: The Case for a Tractable-Design Cycle
Author: Iris van Rooij
Affiliation: Eindhoven University of Technology
Optimization models of cognition abound. For example, Eleanor Rosch proposed
that humans form object categories so as to maximize within-category similarity
and between-category dissimilarity; Paul Thagard proposed that humans make
inferences so as to maintain maximally coherent belief networks; Kurt Koffka
proposed that humans interpret ambiguous images in the simplest possible way.
Formalizations of such optimization models often run into the problem of computational
intractability. Intractable optimization models are unsatisfactory, as they
seem to exclude any computational understanding of how humans optimize. To
deal with this problem, I propose to implement a “tractable-design cycle” (analogous
to the well-known “empirical cycle”): Each round we formulate a
newly adjusted theory and test it against the tractability criterion. If, at
some point, the test comes out positive, we have achieved an understanding
of how the behavioral capacity that seemed intractable at first (in light of
the old theory) is in fact computationally realizable (in light of the new
theory). If, on the other hand, we systematically fail to find a tractable
version of the theory, then we have corroborating evidence that the theory
is fundamentally flawed. In any event, the tractable-design cycle makes for
a better understanding of human optimization abilities and inabilities.
|
