Hardware Genetic Algorithm Optimization by Critical Path Analysis using a Custom VLSI Architecture

Authors

  • Farouk Smith Department of Mechatronics Nelson Mandela Metropolitan University
  • Allan Edward van den Berg Department of Mechatronics Nelson Mandela Metropolitan University

DOI:

https://doi.org/10.18489/sacj.v56i1.275

Keywords:

FPGA, Genetic Algorithm, Virtual Reconfigurable Circuit, Evolutionary Hardware, Logic Element, Digital Circuit, Cartesian Genetic Programming, Hardware Chromosome, Intrinsic Evolution, Off-Chip Evolution, On-Chip Evolution.

Abstract

This paper propose a Virtual-Field Programmable Gate Array (V-FPGA) architecture that allows direct access to its configuration bits to facilitate hardware evolution, thereby allowing any combinational or sequential digital circuit to be realized. By using the V-FPGA, this paper investigates two possible ways of making evolutionary hardware systems more scalable: by optimizing the system’s genetic algorithm (GA); and by decomposing the solution circuit into smaller, evolvable sub-circuits. GA optimization is done by: omitting a canonical GA’s crossover operator (i.e. by using a 1+λ algorithm); applying evolution constraints; and optimizing the fitness function. A noteworthy contribution this research has made is the in-depth analysis of the phenotypes’ CPs. Through analyzing the CPs, it has been shown that a great amount of insight can be gained into a phenotype’s fitness. We found that as the number of columns in the Cartesian Genetic Programming array increases, so the likelihood of an external output being placed in the column decreases. Furthermore, the number of used LEs per column also substantially decreases per added column. Finally, we demonstrated the evolution of a state-decomposed control circuit. It was shown that the evolution of each state’s sub-circuit was possible, and suggest that modular evolution can be a successful tool when dealing with scalability.

Downloads

Published

2015-07-11

Issue

Section

Research Papers (general)