A Genetic algorithm approach to solve the shortest path problem for road maps

Abstract

This Research is to introduce a good Genetic Algorithm (GA) to find the solution for the shortest path problem that, is applicable in finding shortest path for road maps without taking longer computation time. Using a GA to optimize the parameters of the shortest path problem, again, optimizing will most likely mean finding an answer that is consistently good or satisfactory, though perhaps it may not be the perfect answer to the problem. A new method is found to solve the shortest path problem using GAs. The implemented algorithm has been tested for a road map containing more than 125 cities and the experimental results guarantee to provide acceptable solutions for the given search space. Major advantage of this algorithm is that when it converges to a solution it is able to find another set of possible solution by which the destination can be reached. So this is useful for finding multiple possible paths from source to destination. The problem in this algorithm is that, according to the initial population, the individuals may rapidly come to dominate the population causing it to converge on a local maximum as it is common for many GAs. Once the population has converged, the ability of the GA to continue to search for better solutions is effectively eliminated. However, the algorithm finds considerably good solutions for a given search space.