Accelerating the Shuffled Frog Leaping algorithm by parallel implementations in FPGAs

摘要

Meta-heuristics are efficient techniques for solving large scale optimization problems in which traditional mathematical techniques are impractical or provide suboptimal solutions. The Shuffled Frog Leaping algorithm (SFLA) is a stochastic iterative method, bio-inspired on the memetic evolution of a group of frogs when seeking for food, which combines the social behavior-based of the particle swarm optimization technique (PSO) and the global information exchange of memetic algorithms. However, the SFLA algorithm suffers on large execution times, being this problem clearly evident when solving complex optimization problems for embedded applications. This drawback can be overcome by exploiting the parallel capabilities of the SFLA. This paper proposes a hardware parallel implementation of the SFLA algorithm (HPSFLA) using FPGAs (Field Programmable gate Arrays) and the efficient floating-point arithmetic. The proposed architecture allows the SFLA to improve the functionality of the algorithm as well as to decrease the execution times by implementing parallel frogs and parallel memeplexes. Three well-known benchmark problems have been used to validate the implemented algorithm and simulation results demonstrate that the HPSFLA speeds-up by factors of 362, 727 and 211 a C-code implementation using an embedded microprocessor for the Sphere, Rastrigin and Rosenbrock benchmarks problems, respectively. Synthesis, simulation and execution time results demonstrate the effectiveness of the proposed HPSFLA architecture for embedded optimization systems.