ALGORITMO DIVISÃO UTILIZANDO A META-HEURÍSTICA SIMULATED ANNEALING APLICADO NA OTIMIZAÇÃO DE CIRCUITOS REVERSÍVEIS

DOUGLAS  UKA RENNÓ; ALEXANDRE  A. A. DE ALMEIDA; GERHARD  W. DUECK; ALEXANDRE  CÉSAR RODRIGUES DA SILVA

doi:10.20906/CBA2022/87

DOUGLAS UKA RENNÓ Universidade Estadual Paulista - UNESP
ALEXANDRE A. A. DE ALMEIDA Universidade Estadual Paulista - UNESP
GERHARD W. DUECK Universidade de New Brunswick - UNB
ALEXANDRE CÉSAR RODRIGUES DA SILVA Universidade Estadual Paulista - UNESP

DOI: https://doi.org/10.20906/CBA2022/87

Keywords: Simulated Annealing, Divisão, Otimização, Circuito reversível

Abstract

Neste trabalho foram implementados dois algoritmos adaptados para otimiza¸c˜ao de circuitos revers´ıveis, tendo como custo a quantidade de portas no circuito. O algoritmo Simulated Annealing utilizado como m´etodo de otimiza¸c˜ao, em que junto as regras de reescrita permite a altera¸c˜ao do tamanho do circuito sem alterar a respectiva funcionalidade e o algoritmo Divis˜ao, desenvolvido para resolver a inefiˆencia do Simulated Annealing para circuitos com mais de 50 portas, tendo como objetivo evitar o crescimento indesej´avel do circuito nas itera¸c˜oes iniciais. A funcionalidade do m´etodo Divis˜ao ´e aplicar o m´etodo de otimiza¸c˜ao em pequenas partes do circuito por vez. Para avalia¸c˜ao do desempenho do algoritmo Divis˜ao, utilizou-se a heur´ıstica Dynamic Template como compara¸c˜ao. De acordo com os resultados, obteve-se maior redu¸c˜ao de custo em 15 circuitos, mesmo custo em 25 circuitos e piores custos em apenas 3 circuitos.