caa a22 4500 605469008 CHVBK 20210128100319.0 cr unu---uuuuu 210128e20150701xx s 000 0 eng 10.1007/s00500-014-1363-0 doi (NATIONALLICENCE)springer-10.1007/s00500-014-1363-0 Systolic genetic search, a systolic computing-based metaheuristic [Elektronische Daten] [Martín Pedemonte, Francisco Luna, Enrique Alba] In this paper, we propose a new parallel optimization algorithm that combines ideas from the fields of metaheuristics and Systolic Computing. The algorithm, called Systolic Genetic Search (SGS), is designed to explicitly exploit the high degree of parallelism available in modern Graphics Processing Unit (GPU) architectures. In SGS, solutions circulate synchronously through a grid of processing cells, which apply adapted evolutionary operators on their inputs to compute their outputs that are then ejected from the cells and continue moving through the grid. Four different variants of SGS are experimentally studied for solving two classical benchmarking problems and a real-world application. An extensive experimental analysis, which considered several instances for each problem, shows that three of the SGS variants designed are highly effective since they can obtain the optimal solution in almost every execution for the instances and problems studied, as well as they outperform a Random Search (sanity check) and two Genetic Algorithms. The parallel implementation on GPU of the proposed algorithm has achieved a high performance obtaining runtime reductions from the sequential implementation that, depending on the instance considered, can arrive to around a hundred times, and have also exhibited a good scalability behavior when solving highly dimensional problem instances. Springer-Verlag Berlin Heidelberg, 2014 Systolic genetic search nationallicence Evolutionary algorithms nationallicence Systolic computing nationallicence Parallel computing nationallicence Graphics processing units nationallicence CUDA nationallicence GPGPU nationallicence Pedemonte Martín Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565, 11300, Montevideo, Uruguay aut Luna Francisco Depto. de Ingeniería de Sistemas Informáticos y Telemáticos, Centro Universitario de Mérida, Universidad de Extremadura, Santa Teresa de Jornet, 28, 06800, Mérida, Spain aut Alba Enrique Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, E.T.S. Ingeniería Informática, Campus de Teatinos, 29071, Málaga, Spain aut Soft Computing Springer Berlin Heidelberg 19/7(2015-07-01), 1779-1801 1432-7643 19:7<1779 2015 19 500 https://doi.org/10.1007/s00500-014-1363-0 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00500-014-1363-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Pedemonte Martín Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565, 11300, Montevideo, Uruguay aut NATIONALLICENCE 700 1- Luna Francisco Depto. de Ingeniería de Sistemas Informáticos y Telemáticos, Centro Universitario de Mérida, Universidad de Extremadura, Santa Teresa de Jornet, 28, 06800, Mérida, Spain aut NATIONALLICENCE 700 1- Alba Enrique Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, E.T.S. Ingeniería Informática, Campus de Teatinos, 29071, Málaga, Spain aut NATIONALLICENCE 773 0- Soft Computing Springer Berlin Heidelberg 19/7(2015-07-01), 1779-1801 1432-7643 19:7<1779 2015 19 500