PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES

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. A sample of the nondeterministic polynomial time complete (NP-complete) 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 methods 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 computation. In order to get better results, cooling must be done very slowly; however, this significantly increases the computation time. To solve computation time drawback, General Purpose Computing on Graphical Processing Unit (GPGPU) based parallel programming approach is used in this study. Algorithms of the SA functions are redesigned and tailored for the parallel programming approach for massively parallel Graphical Processing Unit (GPU) stream processors. The verified simulation results for various size of TSP shows that a parallel SA algorithm performance can speed computation time up to 7.8 times faster than the classic sequential algorithm performance by using simple tools in MATLAB programming environment

PDF

___

[1] Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, ISBN 0201157675, 1989.

[2] Luke, S., Second edition, available at http://cs.gmu.edu/sean/book/metaheuristics[last reached 10.12.2017]

[3] Talbi, E- Metaheuristics: from Design to Implementation, 0470278587, 2009.

[4] Handbook of Springer, International Series in Operations Research & Management Science, ISBN 978-1-4020-7263-5, 2003.

[5] Garey, MR., Computers and Intractability: A Guide to the Theory of N.P. Completeness, Freeman, New York, 1979.

[6] Lawler, E., Holt Rinehart and Winston, New York, 1976.

[7] Computational complexity Gass, SI. and Harris, CM. (eds), Encyclopedia of Operations Research and Management Science, 2nd edn. Kluwer, Boston, pp 119 122, 2000.

[8] al on computational Interfaces 32(3), pp: 30 61, 2002.

[9] Traveling sale 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 labeling with GPUs and 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/softwaretechnologies/stream [last reached 08.12.2017]

[14] CUDA Compute Unified Device A NVIDIA Press, 2008.

[15] NVIDIA OpenCL Programming Guide for the 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/productdetail/productivity_features/gpu-acceleration/gpuacceleration, [last reached 06.11.2017]

[18] TSPLIB, Gerhard Reinelt U 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] ," 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] www.labmath.uqam.ca/GPUmat_User_Guide_0.27.pd f, Version 0.27, [last reached 06.11.2017]