(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,
Enhanced Optimization With Composite Objectives and Novelty Pulsation
(2) the name, complete physical mailing address, e-mail address of
EACH author,
Hormoz Shahrzad Email: hormoz@cognizant.com +1(925)487-1481
Babak Hodjat Email: babak@cognizant.com
Camille Dolle Email: camille.dolle@sentientim.com
Andrei Denissov Email: andrei.denissov@sentientim.com
Simon Lau Email: simon.lau@sentientim.com
Donn Goodhew Email: donn@sentientim.com
Justin Dyer Email: justin.dyer@sentientim.com
Risto Miikkulainen Email: risto@cs.utexas.edu
Physical address for all:
649 Front Street, Suite #3
San Fransisco, CA 94111, USA
(3) the name of the corresponding author (i.e., the author to whom
notices will be sent concerning the competition),
Hormoz Shahrzad
(4) the abstract of the paper(s),
An important benefit of multi-objective search is that it maintains a diverse population of candidates, which helps in deceptive problems in particular. Not all diversity is useful, however: candidates that optimize only one objective while ignoring others are rarely helpful. A recent solution is to replace the original objectives by their linear combinations, thus focusing the search on the most useful trade-offs between objectives. To compensate for the loss of diversity, this transformation is accompanied by a selection mechanism that favors novelty. This paper improves this approach further by introducing novelty pulsation, i.e. a systematic method to alternate between novelty selection and local optimization. In the highly deceptive problem of discovering minimal sorting networks, it finds state-of-the-art solutions significantly faster than before. In fact, our method so far has established a new world record for the 20-lines sorting network with 91 comparators. In the real-world problem of stock trading, it discovers solutions that generalize significantly better on unseen data. Composite Novelty Pulsation is therefore a promising approach to solving deceptive real-world problems through multi-objective optimization.
(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 <= 10.
Finding the minimum number of comparators for n > 10 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/deceptive problem of stock trading by
combining multi-objective optimization with novelty search, and
as a good benchmark for deceptive domains we picked sorting networks
to validate the method and without any special tuning/customization,
it matched the state of the art for n <= 19 and unexpectedly improved
the state of the art result for n = 20.
Therefore, our result 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 result extend
these results to a more difficult case (n = 20), 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 <= 19
and is better for n = 20.
(D) Since the result improves the upper bounds on network size for
n = 20, it is publishable in its 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 up to n = 19 and
is better for n = 20.
(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 <= 19 and
is better for n = 20.
(G) Even after more than half-century of intensive research, finding
minimal size sorting networks for n > 10 remains an open
problem of indisputable difficulty in Computer Science.
The significance of our approach is its generality in a
sense that it doesn't utilize any domain specific knowledge
to constrain evolutionary search, matching all the rsults for
n <= 19 and producing a better result for n = 20.
(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);
H. Shahrzad, B. Hodjat, C. Dolle, A. Denissov, S. Lau, D. Goodhew, J. Dyer,
and R. Miikkulainen. Enhanced Optimization with Composite Objectives and
Novelty Pulsation. In: Genetic Programming Theory and Practice XVII,
Michigan State University, East Lansing, MI, USA, May 16-19, 2019.
(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 result improve upon half-century of results
published in patents, books, and peer-reviewed literature, making
the result 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.
Third, the method we have used is a general method which we originally
developed for application in stock trading domain and then we applied
it to sorting network without any modification/customization as a
toy domain just to validate its effectiveness, despite tailoring a
method that utilizes the domain specificities like Valsalam, V. K. 2010.
(10)Type of EC used
Genetic Programming
(11)The date of publication of each paper.
If the date of publication is not on or before the deadline for
submission, but instead, the paper has been unconditionally accepted
for publication and is “in press” by the deadline for this competition,
the entry must include a copy of the documentation establishing that
the paper meets the "in press" requirement.
This is the link to GPTP-2019 presentation schedule of accepted papers: http://gptp-workshop.com/schedule.html
{Saturday 18 May, 2019
12:15p Hormoz Sharhzad et al. “Enhanced Optimization with
Composite Objectives and Novelty Pulsation”}
REFERENCES
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
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.