Evolving Minimal Size Sorting Networks
--------------------------------------
(1) the complete title of one (or more) paper(s) published in the open
literature describing the work that the author claims describes a
human-competitive result,
Utilizing Symmetry in Evolutionary Design (PhD Dissertation)
(2) the name, complete physical mailing address, e-mail address, and
phone number of EACH author of EACH paper,
Vinod K. Valsalam (dissertation author)
33 Hudson Street, Apt 2806
Jersey City, NJ 07302 USA
Email: vkv@cs.utexas.edu
Phone: +1-512-364-9298
Risto Miikkulainen (dissertation supervisor)
Department of Computer Sciences
The University of Texas at Austin
1 University Station D9500
Austin, TX 78712-0233 USA
Email: risto@cs.utexas.edu
Phone: +1-512-471-9571
(3) the name of the corresponding author (i.e., the author to whom
notices will be sent concerning the competition),
Vinod K. Valsalam
(4) the abstract of the paper(s),
Can symmetry be utilized as a design principle to constrain
evolutionary search, making it more effective? This dissertation
aims to show that this is indeed the case, in two ways. First, an
approach called ENSO is developed to evolve modular neural network
controllers for simulated multilegged robots. Inspired by how
symmetric organisms have evolved in nature, ENSO utilizes group
theory to break symmetry systematically, constraining evolution to
explore promising regions of the search space. As a result, it
evolves effective controllers even when the appropriate symmetry
constraints are difficult to design by hand. The controllers
perform equally well when transferred from simulation to a
physical robot. Second, the same principle is used to evolve
minimal-size sorting networks. In this different domain, a
different instantiation of the same principle is effective:
building the desired symmetry step-by-step. This approach is more
scalable than previous methods and finds smaller networks, thereby
demonstrating that the principle is general. Thus, evolutionary
search that utilizes symmetry constraints is shown to be effective
in a range of challenging applications.
(5) a list containing one or more of the eight letters (A, B, C, D, E,
F, G, or H) that correspond to the criteria (see above) that the
author claims that the work satisfies,
A, B, D, E, F, G.
(6) a statement stating why the result satisfies the criteria that the
contestant claims (see examples of statements of
human-competitiveness as a guide to aid in constructing this part
of the submission),
A sorting network of n inputs is a fixed sequence of
comparison-exchange operations (comparators) that sorts all inputs
of size n. Minimizing the number of comparators required for a
given n is a hard combinatorial optimization problem that has been
the subject of active research since the 1950's, when O'Conner and
Nelson constructed networks for 4 <= n <= 8 (U.S. Patent 3029413).
Their networks had the minimal number of comparators for 4, 5, 6,
and 8 inputs, but required two extra comparators for 7 inputs.
This result was improved by Batcher (1968), whose algorithmic
construction produces provably minimal networks for n <= 8 (Knuth,
1998).
Still today, provably minimal networks are known only for n <= 8.
Finding the minimum number of comparators for n > 8 is thus a
challenging open problem. It has been studied by various
researchers using specialized techniques, often separately for
each value of n. For example, the 16-input case, for which
Batcher's method requires 63 comparators, was improved by Shapiro
who found a 62-comparator network in 1969. Soon afterward, Green
found a network with 60 comparators, which still remains the best
in terms of the number of comparators. Knuth (1998) documents the
interesting history of how advances were made for the other values
of n and how "each step was forged with some difficulty".
In short, networks designed using human ingenuity are still the
best known solutions for 9 <= n <= 16 (except for n = 13; Juille,
1995). For larger values of n, all the best known solutions are
simply merges of smaller networks; the problem is so difficult
that nobody has been able to improve on these straightforward
constructions (Baddar, 2009).
Our approach was developed as part of research into evolving
solutions to complex problems by utilizing symmetry. It constructs
the required network symmetry step-by-step, thereby focusing the
evolutionary search to more likely candidates. This algorithm was
able to discover new minimal known networks for 17, 18, 19, 20,
and 22 inputs, producing improvements of one or two comparators.
Moreover, for the other n < 24, with the exception of n = 15, it
evolved networks that have the same size as the best known
networks. Thus, out results satisfy the following criteria for
human competitiveness:
(A) Minimal networks for the simpler 4 <= n <= 8 cases are
patented (U.S. Patent 3029413); the current results extend
these results to several more difficult cases (n = 17, 18, 19,
20, 22), and would therefore qualify today as a patentable new
invention.
(B) Knuth (1998) and Koza et al. (1999) have surveyed many results
on minimal sorting networks that have been published in
peer-reviewed scientific journals during the last several
decades. Our results are equal to these results for n <= 14
and for n = 16 and are better for n = 17, 18, 19, 20, and 22.
(D) Since the results improve the upper bounds on network size for
n = 17, 18, 19, 20, and 22, they are publishable in their own
right as new scientific results independent of the fact that
the results were mechanically created.
(E) Knuth (1998) and Koza et al. (1999) describe how a succession
of increasingly better sorting networks for n <= 16 were
designed by humans starting in the 1950's. Our results are
equal to the most recent such solutions except for n = 15 and
are better for n = 17, 18, 19, 20, and 22.
(F) The previous results that reduced the number of comparators
were all considered achievements in the field since they
improved the best known upper bounds on network size. The
current results are equal to these results for n <= 14 and for
n = 16 and are better for n = 17, 18, 19, 20, and 22.
(G) Even after a half-century of intensive research, finding
minimal size sorting networks for n > 8 remains an open
problem of indisputable difficulty in Computer Science. Our
approach makes this problem more tractable by utilizing
symmetry to constrain evolutionary search, producing better
results for n = 17, 18, 19, 20, and 22.
(7) a full citation of the paper (that is, author names; publication
date; name of journal, conference, technical report, thesis, book,
or book chapter; name of editors, if applicable, of the journal or
edited book; publisher name; publisher city; page numbers, if
applicable);
Valsalam, V. K. (2010). "Utilizing Symmetry in Evolutionary
Design". PhD Thesis, Department of Computer Sciences, The
University of Texas at Austin, Austin, TX. Technical Report
AI-10-04. http://nn.cs.utexas.edu/?valsalam:phd10
(8) a statement either that "any prize money, if any, is to be divided
equally among the co-authors" OR a specific percentage breakdown
as to how the prize money, if any, is to be divided among the
co-authors; and
Any prize money, if any, is to be divided equally among the
co-authors.
(9) a statement stating why the judges should consider the entry as
"best" in comparison to other entries that may also be
"human-competitive."
First, our evolved results improve upon half-century of results
published in patents, books, and peer-reviewed literature, making
the results highly significant scientifically. They show that
evolutionary methods can be used to discover solutions to design
problems that have fascinated theorists for a long time.
Second, the solutions are important in practice. Sorting networks
implement oblivious, i.e. data-independent sorting, where the
sequence of comparisons does not depend on input data. Therefore,
they are used to implement sorting in parallel hardware e.g. on
graphics processing units (Kipfer et al., 2004) and in switching
networks (Batcher, 1968). Smaller such networks make such
applications more efficient.
REFERENCES
Batcher, K. E. (1968). Sorting networks and their applications. In
AFIPS Spring Joint Computing Conference, 307--314.
Baddar, S. W. A. (2009). Finding Better Sorting Networks. PhD thesis,
Kent State University.
Juille, H. (1995). Evolution of non-deterministic incremental
algorithms as a new approach for search in state spaces. In
Proceedings of the 6th International Conference on Genetic
Algorithms, 351--358. San Francisco, CA, USA: Morgan Kaufmann
Publishers Inc.
Kipfer, P., Segal, M., and Westermann, R. (2004). Uberflow: A
gpu-based particle engine. In HWWS '04: Proceedings of the ACM
SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, 115--122. New
York, NY, USA: ACM.
Knuth, D. E. (1998). Art of Computer Programming: Sorting and
Searching, vol. 3. Addison- Wesley Professional. Second edition.
Koza, J. R., Bennett III, F. H., Andre, D., and Keane, M. A. (1999).
Genetic Programming III: Darwinian Invention and Problem
Solving. Morgan Kaufmann Publishers.
O'Connor, D. G. and Nelson, R. J. (1962). Sorting System with N-Line
Sorting Switch. United States Patent number 3,029,413. Filed Feb 21,
1957. Issued Apr 10, 1962.