PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES

  • Omer Cetin Hezârfen Aeronautics and Space Technologies Institute

Abstract

Metaheuristic is a computational method that brings a problem to the best possible state by iteratively to improve a candidate solution according to a given quality measure. Even when all of the problem parameters are known and the objective function is linear, there may be many local optima which means that may not be an appropriate representation. Such problems are labeled as non-deterministic-polynomial-time-complete. An example of the NP-complicated problem is the Travel Salesman Problem (TSP), which leads to an investigation where the search area of ​​candidate solutions grows exponentially as the size of the problem increases, and the most appropriate solution may not be feasible. Several well-known classical methods are known for finding the near optimal solution using linear and nonlinear programming for TSPs. One of the distinguished method in literature is Simulated Annealing (SA) and it is not based on any of the conventional optimization techniques, but based on heuristic processes derived from the annealing process of metals. One of the biggest disadvantages for SA is the time consumption of calculation. In order to get better results, cooling must be done very slowly; however this significantly increases the calculation time. To solve computation time drawback, GPGPU based parallel programming approach are used in this study. Algorithms of the SA functions are redesigned and tailored for the parallel programming approach for massively parallel GPU stream processors. The validated simulation results for various size of TSP shows that a parallel SA algorithm performance can speed calculation time up to 7.8 times faster than the classic sequential algorithm performance by using simple tools in MATLAB programming environment.

References

[1] Goldberg, D.E. “Genetic Algorithms in Search, Optimization and Machine Learning”, Kluwer Academic Publishers, ISBN 0201157675, 1989.
[2] Luke, S., “Essentials of Metaheuristics”, Second edition, available at http://cs.gmu.edu/sean/book/metaheuristics [last reached 10.12.2017]
[3] Talbi, E-G., “Metaheuristics: from Design to Implementation”, Wiley, ISBN 0470278587, 2009.
[4] Glover, F., Kochenberger, G.A. “Handbook of metaheuristics”, Springer, International Series in Operations Research & Management Science, ISBN 978-1-4020-7263-5, 2003.
[5] Garey, MR. and Johnson, DS., “Computers and Intractability: A Guide to the Theory of N.P. Completeness”, Freeman, New York, 1979.
[6] Lawler, E., “Combinatorial Optimization”, Holt Rinehart and Winston, New York, 1976.
[7] Hall, L., “Computational complexity”, Gass, SI. and Harris, CM. (eds), Encyclopedia of Operations Research and Management Science, 2nd edn. Kluwer, Boston, pp 119–122, 2000.
[8] Tovey, CA., “Tutorial on computational complexity”, Interfaces 32(3), pp: 30–61, 2002.
[9] Hoffman, KL. and Padberg, M., “Traveling salesman problem”,Gass, SI. and Harris, CM. (eds). Encyclopedia of Operations Research and Management Science, 2nd edn. Kluwer, Boston, pp 849–853, 2000.
[10] T.R. Halfhill; ‘Parallel processing with CUDA’ Microprocessor Report, Nvidia Press, 2008.
[11] K.A. Hawick, A. Leista, and D.P. Playnea; ‘Parallel graph component labelling with GPUs and CUDA’ Parallel Computing Systems and Applications Journal, vol. 36, issue 12, pp: 655-678, 2010.
[12] NVIDIA Compute Unified Device Architecture Programming Technology (CUDA), https://developer.nvidia.com/cuda-zone [last reached 10.12.2017]
[13] ATI Stream Technology, http://www.amd.com/en-us/innovations/software-technologies/stream [last reached 08.12.2017]
[14] NVIDIA ‘CUDA Compute Unified Device Architecture, Programming Guide’, NVIDIA Press, 2008.
[15] NVIDIA ‘OpenCL Programming Guide for the CUDA Architecture’ Version 3.1, NVIDIA Press, 2010.
[16] D. Goldberg; ‘What Every Computer Scientist Should Know About Floating-Point Arithmetic’, ACM Computing Surveys, Volume 23 Issue 1, 1991.
[17] GPU Acceleration, FEKO: Run-time for the MoM solution phase of solving the system of linear equations using different CPUs and GPUs (NVIDIA Graphics Cards), http://www.feko.info/product-detail/productivity_features/gpu-acceleration/gpu-acceleration, [last reached 06.11.2017]
[18] TSPLIB, Gerhard Reinelt Universität Heidelberg Institut für Informatik, https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/; [last reached 02.08.2017]
[19] Choong A., Beidas R., Zhu J.; “Parallelizing Simulated Annealing-Based Placement using GPGPU” IEEE 2010 International Conference on Field Programmable Logic and Applications, Milano, ITALY, Aug. 31st - Sep. 2nd, 2010.
[20] Borovska P., “Parallel Metaheuristics" European Thematic Network, Thesis in Electrical and Computer Engineering Technical University of Sofia, Summer School on Intelligent Systems July, 2-6, 2007
[21] Luong, T.V., Melab, N. and Talbi, E; “Metaheuristics on GPU - DOLPHIN Project”; INRIA, CNRS Supported Scientific Research, Center de Recherce Lille, Nord Europe, 2011.
[22] “GPUmat User Guide”, www.labmath.uqam.ca/GPUmat_User_Guide_0.27.pdf, Version 0.27, [last reached 06.11.2017]
Published
2018-01-26
How to Cite
CETIN, Omer. PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES. Journal of Aeronautics and Space Technologies, [S.l.], v. 11, n. 1, p. 75-85, jan. 2018. ISSN 2148-1059. Available at: <http://www.jast.hho.edu.tr/JAST/index.php/JAST/article/view/285>. Date accessed: 20 feb. 2018.
Section
Articles