Graph Coloring with Genetic Algorithms

University of Piraeus | Department of Informatics

BSc course: Artificial Intelligence and Expert Systems

Semester: 6

Project Completion Year: 2023

Description

This project implements a graph coloring algorithm using genetic algorithms.

The goal is to color a given graph using a limited palette of four colors: blue, red, green, and yellow, ensuring that no two adjacent vertices share the same color.

Features

• Random Initial Population: The algorithm starts with a randomly generated population of potential solutions, consisting of 100 individuals represented as strings of length 16, where each character corresponds to a color (Blue, Green, Yellow, Red).
• Fitness Function: A custom fitness function evaluates the quality of each solution based on the number of conflicts (adjacent vertices with the same color). The fitness values are normalized to convert the minimization problem into a maximization problem.
• Selection Process: A tournament selection mechanism is employed to choose parent solutions for reproduction, with a partial population renewal rate of 60%.
• Crossover and Mutation: The algorithm incorporates single-point crossover and mutation techniques, where a character mutation is applied to 10% of the population with the lowest fitness values.
• Elitism: The best solution (with the highest fitness value) is carried over to the next generation to ensure that the quality of solutions does not degrade.
• Population Maintenance: The remaining solutions are randomly filled to maintain a population size of 100 for the next generation.
• Graph Representation: The input graph is represented in a JSON format, detailing nodes and their neighboring nodes, which is loaded at the start of the algorithm.
• Visualization: The final solution can be visualized through a graph representation, allowing for an intuitive understanding of the coloring results.

How to Run

1. Clone the repository:

git clone https://github.com/dimitrisstyl7/genetic-algorithm-project.git

2. Navigate to the project directory:

cd genetic-algorithm-project

3. Create and activate a virtual environment:

On Linux/Mac

python3 -m venv venv
source venv/bin/activate

On Windows

python -m venv venv
venv\Scripts\activate

4. Install dependencies:

pip install -r requirements.txt

5. Run the program:

On Linux/Mac

python3 genetic_algorithm.py

On Windows

python genetic_algorithm.py

Execution Output Example

Acknowledgments

This project was developed as part of the "Artificial Intelligence and Expert Systems" BSc course at the University of Piraeus. Contributions and feedback are always welcome!

License

This project is licensed under the MIT License - see the LICENSE file for details.