MetaDeeP 2014 – Metaheuristic Design Patterns
Workshop
at GECCO 2014
Conference, Vancouver, BC, Canada. 12-16 July 2014.
You’re unlikely to have arrived at this page unless you’re interested in metaheuristics:
· Do you have an idea about how metaheuristics could be better hybridized or generated?
·
Have you observed some commonality (e.g. across
frameworks or methodologies) that is not yet widely recognized?
·
Are you frustrated when researchers don’t follow
best practices that are well-understood in your field?
If so, then you should attend MetaDeeP
2014 – the first Workshop on Metaheuristic Design
Patterns.
We envision the workshop as
spearheading a community initiative that is primarily bottom-up, i.e. driven
by the ideas and needs of practitioners rather than by arbitrary assumptions.
What are Metaheuristic Design Patterns?
Seasoned metaheuristic practitioners acquire vital knowledge about
the algorithms, methodologies and components that are likely to be useful for
solving a particular problem. While rarely explicitly documented, these
higher-level sensibilities are often the key to success of a particular
approach.
Traditionally,
the decomposition of metaheuristics can be considered
`vertical’ in that it describes frameworks (Iterated Local Search, Evolutionary
Computation, Ant Colony Optimization etc). While
these frameworks can certainly be described in “pattern language” terms (see
[4]) the additional motivation behind the “Metaheuristic
Design Patterns” Workshop is twofold:
1. Educational.
In
adopting a `pattern-based’ perspective, we’re additionally seeking to decompose
good research practice by cutting `horizontally’ across frameworks and
methodologies, looking to abstract out aspects that have yet to be folded back
into the mainstream. This can be seen as serving an educational purpose: “how best to convey the practicalities of metaheuristic engineering to the uninitiated?”.
2. Declarative.
The
“Problem Statement” aspect of the design pattern format essentially gives
heuristic preconditions for the application of a pattern. This lends itself
well to the process of component selection/generation. Since this is an
essential part of the automated design of metaheuristics,
what we’d really like is to be able to convey this heuristic information
declaratively (i.e. so that even a computer can understand it). The ultimate
goal is to use this information to help reformulate metaheuristic
design as a problem of (potentially dynamic) software component assembly. See [1] for more on this.
Pattern Categories
In the
original “Design Patterns” book, Gamma et al. identify three pattern
categories:
Creational patterns: deals with component creation.
Structural patterns: describe the static component architecture.
Behavioral patterns: capture dynamic interaction between components.
Some
other categories (by no means exhaustive) that seem appropriate to metaheuristics include:
Semantic Patterns: `Whitebox’
representations of (problem or solution) domain information.
Metrics: Potentially useful measures for solutions or metaheuristic components.
Methodological patterns: Metaheuristics research methodology captures many important
patterns. An example of particular importance is the notion of `best practice’
in terms of design and analysis of experiments. Achieving
consensus on `experimental templates’ would be invaluable to the metaheuristics community.
Equivalences: a `roadmap’ for navigating
between data-structures and/or algorithms, intended to suggest alternative
solution schemes to an experimenter, or maybe even to a (sufficiently curious)
automated design system.
Anti-patterns: Bad practices that should
be discouraged.
Call for Papers
Over the last 20 years, Evolutionary Computation
(and meta- and hyper- heuristics in general) has flourished, spawning an
enormous variety of algorithms, operators and representations.The
history of science and mathematics demonstrates that such proliferation is
inevitable in a growing field, but that in order to progress non-incrementally
it is periodically necessary to obtain a unifying perspective.
Existing EC/metaheuristic
frameworks provide a certain level of abstraction, but these are not generally
sufficient to capture cross-cutting concerns such as the application of
dimensionality reduction or neutrality-handling strategies. In particular, they
do not lend themselves to higher-level issues such as the automatic design of metaheuristics "in the large" (c.f. Dijkstra on software componentization).
The "Design Patterns" revolution in 1994
was successful in addressing analogous issues in the software industry. The
default level of discourse among practitioners was consequently significantly
increased, and today “factory method” and “chain of responsibility” are
software engineers’ lingua franca, immensely facilitating communication and
design of software systems.
We believe that the EC/metaheuristics
community needs and deserves a corresponding breakthrough. The domain of metaheuristics has good mathematical and conceptual
foundations, so nothing precludes the creation of a coherent and useful set of
concepts that moves our thinking about metaheuristics
up an abstraction level. For instance, as per the example below, it is possible
to consider hyper-heuristics in terms of the application of the well-known
composite pattern to metaheuristics. Framing
recurring methodological and algorithmic themes in terms of such Metaheuristic Design Patterns has been advocated in a
recent talk [1] and several papers [2,3]; some foundational work can be seen in
[4].
This workshop provides a forum for those interested
in contributing to the MDP vision and/or willing to demonstrate its usefulness
in practical and theoretical studies.
Expanded versions of sufficiently
high quality submissions
will be considered for inclusion
in a forthcoming book from Springer.
Scope
The workshop welcomes original submissions on all
applications of design patterns to metaheuristics, which
include (but are not limited to) the following topics and themes:
·
Applications of existing design patterns (e.g. from
[5]) to metaheuristics. Some examples are given in [1,4] and below.
·
New metaheuristic design
patterns. Algorithms and methodologies that might be expected to be widely
applicable but which have not yet been documented at the appropriate level of
abstraction.
·
Automated metaheuristic
design via patterns. An outline of one possible approach is given in the latter
part of [1]. There is also a wealth of pattern literature in the Software
Engineering (and Search-Based Software Engineering) community related to
software automation. Much of this is directly applicable to metaheuristic
design.
·
Pattern languages for metaheuristics.
See [4] for the definitive example.
Examples
·
Template-Method
Hyper-heuristics.
·
Hyper-heuristic
as Composite.
·
Interactive Solution
Presentation.
Submission instructions
Submitted papers should follow the standard
GECCO sig-alternate ACM format, and be between
2 and 4 pages in length.
The prototypical recommended structure for the pattern description can be
found in [4], and an appropriately formatted example is Template-Method Hyper-heuristics.
Please see the GECCO 2014 information for authors
for further details. Note that the review process of the workshop is not
double-blind and hence authors' information should appear in the paper.
All accepted papers will be presented at the
workshop and appear in the GECCO workshop volume.
Proceedings of the workshop will be published on
CD-ROM, and distributed at the conference.
Papers should be submitted by 28 March, 2014 in PDF
format to:
[jerry.swan -at-
cs.stir.ac.uk] containing the subject line "Metaheuristic
Design Patterns Workshop".
Important Dates
Paper submission deadline: 28 March, 2014.
Notification of acceptance: April 15, 2014.
Camera-Ready Accepted Papers Due: April 25, 2014.
GECCO-2014:
July 12-16, 2014.
Workshop organizers
Jerry Swan - University of Stirling, United
Kingdom.
jsw –at- cs.stir.ac.uk
John Clark - University of York, United Kingdom.
john.clark -at- cs.york.ac.uk
Krzysztof Krawiec - Poznan University of
Technology, Poland.
krawiec –at- cs.put.poznan.pl
Chris Simons - University of the West of England,
United Kingdom.
chris.simons -at- uwe.ac.uk
John Woodward - University of Stirling, United
Kingdom.
jrw –at- cs.stir.ac.uk
References
[1]
Jerry Swan. Metaheuristic
Design Patterns.
[2]
Krzysztof Krawiec and Jerry Swan, Pattern-guided genetic programming. GECCO
2013.
[3] John R. Woodward and Jerry Swan, The automatic
generation of mutation operators for genetic algorithms, GECCO 2012.
[4] Natalio Krasnogor. Handbook of Natural
Computation, chapter “Memetic Algorithms”. Natural Computing. Springer Berlin /
Heidelberg, 2009.