Hyper-Heuristics with Graph-Transformations - School of Computing Seminar Series

Hyper-Heuristics is a search method for selecting and generating heuristics to solve combinatorial optimisation problems. A heuristic is a practical approach to problem solving that uses rule of
thumbs, educated guesses or trial and error which does not guarantee optimal results but often provides results “good enough” and “soon enough”.
Unfortunately heuristics, and the solutions they operate on, tend to have their own specific representation both in terms of underlying data structure and in the taxonomy used to describe their approach. Having to develop a specific representation and related operators for each new problem class limits the applicability of Hyper-Heuristics frameworks.
This talk will present the work undergone to provide a generic graph based representation for combinatorial optimisation problems and a description of heuristic operators based on graph transformations.
Graph transformation is a technique concerned with the modification of graphs based on category theory often used in the context of formal specification and software engineering.
This will include a comparison with classical techniques, a discussion of the trade-offs and a list of open issues.