A Cellular Genetic Algorithm Architecture for FPGAs

Abstract

This paper proposes a new architecture of a cellular genetic algorithm (cGA) suitable for FPGA implementation. By spreading the algorithm solutions (population) into subpopulations accessed from different processing nodes, a scalable array of processing elements can be run in parallel. Each subpopulation is saved in a dual-port memory block (BRAM) so that two different processing elements can share the same information. Preliminary results of a simple GA implementation for the travelling salesman problem (TSP) have shown that the problem size allocated for the algorithm is mainly constrained by the available memory and not by the other logic resources. Simulations performed to evaluate the effectiveness of the cGA as an optimization procedure have shown that this cGA architecture does not degrade the quality of the final solution and the performance almost linearly increases with the number of processing nodes.