Cargando…

Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain

Reversible circuits are one of the technologies that can provide future low energy circuits. The synthesis of an optimal reversible circuit for a given function is an np-hard problem. The meta-heuristic approaches are one of the most promising methods for these types of optimization problems. In thi...

Descripción completa

Detalles Bibliográficos
Autor principal: Podlaski, Krzysztof
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7302832/
http://dx.doi.org/10.1007/978-3-030-50426-7_18
_version_ 1783547931341619200
author Podlaski, Krzysztof
author_facet Podlaski, Krzysztof
author_sort Podlaski, Krzysztof
collection PubMed
description Reversible circuits are one of the technologies that can provide future low energy circuits. The synthesis of an optimal reversible circuit for a given function is an np-hard problem. The meta-heuristic approaches are one of the most promising methods for these types of optimization problems. In this paper, a new approach for ACO reversible synthesis is presented. Usually, authors build an ACO system with the use of truth table or permutation representation of the reversible function. In this work, a Walsh spectral representation of a Boolean function is used. This allows dividing search spaces into smaller “promising” areas with well-defined transition operations between them. As a result, we can minimize the enormous search space and generate better solutions than obtained by ACO synthesis with classical reversible function representation. The proposed approach was applied to benchmark reversible functions of 4,5 and 6 variables and compared to other meta-heuristic results and best-known solutions.
format Online
Article
Text
id pubmed-7302832
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73028322020-06-19 Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain Podlaski, Krzysztof Computational Science – ICCS 2020 Article Reversible circuits are one of the technologies that can provide future low energy circuits. The synthesis of an optimal reversible circuit for a given function is an np-hard problem. The meta-heuristic approaches are one of the most promising methods for these types of optimization problems. In this paper, a new approach for ACO reversible synthesis is presented. Usually, authors build an ACO system with the use of truth table or permutation representation of the reversible function. In this work, a Walsh spectral representation of a Boolean function is used. This allows dividing search spaces into smaller “promising” areas with well-defined transition operations between them. As a result, we can minimize the enormous search space and generate better solutions than obtained by ACO synthesis with classical reversible function representation. The proposed approach was applied to benchmark reversible functions of 4,5 and 6 variables and compared to other meta-heuristic results and best-known solutions. 2020-05-25 /pmc/articles/PMC7302832/ http://dx.doi.org/10.1007/978-3-030-50426-7_18 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Podlaski, Krzysztof
Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain
title Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain
title_full Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain
title_fullStr Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain
title_full_unstemmed Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain
title_short Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain
title_sort ant colony optimization implementation for reversible synthesis in walsh-hadamard domain
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7302832/
http://dx.doi.org/10.1007/978-3-030-50426-7_18
work_keys_str_mv AT podlaskikrzysztof antcolonyoptimizationimplementationforreversiblesynthesisinwalshhadamarddomain