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
Ano de defesa: | 2022 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | , |
Tipo de documento: | Dissertação |
Tipo de acesso: | Acesso aberto |
Idioma: | por |
Instituição de defesa: |
Universidade Federal de Juiz de Fora (UFJF)
|
Programa de Pós-Graduação: |
Programa de Pós-graduação em Ciência da Computação
|
Departamento: |
ICE – Instituto de Ciências Exatas
|
País: |
Brasil
|
Palavras-chave em Português: | |
Área do conhecimento CNPq: | |
Link de acesso: | https://doi.org/10.34019/ufjf/di/2022/00122 https://repositorio.ufjf.br/jspui/handle/ufjf/14267 |
Resumo: | 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. |