 |
    |
Travelling Salesman Problem Solved ‘in materio’ by Evolved Carbon Nanotube Device
Kester Dean Clegg1, Julian Francis Miller1, Kieran Massey2, and Mike Petty2
1The University of York, UK
kester.clegg@york.ac.uk
julian.miller@york.ac.uk
2Durham University, UK
m.k.massey@durham.ac.uk
m.c.petty@durham.ac.uk
Abstract. We report for the first time on finding shortest path solutions for the travelling salesman problem (TSP) using hybrid “in materio” computation: a technique that uses search algorithms to configure materials for computation. A single-walled carbon nanotube (SWCNT) / polymer composite material deposited on a micro-electrode array is configured using static voltages so that voltage output readings determine the path order in which to visit cities in a TSP. Our initial results suggest that the hybrid computation with the SWCNT material is able to solve small instances of the TSP as efficiently as a comparable evolutionary search algorithm performing the same computation in software. Interestingly the results indicate that the hybrid system’s search performance on TSPs scales linearly rather than exponentially on these smaller instances. This exploratory work represents the first step towards building SWCNT-based electrode arrays in parallel so that they can solve much larger problems.
LNCS 8672, p. 692 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014