This repository contains the implementation of a Genetic Algorithm (GA) to solve the Set Cover Problem (SCP), an NP-hard optimization problem where the objective is to cover a universe of elements using the minimum number of subsets.
Given a universe of elements and a collection of subsets, the goal is to find the smallest combination of subsets that covers all elements in the universe.
The solution leverages a Genetic Algorithm (GA) to find near-optimal solutions. The GA workflow involves:
- Population Initialization: A random set of individuals representing potential solutions (subset selections).
- Fitness Evaluation: Individuals are evaluated based on their subset count and universe coverage.
- Selection: Fitter individuals are more likely to be selected for crossover.
- Crossover & Mutation: New individuals are generated by combining parent solutions and introducing random mutations for diversity.
- Elitism: Top-performing individuals are preserved across generations.
- Termination: The algorithm runs for a set number of generations or until convergence.