The Hardware Implementation of a Novel Genetic Algorithm

Authors: Zhenhuan Zhu, David Mulvaney, Vassilios Chouliaras

Abstract:

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.

Keywords: Genetic algorithms, hardware-based machinelearning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1074591

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/.