Demo - Genetic Algorithm

Genetic Algorithm for Graph Optimization

Overview

This simulation applies a Genetic Algorithm (GA) to solve a Minimum Spanning Tree (MST) problem, aiming to minimize the total edge weight while ensuring all nodes remain connected.

How It Works

1. Graph Generation → A random weighted graph is created, with nodes distributed across a canvas.

2. Population Initialization → Multiple potential solutions (subsets of edges) are randomly generated.

3. Fitness Calculation → Each solution is evaluated based on the total edge weight while maintaining connectivity.

4. Selection → The best candidates are more likely to be chosen as parents for the next generation.

5. Crossover & Mutation → Offspring are produced by combining edges from parents and introducing small random changes.

6. Iteration → The process repeats over multiple generations, evolving toward an optimal MST.

Key Features

✅ Graph Visualization → Nodes and edges are dynamically rendered, with optimal solutions appearing in red.
✅ Real-Time Logging → Displays best fitness scores over generations.
✅ Genetic Algorithm Operations → Implements selection, crossover, and mutation for solution improvement.
✅ Adaptive Evolution → The algorithm progressively refines the network for minimum cost connectivity.

Applications

✔ Network Optimization → Reducing costs in telecom, transportation, and logistics networks.
✔ Circuit Design → Ensuring efficient wiring in VLSI chip layouts.
✔ AI in Robotics → Helping autonomous agents optimize navigation paths.
✔ Supply Chain & Routing → Finding minimal-cost paths for deliveries and logistics.