Genetic Algorithms for Planarization Problems

F. Comellas Departament de Matemàtica Aplicada i Telemàtica Universitat Politècnica de Catalunya ETSE Telecomunicació, Girona Salgado s/n E-08034 Barcelona, Catalonia, Spain

Abstract

Two near-optimum planarization algorithms are presented. The algorithms belong to a general class of algorithms known as genetic algorithms because the search procedures on which they are based are inspired on the mechanics of natural selection and natural genetics. The first algorithm is intended to generate a near-maximal planar subgraph from a given graph and also provides the routing information needed to embed the subgraph on the plane. The second planarization algorithm studied finds a near-maximum independent set of a circle graph. This algorithm may be used for finding a routing on one layer from a set of n two-pin nets in a channel. After small modifications, it may also be used to predict the secondary structure of ribonucleic acids. The main advantage of both algorithms is that they are easily implemented in a parallel computer.

Proc. of the 13th IMACS World Congress on Computation and Applied Mathematics July 22-26, 1991, Trinity College, Dublin, Ireland, pp. 211-212

1 Introduction

Genetic algorithms were first introduced by J.H. Holland in the 60’s, and have been successfully applied to pattern recognition, classifier systems, pipeline operations, scheduling, symbolic system evolution, and some other problems (see [1] for an extensive description and bibliography).

Genetic algorithms try to find the best solution in a general state space of solutions to the problem studied. The starting point is always a collection of possible solutions generated at random. This set is known as generation. At each iteration a new collection of solutions (a new generation) is obtained by mating the best of the old solutions with one another. Some randomness is also introduced through a mechanism called mutation, to ensure that the algorithms may avoid getting stuck at local minima. If a new solution is superior to its parents, it joins the list of preferred breeders that will be used for calculating the next generation. At each generation the best solution is recorded. The algorithm ends when the results stabilize or the optimum, when it may be identified, is reached.

The main aim of this work is the study of the applicability of genetic algorithms to some problems related to the planarization of graphs.

2 Graph planarization

The first graph planarization problem studied is directly related to the design of printed circuit boards and the routing of very large scale integration circuits (VLSI), and consists of finding a near-maximal (or maximal) planar subgraph from a given, in general non-planar, graph. The genetic algorithm not only yields this near-maximal subgraph but also provides the routing information for the embedding on the plane of the subgraph found. See Figure 1.

The second algorithm presented here, finds a near-maximum independent set of a circle graph. An independent set in a given graph is a set of vertices, no two of which are adjacent. An independent set with the largest possible cardinality is a maximum independent set of the graph. A circle graph is the graph associated to a finite set of chords of a circle in such a way that each vertex of the graph corresponds to a chord and that there is an edge between each pair of vertices whose corresponding chords intersect. The algorithm may be used directly for finding a routing on one layer from a set of n two-pin nets in a channel. See Figure 2.

A modification of the algorithm, based on [2], is discussed. It is useful for predicting the secondary structure of ribonucleic acids (RNA). The primary structure of RNA is determined by the sequence of organic bases. The folding of the chains into a two-dimensional shape determines the secondary structure. Nonintersecting edges in a circle graph may be related with the base pairs for this folding. To generate a stable RNA structure there it is required to maximize the number of nonintersecting edges or base pairs. The use of the RNA structure stability model from Tinoco et al. [3], enables the computation of the stability number of the resulting structures and the comparison with the results obtained by other authors.

3 Implementation details

In the implementation of the algorithms one important point to be considered is the codification of the solutions that should facilitate the reproduction and mutation processes. For both algorithms, the graph is represented by a list. Each element of the list corresponds to an edge of the graph and its value indicates if the edge is being considered in that solution and, for the first algorithm, the corresponding routing. The list is known in the terminology of genetic algorithms as a gene.

Another aspect of relevance is the definition of the cost functions that will be used for the evaluation of the solutions. For the first algorithm the cost function Figure 1: Convergence of the genetic algorithm to a solution of the planarization problem. (a) Single-row representation of the best solution at the first generation.

(b) Representation of the optimal solution found several generations later.

Figure 2: The final state for a circle graph problem evolution. Dashed chords are not considered.

takes into account the number of edges considered and the number of cuts between them. The cost function in the second algorithm depends also on the length of the chords.

Other parameters that affect the efficiency of the algorithms are the population size and the crossover and mutation rates.

4 Conclusions

The results show that the algorithms perform well, and that with a similar (or less) computational effort than in other approaches (heuristic methods, neural networks, simulated annealing ...) it is possible to obtain the seeked solutions.

The main advantage of the method arises from its simplicity and from the fact that the algorithms, by its own nature, may be easily implemented in a parallel computer.

References

[1] D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.

[2] Y. Takefuji, L.L. Chen, K.C. Lee and J. Huffman, “Parallel Algorithms for finding a near-maximum independent set of a circle graph ”, IEEE Trans. Neural Nets., vol. 1(3), pp. 263-267, 1990.

[3] I. Tinoco, O.C. Uhlenbeck and M.D. Levine, “Estimation of secondary structure in ribonucleic acids”, Nature, vol. 230, pp. 362-367, 1971.