Genetic Algorithm for Set Covering Problem

This project implements and optimizes a Genetic Algorithm to solve the Set Covering Problem (SCP). Given a universe of 100 elements and a collection of subsets, the algorithm finds the minimum number of subsets needed to cover every element in the universe.

Features

• Genetic Algorithm with elitism, culling, crossover, and mutation
• Fitness function that minimizes the number of subsets used while enforcing full coverage
• Coverage repair mechanism to ensure all individuals are always valid solutions
• Early stopping based on a time limit (45 seconds) or stagnation detection
• Random SCP instance generation with configurable number of subsets
• JSON-based problem input and output for reproducibility
• Fitness progression plot generated after each run

Requirements

• Python 3.x
• Matplotlib

Installation

1. Clone this repository
2. Install the required packages: pip install matplotlib
3. Ensure scp_test.json is present in the project directory, or let the script generate a new instance automatically

Usage

Run the main script:

    python 2021A3PS3056G_YASHI.py

The script will generate a random SCP instance with 150 subsets over a universe of 100 elements, write it to a JSON file, read the problem from scp_test.json, run the genetic algorithm, and print the best solution found along with the minimum number of subsets required.

To generate a custom SCP instance separately:

    python SetCoveringProblemCreator.py 100 150

This creates a JSON file scp_150.json with 150 subsets over a universe of 100 elements.

Algorithm Parameters

• Population size: 100
• Max generations: 1000
• Mutation rate: 0.01
• Elitism rate: 0.01 (top 1% preserved each generation)
• Culling rate: 0.95 (bottom 95% removed each generation)
• No-improvement limit: 100 generations before early stopping
• Time limit: 45 seconds

Note

The algorithm stops early if no improvement is seen for 100 consecutive generations or if the 45-second time limit is exceeded. Results may vary between runs due to the randomized nature of the algorithm.