Hybrid Architectures for Evolutionary Computing Algorithms

摘要

This report documents the results of an in-house project aimed at identifying, developing and evaluating applications of evolutionary computing methods to hard optimization problem test cases on a single PC computer, a cluster of computers, and hardware FPGA platforms. We surveyed the evolutionary computing literature and chose to focus on the Genetic Algorithm (GA). We applied the GA to Non-Linear Coupled Ordinary Differential Equation (ODE) Parameterization, the DNA Code Word Library Problem, and the Networked Sensor Power Management Policy Problem. The first problem used an ODE biomodel for Antigen-Antibody binding, and we demonstrated speed-ups on the order of 100- 1000x by moving from interpreted languages to compiled C. We parallelized this C code using the Message Passing Interface (MPI), and demonstrated linear speed- ups on a cluster. A GA solution for the DNA Code Word Library Problem was also parallelized, and was faster than any algorithm found in the literature. We also developed hardware accelerated prototypes for the GA for this problem that achieved speed-ups on the order of 1000x. These prototypes used random and rank based selection, single point crossover mating, a declone operator, systolic arrays for the LLCS and Gibbs energy metrics, a multi-deme GA, and exhaustive search for producing locally optimum codes.