Proposal of Flexible Implementation of Genetic Algorithms on FPGAs

Tatsuhiro TACHIBANA  Yoshihiro MURATA  Naoki SHIBATA  Keiichi YASUMOTO  Minoru ITO 

Publication
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)  Vol.J89-D  No.6  pp.1182-1191
Publication Date: 2006/06/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
Type of Manuscript: Special Section PAPER (Special Issue Reconfigurable Systems)
Category: 
Keyword: 
genetic algorithm,  FPGA,  hardware design automation,  knapsack problem,  traveling salesman problem, 

Full Text(in Japanese): PDF(369.1KB)

Summary: 
Genetic Algorithm (GA) can be used for various applications including complex computations such as combinatory optimization problems. Such GA applications can be available to information appliances with poor resources by implementing them on dedicated hardware chips like FPGA. In this paper, we propose a method for efficiently design and implement GA applications on FPGA. Our method consists mainly of a parallel and pipelined architecture for various GA applications and a model to predict the size of the synthesized hardware circuits for various parameter values such as the size of the problem and the number of parallel pipelines. To facilitate hardware design, we have implemented two tools. The first tool uses a 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 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 models predict the sizes of the synthesized circuits accurately enough for practical use.