The Graph Colouring Problem
In mathematics, particularly graph theory, a graph is a representation of a set of objects interconnected with links. Every object, known as node (or vertice, or point), represents a given element of an object which could be abstract (mathematical operation) or physical (person, material, etc.) and the relatinoship between them.
Here we present a genetic algorithm used to solve the graph coloring problem using as basis the solution implemented on [1].
Here we present a genetic algorithm used to solve the graph coloring problem using as basis the solution implemented on [1].
ga-master.zip | |
File Size: | 367 kb |
File Type: | zip |
ga_02_graphjavaver.tar.gz | |
File Size: | 528 kb |
File Type: | gz |
Functional algorithm in C++
How does it work?
1. The application reads a file settings.txt that contains the specifications for the Genetic Algorithm such as the population size and generations number. 2. The application reads a file called test.col that contains the graph in DIMAC format [3]. In this case the graph represents the one shown in figure 1. 3. The application stores each of the node's connections as a row in an integers vector. Ex. Vector [0] --- Represents node [1] --- Connections {[2], [3]} Vector [1] --- Represents node [2] --- Connections {[1], [4], [5]} .... Vector [4] --- Represents node [5] --- Connections {[2], [3], [4]} 4. The genetic algorithm generates a population set which represents a solution assigning a random color to each node where the initial number of colors available is equal to the number of nodes + 1. 5. The algorithm takes each of the node's colors and compares it with the colors of the connected nodes. If they're similar, then it adds to the number of conflicts, otherwise adds to the number of non-conflicts. 6. Calculates the cost function which is: Cost = 1 - [conflicts / (conflicts-non_conflicts)] 7. Selects, evolves and evaluates iteratively until it finds the solution with zero conflicts. If found, the algorithm decrements the color number. Otherwise it displays the result with the least number of colors required so that the nodes don't conflict.
|
[1] https://github.com/Mati20041/GA
[2] http://ceur-ws.org/Vol-841/submission_10.pdf
[3] http://dimacs.rutgers.edu/Challenges/
[4] http://mat.gsia.cmu.edu/COLOR/instances.html
[2] http://ceur-ws.org/Vol-841/submission_10.pdf
[3] http://dimacs.rutgers.edu/Challenges/
[4] http://mat.gsia.cmu.edu/COLOR/instances.html