Publication Details
Evolutionary Development of Growing Generic Sorting Networks by Means of Rewriting Systems
Dobeš Michal, Ing.
genetic algorithm, development, rewriting system, sorting network, scalability
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.
@article{BUT161834,
author="Michal {Bidlo} and Michal {Dobeš}",
title="Evolutionary Development of Growing Generic Sorting Networks by Means of Rewriting Systems",
journal="IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION",
year="2020",
volume="24",
number="2",
pages="232--244",
doi="10.1109/TEVC.2019.2918212",
issn="1089-778X",
url="https://ieeexplore.ieee.org/document/8720059"
}