基于支持向量机的改进遗传算法在模糊最短路问题中的应用
The Application of Improved Genetic Algorithm Based on Support Vector Machine in Fuzzy Shortest Path Problem

DOI: 10.12677/CSA.2021.1110253, PP. 2496-2505

Keywords: 遗传算法，模糊最短路问题，支持向量机，适应度值
Genetic Algorithm, Fuzzy Shortest Path Problem, Support Vector Machine, Fitness Value

Full-Text   Cite this paper   Add to My Lib

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.

References

[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. https://doi.org/10.1109/NAFIPS.2005.1548615
[4]	Shinkoh, O. (2004) Fuzzy Shortest Path Problems Incorporating Interactivity among Paths. Fuzzy Sets and Systems, 142, 335-357. https://doi.org/10.1016/S0165-0114(03)00225-2
[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. https://doi.org/10.1007/s10700-005-3665-2
[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. https://doi.org/10.1016/j.asoc.2011.11.011
[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. https://doi.org/10.1016/j.mcm.2011.03.040
[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. https://doi.org/10.1007/s40747-020-00195-8
[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. https://doi.org/10.1016/j.fss.2007.02.022
[10]	Klein, C.M. (1991) Fuzzy Shortest Paths. Fuzzy Sets and Systems, 39, 27-41. https://doi.org/10.1016/0165-0114(91)90063-V
[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. https://doi.org/10.1016/j.asoc.2008.07.002
[12]	王宁, 谢敏, 邓佳梁, 等. 基于支持向量机回归组合模型的中长期降温负荷预测[J]. 电力系统保护与控制, 2016, 44(3): 92-97.
[13]	鞠秋文. PSO-SVM算法在网络入侵检测中的研究[J]. 计算机仿真, 2011, 28(4): 130-132.
[14]	王江, 孙劲光. 遗传算法在最短路径问题中的应用[J]. 微计算机信息, 2010, 26(36): 226-227, 114.

Full-Text