GA Maximum Flow Solver – Network Optimization with Genetic Algorithm
Interactive visualization of evolutionary approach for Maximum Network Flow Problem
Artificial Intelligence course final project applying Genetic Algorithm to solve Maximum Network Flow Problem. Implemented custom GA operators: path-based crossover to maintain flow conservation, adaptive mutation for escaping local optima, and balance flow mechanism. Built interactive Python GUI for real-time graph editing, parameter tuning, and algorithm comparison with Ford-Fulkerson.
Timeline
2025
Type
Project
Status
completed
Outcome / Impact
- •Achieved up to 100% optimality ratio on graphs with ≤30 nodes, competitive with Ford-Fulkerson exact solution
- •Path-based crossover maintains flow conservation constraint, avoiding invalid offspring after genetic operations
- •Adaptive mutation automatically increases exploration when stuck at local optima (10+ generations no improvement)
- •Built interactive GUI: real-time graph editing, parameter tuning, fitness evolution chart, top-5 solutions ranking
Tech / Skills
Case Study
1) Context / Problem
Maximum Network Flow is a classic optimization problem with applications in transportation, logistics, and data networks. Traditional algorithms like Ford-Fulkerson guarantee optimal solutions but are limited to standard formulations. GA offers flexibility for extended variants (multi-objective, dynamic networks) but faces challenges in maintaining flow conservation constraints after crossover/mutation.
2) Your Role
As Team Lead, I coordinated 4 team members, designed and implemented the interactive GUI with graph editor, integrated the GA solver with visualization components, and compiled the final report. Responsible for overall project architecture and user experience design.
3) Approach
Implemented dictionary-based individual representation (edge→flow mapping) instead of matrix for easier constraint handling. Key operators: (1) Biased initialization prioritizing source/sink edges, (2) Path-based crossover combining augmenting paths from parents, (3) Adaptive mutation rate that increases when no improvement for 10+ generations, (4) Balance flow post-processing (limited to 3 passes) to restore conservation. Used tournament selection + elitism for selection pressure.
4) Result / Impact
On small graphs (≤30 nodes): 95-100% optimality ratio. On larger graphs (40+ nodes): 50-65% ratio with increased computation time. Parameter sensitivity analysis showed population size 50, mutation rate 0.1-0.2, and top-k=10 elitism yielded best results. Compared with Ford-Fulkerson: GA is slower but more flexible for constraint extensions.
5) Learnings
Balance flow is essential but can destroy genetic information if too aggressive - limited to 3 passes. Path-based crossover preserves constraint better than random edge crossover. Adaptive mutation prevents premature convergence. Future work: parallel GA implementation, hybrid with local search, multi-commodity flow extension.
6) Links
See links above.