Travelling Salesman Problem Solved ‘in materio’ by Evolved Carbon Nanotube Device

Kester Dean Clegg, Julian Francis Miller, Kieran Massey, Micheal Petty

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XIII
Subtitle of host publication13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings
PublisherSpringer
Pages692-701
Number of pages10
Volume8672
ISBN (Electronic)978-3-319-10762-2
ISBN (Print)978-3-319-10761-5
DOIs
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume8672
ISSN (Print)0302-9743

Cite this