Evolutionary graph generation system with transmigration capabilityand its application to arithmetic circuit synthesis

摘要

The paper presents a novel graph-based evolutionary optimisationntechnique called evolutionary graph generation (EGG) and its applicationnto the design of fast constant-coefficient multipliers using parallelncounter-tree architecture. A unique feature of EGG is its capability tonhandle the general graph structures directly in the evolution processninstead of encoding the graph structures into indirect representations,nsuch as bit strings and trees. The paper also demonstrates that thenevolution process of EGG can be accelerated by a simple operation,ncalled 'transmigration', which is to import previously generated goodnsolutions (constant-coefficient multipliers) for creating multipliersnwith different target coefficients. The authors' observation shows thatntransmigration accelerates a typical evolutionary run by an average ofn8.7 times. This implies that the EGG system can acquire and reuse usefulnsubcircuit structures contained in the previously generated multipliersnduring the evolution process