Accessibility navigation


Perceived optimality of competing solutions to the Euclidean travelling salesperson problem

Kyritsis, M. ORCID: https://orcid.org/0000-0002-7151-1698, Gulliver, S. R. ORCID: https://orcid.org/0000-0002-4503-5448, Feredoes, E. and Stouraitis, V. (2022) Perceived optimality of competing solutions to the Euclidean travelling salesperson problem. Cognitive Systems Research, 74. pp. 1-17. ISSN 1389-0417

[img]
Preview
Text (Open Access) - Published Version
· Available under License Creative Commons Attribution.
· Please see our End User Agreement before downloading.

6MB
[img] Text - Accepted Version
· Restricted to Repository staff only
· Available under License Creative Commons Attribution Non-commercial No Derivatives.

1MB

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1016/j.cogsys.2022.02.001

Abstract/Summary

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.

Item Type:Article
Refereed:Yes
Divisions:Life Sciences > School of Psychology and Clinical Language Sciences > Department of Psychology
Henley Business School > Business Informatics, Systems and Accounting
ID Code:103818
Publisher:Elsevier

Downloads

Downloads per month over past year

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation