A Novel Genetic Algorithm Designed for Hardware Implementation

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.

• Zhenhuan Zhu
• David Mulvaney
• Vassilios Chouliaras

• Genetic algorithms
• genetic hardware
• machinelearning.

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