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.
The automatic design of multi-objective ant colony optimization algorithms.
2. The name, complete physical mailing address, e-mail address, and
phone number of EACH author of EACH paper:
Manuel López-Ibáñez
IRIDIA, Université Libre de Bruxelles (ULB),
Av. F. Roosevelt 50, CP 194/6, 1050 Brussels, Belgium.
manuel.lopez-ibanez@ulb.ac.be
+32 (0) 2650 2745
Thomas Stützle
IRIDIA, Université Libre de Bruxelles (ULB),
Av. F. Roosevelt 50, CP 194/6, 1050 Brussels, Belgium.
stuetzle@ulb.ac.be
+32 (0) 2650 3167
3. The name of the corresponding author (i.e., the author to whom
notices will be sent concerning the competition)
Manuel López-Ibáñez (manuel.lopez-ibanez@ulb.ac.be)
4. The abstract of the paper(s)
Multi-objective optimization problems are problems with several,
typically conflicting criteria for evaluating solutions. Without any
a priori preference information, the Pareto optimality principle
establishes a partial order among solutions, and the output of the
algorithm becomes a set of nondominated solutions rather than a
single one. Various ant colony optimization (ACO) algorithms have
been proposed in recent years for solving such problems. These
multi-objective ACO (MOACO) algorithms exhibit different design
choices for dealing with the particularities of the multi-objective context.
This paper proposes a formulation of algorithmic components that
suffices to describe most MOACO algorithms proposed so far. This
formulation also shows that existing MOACO algorithms often share
equivalent design choices but they are described in different
terms. Moreover, this formulation is synthesized into a flexible
algorithmic framework, from which not only existing MOACO algorithms
may be instantiated, but also combinations of components that were never
studied in the literature. In this sense, this paper goes beyond
proposing a new MOACO algorithm, but it rather introduces a family of
MOACO algorithms.
The flexibility of the proposed MOACO framework facilitates the
application of automatic algorithm configuration techniques. The
experimental results presented in this paper show that the
automatically configured MOACO framework outperforms the MOACO
algorithms that inspired the framework itself. This paper is also
among the first to apply automatic algorithm configuration
techniques to multi-objective algorithms.
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
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.
D The result is publishable in its own right as a new scientific
result independent of the fact that the result was mechanically
created.
E The result is equal to or better than the most recent
human-created solution to a long-standing problem for which there
has been a succession of increasingly better human-created
solutions.
6. A statement stating why the result satisfies the criteria that the
contestant claims.
Since the proposal of the ant colony optimization (ACO) metaheuristic
in the 1990s, there is an ongoing research on applying the ACO
metaheuristic to multi-objective optimization problems. This interest
has resulted on a dozen competing proposals on how to design such
multi-objective ACO (MOACO) algorithms. The different MOACO designs
share common ideas but are also distinguished by alternative choices
for various algorithmic components. In fact, it is possible to design
hundreds of "new" MOACO algorithms by merely combining in novel ways
the algorithmic components already proposed in the
literature. Following this idea, we have build a parametrized
framework that allows us to instantiate new designs of MOACO
algorithms. However, instead of deciding by ourselves what would be
the best design for a given problem, we let an automatic
configuration tool to choose the best parameters of the framework
given a set of training problem instances. Our approach is the first
that automatically configures heuristic multi-objective
optimizers. The proposed framework, from which MOACO algorithm
designs are instantiated, has overall 16 configurable parameters of
which 7 categorical and 3 numerical directly affect the design
choices for the MOACO algorithm.
The result of our automatic design procedure is a MOACO algorithm
that outperforms at least nine MOACO algorithms from the literature,
even after the numerical parameters of those algorithms are tuned in
order to improve their performance. Therefore, our automatic design
procedure satisfies the following criteria:
(B) Our automatically designed MOACO algorithm is better than nine
other human-designed MOACO algorithms, which were accepted as a
new scientific result at the time when they were published
in a peer-reviewed scientific journal.
(D) Our result was published, in the prestigious IEEE Transactions
on Evolutionary Computation, in its own right as a new scientific
result independent of the fact that the result was mechanically
created.
(E) Our result completely outperforms the best human-created MOACO
algorithm for the bi-objective TSP. García-Martínez et
al. (2007) compared ten human-designed MOACO algorithms and
found BicriterionAnt to be the best for the bi-objective
TSP. Our automatically designed MOACO algorithm completely
outperforms BicriterionAnt, even after we tuned the parameters
of the latter to further improve its performance.
C. García-Martínez, O. Cordón, and F. Herrera. A taxonomy and an
empirical analysis of multiple objective ant colony optimization
algorithms for the bi-criteria TSP. European Journal of
Operational Research, 180 (1):116–148, 2007.
7. A full citation of the paper
M. López-Ibáñez and T. Stützle. The automatic design of multi-objective
ant colony optimization algorithms. IEEE Transactions on Evolutionary
Computation, 16(6):861–875, 2012. doi:10.1109/TEVC.2011.2182651.
8. 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."
Let us state the reasons why the judges may consider the
entry to be "not the best", and we will reply to each of these
reasons:
* "The design of MOACO algorithms for the bi-objective TSP is a
lesser problem compared to other problems related to health,
energy or the economy."
Our answer is that the problem we tackled is a representative case
of the more general problem of designing complex algorithms from a
large number of potential components. The facts that almost all
human-designed MOACO algorithms are included in our comparison,
and that we chose a simple problem for which recent independent
work is available, make our conclusions more robust than if we had
chosen a more complex problem for which a definition of "best"
would be hard to establish. In addition, we provide
[http://iridia.ulb.ac.be/~manuel/moaco] the problem instances, the
source code of the algorithmic framework, and the source code of
the automatic configuration tool used in our study, which would
allow anyone to replicate our results.
* "The idea of automatically designing algorithms is not new."
Although Genetic Programming, Grammatical Evolution, and similar
approaches also have the goal of automatically designing
algorithms, our method is radically different. We make use of
the knowledge and imagination already available in the literature
in the form of alternative design choices, but we let an automatic
procedure decide which design choices should be integrated into
the final algorithm and how. In some sense, the humans contribute
their imagination and inventiveness in the form of potential
algorithmic designs, and the machine provides an unbiased
selection among those designs based on a large amount of
experimental data. The real contribution of our work is to show
that this approach is not only feasible, but it clearly surpasses
the capabilities of human designers. We believe this should become
the standard way to design optimization algorithms in the future.
* "There is no indication that this method works besides this case
study."
On the contrary, there is increasing evidence that the method used
in our paper leads to new algorithm designs that surpass those
designed by humans. Dubois-Lacoste et al. (2011) have used our
method to further improve the state-of-the-art algorithm for
various bi-objective permutation flowshop problems. The new design
is not very different from the previous state-of-the-art
algorithm, however, the fact that there is an improvement at all
is significant. KhudaBukhsh et al. (2009) followed a similar
method to automatically build solvers for the SAT competition,
outperforming several human-designed algorithms. However, their
work was targeted for algorithms that tackle a single objective
problem. Our work is the first that considers the automatic
configuration of multi-objective optimizers where numerical and
categorical parameters, which are related to algorithm design, are
considered in the automatic configuration process.
J. Dubois-Lacoste, M. López-Ibáñez, and T. Stützle. Automatic
configuration of state-of-the-art multi-objective optimizers using the
TP+PLS framework. In N. Krasnogor and P. L. Lanzi, editors,
Proceedings of the Genetic and Evolutionary Computation Conference,
GECCO 2011, pages 2019–2026. ACM Press, New York, NY,
2011. doi:10.1145/2001576.2001847.
A. R. KhudaBukhsh, L. Xu, H. H. Hoos, and K. Leyton-Brown,
"SATenstein: Automatically building local search SAT solvers from
components," in Proceedings of the Twenty-First International
Joint Conference on Artificial Intelligence (IJCAI-09), 2009,
pp. 517–524.
Given the above arguments, we believe that our work is not only
human-competitive, but rather it successfully replaces the human
component from a key step on the design of algorithms leading to
better results.