micycle.pgs.commons

Class GeneticColoring<V,E>

java.lang.Object

micycle.pgs.commons.GeneticColoring<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

org.jgrapht.alg.interfaces.VertexColoringAlgorithm<V>

public class GeneticColoring<V,E>
extends Object
implements org.jgrapht.alg.interfaces.VertexColoringAlgorithm<V>

Finds a solution to a graph coloring using a genetic algorithm.

This class implements the technique described in Genetic Algorithm Applied to the Graph Coloring Problem by Musa M. Hindi and Roman V. Yampolskiy.

The genetic algorithm process continues until it either finds a solution (i.e. 0 conflicts between adjacent vertices) or the algorithm has been run for the predefined number of generations.

The goal of the algorithm is to improve the fitness of the population (a coloring) by mating its fittest individuals to produce superior offspring that offer a better solution to the problem. This process continues until a terminating condition is reached which could be simply that the total number of generations has been run or any other parameter like non-improvement of fitness over a certain number of generations or that a solution for the problem has been found.

Author:

Soroush Javadi, Refactored for JGraphT by Michael Carleton

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm

org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring<V>, org.jgrapht.alg.interfaces.VertexColoringAlgorithm.ColoringImpl<V>

Constructor Summary

Constructors

Constructor and Description
GeneticColoring(org.jgrapht.Graph<V,E> graph) Creates with a population size of 50; "the value was chosen after testing a number of different population sizes.
GeneticColoring(org.jgrapht.Graph<V,E> graph, int maxGenerations, int populationSize, int fitnessThreshold)

Method Summary

Modifier and Type	Method and Description
org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring<V>	getColoring()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GeneticColoring

public GeneticColoring(org.jgrapht.Graph<V,E> graph)

Creates with a population size of 50; "the value was chosen after testing a number of different population sizes. The value 50 was the least value that produced the desired results".

Parameters:

graph -

GeneticColoring

public GeneticColoring(org.jgrapht.Graph<V,E> graph,
                       int maxGenerations,
                       int populationSize,
                       int fitnessThreshold)

Method Detail

getColoring

public org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring<V> getColoring()

Specified by:

getColoring in interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm<V>