Adaptive Genetic Algorithm for the Maximum Diversity Problem (MDP)

This repository contains the implementation and analysis of an Adaptive Genetic Algorithm (GA) designed to solve the Maximum Diversity Problem (MDP). The project focuses on developing an evolutionary system capable of dynamically adjusting to the characteristics of each problem instance, exploring different diversity models and selection strategies.

Academic Context

This project was developed for the Modeling course within the Bachelor's Degree in Mathematics and Computer Science at the Technical University of Madrid (UPM).

• Authors: María Sáez Díaz & Diego González Molina.
• Supervisor: Prof. Luis Magdalena Layos.
• Year: 2024-2025

Key Features

The algorithm implements a progressive and modular approach with the following key functionalities:

• Diversity Models:

  • MaxSum: Maximization of the total sum of distances (average dispersion).
  • MaxMin: Maximization of the minumum distance (uniform dispersion to avoid clustering).

• Adaptive Mechanism:

  • Repair Mechanism: Hierarchical strategy to ensure valid individuals after crossover, preserving common genes from parents.
  • Hybrid Selection: Combination of tournament/roulette strategies with diversity injection relative to the elite population.

• Tech Stack:

  • DEAP: Main evolutionary computation framework.
  • Pulp: Linear solver for exact solution benchmarking.
  • Scikit-learn (MDS): Dimensionality reduction for 2D visualization of solutions.

Repository Structure

MDP-Adaptive-GA/
├── src/                # Python Source Code
│   ├── main.py         # Entry point and execution configuration
│   ├── gen1.py         # GA Logic with DEAP (fitness, operators, adaptation)
│   ├── utils.py        # MDPLIB file parsing and helper tools
│   ├── plotting.py     # Evolution and fitness visualization
│   └── ...
├── data/               # Problem instances (MDPLIB format)
├── docs/               # Project Documentation and Report (PDF)
└── results/            # Output images and execution logs

Installation & Usage

1. Clone the repository:

git clone [https://github.com/maariia-saez/MDP-Adaptive-GA.git](https://github.com/maariia-saez/MDP-Adaptive-GA.git)
cd MDP-Adaptive-GA

2. Install dependencies:

pip install -r requirements.txt

3. Run the algorithm:

python src/main.py

Results & Visualization

The system automatically generates:

• Evolution Plots: Tracking of maximum, average, and minimum fitness per generation.
• 2D Maps (MDS): Spatial visualization of selected elements to compare the distribution between MaxSum anf MaxMin approaches.

📚 Data Source

The benchmark instances used for testing were obtained from the MDPLIB (Maximum Diversity Problem Library).

• Source: http://www.optsicom.es/mdp/
• Reference: Martí, R., Gallego, M., Duarte, A., & Laguna, M. (2010). Heuristics and metaheuristics for the maximum diversity problem. Journal of Heuristics.

The repository includes a subset of these instances (specifically from the GKD and SOM sets) located in the data/ directory for demonstration purposes.

This is an academic and educational project.