Precise Evolution: Optimizing Shortest Path Routing with Genetic Algorithms and Population Sizing

TL;DR

The paper presents a robust Genetic Algorithm (GA) for the Shortest Path (SP) problem that breaks the limitations of traditional evolutionary routing. By using variable-length chromosomes, position-independent crossover, and a mathematical population-sizing model based on the Gambler's Ruin theory, the authors achieve faster convergence and higher path optimality than previous SOTA GA methods and even outperform Dijkstra’s algorithm in large-scale execution time.

Background & Positioning

Shortest Path (SP) routing is the backbone of the Internet and Mobile Ad-hoc Networks (MANETs). While Dijkstra’s algorithm is the "gold standard" for fixed networks, its polynomial complexity becomes a bottleneck in rapidly changing topologies. This paper positions the GA not just as a heuristic, but as a scalable, hardware-friendly alternative that can be mathematically tuned for specific Quality of Service (QoS) requirements.

The Problem: Why Previous GAs Failed

Most early GA approaches for routing were plagued by two issues:

1. Positional Dependency: Crossover often required identical nodes to be at the same index in two parent chromosomes. In variable-length routes, this is rare, stifling the search space.
2. Infeasible Offspring: Random crossover often creates loops. Previous methods used expensive "repair" functions (like re-running Dijkstra), which defeated the purpose of using a GA for speed.

The Methodology: Smart Crossover and Analytical Sizing

1. Position-Independent Crossover

The core innovation is the crossover mechanism. Instead of looking for matching indices, the algorithm identifies any common node (excluding source/destination) between two parent paths.

In the figure above, nodes 3 and 2 are shared across different positions, allowing for a flexible exchange of partial routes.

2. The Gambler’s Ruin Population Model

Determining population size ($n$) is usually a "black art." The authors utilize the Gambler's Ruin model, which treats the survival of beneficial "building blocks" (BBs) in a population like a gambler trying to reach a winning streak.

They derived a generalized equation: $n=-\frac{{\chi }^k}{2}\cdot \ln (\alpha )\cdot \left(\frac{{\chi }^k-1}{2}\cdot \sqrt{\pi m^{\prime }}+1\right)$ Where:

• $\chi$: Alphabet cardinality (average node connectivity).
• $k$: Average order of building blocks.
• $\alpha$: Probability of GA failure.

Experimental Validation

The authors tested their approach against Munemoto’s and Inagaki’s algorithms across various network sizes (15 to 50 nodes).

Convergence Speed

The proposed GA reached convergence in significantly fewer fitness evaluations. For a 30-node network, it was 1.92x faster than Munemoto's and 7.27x faster than Inagaki's.

Note: The proposed algorithm (bottom line) reaches the optimal cost much faster than competitors.

Scalability vs. Dijkstra

Interestingly, as network size grows, the computation time of Dijkstra's increases significantly, whereas the proposed GA remains relatively flat and efficient, especially when considering potential hardware acceleration.

Critical Insight & Conclusion

The real value of this paper isn't just a "faster GA"; it's the bridge between evolutionary heuristics and statistical reliability. By providing an equation to size the population based on a desired failure probability ($\alpha$), the authors transform the algorithm into a predictable engineering tool.

Limitations: While the sizing equation is highly accurate for optimality targets $>90\%$, it tends to become an "upper bound" (overestimated size) for lower-quality targets. Future work could refine the average order ($k$) calculation for extremely dense or sparse topologies.