Show all publications

A Massively Parallel Neural Network Approach to Large-Scale Euclidean Traveling Salesman Problems

Open DOI PageDownload Bibliography in Open DocumentDownload Bibliography in HTMLDownload BibTeXDownload RISDownload Bibliographical Ontology (RDF)
Authors:
Details:
In Neurocomputing, vol. 240, pp. 137-151, 2017.
DOI: 10.1016/j.neucom.2017.02.041.
Abstract:
This paper proposes a parallel computation model for the self-organizing map (SOM) neural network applied to Euclidean traveling salesman problems (TSP). This model is intended for implementation on the graphics processing unit (GPU) platform. The Euclidean plane is partitioned into an appropriate number of cellular units, called cells, and each cell is responsible of a certain part of the data and network. Compared to existing GPU implementations of optimization metaheuristics, which are often based on data duplication or mixed sequential/parallel solving, the advantage of the proposed model is that it is decentralized and based on data decomposition. Designed for handling large-scale problems in a massively parallel way, the required computing resources grow linearly along the problem size. Experiments are conducted on 52 publicly available Euclidean TSP instances with up to 85,900 cities for the largest TSPLIB instance and 71,009 cities for the largest National TSP instance. Experimental results show that our GPU implementations of the proposed model run significantly faster than the currently best- performing neural network approaches, to obtain results of similar quality.
Keywords:
Neural network; Self-organizing map; Parallel computing; Graphics processing unit; Euclidean traveling salesman problem
Publication Category:
International journal with reading committee
Copyright 2010-2019 © Laboratoire Connaissance et Intelligence Artificielle Distribu√©es - Université Bourgogne Franche-Comté - Privacy policy