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 m...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Turkish Air Force Academy
2018-01-01
|
| Series: | Havacılık ve Uzay Teknolojileri Dergisi |
| Subjects: | |
| Online Access: | http://www.jast.hho.edu.tr/JAST/index.php/JAST/article/view/285/261 |
| _version_ | 1797922224917708800 |
|---|---|
| author | Omer Cetin |
| author_facet | Omer Cetin |
| author_sort | Omer Cetin |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T14:28:06Z |
| format | Article |
| id | doaj.art-167d2f240b0d400a8522d81b68f78ba9 |
| institution | Directory Open Access Journal |
| issn | 1304-0448 1304-0448 |
| language | English |
| last_indexed | 2024-04-10T14:28:06Z |
| publishDate | 2018-01-01 |
| publisher | Turkish Air Force Academy |
| record_format | Article |
| series | Havacılık ve Uzay Teknolojileri Dergisi |
| spelling | doaj.art-167d2f240b0d400a8522d81b68f78ba92023-02-15T16:08:57ZengTurkish Air Force AcademyHavacılık ve Uzay Teknolojileri Dergisi1304-04481304-04482018-01-011117585PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURESOmer Cetin0Hezârfen Aeronautics and Space Technologies InstituteMetaheuristic 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.http://www.jast.hho.edu.tr/JAST/index.php/JAST/article/view/285/261MetaheuristicParallel ProgrammingSimulated AnnealingGPGPU |
| spellingShingle | Omer Cetin PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES Havacılık ve Uzay Teknolojileri Dergisi Metaheuristic Parallel Programming Simulated Annealing GPGPU |
| title | PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES |
| title_full | PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES |
| title_fullStr | PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES |
| title_full_unstemmed | PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES |
| title_short | PARALLELIZING SIMULATED ANNEALING ALGORITHM FOR TSP ON MASSIVELY PARALLEL ARCHITECTURES |
| title_sort | parallelizing simulated annealing algorithm for tsp on massively parallel architectures |
| topic | Metaheuristic Parallel Programming Simulated Annealing GPGPU |
| url | http://www.jast.hho.edu.tr/JAST/index.php/JAST/article/view/285/261 |
| work_keys_str_mv | AT omercetin parallelizingsimulatedannealingalgorithmfortsponmassivelyparallelarchitectures |