No Access

Collaborative Parallel Hybrid Metaheuristics on Graphics Processing Unit

Electrical and Computer Engineering Department, Royal Military College of Canada, P. O. Box 17000, Station Forces, Kingston, Ontario, K7K 7B4, Canada

Search for more papers by this author

Mohammed Tarbouchi

Electrical and Computer Engineering Department, Royal Military College of Canada, P. O. Box 17000, Station Forces, Kingston, Ontario, K7K 7B4, Canada

Search for more papers by this author

, and

Francis Okou

Electrical and Computer Engineering Department, Royal Military College of Canada, P. O. Box 17000, Station Forces, Kingston, Ontario, K7K 7B4, Canada

Search for more papers by this author

https://doi.org/10.1142/S1469026815500029Cited by:4 (Source: Crossref)

Abstract

Metaheuristics are nondeterministic optimization algorithms used to solve complex problems for which classic approaches are unsuitable. Despite their effectiveness, metaheuristics require considerable computational power and cannot easily be used in time critical applications. Fortunately, those algorithms are intrinsically parallel and have been implemented on shared memory systems and more recently on graphics processing units (GPUs). In this paper, we present highly efficient parallel implementations of the particle swarm optimization (PSO), the genetic algorithm (GA) and the simulated annealing (SA) algorithm on GPU using CUDA. Our approach exploits the parallelism at the solution level, follows an island model and allows for speedup up to 346× for different benchmark functions. Most importantly, we also present a strategy that uses the generalized island model to integrate multiple metaheuristics into a parallel hybrid solution adapted to the GPU. Our proposed solution uses OpenMP to heavily exploit the concurrent kernel execution feature of recent NVIDIA GPUs, allowing for the parallel execution of the different metaheuristics in an asynchronous manner. Asynchronous hybrid metaheuristics has been developed for multicore CPU, but never for GPU. The speedup offered by the GPU is far superior and key to the optimization of solutions to complex engineering problems.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

R. M. Ragnarsson , H. Stefánsson and E. I. Ásgeirsson , Eng. Risk Manage. 1 , 457 ( 2011 ) . Google Scholar
G. A. Sena, D. Megherbi and G. Isern, Future Gener. Comput. Syst. 17(4), 477 (2001). Crossref, Google Scholar
N. Melab, S. Cahon and E.-G. Talbi, J. Parallel Distrib. Comput. 66(8), 1052 (2006). Crossref, Google Scholar
D. Weyland, R. Montemanni and L. M. Gambardella, Metaheuristics GPUs 73(1), 74 (2013). Google Scholar
D. H. Wolpert and W. G. Macready, IEEE Trans. Evol. Comput. 1(1), 67 (1997). Crossref, Google Scholar
Y. Fu et al. , IEEE Trans. Syst. Man Cybern. Syst. 99 , 1 ( 2013 ) . Google Scholar
J. M. Cadenas, M. C. Garrido and E. Muñoz, A Hybrid system of nature inspired metaheuristics, Nature Inspired Cooperative Strategies for Optimization (NICSO 2007)129, eds. N. Krasnogoret al. (Springer, Berlin, 2008) pp. 95–104. Google Scholar
C. Li and S. Yang, Simulated Evolution and Learning 5361, eds. X. Liet al. (Springer, Berlin, 2008) pp. 180–189. Crossref, Google Scholar
D. Izzo, M. Ruciński and F. Biscani, Parallel Architectures and Bioinspired Algorithms 415, eds. F. Fernández de Vega, J. I. Hidalgo Pérez and J. Lanchares (Springer, Berlin, 2012) pp. 151–169. Crossref, Google Scholar
V. Roberge and M. Tarbouchi, World Sci. Eng. Acad. Soc. Trans. Comput. 11(6), 170 (2012). Google Scholar
V. Roberge and M. Tarbouchi, Int. J. Comput. Intell. Appl. 12(1), 1350006 (2013). Link, Google Scholar
V. Roberge and M. Tarbouchi, Efficient parallel particle swarm optimizers on GPU for real-time harmonic minimization in multilevel inverters, IECON 2012—38th Annual Conf. IEEE Industrial Electronics Society (2012) pp. 2275–2282. Google Scholar
M. Oisoet al., Accelerating steady-state genetic algorithms based on CUDA architecture, IEEE Congr. Evol. Comput. CEC 2011 (2011) pp. 687–692. Google Scholar
Y. Han, S. Roy and K. Chakraborty, Optimizing simulated annealing on GPU: A case study with IC floorplanning, Int. Symp. Quality Electronic Design (2011) pp. 1–7. Google Scholar
A. Munawaret al., Genet. Program. Evol. Mach. 10(4), 391 (2009). Crossref, Google Scholar
T. Van Luong, N. Melab and E. Talbi, Parallel hybrid evolutionary algorithms on GPU, IEEE Congr. Evolutionary Computation CEC 2010 (2010) p. 18. Google Scholar
J. Kennedy and R. Eberhart, Particle swarm optimization, Proc. 1995 IEEE Int. Conf. Neural Networks4 (1995) pp. 1942–1948. Google Scholar
M. Harris, Optimizing parallel reduction in CUDA, presented at the NVIDIA Developer Technology, 2007 . Google Scholar
J. H. Holland , Adaptation in Natural and Artificial Systems ( University of Michigan Press , 1975 ) . Google Scholar
E.-G. Talbi , Metaheuristics: From Design to Implementation , Wiley Series on Parallel and Distributed Computing ( Wiley , 2009 ) . Crossref, Google Scholar
S. Kirkpatrick, C. Gelatt and M. Vecchi, Science 220(4598), 671 (1983). Crossref, Google Scholar
M. Zbierski, Parallel Processing and Applied Mathematics 7203, eds. R. Wyrzykowskiet al. (Springer, Berlin, 2012) pp. 750–759. Crossref, Google Scholar
H. Li and C. Liu, Prediction of protein structures using GPU based simulated annealing, 11th Int. Conf. Machine Learning and Applications (ICMLA), 20121 (2012) pp. 630–633. Google Scholar
N. Safaei, D. Banjevic and A. K. S. Jardine, Simulated Annealing, ed. C. M. Tan (In-Tech, Croatia, 2008) pp. 27–48. Google Scholar