09-02-2013, 04:39 PM
GENETIC ALGORITHM TO FIND SHORTTEST PATH
1GENETIC ALGORITHM.doc (Size: 95 KB / Downloads: 23)
ABSTRACT
The problem of finding the shortest path between two nodes is a well known problem in network analysis. Optimal routing has been widely studied for interconnection networks this paper considers the problem of finding the shortest path. A Genetic algorithm based strategy is proposed and the algorithm has been developed to find the shortest (Optimal) Path 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. Even though shortest path routing algorithms are already well established, there are researchers who are trying to find alternative methods to find shortest paths through a network. One such alternative is to use genetic algorithm (GA). GA is a multi-purpose search and optimization algorithm that is inspired by the theory of genetics and natural selection.