Rapid Physarum Algorithm for shortest path problem

Dynamic remodeling model based on chemotaxis of slime molds

Social infrastructure networks, essential for daily life and economic activities, encompass utilities such as water, electricity, roads, and telecommunications. Dynamic remodeling of these systems is crucial for responding to continuous changes, unexpected events, and increased demand. This study proposes a new dynamic remodeling model inspired by biological mechanisms, focusing on a model based on the chemotaxis of slime molds. Slime molds adapt spontaneously to environmental changes by remodeling through the growth and degeneration of tubes. This capability can be applied to optimizing and dynamic remodeling social infrastructure networks. This study elucidated the chemotactic response characteristics of slime molds using biological experiments. The mold's response was observed by considering changes in the concentration of chemicals as environmental changes, confirming that slime molds adapt to environmental changes by shortening their periodic cycles. Subsequently, based on this dynamic response, we propose a new dynamic model (oscillated Physarum solver, O-PS) that extends the existing Physarum solver (PS). Numerical simulations demonstrated that the O-PS possesses rapid and efficient path-remodeling capabilities. In particular, within a simplified maze network, the O-PS was confirmed to have the same shortest-path searching ability as the PS, while being capable of faster remodeling. This study offers a new approach for optimizing and dynamically remodeling social infrastructure networks by mimicking biological mechanisms, enabling the rapid identification of solutions considering multiple objectives under complex constraints. Furthermore, the variation in convergence speed with oscillation frequency in the O-PS suggests flexibility in responding to environmental changes. Further research is required to develop more effective remodeling strategies.

A growth model for water distribution networks with loops

Water distribution networks (WDNs) expand their service areas over time. These growth dynamics are poorly understood. One facet of WDNs is that they have loops in general, and closing loops may be a functionally important process for enhancing their robustness and efficiency. We propose a growth model for WDNs that generates networks with loops and is applicable to networks with multiple water sources. We apply the proposed model to four empirical WDNs to show that it produces networks whose structure is similar to that of the empirical WDNs. The comparison between the empirical and modelled WDNs suggests that the empirical WDNs may realize a reasonable balance between cost, efficiency and robustness in terms of the network structure. We also study the design of pipe diameters based on a biological positive feedback mechanism. Specifically, we apply a model inspired by Physarum polycephalum to find moderate positive correlations between the empirical and modelled pipe diameters. The difference between the empirical and modelled pipe diameters suggests that we may be able to improve the performance of WDNs by following organizing principles of biological flow networks.

Physarum-Inspired Bicycle Lane Network Design in a Congested Megacity

Improvement of mobility, especially environment-friendly green mobility, is challenging in existing megacities due to road network complexity and space constraints. Endorsing the bicycle lane network (BLN) in congested megacities is a promising option to foster green mobility. This research presents a novel bioinspired network design method that considers various constraints and preferences related to the megacity for designing an optimal BLN. The proposed method is inspired by natural Physarum polycephalum, a brainless, multi-headed single-celled organism, which is capable of developing a reticulated network of complex foraging behaviors in pursuit of food. The mathematical model of Physarum foraging behavior is adapted to maneuver various BLN constraints in megacity contexts in designing the optimal BLN. The Physarum-inspired BLN method is applied to two case studies on the megacity Dhaka for designing BLNs: the first one covers congested central city area, and the second one covers a broader area that includes major locations of the city. The obtained BLNs were evaluated comparing their available routes between different locations with the existing vehicle routes of the city in terms of distance and required travel times in different time periods, and the BLN routes were found to be suitable alternatives for avoiding congested main roads. The expected travel time using BLNs is shorter than other transport (e.g., car and public bus); additionally, at glance, the average travel speed on BLNs is almost double that of public buses in peak hours. Finally, the designed BLNs are promising for environment-friendly and healthy mobility.

An Accelerated Physarum Solver for Network Optimization

As a novel computational paradigm, Physarum solver has received increasing attention from the researchers in tackling a plethora of network optimization problems. However, the convergence of Physarum solver is grounded by solving a system of linear equations iteratively, which often leads to low computational performance. Two factors have been highlighted along the process: 1) high time complexity in solving the system of linear equations and 2) extensive iterations required for convergence. Thus, Physarum solver has been largely restricted by its unsatisfactory computational performance. In this paper, we aim to address these two issues by developing two enhancement strategies: 1) pruning inactive nodes and 2) terminating Physarum solver in advance. First, extensive nodes and edges become and stay inactive after a few iterations in identifying the shortest path. Removing these inactive nodes and edges significantly decreases the graph size, thereby reducing computational complexity. Second, we define a transition phase for edges. All of the paths experiencing such a transition phase are dynamically aggregated to form a set of near-optimal paths among which the optimal path is included. Depth-first search is then leveraged to identify the optimal path from the near-optimal paths set. Earlier termination of Physarum solver saves considerable iterations while guaranteeing the optimality of the found solution. Empirically, 20 randomly generated sparse and complete graphs with network sizes ranging from 50 to 2000 as well as two real-world traffic networks are used to compare the performance of accelerated Physarum solver to the other two state-of-the-art algorithms.

An improved bio-inspired algorithm for the directed shortest path problem

Because most networks are intrinsically directed, the directed shortest path problem has been one of the fundamental issues in network optimization. In this paper, a novel algorithm for finding the shortest path in directed networks is proposed. It extends a bio-inspired path finding model of Physarum polycephalum, which is designed only for undirected networks, by adopting analog circuit analysis. Illustrative examples are given to show the effectiveness of the proposed algorithm in finding the directed shortest path.