Genetic Hyper-Heuristics for Graph Layout Problems

Created by W.Langdon from gp-bibliography.bib Revision:1.4549

  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 =          "",
  URL =          "",
  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",

Genetic Programming entries for Behrooz Koohestani