Project for the 2023-24 course of Global and Multi-Objective Optimization at Units. The goal of the project is to implement a Genetic Algorithm to solve the Graph Coloring problem.
In this project we implement two Genetic Algorithms to solve the Graph Coloring problem.
The Graph Coloring problem consists in assigning a color to each vertex of a graph such that no two adjacent vertices have the same color. It is a NP-hard problem.
In particular, we tackle the decision version of the problem, that is, given a graph
The genetic algorithm is implemented in two ways: a naive version and a more problem-specific version. the naive version is a general implementation of a genetic algorithm, while the problem-specific uses more specific selection and mutation operators.
Additionally, sudoku problems are a special case of the Graph Coloring problem, where the graph is fixed and a 9-coloring is searched. An implementation of the algorithm described above is used to solve sudoku problems.
To install the project, clone the repository and install the requirements:
git clone [email protected]:Brusa99/GA4GraphColoring.git
cd GA4GraphColoring
pip install -r requirements.txtAdditionally, to run the examples jupyter and matplotlib are required.
The project can be used as a library, for example:
import ga4graphcoloring as ga
# Create a graph and a population to color it
graph = ga.Graph(n_vertices=10, density_factor=0.5)
pop = ga.Population(max_colors=4, pop_size=20, graph=graph)
# Run the genetic algorithm
for it in range(100):
pop.evolve()
if pop.best_fitness == 0:
print(f"Solution found in {it} iterations")
print(f"Solution: {pop.solution}")
breakFor more examples, see the examples directory.