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

Autor: Möller, Frederico José Dias
Přispěvatelé: Bernardino, Heder Soares, Soares, Stênio Sã Rosário Furtado, Barbosa, Helio José Corrêa, Manfrini, Francisco Augusto Lima
Jazyk: portugalština
Rok vydání: 2022
Předmět:
Zdroj: Repositório Institucional da UFJF
Universidade Federal de Juiz de Fora (UFJF)
instacron:UFJF
Popis: A otimização de circuitos lógicos combinacionais pode levar a dispositivos eletrônicos mais rápidos e baratos, mas é um problema NP-completo. Os algoritmos determinísticos para esta tarefa são limitados a pequenos problemas e a lógica de dois níveis. Para resolver esse tipo de problema, recorre-se ao uso de meta-heurísticas e a Programação Genética Cartesiana (CGP) é amplamente adotada na literatura, dentre as alternativas de computação evolutiva. Na CGP, a mutação é tradicionalmente o único operador para gerar novas soluções candidatas. Assim, o desempenho dessa abordagem depende da eficiência de tal operador. Diferentes operadores de mutação foram propostos para a CGP, mas a maioria deles se diferencia apenas na escolha dos nós que serão modificados. Porém, na modificação dos nós a mutação atua de forma não enviesada. Existem trabalhos na literatura que propõem matrizes estáticas de enviesamento nas mutações do tipo de porta lógica para a CGP e tais trabalhos obtiveram bons resultados. Entretanto, o enviesamento adotado nesses trabalhos não varia ao longo da busca, de modo que não acompanham as mudanças que podem ocorrer no processo de otimização a depender da região do espaço de busca que a solução candidata se encontra. Portanto, uma mutação adaptativa via Aprendizado por Reforço (RL) é proposta aqui para a CGP. A chamada CGP-RL foi avaliada num conjunto de problemas de otimização de portas lógicas e em outro para a minimização do número de transistores de circuitos digitais combinacionais. A CGP-RL proposta conseguiu melhores soluções em 3 dos 5 problemas de otimização de portas lógicas quando comparada com uma CGP com mutação enviesada da literatura e melhores médias em quase 60% dos problemas testados nesse trabalho para a minimização do número de transistores quando comparada com uma CGP tradicional. Em seguida à CGP-RL, outra técnica foi desenvolvida focando na escolha do elemento do nó a ser modificado pelo operador de mutação: entradas e operação lógica. A Node CGP-RL conseguiu melhores médias em cerca de 75% dos problemas abordados alcançando também as melhores soluções, quando comparada com a CGP, em 13 dos 23 problemas analisados, apresentando soluções finais com até 10% menos transistores que a CGP. 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.
Databáze: OpenAIRE
Externí odkaz: