Research On The Key Issues Of Graph Theory Based On Physarum Polycephalum Model

Graph theory is one of fundamental optimization problems, and it is closely related to many practical applications. In the past decades, researchers have studied many problems and made huge progress. Since these problems lay firm foundations for many real-world applications, any improvement on the solutions to these problems is very helpful. For example,the shortest path problem, and the maximum flow problem, they are widely used in routing,traffic networks, network optimization, and decision support systems. However, there is no breakthrough in the development of the algorithms for solving these problems.In single source shortest path tree problem, if there is no links with negative weights, the time complexity for the classical Dijkstra algorithm is O(m + n log n), where m is the number of edges in the network. Dijkstra is the fastest algorithm so far. However, if there is links with negative weights, the best algorithm is Bellman-Ford with a time complexity of O(nm). Dinic is the most commonly used algorithm for solving the maximum flow problem, and its time complexity is O(n2m). In this algorithm, there is a upper bound on the time complexity:O(nm). Any algorithm based on dummy links cannot have lower time complexity. Many decent algorithms have almost achieved the same time complexity, but their implementations are very complicated. In addition, their efficiency is very low. All these drawbacks limit their wide applications. Dinic reduces the time complexity to O(nm log n) by using dynamic trees.But dynamic tree is a very complicated data structure, which is very difficult to implement.In 1998, Goldberg and Rao broke the upper bound of the time complexity for the first time,and they further reduced the time complexity to O(min{n2/3, m1/2}m log(n2/m) log U). But this algorithm requires many operations to transform the network, which increases the complexity. The traditional algorithms for solving graph problems is based on graph traversals,and they could hardly be optimized any more. Heuristic algorithms, such as ant colony optimization, genetic algorithms, provide us a new insight into these problems, that is emergent computation.Heuristic algorithms have been widely used to solve many complicated NP problem where the traditional algorithms are not able to handle, but they are still unable to address the shortest path problem and maximum flow problem effectively because they are probabilistic algorithms. In addition, the convergence speed is lower than traditional algorithms. In 2000,Tero et al. discovered the special ability of physarum polycephalum in finding the optimal path of a maze. Physarum polycephalum is a large single-cell slime molds. According to the classification of biology, it belongs to the physarum, myxomycetes, amoebozoa, and its nutrition, movement and foraging is similar to the amoeba. In 2007, they built a mathematical model to describe the adaptive behavior of physarum polycephalum in finding the optimal path. In this dissertation, we extend the original model to an algorithm which I have called amoeba algorithm, and use it to solve the single-source shortest path problem and the maximum flow problem. Our algorithm has the best performance in terms of time complexity. Amoeba algorithm can be seen as a non-linear dynamic system. Due to the positive feedback in this dynamic system, it converges to the required solution gradually. To cope with each problem, we impose the corresponding constraint. In amoeba algorithm, it is required to solve linear systems of equations. But they are very special and can be formulated as Laplacian system, which is solvable in O(m log n). Hence, the time complexity for amoeba algorithm can be described as O(km log n), where k is the number of iterations in the loop.In this dissertation, we focus on the single-source shortest path problem and the maximum flow problem, and their applications. Our contributions can be summarized as:1. We proved the convergence and correctness of physarum polycephalum model, analyzed its convergence speed, and got the original amoeba algorithm. In the physarum polycephalum model proposed by Tero et al. in 2007, its convergence has not been fully research and proof. We developed a generalized physarum polycephalum model and proved its convergence to the shortest path if the link weight is positive and each entry in the initial conductivity matrix is non-zero. In addition, its convergence speed is closely related to the specific network topology. We discretize the dynamic system, and form an original version of implementable amoeba algorithm. The experimental results show that amoeba algorithm is a pseudo-polynomial algorithm, and its time complexity is O(U m log2n).2. By extending the original amoeba algorithm, we developed a generalized algorithm to solve the single-source shortest path problem with negative link weights, and compared its performance with Bellman-Ford algorithm. Our algorithm is able to detect, locate, and eliminate the cycles in the network. Bellman-Ford algorithm is able to find the single-source shortest path and verify the existence of cycles with negative weights in O(nm). We proposed Physarum-inspired algorithm for solving the single-source shortest path problem in O(√nm log n). If there are negative cycles in the network, in the worst case, Bellman-Ford algorithm is only able to judge the existence of the cycle at the last iteration, while amoeba algorithm can detect, locate, and remove the cycles with negative weights without damaging the connectivity of the network in O(n0.Zm log n), where 0.Z ≈ 0.65.3. In the maximum flow problem, we modified the original amoeba algorithm and demonstrated that it is superior than Dinic algorithm. So far, there is no explicit low bound for solving the maximum flow problem. The flow decomposition barrier limits the time complexity as O(nm). In 1998, researchers developed an algorithm with time complexity O(min{n2/3, m1/2}m log(n2/m) log U). But they all need complicated data structures, and the efficiency is very low. We designed a Physarum-based algorithm to resolve the maximum flow problem, and its time complexity is O(log(n U) m log n). Most importantly, it is very easy to implement. Additionally, our algorithm surpasses the time complexity of the flow decomposition algorithm and Dinic algorithm. At the same time, our algorithm decomposes the network into several subnetworks according to the minimum cut sets, and obtains the maximum flow and the minimum cut sets simultaneously.