FPGA Based Engines for Genetic and Memetic Algorithms

Abstract

Memetic algorithms are highly efficient procedures to solve complex optimization problems. They combine strengths of well known metaheuristics, like the genetic algorithm (GA), with local search (LS) procedures to intensify the search. This paper proposes a computing architecture to support the execution of a memetic algorithm (MA). The Travelling Salesman Problem is elected as a case study for this work since it is a representative problem in the field of graph theory. A GA implementation in a Virtex 4 FPGA device is shown for solving a TSP with 1002 cities at a frequency of 96MHz. The proposed architecture is based in a pipeline capable of processing 1 city per clock cycle. New ideas are discussed on how to implement a LS on a GA solution by exploiting the run-time reconfiguration features of modern FPGAs.