Bio-inspired Route Optimization And Source Identification

In the research field of network science,there are two important topics.On one hand,in order to maximize the whole efficiency of the system,we need to research into many kinds of optimization problems.Among them,route optimization is one of the most important optimization problems,which has wide applications in many areas such as optimization of knowledge diffusion route in social network,optimization of vehicle routes in transportation network and optimization of node transfer trajectory in communication network.On the other hand,in order to protect the network from harms such as phishing viruses or rumors,we need to research into the propagation dynamics,which include network immunization,source identification and so on.Predicting and analyzing the spreading dynamical process are of great significance to provide important references for early warning and monitoring the real spreading behavior.First,in the aspect of route optimization,the thesis focuses on solving the Uncertain Capacitated Arc Routing Problem(UCARP).The main goal is to reduce the extra costs caused by uncertainty.Second,recent researches show that the Physarum has excellent abilities in route optimization and network optimization,which are useful for solving complex problems.In this aspect,the thesis focuses on the modeling and computing based on Physarum.First,a new model inspired by the intelligent behaviors of Physarum in the foraging process is proposed.Then,new approaches to route optimization and source identification are proposed,respectively.The main contents and achievements are summarized as follows:1.The existing algorithms may spend lots of time to make decisions in real time for UCARP,which are inapplicable in the real world.Addressing on this issue,the Genetic Programming Hyper-Heuristic(GPHH)is proposed to evolve the routing policies automatically,which can be used to make decisions immediately in the real time.Meanwhile,a novel effective meta-algorithm with the usage of domain knowledge is designed to evaluate the routing policy.And the meta-algorithm also can address on the failures caused by the environment change.Experimental results show that eliminating the infeasible and distant tasks in advance can reduce much noise and improve the efficacy of the evolved routing policy.2.The greedy recourse policy reduces the effiency of baseline solution seriously.Addressing on this issue,a new solution representation that consists of a baseline solution and a recourse policy is proposed.Meanwhile,a cooperative co-evolution framework is developed to optimize the two components simultaneously.Experimental results show that the proposed algorithm significantly outperforms the state-of-the-art algorithms to UCARP.Through further analysis,useful patterns that occur in the promising individuals are discovered.3.Inspired by the search and contraction behaviors of Physarum in foraging,a multi-agent system is developed based on the fundamental design principles of a self-organized computational system.The computational ability of the multi-agent system is verified by solving the shortest path problem and the maze problem.And the positive feedback mechanism of the system is highlighted by calculating the dynamic changes of the population of agents and the percentage of different types of behaviors.4.New approaches based on the positive feedback mechanism of Physarum are proposed for solving the route optimization and source identification,respectively.These researches show that the Physarum model can be good candidate for solving complex problems.In details,according to the shortcomings that ant colony optimization has the problems of premature convergence and stagnation in general,a universal optimization strategy for updating the pheromone matrix in the ant colony optimization is proposed based on the positive feedback mechanism of Physarum model.Experimental results show that the optimized algorithm can get better global optimal solutions for solving single and multiple objectives travelling salesman problems.Moreover,the positive feedback mechanism is used to learn the distribution of delays along the path of propagation,and then a Physarum-inspired model is proposed for identifying the diffusion source.The new model is independent of the assumption about the propagation delays along edges.Experimental results show that the accuracy of the existing methods decline dramatically when the propagation models of the actual process and the inferring process are different.However,the Physarum-inspired method can achieve a higher accuracy.In summary,the main contributions of our work include:1.In order to solve the problem of time consuming of existing approaches in making on-line decisions,GPHH is proposed for automatic routing policy design for UCARP.The new meta-algorithm based on the domain knowledge is designed.The goal that making efficient decisions in real time for UCARP is achieved.2.Addressing on the inefficiency of the baseline solution,a new solution representation is designed,and a cooperative co-evolution algorithm is developed to evolve the baseline solution and recourse policy simultaneously.The efficiency and robustness of the final routes are improved.3.A multi-agent system is proposed by getting inspiration from the foraging process of Physarum.The model reveals the positive feedback mechanism of Physarum in foraging,which is applied for solving route optimization and source identification then.We demonstrate that approaches based on the intelligent behaviors of Physarum can not only solve route optimization problems,but also have promising performance for solving the inverse problem,i.e.source identification.