Abstract
Aiming at the complex large-scale shortest path problem, a modified genetic learning algorithm has been offered. Firstly, in order to prevent premature convergence of evolution population, a new fitness function for the shortest path is proposed. At the same time, to ensure the global search ability of the algorithm a selection method of crossover probability is proposed. And to ensure the local search ability of genetic algorithm a selection method of mutation probability is proposed. The experimental results show that the modified genetic algorithm has a better success rate compared with the traditional algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ko, Y.D., Jang, Y.J., Min, S.L.: The optimal economic design of the wireless powered intelligent transportation system using genetic algorithm considering nonlinear cost function. Comput. Ind. Eng. 89(C), 67–79 (2015)
Chitra, C., Subbaraj, P.: A nondominated sorting genetic algorithm solution for shortest path routing problem in computer networks. Expert Syst. Appl. 39(1), 1518–1525 (2012)
Cheng, H.: Obstacle avoidance shortest path algorithm and its application. Electron. Des. Eng. 16, 56–60 (2013). (in Chinese)
Qi, X., Liu, S.: Selection algorithm for QoS routing based on k-shortest paths. J. Jilin Univ. (Eng. Technol. Ed.) 05, 526–530 (2005). (in Chinese)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Bellman, R.: On a routing problem. Q. Appl. Math. 16, 87–90 (1958)
Lin, L., Gen, M.: Priority-based genetic algorithm for shortest path routing problem in OSPF. Stud. Comput. Intell. 187, 91–103 (2009)
Holland, J.H.: Adaptation in Natural Artificial Systems, pp. 1–17. MIT Press, Cambridge (1975)
Cao, Z.: The study on exhaust algorithm, search algorithm, dynamic design for 0–1 Knapsack problem. Comput. Knowl. Technol. 5(12), 3193–3198 (2009). (in Chinese)
Srinivas, M., Patnaik, L.: Adaptive probabilities of crossover and mutation in genetic algorithm. IEEE Trans. Syst. Man Cybern. 24(4), 656–666 (1994)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Wang, B., Yao, S., Lu, K., Zhao, H. (2018). Research on the Shortest Path Problem Based on Improved Genetic Algorithm. In: Zu, Q., Hu, B. (eds) Human Centered Computing. HCC 2017. Lecture Notes in Computer Science(), vol 10745. Springer, Cham. https://doi.org/10.1007/978-3-319-74521-3_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-74521-3_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-74520-6
Online ISBN: 978-3-319-74521-3
eBook Packages: Computer ScienceComputer Science (R0)