Application of Genetic Algorithm Technology to Graph Layout

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...