# Genetic Hyper-Heuristics for Graph Layout Problems

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

```@PhdThesis{Koohestani:thesis,
author =       "Behrooz Koohestani",
title =        "Genetic Hyper-Heuristics for Graph Layout Problems",
school =       "Computer Science and Electronic Engineering,
University of Essex",
year =         "2013",
month =        "15 " # jan,
keywords =     "genetic algorithms, genetic programming",
URL =          "http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/Behrooz_PHDThesis_FinalVersion.pdf",
URL =          "http://www.essex.ac.uk/csee/news_and_seminars/newsEvent.aspx?e_id=5802",
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