Researches On The Optimization Of Physarum-Inspired Models And Applications

Models inspired by bio-systems can provide new insights into complex computing problems in the real-world.A unicellular and multi-headed slime mold, named as Physarum polycephalum, has been a research hotspot over the last few years. The intelligences of Physarum lie that it can form self-adaptive and high efficient networks without central consciousness in the process of foraging, which have inspired researchers to propose lots of bio-inspired models. These models can imitate the intelligent behaviors of Physarum and show great advantages in solving complex problems. However, there still have some shortcomings and uncovered applications of models. (1) The evolution time of most models is often very long, and the computational complexities of them are high. With the increment of problem scale, the amount of computation grows exponentially. (2) The ability of constructing high efficient networks with sample evolving mechanism of Physarum is the focus of transport network design. Moreover, problems, such as congestion and interruption, commonly exist in modern transport networks. Hence, it’s an urgent demand to apply Physarum-inspired models for transport network design. (3) Most ant colony algorithms suffer low convergence rate and premature convergence for solving the traveling salesman problems. The Physarum-inspired mathematical model proposed by Tero et al. exhibits a positive feedback mechanism, which is similar to that of in ant colony algorithms. Hence, it will be significant to use the mathematical model to optimize ant colony algorithms.Above all, based on the latest researches about Physarum, and combined with practical problems, my thesis conducts three studies as follows:(1) Optimizing the Physarum-inspired model CELL. Compared with other Physarum-inspired models, CELL can explain the relationship between the process of network formation and the movement of Physarum, which plays a central role in Physarum computing. Therefore, we choose CELL to optimize. CELL emulates the evolution process of Physarum networks through bubbles transportation. However, a bubble in this model often transports within local regions and the exploration efficiency is very low because of the single bubble’s transportation. In order to overcome these shortcomings, a new evolution model, named as IBTM (Improved Bubble Transportation Model) is proposed.The new model adds a time label for each grid in the environment in order to drive bubbles to explore new areas, and takes advantage of multiple bubbles to improve the evolving efficiency. IBTM is used to reveal the emerged process of Physarum networks. Some experiments are used to analyze the influence of the number of bubbles and food sources on the evolving efficiency of IBTM. The simulation results validate the accuracy, the self-organization characteristics and the high efficiency of IBTM.(2) Designing transport networks with the Vacant Particle model with Shrinkage (VP-S model). The VP-S model has been proposed by Gunji et al. in 2011 based on CELL. Compared with CELL, the VP-S model can account for a change of thickness at the site of food sources, which can implement the imitation of constructing self-adaptive Physarum networks connecting multiple food sources. Therefore, we apply the VP-S model for transport network design. We first construct the environment of the VP-S model with actual data, and transfer a disordered VP-S network to a common network with weights. Then, we compare the performance of the network designed based on the VP-S model with the real-world transport network in terms of average path length, network efficiency and robustness. In particular, we consider the topology robustness and functional robustness, which are two important factors in transport networks. Experimental results show that the network designed based on the VP-S model has better performance than the real-world transport network in all measurements. Our study indicates that the Physarum-inspired model can provide useful suggestions to the real-world transport network design.(3) Solving the traveling salesman problems with Physarum-based ant colony algorithms. Taking advantage of the unique feature of the mathematical model that critical tubes are reserved in the process of network evolution, we propose a direct pheromone matrix optimization strategy in ant colony algorithms. The route designing problems in the real-world are modeled as the traveling salesman problems, which are solved by the optimized ant colony algorithm, the traditional ant colony algorithm and other meta-heuristic algorithms (e.g., genetic algorithm, particle swarm optimization algorithm). The experimental results show that the proposed new ant colony algorithm outperforms the classical meta-heuristic algorithms in the exploitation of the optimal solution, running time and robustness.