NEIGHBORHOOD STRUCTURES FOR GPU-BASED LOCAL SEARCH ALGORITHMS
Abstract
Local search algorithms are powerful heuristics for solving computationally hard problems in science and industry. In these methods, designing neighborhood operators to explore large promising regions of the search space may improve the quality of the obtained solutions at the expense of a high-cost computation process. As a consequence, the use of GPU computing provides an efficient way to speed up the search. However, designing applications on a GPU is still complex and many issues have to be faced. We provide a methodology to design and implement different neighborhood structures for LS algorithms on a GPU. The work has been evaluated for binary problems and the obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.
References
-
E.-G. Talbi , From design to implementation ( Wiley , 2009 ) . Google Scholar - INFORMS Journal on Computing 19(3), 416 (2007), DOI: 10.1287/ijoc.1060.0193. Crossref, ISI, Google Scholar
- J. Parallel Distrib. Comput. 68(10), 1389 (2008), DOI: 10.1016/j.jpdc.2008.05.011. Crossref, ISI, Google Scholar
J.-M. Li , An efficient fine-grained parallel genetic algorithm based on gpu-accelerated, Network and Parallel Computing Workshops, 2007. NPC Workshops. IFIP International Conference pp. 855–862, http://dx.doi.org/10.1109/NPC.2007.108. Google ScholarD. M. Chitty , A data parallel approach to genetic programming using programmable graphics hardware, GECCO pp. 1566–1573. Google Scholar- Parallel Evolutionary Computations 133 (2006), DOI: 10.1007/3-540-32839-4_7. Google Scholar
- IEEE Intelligent Systems 22(2), 69 (2007). Crossref, Google Scholar
D. Pointcheval , A new identification scheme based on the perceptrons problem, EUROCRYPT pp. 319–328. Google Scholar- NVIDIA, CUDA Programming Guide Version 2.3, 2010 . Google Scholar
D. A. Bader and V. Sachdeva , A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic, ISCA PDCS pp. 41–48. Google Scholar- ACM Queue 6(2), 40 (2008), DOI: 10.1145/1365490.1365500. Crossref, Google Scholar
L. R. Knudsen and W. Meier , Cryptanalysis of an identification scheme based on the permuted perceptron problem, EUROCRYPT pp. 363–374. Google Scholar- Parallel Computing 17(4-5), 443 (1991), DOI: 10.1016/S0167-8191(05)80147-4. Crossref, ISI, Google Scholar
- J. Heuristics 10(3), 357 (2004), DOI: 10.1023/B:HEUR.0000026900.92269.ec. Crossref, ISI, Google Scholar


