Stephen D. Scott. HGA: A Hardware-Based Genetic Algorithm. Master's thesis, University of Nebraska, August 1994. Also in technical report UNL-CSE-94-020, University of Nebraska.
Abstract
445Kb compressed PostScript
Slides:

Abstract

A genetic algorithm (GA) is a robust problem-solving method based on natural selection. Genetic algorithms have been successful in many hard optimization problems. Simple operations are performed on a population of solutions, not just from a single point, using a ``safety in numbers'' strategy which reduces the risk of reaching a false peak. The core GA operators--reproduction, crossover and mutation--involve only random number generation, copying, and partial string exchange. Thus, GAs are simple to implement and difficult to trick [2].

Because of its simplicity, it would seem natural to implement a GA in hardware. Hardware's speed advantage and its ability to parallelize offer great rewards to genetic algorithms. Speedups of 1-3 orders of magnitude have been observed when frequently used software routines were implemented in hardware by way of reprogrammable field-programmable gate arrays (FPGAs) [1]. FPGAs were used because they are reprogrammable and thus can be easily changed to fit the current application. This reprogrammability is essential in a general-purpose GA engine because certain GA modules require changeability (e.g. the function to be optimized by the GA). Thus a hardware-based GA is both feasible and desirable.

Little work has been done in hardware-based GAs. A fully functional hardware-based genetic algorithm (the HGA) is presented in this thesis. It was designed to act as a coprocessor with the CPU of a PC. The user programs the FPGAs which implement the function to be optimized. Other GA parameters may also be specified by the user.

Simulation results and performance analyses of the HGA are presented. A prototype HGA is described and compared to a similar GA implemented in software. In the simple tests, the prototype took less than 6% as many clock cycles to run as the software-based GA. Finally, other design ideas are suggested which should improve the HGA's performance. These improvements could realistically make the HGA 2-3 orders of magnitude faster than the software-based GA.

1
P. M. Athanas and H. F. Silverman. Processor reconfiguration through instruction-set metamorphosis. IEEE Computer, 26(3):11-18, March 1993.

2
D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, Incorporated, Reading, Massachusetts, 1989.

To Stephen D. Scott's home page

Last modified 06 June 2000.