WG211/M18Barwell

Adam Barwell Folds, Unfolds, and Metaheuristics: Towards Automatic Rewriting and Derivation of Metaheuristics

Abstract. Metaheuristics are families of algorithms that describe how to achieve acceptable solutions for hard optimisation problems. Current approaches to the design, development, and transformation of metaheuristics algorithms are predominantly ad hoc and error-prone. In this paper, we describe preliminary work on a dependently-typed representation of metaheuristics that uses the well-understood laws of hylomorphisms to facilitate the safe and automatic rewriting of metaheuristic algorithms. In the full paper we will provide a rewrite system and decision procedure for transforming, and ultimately deriving known algorithms; e.g. deriving Tabu Search or Ant Colony Optimisation from Hill-Climbing. This approach will provide a formal foundation for not only the definition of metaheuristic algorithms, but also the comparison of metaheuristic algorithms with regard to specific problems.