Speaker
Description
Evolutionary design has become a successful concept in areas where a solution to a problem needs an exploration of extensive search space (i.e. the analytical approach is intractable or not known). It has been shown during recent years that innovative designs can be obtained automatically using proper evolutionary setups. However, the complexity of the problem to be solved (the size of its instance) makes the evolution very difficult especially due to the following aspects: (1) the representation of candidate solutions requires extensive encoding for the evolutionary algorithm that, eventually, fails to find acceptable solutions and (2) the time needed to evaluate a solution grows enormously which limits the evolution to explore the design space in a reasonable time. This issue is generaqlly referred to as the problem of scale. Several techniques exist that allow overcoming this problem. Developmental encoding represents a potentially suitable way which is the point of interest in this contribution. In particular, a developmental method is presented for designing arbitrarily large sorting networks. The main idea is based on a parallel rewriting system (a grammar), specified by an alphabet, an initial string (an axiom) and a set of rewriting rules, that allows for encoding comparator structures - building blocks of sorting networks. 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 the comparator structures. The construction of the sorting networks is performed in such a way that a given (initial) 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 and may exhibit significantly better properties (the number of comparators and delay) in comparison with solutions obtained by means of similar existing methods.
