The Hardware Implementation of a Novel Genetic Algorithm

This paper presents a novel genetic algorithm, termed the Optimum Individual Monogenetic Algorithm (OIMGA) and describes its hardware implementation. As the monogenetic strategy retains only the optimum individual, the memory requirement is dramatically reduced and no crossover circuitry is needed, thereby ensuring the requisite silicon area is kept to a minimum. Consequently, depending on application requirements, OIMGA allows the investigation of solutions that warrant either larger GA populations or individuals of greater length. The results given in this paper demonstrate that both the performance of OIMGA and its convergence time are superior to those of existing hardware GA implementations. Local convergence is achieved in OIMGA by retaining elite individuals, while population diversity is ensured by continually searching for the best individuals in fresh regions of the search space.

Authors:

• Zhenhuan Zhu
• David Mulvaney
• Vassilios Chouliaras

Keywords:

• Genetic algorithms
• hardware-based machinelearning.

References:

[1] Sharawi, M.S., Quinlan, J. and Abdel-Aty-Zohdy, H.S., "A hardware
implementation of genetic algorithms for measurement
characterization", IEEE 9th International Conference of Electronics,
Circuits, and Systems, Dubrovnik, Croatia, 3, 2002, pp.1267-1270.
[2] Hauser, J.W. and Purdy, C.N., "Sensor data processing using genetic
algorithms", IEEE Mid- West Symp. on Circuits and Systems, August
2000.
[3] Aporntewan, C. and Chongstitvatana, P., "A hardware implementation
of the compact genetic algorithm", 2001 IEEE Congress on
Evolutionary Computation, Seoul, Korea, 2001, pp.27-30.
[4] Wakabayashi, S., Koide, T., Toshine, N., Yamane, M. and Ueno, H.,
"Genetic algorithm accelerator GAA-II", Proc. Asia and South Pacific
Design Automation Conference, Yokohama, Japan, January 2000.
[5] Scott, S.D., Samal, A. and Seth, S., "HGA: A hardware-based genetic
algorithm", Proc. 3rd ACM/SIGDA Int. Symp. on FPGAs, 1995, pp.53-
59.
[6] Ramamurthy, P. and Vasanth, J., "VLSI implementation of genetic
algorithms" (under review).
[7] Radolph, G., "Convergence analysis of canonical genetic algorithms",
IEEE Trans. Neural Networks, 5(1), 1994, pp.96-101.
[8] Li, J. and Wang, S., "Optimum family genetic algorithm", Journal of
Xi-an Jiao Tong University, 38, Jan 2004.
[9] Zhang, L. and Zhang, B., "Research on the mechanism of genetic
algorithms", Journal of Software, 11(7), 2000.
[10] Matlab, http://www.mathworks.com/.