Mutações adaptativas via aprendizado por reforço para programação genética cartesiana aplicada ao projeto e otimização de circuitos lógicos combinacionais

Abstract

Optimizing combinational logic circuits can lead to faster and cheaper electronic devices, but it is an NP-complete problem. The deterministic algorithms for this task are limited to small problems and two-level logic. To solve this type of problem, meta-heuristics are used and Cartesian Genetic Programming (CGP) is widely adopted in the literature, among the alternatives to evolutionary computation. In CGP, the mutation is traditionally the only operator to generate new candidate solutions. Thus, the performance of this approach depends on the efficiency of such an operator. Different mutation operators have been proposed for the CGP, but most of them differ only in the choice of nodes to be modified. However, when modifying nodes, the mutation acts in an unbiased way. There are works in the literature that propose static bias matrices in the mutations of the logic gate type for the CGP and such works obtained good results. However, the bias adopted in these works does not vary along the search, so they do not follow the changes that may occur in the optimization process depending on the region of the search space where the candidate solution is. Therefore, an adaptive mutation via Reinforcement Learning (RL) is proposed here for PGC. The so-called CGP-RL was evaluated in a set of logic gate optimization problems and another for minimizing the number of transistors in combinational digital circuits. The proposed CGP-RL achieved better solutions in 3 out of 5 logic gate optimization problems when compared to a skewed mutation CGP in the literature and better averages in almost 60% of the problems tested in this work for the minimization of the number of transistors when compared with a traditional PGC. After CGP-RL, another technique was developed, focusing on choosing the node element to be modified by the mutation operator: inputs and logic operation. The Node CGP-RL achieved better averages in about 75% of the problems addressed, also reaching the best solutions, when compared to the CGP, in 13 of the 23 problems analyzed, presenting final solutions with up to 10% fewer transistors than CGP.