A Genetic Hillclimbing Algorithm for the Optimal Linear Arrangement Problem

Article type: Research Article

Authors: Poranen, Timo

Affiliations: Department of Computer Sciences, P.O. Box 607, FIN-33014 University of Tampere, Finland. E-mail: tp@cs.uta.fi

Abstract: The optimal linear arrangement problem is defined as follows: given a graph G, find a linear ordering for the vertices of G on a line such that the sum of the edge lengths is minimized over all orderings. The problem is NP-complete and it has many applications in graph drawing and in VLSI circuit design. We introduce a genetic hillclimbing algorithm for the optimal linear arrangement problem. We compare the quality of the solutions and running times of our algorithm to those obtained by simulated annealing algorithms. To obtain comparable results, we use a benchmark graph suite for the problem. Our experiments show that there are graph classes for which the optimal linear arrangement problem can be efficiently approximated using our genetic hillclimbing algorithm but not using simulated annealing based algorithms. For hypercubes, binary trees and bipartite graphs, the solution quality is better and the running times are shorter than with simulated annealing algorithms. Also the average results are better. On the other hand, there also are graph classes for which simulated annealing algorithms work better.

Keywords: Genetic algorithm, optimization, hillclimbing, optimal linear arrangement problem

Journal: Fundamenta Informaticae, vol. 68, no. 4, pp. 333-356, 2005