Research on Multi-objective Shortest Path Based on Genetic Algorithm

The shortest path problem is a search for the shortest or minimum path between the source and destination under the relevant parameter constraints, and it is an effective method for solving network routing problems. Many good algorithms have been proposed by researchers for single-parameter shortest path problems, but the process of finding shortest paths for multiple parameters is an NP-complete problem, and less research has been done. In this paper, a multi-objective shortest path algorithm MQGASP based on genetic algorithm is proposed, which regards the feasible solution of the nearest ideal solution of partial distance measurement as the solution to be found. Because the priority based coding method can potentially represent all possible paths in the directed graph, it can well represent the paths in the network graph with chromosomes. Simulation experiments show that the MQGASP algorithm has better performance in solving multi-QoS routing and is able to find the shortest transmission path with maximum bandwidth and minimum delay.