A scalable array for Cellular Genetic Algorithms: TSP as case study
- 1 December 2012
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Cellular Genetic Algorithms (cGAs) exhibit a natural parallelism that makes them interesting candidates for hardware implementation, as several processing elements can operate simultaneously on subpopulations shared among them. This paper presents a scalable architecture for a cGA, suitable for FPGA implementation. A regular array of custom designed processing elements (PEs) works on a population of solutions that is spread into dual-port memory blocks locally shared by adjacent PEs. A travelling salesman problem with 150 cities was used to verify the implementation of the proposed cGA on a Virtex-6 FPGA, using a population of 128 solutions with different levels of parallelism (1, 4, 16 and 64 PEs). Results have shown that an increase of the number of PEs does not degrade the quality of the convergence of the iterative process, and that the throughput increases almost linearly with the number of PEs. Comparing with a software implementation running in a PC, the cGA with 64 PEs has shown a 45x speedup.Keywords
This publication has 11 references indexed in Scilit:
- Advanced genetic algorithm to solve MINLP problems over GPUPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Parallel Genetic AlgorithmsPublished by Springer Science and Business Media LLC ,2011
- FPGA Based Engines for Genetic and Memetic AlgorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- A multi-GPU implementation of a Cellular Genetic AlgorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Customizable FPGA IP Core Implementation of a General-Purpose Genetic Algorithm EngineIEEE Transactions on Evolutionary Computation, 2009
- DFS algorithm with ranking based on Genetic Algorithm in UHF portable systemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Image Matching for Workpiece Based on Genetic AlgorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- General Architecture for Hardware Implementation of Genetic AlgorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- FPGA implementation of neighborhood-of-four cellular automata random number generatorsPublished by Association for Computing Machinery (ACM) ,2002
- Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and OperatorsArtificial Intelligence Review, 1999