Show all publications

A Massive Parallel Cellular Gpu Implementation of Neural Network to Large Scale Euclidean Tsp

Download AwardOpen DOI PageDownload Bibliography in Open DocumentDownload Bibliography in HTMLDownload BibTeXDownload RISDownload Bibliographical Ontology (RDF)
Authors:
Details:
In Proc. of 12th Mexican International Conference on Artificial Intelligence, MICAI 2013, Mexico City, Mexico, November 24-30, 2013, Proceedings, Part II (Best Student Paper Award), Advances in Soft Computing and Its Applications, Lecture Notes in Computer Science, Volume 8266, pp.118-129, Best Paper Award, 2013.
DOI: 10.1007/978-3-642-45111-9_10.
Abstract:
This paper proposes a parallel model of the self- organizing map (SOM) neural network applied to the Euclidean traveling salesman problem (TSP) and intended for implementation on the graphics processing unit (GPU) platform. The plane is partitioned into an appropriate number of cellular units, that are each responsible of a certain part of the data and network. The advantage of the parallel algorithm is that it is decentralized and based on data decomposition, rather than based on data duplication, or mixed sequential/parallel solving, as often with GPU implementation of optimization metaheuristics. The processing units and the required memory are with linear increasing relationship to the problem size, which makes the model able to deal with very large scale problems in a massively parallel way. The approach is applied to Euclidean TSPLIB problems and National TSPs with up to 33708 cities on both GPU and CPU, and these two types of implementation are compared and discussed.
Keywords:
Neural network, Self-organizing map, Euclidean traveling salesman problem, Parallel cellular model, Graphics processing unit
Publication Category:
International conference with proceedings
Copyright 2010-2019 © Laboratoire Connaissance et Intelligence Artificielle Distribu√©es - Université Bourgogne Franche-Comté - Privacy policy