GA for evolution of scalable circuits

We evolve a population of individuals carrying a genome coding for a small (bounded) number of SLBs by tournament selection. We don’t compare the two contesters by exhaustively testing their performance on all possible multiplications of a given bit length. Instead, each individual genome also codes for a small (bounded) number of test problems (16 turned out to be sufficient), whereby, in a contest A vs. B, A poses its problems to B and vice versa, see Fig. 3. Because the test problems are encoded in the genome they are also evolvable. This leads to an autonomous regulation of the test problems towards the most intricate ones as multiplication approaches perfection.

Sixteen test problems are sufficient, but we also observed that it is much harder to obtain structured solutions if the number is too large. A small and (comparably) rapidly evolving number of test problems makes it nearly worthless to simply store the result of a specific multiplication task but it makes it highly advantageous to develop the structures to multiply by e.g. a power of two (a simple bit shift) because a specific instance, say 2x17, will rapidly vanish from the test problem population by fluctuation, but the principal ability to treat multiplications involving powers of two is of permanent value, because there is a significant probability for them to occur.   

In the case of multiplication, the individual tasks can be grouped into five categories, representing different levels of complexity: I: multiplication with zero (circuit produces only zeros), II: multiplication by unity (signals only need to be transferred) III: multiplication by a power of two (inputs are shifted) IV: multiplications not requiring carry logic V: multiplications with carry. The time evolution of the number of correct bits is shown in Fig. 4 for the evolution of an 8bit x 8bit multiplier.

Copyright 2007. All rights reserved. Web managers: J. S. McCaskill, P. Wagler