FPGA based engines for genetic and memetic algorithms

• Type: Article in International Conference Proceedings Book
• Date: 2010

Authors

Santos, PV (Author) Other; José Carlos Alves (Author) FEUP

Conference proceedings International

Title: Proceedings - 2010 International Conference on Field Programmable Logic and Applications, FPL 2010

Pages: 251-254

20th International Conference on Field Programmable Logic and Applications, FPL 2010

Milano, 31 August 2010 through 2 September 2010

Indexing

Scopus - 3 Citations

Other information

Authenticus ID: P-007-XDN

DOI: 10.1109/fpl.2010.58

Abstract (EN): 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 runtime reconfiguration features of modern FPGAs. © 2010 IEEE.

Language: English

Type (Professor's evaluation): Scientific