Abstract
Genetic Algorithms (GA) can be used for various applications including complex computations such as combinatory optimization problems. Such GA applications are desired to be available to information appliances with poor resources by implementing them on dedicated hardware chips like FPGA. In this paper, we propose a method to efficiently design and implement GA applications on FPGA. Our method consists mainly of a parallel and pipelined architecture suitable for various GA applications and a model to predict the size of the synthesized hardware circuits from various parameter values such as the size of the problem and the number of parallel pipelines. In order to facilitate hardware design, we have implemented two tools. The first tool uses our prediction model and calculates parameter values with which the hardware circuits can be synthesized on a specified FPGA device. The second tool generates the RT level VHDL description when the parameter values are given. In order to show efficiency of the proposed method, we have applied our method to the Knapsack Problem and Traveling Salesman Problem. As a result, we have confirmed that the circuits synthesized with our tools achieve high performance on gate level simulation and low power consumption, and that our prediction model predicts the sizes of the synthesized circuits accurately enough for practical use. Β©2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(13): 28β38, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20779