Package 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 extends Object>, org.jgrapht.alg.interfaces.VertexColoringAlgorithm.ColoringImpl<V extends Object>

  • Constructor Summary

    Constructors
    Constructor
    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
    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 Details

    • 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 Details

    • getColoring

      public org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring<V> getColoring()
      Specified by:
      getColoring in interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm<V>