MetaDeeP 2014 – Metaheuristic Design Patterns

Workshop at GECCO 2014 Conference, Vancouver, BC, Canada. 12-16 July 2014.

[Workshop Program]

 

 

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.

·         Representative.

·         Candidate Solution Repair.

 

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.

 

[5] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Boston, USA. 1995.

 

Site Meter