ABSTRACT
Learn-and-Optimize (LaO) is a generic surrogate based
method for parameter tuning combining learning and optimization.
In this paper LaO is used to tune Divide-and-
Evolve (DaE), an Evolutionary Algorithm for AI Planning.
The LaO framework makes it possible to learn the relation
between some features describing a given instance and
the optimal parameters for this instance, thus it enables
to extrapolate this knowledge to unknown instances in the
same domain. Moreover, the learned relation is used as a
surrogate-model to accelerate the search for the optimal parameters.
It hence becomes possible to solve intra-domain
and extra-domain generalization in a single framework. The
proposed implementation of LaO uses an Articial Neural
Network for learning the mapping between features and optimal
parameters, and the Covariance Matrix Adaptation
Evolution Strategy for optimization. Results demonstrate
that LaO is capable of improving the quality of the DaE results
even with only a few iterations. The main limitation of
the DaE case-study is the limited amount of meaningful features
that are available to describe the instances. However,
the learned model reaches almost the same performance on
the test instances, which means that it is capable of generalization.
Categories and Subject Descriptors
I.2.6 [Computing Methodologies]: Articial Intelligence
Learning Parameter learning
General Terms
Theory
Keywords
parameter tuning, AI Planning, evolutionary algorithms
1. INTRODUCTION
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
GECCO’11, July 12–16, 2011, Dublin, Ireland.
Copyright 2011 ACM 978-1-4503-0690-4/11/07 ...$10.00.
Parameter tuning is basically a general optimization problem
applied o-line to nd the best parameters for complex
algorithms, for example for Evolutionary Algorithms (EAs).
Whereas the eciency of EAs has been demonstrated on
several application domains [29, 18], they usually need computationally
expensive parameter tuning. Consequently, one
is tempted to use either the default parameters of the framework
he is using, or parameter values given in the literature
for problems that are similar to his one.
Being a general optimization problem, there are as many
parameter tuning algorithms as optimization techniques [7,
19]. However, several specialized methods have been proposed,
and the most prominent ones today are Racing [5],
REVAC [21], SPO [2], and ParamILS [14]. All these approaches
face the same crucial generalization issue: can a
parameter set that has been optimized for a given problem
be successfully used for another one? The answer of course
depends on the similarity of both problems. However, even
in an optimization domain as precisely dened as AI Planning,
there are very few results describing meaningful similarity
measures between problem instances. Moreover, until
now, suciently precise and accurate features have not been
specied that would allow the user to accurately describe the
problem, so that the optimal parameter-set could be learned
from this feature-set, and carried on to other problems with
similar description. To the best of our knowledge, no design
of a general learning framework has been proposed, and no
general experiments have been carried out yet with some
representative domains of AI planning.
In the SAT domain, however, one work must be given as an
example of what can be done along those lines. In [13], many
relevant features have been gathered based on half a century
of SAT-research, and hundreds of papers. Extensive parameter
tuning on several thousands of instances has allowed
the authors to learn, using function regression, a meaningful
mapping between the features and the running-time of
a given SAT solver with given parameters. Optimizing this
model makes it possible to choose the optimal parameters
for a given (unknown) instance. The present paper aims at
generalizing this work made in AI planning, with one major
dierence: the target will be here to optimize the tness
value for a given runtime, and not the runtime to solution {
as the optimal solution is generally not known for AI planning
problems.
Unfortunately, until now, nobody has yet proposed a set of
features for AI Planning problems in general, that would
be sucient to describe the characteristics of a problem,
like was done in the SAT domain [13]. This paper makes a