A Novel Genetic Algorithm Designed for Hardware Implementation

Authors: Zhenhuan Zhu, David Mulvaney, Vassilios Chouliaras

Abstract:

A new genetic algorithm, termed the 'optimum individual monogenetic genetic algorithm' (OIMGA), is presented whose properties have been deliberately designed to be well suited to hardware implementation. Specific design criteria were to ensure fast access to the individuals in the population, to keep the required silicon area for hardware implementation to a minimum and to incorporate flexibility in the structure for the targeting of a range of applications. The first two criteria are met by retaining only the current optimum individual, thereby guaranteeing a small memory requirement that can easily be stored in fast on-chip memory. Also, OIMGA can be easily reconfigured to allow the investigation of problems that normally warrant either large GA populations or individuals many genes in length. 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. The results given in this paper demonstrate that both the performance of OIMGA and its convergence time are superior to those of a range of existing hardware GA implementations.

Keywords: Genetic algorithms, genetic hardware, machinelearning.

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

References:

[1] 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.
[2] 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.
[3] 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.
[4] 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.
[5] Hauser, J.W. and Purdy, C.N., "Sensor data processing using genetic algorithms", IEEE Mid- West Symp. on Circuits and Systems, August 2000.
[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, pp.945-952.
[10] Matlab, http://www.mathworks.com/