IMPROVING THE EFFICIENCY OF THE SHORTEST PATH ROUTING PROBLEM WITH GENETIC ALGORITHM
Mingming Chen · Journal of Petrochemical Universities · 2005
A genetic algorithmic approach to the shortest path (SP) routing problem in large network was presented in order to improve the efficiency of computation. Encoding chromosome with variable length was applied for improving the efficiency of solving problem. A search capability that can improve quality of solution and enhance rate of convergence for network with lots of nodes is found by making crossover and mutation. Because crossover and mutation may generate infeasible chromosomes,a simple repair function is used to cure all the infeasible chromosomes, which keep the diversity of the population and can be used for computation of genetic algorithm to improve the efficiency of computation. Simulation results for SP in the large network indicate that the using time of GA is less than that of Dijkstra algorithm in the same network. So the efficiency of the genetic algorithm is much better than that of the Dijkstra algorithm for SP in large network.