A genetic algorithm for the fuzzy shortest path problem in a fuzzy network
- PDF / 419,665 Bytes
- 10 Pages / 595.276 x 790.866 pts Page_size
- 22 Downloads / 248 Views
ORIGINAL ARTICLE
A genetic algorithm for the fuzzy shortest path problem in a fuzzy network Lihua Lin1 · Chuzheng Wu1 · Li Ma1 Received: 26 May 2020 / Accepted: 30 August 2020 © The Author(s) 2020
Abstract The shortest path problem (SPP) is an optimization problem of determining a path between specified source vertex s and destination vertex t in a fuzzy network. Fuzzy logic can handle the uncertainties, associated with the information of any real life problem, where conventional mathematical models may fail to reveal proper result. In classical SPP, real numbers are used to represent the arc length of the network. However, the uncertainties related with the linguistic description of arc length in SPP are not properly represented by real number. We need to address two main matters in SPP with fuzzy arc lengths. The first matter is how to calculate the path length using fuzzy addition operation and the second matter is how to compare the two different path lengths denoted by fuzzy parameter. We use the graded mean integration technique of triangular fuzzy numbers to solve this two problems. A common heuristic algorithm to solve the SPP is the genetic algorithm. In this manuscript, we have introduced an algorithmic method based on genetic algorithm for determining the shortest path between a source vertex s and destination vertex t in a fuzzy graph with fuzzy arc lengths in SPP. A new crossover and mutation is introduced to solve this SPP. We also describe the QoS routing problem in a wireless ad hoc network. Keywords Fuzzy graph · Shortest path problem · Fuzzy shortest path problem · Genetic algorithm
Introduction The shortest path problem (SPP), which concentrates on obtaining a shortest path between a specified starting node and other destination nodes, is one of the most important and fundamental combinatorial network optimization problems [6,8] in graph theory that has been appeared in several real life applications as a sub problem. fields including routing, transportation, supply chain management, communications and wireless network. The SPP has been researched extensively in several academic fields such as operations research and computer engineering in the conditions of efficiency ,effectiveness and analytical algorithmic techniques. Recently, many different types of SPPs have been studied. For e.g.,
B
Lihua Lin [email protected] Chuzheng Wu [email protected] Li Ma [email protected]
1
Department of Telecommunication and information, Xi’an University of Science and Technology, Xi’an 710054, China
Cheng et al. [4] have presented SPP for (n, k)-star graphs. In [40], Zhu and Wilhelm described the resource constrained SPP on a graph. Experts emerge graph the modeling as a mathematical model for several decision making problems, e.g., routing [27], transportation [10], supply chain management [20], communications [31], wireless network [36], etc. They have remodeled those problems as a SPP between source node and other nodes within the modeled graph of the specific problem. The best path is determined u
Data Loading...
