Programação genética cartesiana com recombinação e mutação guiada aplicada ao projeto de circuitos lógicos combinacionais

Abstract

Several approaches are found in the literature regarding the use of evolutionary computational techniques for the digital circuits design. However, the scalability problem remains a bottleneck for evolvable hardware. These techniques have proved promising for nding designs di erent from those of human conception. Among the digital circuits, the combinational logic ones comprise a large part including arithmetic circuits (multipliers and adders), comparators, among others. The Cartesian Genetic Programming (CGP) is pointed out as the most e cient evolutionary method for the digital circuits design. The use of CGP in the design of combinational logic circuits is addressed here, as well as the proposal of methods to assist it. The main contributions are: (i) a study of CGP's di culties in obtaining feasible circuits, (ii) a recombination operator, (iii) a mutation operator acting on the worst individuals' subgraph , called Guided Active Mutation (GAM), (iv) an approach that modi es the Evolutionary Strategy (ES) commonly used in CGP, operating with two mutation strategies, (v) the use of multiplexers as a logical element in the CGP function set, and (vi) a new evolving method of logic circuits in three stages by coupling a multiplexer with two inputs in each circuit output. The computational experiments that validated the proposed methods were composed of problems widely used in the literature and benchmark circuits. In the experiments using recombination, this operator shown to be important to increase the amount of feasible circuits and, when combined with GAM mutation operator and the modi cation of ES, to decrease the number of evaluations necessary to obtain feasible solutions. In addition, approaches that use multiplexers decreases the number of evaluations needed to nd a feasible solution, and they were able to evolve circuits with more inputs than traditional methods.