Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/7A1B060C-D4A2-42DA-948B-3544EBAF3AEF | ||
| Year | 2009 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | M. Vavouras, K. Papadimitriou, I. Papaefstathiou, "Implementation of a genetic algorithm on a virtex-ii pro FPGA," in ACM/SIGDA international symposium on Field programmable gate arrays, 2009, pp. 287-287. doi: 10.1145/1508128.1508206 https://doi.org/10.1145/1508128.1508206 | ||
| Appears in Collections |
This paper presents the implementation of a Genetic Algorithm on a XUPV2P platform with a Virtex-II Pro FPGA. A Genetic Algorithm (GA) is a search technique finding exact or approximate solutions to optimization and search problems. It is a computer simulation approach in which a population of abstract representations of candidate solutions to an optimization problem evolves toward better solutions. The aim is the optimization of a given function, called fitness function, which is evaluated upon the initial population as well as upon the solutions after successive generations. The motivation for implementing GAs in hardware stems from the fact that they are very CPU intensive while they are also intrinsically parallel algorithms and the basic operations of a GA can execute in a pipelining fashion. Our architecture incorporates a Power PC, and built-in hardcore resources like multiplier blocks and BRAMs in order to create an efficient hardware-based genetic algorithm. We have fine tuned the architecture so as to be more parallel, and added complex fitness functions. The design executes on 100 MHz and although complex in logic, it has low silicon requirements as it utilizes 16% slices, 7% BRAMs and 11% multiplier blocks, plus the Power PC of the XC2VP30 FPGA. The result is a functional prototype on which experiments for a range of different genetic parameters can be conducted. We explore the GA's behavior with real-world experiments for different fitness functions and different number of generations. Our design is the first single-chip fully embedded approach that optimizes six fitness functions, which is more than any other proposed solution, while its current implementation supports populations of up to 32 members. The experiments show that our system outperforms in terms of execution time the existing and proposed hardware systems from 23% up to 5895%.
Copyright © DIAS 2013
