Application of Genetic Algorithm Technology to Graph Layout
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Publishing Venue
IBM
Related People
Abstract
A process is disclosed which addresses the following problem: Given a graph (e.g., nodes and connectors), provide a 2-dimensional layout of the graph with characteristics that render it "humanly" comprehensible. The characteristic focused upon here is the minimization of the number of line (connector) crossings. The algorithm used to achieve such a layout is based on genetic algorithm technology as described in [*]. The genetic algorithm starts with a population of trial solutions and generates successive populations through iterating cycles of reproduction, crossover, and mutation. Fitness of trial solutions is gauged against an evaluation function which is to be maximized. By the Schema Theorem [*], successive populations of solutions converge to optimal fitness.
Application of Genetic Algorithm Technology to Graph Layout
A process is
disclosed which addresses the following
problem: Given a graph (e.g., nodes and
connectors), provide a
2-dimensional layout of the graph with characteristics that render it
"humanly" comprehensible. The characteristic focused upon here is the
minimization of the number of line (connector) crossings. The
algorithm used to achieve such a layout is based on genetic algorithm
technology as described in [*]. The
genetic algorithm starts with a
population of trial solutions and generates successive populations
through iterating cycles of reproduction, crossover, and mutation.
Fitness of trial solutions is gauged against an evaluation function
which is to be maximized. By the Schema
Theorem [*], successive
populations of solutions converge to optimal fitness.
The layout is
realized in a fixed-size coordinate space.
Without loss of generality, the coordinate space is assumed to be the
upper right quadrant (positive x and y axes).
A graph is described
as a list of N nodes and R connectors.
Node position locations are
assumed restricted to integer coordinates, and the coordinate space
is assumed to be of sufficient size to accommodate any graph given as
input. A trial solution to the layout
problem consists of coordinate
assignments to each node with the provision that no two nodes have
the same coordinates. The coding of a
solution (termed a chromosome)
consists of N pairs of integers representing the positions of the
nodes. The initial population of
solutions is generated randomly.
The genetic
algorithm evaluation function is based on a
function g:{Chromosomes}TS where S is the positive real numbers. The
function g computes the number of improper crossings in the graph
whose layout is represented by some chromosome.
Since genetic
algorithms attempt to maximize the evaluation function, the
evaluation function used is: f(c)=Rx(R-1)/2-g(c) where
ce{Chromosomes}. Here, R is the number of connector lines defined by
the given graph description. This
ensures a non-negative function
which increases in value with fewer crossovers. f(c) is referred to
as the value of the chromosome c.
A complete
outline of the genetic layout algorithm is given
below. The reproduction technique used
is stochastic sampling with
replacement as described in (*, p. 121).
Also during the
reproduction cycle the fitness scaling technique used is outlined in
(*, pp. 76-79). The special
considerations that separate this
genetic algorithm from the standard genetic algorithm concern the
cross-over and mutation cycles of the algorithm to enforce that t...