A genetic algorithm for shortest path routing problem and the sizing of populations
Chang Wook Ahn, R. S. Ramakrishna · IEEE Transactions on Evolutionary Computation · 2002
This paper presents a genetic algorithmic approach to the shortest path (SP) routing problem. Variable-length chromosomes (strings) and their genes (parameters) have been used for encoding the problem. The crossover operation exchanges partial chromosomes (partial routes) at positionally independent crossing sites and the mutation operation maintains the genetic diversity of the population. The proposed algorithm can cure all the infeasible chromosomes with a simple repair function. Crossover and mutation together provide a search capability that results in improved quality of solution and enhanced rate of convergence. This paper also develops a population-sizing equation that facilitates a solution with desired quality. It is based on the gambler ruin model; the equation has been further enhanced and generalized. The equation relates the size of the population, quality of solution, cardinality of the alphabet, and other parameters of the proposed algorithm. Computer simulations show that the proposed algorithm exhibits a much better quality of solution (route optimality) and a much higher rate of convergence than other algorithms. The results are relatively independent of problem types for almost all source-destination pairs. Furthermore, simulation studies emphasize the usefulness of the population-sizing equation. The equation scales to larger networks. It is felt that it can be used for determining an adequate population size in the SP routing problem.
Cited by 683 works. doi:10.1109/tevc.2002.804323
Authors
References
- Genetic algorithms in search, optimization, and machine learning
- Adaptation in Natural and Artificial Systems
- Genetic Algorithms in Search, Optimization and Machine Learning
- Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers
- Genetic Algorithms
- Routing Information Protocol
- An efficient routing protocol for wireless networks
- Uniform crossover in genetic algorithms
- An Analysis Of The Behavior Of A Class Of Genetic Adaptive Systems.
- Genetic algorithms, noise, and the sizing of populations