- author = "Behrooz Koohestani",
- title = "Genetic Hyper-Heuristics for Graph Layout Problems",
- school = "Computer Science and Electronic Engineering, University of Essex",
- year = "2013",
- address = "UK",
- month = "15 " # jan,
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/Behrooz_PHDThesis_FinalVersion.pdf",
- broken = "http://www.essex.ac.uk/csee/news_and_seminars/newsEvent.aspx?e_id=5802",
-
URL = "
https://www.essex.ac.uk/people/POLIR15101/Riccardo-Poli#behrooz",
- size = "181 pages",
- abstract = "Graph layout problems are a special class of combinatorial optimisation problems, aiming at discovering a linear layout of an input graph such that a certain objective function is optimised. A linear layout is a labelling of the nodes of a graph with unique integers. Graph layout problems are mainly NP-complete, meaning that a guaranteed optimal solution cannot be reached in polynomial time. Because a large number of problems in science and engineering can be formulated as graph layout problems, a variety of methods have been proposed for addressing them. These methods are mainly heuristic in nature and based on graph-theoretic concepts. The best graph-theoretic heuristic algorithms can produce good-quality solutions in a short time, but, of course, they do not guarantee the optimality of the solutions obtained, and the solutions may be far from ideal. Meta-heuristic and Hyper-heuristic approaches are popular alternatives to classical optimisation techniques in a variety of domains. However, in the case of graph layout problems, there has been a limited exploration of such methods. Although meta-heuristics applied to these problems have shown to typically produce better results than graph-theoretic heuristics, in practice, graph-theoretic heuristics are much more preferred due to being substantially faster and more reliable. This thesis presents Genetic Hyper-Heuristics, which are heuristic search algorithms, exploring the space of problem solvers. They are designed to automatically evolve heuristic algorithms for graph layout problems. The evolved heuristics are reusable, meaning that they are intended for use on unseen problems. The central organising element of the genetic hyper-heuristics is a specialised Genetic Programming system. In addition to its application as a hyper-heuristic, our proposed genetic programming system can be used as a meta-heuristic in order to solve this class of problems. This is also presented in the thesis. In this study, we particularly focus on two of the most important graph layout problems, namely bandwidth and envelope reduction problems, and use them as testbeds for our algorithms. In order to assess the performance of the heuristics generated, we evaluate them on a large set of standard benchmark matrices from the Harwell-Boeing sparse matrix collection against the best bandwidth and envelope reduction algorithms from the literature. The results obtained show that the evolved heuristic algorithms are able to outperform state-of-the-art human-designed algorithms. In addition to being highly effective, the heuristics generated by our hyper-heuristic methods are very fast, and therefore suitable for practical use.",
-
notes = "Sloan Algorithm, GHH3 S*+
Supervisor: Riccardo Poli",
