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.