Genetic Programming for Signal Processing Algorithm Development, 16-R9599Printer Friendly Version
Inclusive Dates: 01/10/06 Current
Background - Signal recognition and identification is a key technology area for the Signal Exploitation and Geolocation Division. The goal of the project is to investigate whether Genetic Programming (GP) is capable of automatically discovering digital signal processing (DSP) algorithms. While GP is similar to Genetic Algorithm (GA) technologies that have been successfully employed by the division to develop optimum antenna placements, GP is a relatively new field of artificial intelligence that is distinct from GA. The principal difference is that GP produces directly executable programs.
Approach - Currently available GP Environments provide little or no support for the vector and math operations typically encountered in DSP applications. We are pursuing several innovative ideas to address this shortcoming. First, we developed a new GP language patterned after FORTH, which has a very simple syntactical structure. Unlike FORTH, our language (which we call FIFTH) operates using a single data stack that can hold multiple data types. The stack holds containers, and a single container may represent a scalar value, a vector, or a matrix. To facilitate evaluation of random programs, language functions that operate on the stack are designed to "do something reasonable" rather than failing when errors are encountered. The language also includes high-level, DSP-specific functions like Fourier transforms. Our second innovation is a linear program representation structure. Most GP researchers use a tree-based structure to simplify evolutionary procedures such as mutation and crossover. However, tree-based representations are restricted in their ability to include program structures such as branching and looping, which we believe will be essential for DSP algorithms. Our linear representation easily accommodates these as it can track location-dependant signatures through a program to account for data stack depth, branch depth, and loop depth, including recursion and nesting. The complete Genetic Programming Environment for FIFTH also includes a Distributed Evaluation Controller and a Distributed Program Interpreter that enable the evolutionary algorithm to use multiple distributed resources to speed up the evaluation of each generation.
Accomplishments - At present, we are completing the genetic manipulation operations (mutation and crossover) and will shortly begin running experiments to assess the viability of our approach.