Show all publications

Massive Parallel Self-Organizing Map and 2-Opt on Gpu to Large Scale Tsp

Open DOI PageDownload Bibliography in Open DocumentDownload Bibliography in HTMLDownload BibTeXDownload RISDownload Bibliographical Ontology (RDF)
Authors:
Details:
In Proc. of International Work-Conference on Artificial Neural Networks. Lecture Notes in Computer Science LNCS, Volume 10305, Springer, Cham, 2017: 471-482., pp. 471-482, Cádiz, Espagne, 2017.
ISBN 978-3-319-59152-0
DOI: 10.1007/978-3-319-59153-7_41.
Abstract:
This paper proposes a platform both for parallelism of self-organizing map (SOM) and the 2-opt algorithm to large scale 2-Dimensional Euclidean traveling salesman problems(TSP). Given a TSP tour with N input point, this platform makes these two algorithms working in a massively parallel way on graphical processing unit (GPU). Advantages of this platform include its flexibly topology preserving network, its fine parallel granularity and it allows maximum (N/3) 2-opt optimization moves to be executed with O(N) time complexity within one tour orientation as well as keep the tour valid. The parallel technique follows data decomposition and decentralized control. We test this optimization method on large TSPLIB instances, experiments show that the acceleration factor we obtained makes the proposed method competitive, and allows for further increasing for very large TSP instances along with the quantity increase of physical cores in GPU systems.
Keywords:
irregular topology, massive parallel 2-opt, SOM, doubly linked network, local spiral search, TSP
Publication Category:
International conference with proceedings
Copyright 2010-2019 © Laboratoire Connaissance et Intelligence Artificielle Distribuées - Université Bourgogne Franche-Comté - Privacy policy