Graph Partitioning Using Genetic Algorithms

Shiraz University - CSE Dept - Project # 3

M.M.Haji
mehdi.haji@gmail.com

Problem Definition:

In this project, we apply a GA to the graph partitioning problem which is a combinatorial problem and needs special mutation and cross-over operators. Graph partitioning has applications in VLSI layout design. The problem is as follows: Consider we have the graph G(V,E) where V is the set of vertices and E is the set of edges of the graph, the aim is to partition V into two disjoint and non-empty subsets V1 and V2 ( they don't need to be of the same size ) such that the edges between these two sets are minimized. For example, the following graph has obviously {1,3,6,7} as one partition and {0,2,4,5} as another partition:

And there is only two edges between these two partitions.

It is obvious that the order of this problem is exponential, and the search space size is 2^|V| - 2 ( that is the number of non-empty subsets of V ) so it is not possible to use an exhaustive search for large |V|. So a GA is a good technique to solve this problem because it finds a good ( or even the best ) solution in a short amount of time.

Implementation:

The program reads the graph description from a text file, in this file each line is a comment ( started with // ) or an empty line or otherwise specifies an edge of the graph, such that the first number on this line is the starting vertex, the second is the ending vertex and the third is the weight of this edge. And it is assumed that the graph is directed so each line represents one edge ( not two edges as in undirected graphs ). For example, the above graph is represented by graph.txt.

The chromosome representation is a "pick list" of vertices. For example, the pick list 0 0 2 2 0 0 0 would map the vertices 0 1 2 3 4 5 6 to 0 1 4 5 2 3 6. This comes about as follows: pick the 0'th vertex, which gives 0, then remove this from the list. Next, pick the 0'th vertex, which gives 1, then remove. Next pick the 2'nd vertex which gives 4 then remove. And this procedure continues for the remaining members of the pick list as well. The reason for this complicated chromosome representation is that it avoids the generation of invalid partitions which may otherwise have arisen by random selection in the initial population and the processes of crossover and mutation. If the vertex numbers itself were used as the chromosome, then the duplication would be unavoidable.

The implementation contains four java files:

GAUtils.java which contains useful procedures such as methods for working with pick lists and making random permutations.
GAIndividual.java which is a candidate solution for the graph to be partitioned. It has two disjoint and non-empty subsets of the graph vertices ( namely left and right ) which represent the partitions. In this class 1-point cross-over and some mutation operators is implemented such that applying each operator on one or two parents, generate a legal offspring.
GAPopulation.java which is a population of GAIndividuals. The main method of this class is generate, which generates a new population from the current population by cross-over, mutation and reproduction. The selection method is a tournament selection of size 10. Each GAPopulation evaluates the best, average and worst fitness of its individuals for later purposes.

GAEvolve.java which is the main class. It runs a simple GA with several initial populations and several runs over the same graph to find the solution, and finally makes a M file such that if executed in MATLAB the best fitness versus generation, average fitness versus generation and worst fitness versus generation are plotted. Let's look at its main method:

public static void main(String[] args) {

    GAIndividual.adj_matrix = GAUtils.readMatrix("graph.txt");
    int nvert = GAIndividual.adj_matrix.length; // number of vertices

    GAEvolve.evolveAndMakeMFile("ga.m",1,100,100,nvert,60,30);
}

In the first line, the graph is read from the text file garph.txt. In the second line, the number of vertices of the graph is stored in the variable nvert. In the third line the evolveAndMakeMFile method is called: the first argument is the M file name that will be generated, the second argument is the number of runs, the third and fourth argument are the number of generations and population size respectively, the fifth argument is the number of vertices of the graph to be partitioned, and the last two arguments are the cross-over and mutation rate respectively.

Download class files here: GAUtils.class, GAIndividual.class, GAPopulation.class, GAEvolve.class.

Compile and Run:

To compile and run the program, java 2 complier must be installed on your system. If so, execute the following commands:

javac GAUtils.java
javac GAIndividual.java
javac GAPopulation.java
javac GAEvolve.java
java GAEvolve

Results:

For the above graph, the genetic algorithm with 1 run, 100 generations, population size of 100, cross-over rate of 60% and mutation rate of 30%, found {4,0,2,5} and {6,1,3,7} as two partitions, that is obviously the correct answer. The following graph shows the algorithm has converged before generation 10: