Multi-GAP: parallel and distributed genetic algorithms in VLSI

Abstract

The advance of VLSI technologies enables us to implement genetic algorithms (GA) in VLSI hardware to achieve drastic performance improvement. The paper presents a VLSI hardware design for GA, GAP (Genetic Algorithm Processor), and its extensions for parallel and distributed GA. The basic architecture of GAP employs the steady-state GA, and introduces the simplified tournament selection scheme. This architecture enabled us to implement two-level parallelization of parallel GA (fine-grained parallelism) and distributed GA (coarse-grained parallelism). We implemented the design of GAP, and have evaluated it by logic simulation and logic synthesis. Our examples for evaluation include a data partitioning problem which is one of the most complex ones ever applied for GA-VLSIs. Our prototype implementations and experiments prove that the basic architecture of GAP facilitates two-level parallelization of parallel GA and distributed GA, which is effective in performance and convergence improvement.