2005 HUMAN-COMPETITIVE AWARDS IN GENETIC AND EVOLUTIONARY COMPUTATION, GECCO, 2005, Washington D.C.
(1) paper title
Evolutionary Design of Arbitrarily Large Sorting Networks Using Development
Because the paper is more general (the result defended here is only one of its outcomes) and its title does not exactly explain our entry for this competition, we would like to use the following title for the competition:
How to create (n+1) or (n+2)-input sorter from n-input sorter
(2) authors
Lukas Sekanina
Faculty of Information Technology, Brno University of Technology
Bozetechova 2, 612 66 Brno, Czech Republic
telephone: +420 54114 1215, fax: +420 54114 1270
email: sekanina@fit.vutbr.cz
http://www.fit.vutbr.cz/~sekanina
Michal Bidlo
Faculty of Information Technology, Brno University of Technology
Bozetechova 2, 612 66 Brno, Czech Republic
telephone: +420 54114 1206, fax: +420 54114 1270
email: bidlom@fit.vutbr.cz
http://www.fit.vutbr.cz/~bidlom
(3) corresponding author
Lukas Sekanina
(4) the abstract of the paper
An evolutionary algorithm is combined with an application-specific developmental scheme in order to evolve efficient arbitrarily large sorting networks (SN). First, a small sorting network (that we call the embryo) has to be prepared to solve the trivial instance of a problem. Then the evolved program (the constructor) is applied on the embryo to create a larger sorting network (solving a larger instance of the problem). Then the same constructor is used to create a new instance of the sorting network from the created larger sorting network and so on. The proposed approach allowed us to rediscover the conventional principle of insertion which is traditionally used for constructing large sorting networks. Furthermore, the principle was improved by means of the evolutionary technique. The evolved sorting networks exhibit a lower implementation cost and delay.
(5) Criteria: D, F, B
(6) a statement stating why the result satisfies that criteria
Sorting is a traditional and non-trivial problem in computer science and engineering. Plenty of results were patented in the area of sorting algorithms (see summary in [1], pages 380-391). As the research area is well explored by computer scientists it is difficult to obtain a new result. We evolved a program (constructor) that is able to create a valid (n+1) or (n+2)-input sorting network from a valid n-input sorting network by modifying and copying comparators. First, the method described in [1] (page 222) was reinvented (the evolved program adds n new comparators to create (n+1)-input SN). Second, the method was improved for (n+2)-input SN. The evolutionary approach was used not only to solve one instance of the problem (to design a sorting network with a given number of inputs) but to solve all instances of the problem (to create an arbitrarily large SN). Therefore, a new general design principle was invented.
(D) The result is publishable in its own right as a new scientific result - independent of the fact that the result was mechanically created.
Why: The approach significantly decreases the number of comparators and delay of SNs if one has to create a larger SN from an existing smaller one. The result is important, for example, when one has to extend an existing sorting algorithm implemented in hardware. Because the area of sorting networks is well explored by computer scientists (many patents awarded) it is difficult to discover a novel result. A new general design principle was invented. Therefore, the result is publishable in its own right as a new scientific result.
(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
Why: Knuth [1] (page 222) presents an approach to creating a larger valid SN from a smaller valid SN. We rediscovered and improved the mentioned approach.
(B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.
Why: Sorting networks created using the proposed approach exhibit lower number of comparisons and shorter delay than the straight-insertion sort algorithm (which can be implemented as a SN). In Germany, K. Zuse constructed a program for straight-insertion sorting in 1945 in hi s language. This pioneering work remained unpublished for nearly 30 years; see Berichte der Gesellschaft fur Mathematik und Datenverarbeitung 63 (Bonn, 1972), part 4, 84-85 (cited from [1] pages 385-386)
(7) a full citation of the paper
Sekanina, L., Bidlo, M.: Evolutionary Design of Arbitrarily Large Sorting Networks Using Development. J. on Genetic Programming and Evolvable Machines, Springer, 2005, 34 p. (accepted, in press)
PDF file