基于支持向量机的改进遗传算法在模糊最短路问题中的应用
The Application of Improved Genetic Algorithm Based on Support Vector Machine in Fuzzy Shortest Path Problem
摘要: 最短路问题是图论中重要的优化问题之一。随着网络的增大，求最短路径的时间复杂度越来越大。本文基于模糊图中部分路径的长度，设计了基于支持向量机的改进遗传算法，并用该算法求得了模糊最短路问题的较好近似解。最后通过数值算例模拟该算法，并与标准的遗传算法作对比，结果表明该算法是有效的。
Abstract: The shortest path problem is one of the important optimization problems in graph theory. As the network grows, the time complexity of finding the shortest path is getting bigger and bigger. Based on the length of some paths in the fuzzy graph, this paper designs an improved genetic algorithm based on support vector machines, and uses this algorithm to obtain a better approximate solution to the fuzzy shortest path problem. Finally, the algorithm is simulated through a numerical calculation example and compared with the standard genetic algorithm. The result shows that the algorithm is effective.
文章引用：孙亚莉, 陈学刚, 陈甜甜. 基于支持向量机的改进遗传算法在模糊最短路问题中的应用[J]. 计算机科学与应用, 2021, 11(10): 2496-2505. https://doi.org/10.12677/CSA.2021.1110253

参考文献

[1] Dubis, D. and Prade, H. (1980) Theory and Application/Fuzzy Sets and Systems. Academic Press, New York.
[2] Chanas, S. and Kamburowski, J. (1983) The Fuzzy Shortest Route Problem. Interval and Fuzzy Mathematics, Poznan,: 35-41.
[3] Takahashi, M.T. and Yamakami, A. (2005) On Fuzzy Shortest Path Problems with Fuzzy Parame-ters: An Algorithmic Approach. NAFIPS 2005-2005 Annual Meeting of the North American Fuzzy Information Pro-cessing Society, Detroit, 26-28 June 2005, 654-657. [Google Scholar] [CrossRef] 
[4] Shinkoh, O. (2004) Fuzzy Shortest Path Problems Incorporating Interactivity among Paths. Fuzzy Sets and Systems, 142, 335-357. [Google Scholar] [CrossRef] 
[5] Nayeem, S. and Pal, M. (2005) Shortest Path Problem on a Network with Imprecise Edge Weight. Fuzzy Optimization and Decision Making, 4, 293-312. [Google Scholar] [CrossRef] 
[6] Deng, Y., Chen, Y., Zhang, Y. and Mahadevan, S. (2012) Fuzzy Dijkstra Algorithm for Shortest Path Problem under Uncertain Environment. Applied Soft Computing, 12, 1231-1237. [Google Scholar] [CrossRef] 
[7] Hassanzadeh, R., Mahdavi, I., Mahdavi-Amiri, N., et al. (2013) A Genetic Algorithm for Solving Fuzzy Shortest Path Problems with Mixed Fuzzy Arc Lengths. Mathematical & Comput-er Modelling, 57, 84-99. [Google Scholar] [CrossRef] 
[8] Lin, L., Wu, C. and Ma, L. (2020) A Genetic Algorithm for the Fuzzy Shortest Path Problem in a Fuzzy Network. Complex & Intelligent Systems, 3, 1-10. [Google Scholar] [CrossRef] 
[9] Hernandes, F., Lamata, M.T., Verdegay, J.L. and Yamakami, A. (2007) The Shortest Path Problem on Networks with Fuzzy Parameters. Fuzzy Sets and Systems, 158, 1561-1570. [Google Scholar] [CrossRef] 
[10] Klein, C.M. (1991) Fuzzy Shortest Paths. Fuzzy Sets and Systems, 39, 27-41. [Google Scholar] [CrossRef] 
[11] Iraj, M., Rahele, N., Armaghan, H. and Mahdavi, A.N. (2009) A Dynamic Programming Approach for Finding Shortest Chains in a Fuzzy Network. Applied Soft Computing, 9, 503-511. [Google Scholar] [CrossRef] 
[12] 王宁, 谢敏, 邓佳梁, 等. 基于支持向量机回归组合模型的中长期降温负荷预测[J]. 电力系统保护与控制, 2016, 44(3): 92-97.
[13] 鞠秋文. PSO-SVM算法在网络入侵检测中的研究[J]. 计算机仿真, 2011, 28(4): 130-132.
[14] 王江, 孙劲光. 遗传算法在最短路径问题中的应用[J]. 微计算机信息, 2010, 26(36): 226-227, 114.