Algoritmo Divisão utilizando a meta-heurística Simulated Annealing aplicado na otimização de circuitos reversíveis

Douglas Uka Rennó¹; Alexandre Araujo Amaral de Almeida¹; Gerhard W. Dueck²; Alexandre César Rodrigues da Silva¹

¹ Universidade Estadual Paulista - UNESP; ² Universidade de New Brunswick - UNB

Baixar PDF doi:10.20906/CPS/CBA2018-0131

Resumo

Neste trabalho foram prospostos algoritmos para a otimização de circuitos reversíveis. Os algoritmos desenvolvidos foram o Simulated Annealing e o Divisão utilizando como método de otimização a meta-heurística Simulated Annealing. A diferença entre os algoritmos é o espaço de busca utilizado em cada um. No Simulated Annealing o espaço de busca é o circuito por completo, enquanto que no método Divisão o espaço de busca é reduzido para 15 portas com o propósito de aumentar a eficácia da otimização. Os resultados obtidos demonstraram que o algoritmo Divisão apresentou melhor desempenho, obtendo uma redução no custo de 8,5% com um tempo de execução 99,68% menor no circuito hwb9_123. Além disso, para avaliar o algoritmo Divisão, comparou-se com a heurística Dynamic Template, alcançando melhor resultado em 15 dos 42 circuitos reversíveis selecionados.

Palavras-chave: Simulated Annealing; Divisão; Otimização; Circuito reversível