A Synthesizable VHDL Coding of a Genetic Algorithm.

Stephen D. Scott, Sharad Seth, and Ashok Samal. A synthesizable VHDL coding of a genetic algorithm. In Lance Chambers, editor, The Practical Handbook of Genetic Algorithms, Volume III: Complex Coding Systems. CRC Press, Inc., 1998. ISBN: 0849325390. Includes detailed description of functionality of the HGA's VHDL code.
Abstract

Abstract

This chapter presents the HGA, a genetic algorithm written in VHDL and intended for a hardware implementation. Due to pipelining, parallelization, and no function call overhead, a hardware GA yields a significant speedup over a software GA, which is especially useful when the GA is used for real-time applications, e.g. disk scheduling and image registration. Since a general-purpose GA requires that the fitness function be easily changed, the hardware implementation must exploit the reprogrammability of certain types of field-programmable gate arrays (FPGAs), which are programmed via a bit pattern stored in a static RAM and are thus easily reconfigured.

After presenting some background on VHDL, this chapter takes the reader through the HGA's code. We then describe some applications of the HGA that are feasible given the state-of-the-art in FPGA technology and summarize some possible extensions of the design. Finally, we review some other work in hardware-based GAs.

Contents

1 Introduction
2 A VHDL Primer
- 2.1 Entities, Architectures and Processes
- 2.2 Finite State Machines
- 2.3 Data Types
- 2.4 Miscellany
3 The Design
- 3.1 The User-Controlled (Run-Time) Parameters
- 3.2 The VHDL Compile-Time Parameters
- 3.3 The Architecture
- 3.4 Inter-Module Communication
- 3.5 Component Modules
  - 3.5.1 Pseudorandom Number Generator (RNG)
  - 3.5.2 Shared Memory
  - 3.5.3 Memory Interface and Control Module (MIC)
  - 3.5.4 Population Sequencer (PS)
  - 3.5.5 Selection Module (SM)
  - 3.5.6 Crossover/Mutation Module (CMM)
  - 3.5.7 Fitness Module (FM)
- 3.6 Combining the Modules
4 Example Applications
- 4.1 A Mathematical Function
- 4.2 Logic Partitioning
- 4.3 Hypergraph Partitioning
- 4.4 Test Vector Generation
- 4.5 Traveling Salesman and Related Problems
- 4.6 Other NP-Complete Problems
5 Extensions of the Design
6 Summary and Related Work

To Stephen D. Scott's home page

Last modified 06 June 2000.