Publication Details

Evolutionary Development of Growing Generic Sorting Networks by Means of Rewriting Systems

BIDLO Michal and DOBEŠ Michal. Evolutionary Development of Generic Sorting Networks by Means of Rewriting Systems. IEEE Transactions on Evolutionary Computation, vol. 24, no. 2, 2020, pp. 232-244. ISSN 1089-778X. Available from: https://ieeexplore.ieee.org/document/8720059
Czech title
Evoluční vývin rostoucích řadicích sítí pomocí přepisovacích systémů
Type
journal article
Language
english
Authors
Bidlo Michal, doc. Ing., Ph.D. (DCSY FIT BUT)
Dobeš Michal, Ing. (FIT BUT)
URL
Keywords

genetic algorithm, development, rewriting system, sorting network, scalability

Abstract

This paper presents an evolutionary developmental method for the design of arbitrarily growing sorting networks. The developmental model is based on a parallel rewriting system (a grammar) that is specified by an alphabet, an initial string (an axiom), and a set of rewriting rules. The rewriting process iteratively expands the axiom in order to develop more complex strings during a series of development steps (i.e., derivations in the grammar). A mapping function is introduced that allows for converting the strings onto comparator structures-building blocks of sorting networks. The construction of the networks is performed in such a way that a given (initial) sorting network grows progressively by adding further building blocks within each development step. For a given (fixed) alphabet, the axiom together with the rewriting rules themselves are the subjects of the evolutionary search. It will be shown that suitable grammars can be evolved for the construction of arbitrarily large sorting networks that grow with various given sizes of development steps. Moreover, the resulting networks exhibit significantly better properties (the number of comparators and delay) in comparison with those obtained by means of similar existing methods.

Published
2020
Pages
232-244
Journal
IEEE Transactions on Evolutionary Computation, vol. 24, no. 2, ISSN 1089-778X
Publisher
IEEE Computational Intelligence Society
DOI
UT WoS
000524328700003
EID Scopus
BibTeX
@ARTICLE{FITPUB11778,
   author = "Michal Bidlo and Michal Dobe\v{s}",
   title = "Evolutionary Development of Growing Generic Sorting Networks by Means of Rewriting Systems",
   pages = "232--244",
   journal = "IEEE Transactions on Evolutionary Computation",
   volume = 24,
   number = 2,
   year = 2020,
   ISSN = "1089-778X",
   doi = "10.1109/TEVC.2019.2918212",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11778"
}
Back to top