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 |
| Summary: | 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. |
|---|---|
| ISSN: | 1304-0448 1304-0448 |