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

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.