Research On Graph Related Problems Based On Physarum-inspired Models

Graph is a complex data structure used to describe the relationship between things in nature or society.With the rapid development of information technology,graph has gradually covered all aspects of our daily life,especially in the fields of transportation,social affairs and so on.The application of graph models is ubiquitous,which has greatly promoted the development of theoretical research such as graph coloring problem,vehicle routing problem and propagation source identification.In-depth research on graph issues such as graph coloring,vehicle routing,and propagation source identification can not only optimize resource allocation,but also help improve logistics distribution mechanisms,reduce distribution costs,and help governments quickly grasp the source of online public opinion and maintain social stability.Therefore,how to efficiently solve graph problems such as graph coloring,vehicle routing,propagation source identification has become a hotspot of current scholars' research.After years of research,scholars have proposed a series of algorithms for solving graph problems,which can be divided into two categories: precise algorithms and intelligent algorithms.Precise algorithms usually refer to algorithms that can find the global optimal solution,such as natural linear programming,dynamic programming,and backtracking.Since most graph theory problems are NP-Hard problems,and applying accurate algorithms to solve them,the calculation cost of the algorithm will increase exponentially as the problem size increases.Obviously,with the blowout growth of social data,especially in the context of the current era of big data,accurate algorithms can no longer meet the needs of solving graph problems.Therefore,scholars have gradually shifted their research focus to intelligent algorithms,and proposed a series of algorithms such as ant colony algorithm,genetic algorithm,particle swarm algorithm,and tabu search algorithm to solve graph problems,and have been committed to pursuing more efficient solution algorithms.In recent years,a slime mold called physarum polycephalum has shown self-organization,self-optimization and other intelligent behaviors in the foraging process,which has attracted extensive attention in the theoretical community.A series of bionic models such as bubble model,agent model,gradient model,oregon model and positive feedback model have been established successively.Among them,the positive feedback model is the most widely used due to its characteristics such as “key cultivation of key pipeline” and rapid convergence to the shortest path.Based on the above analysis,this paper selects three classical graph problems: graph coloring,vehicle routing,and propagation source identification as research objects,and uses the positive feedback mechanism of the physarum-inspired model to optimize their existing algorithms.Specifically,it mainly includes the following three aspects:(1)Solving the graph coloring problem(GCP)based on the physarum-inspired model: Based on the characteristics of the GCP,the physarum-inspired positive feedback model is used to improve the pheromone concentration updating mechanism of ant colony optimization(ACO),and the physarum-ACO(PM-ACO)is proposed to solve the GCP.Simulation experiments are performed based on international standard examples.The results show that PM-ACO algorithm is better than the typical ACO and other state-of-art algorithms in terms of the best coloring number,average coloring number or average convergence algebra under the premise of controlling the time overhead,which indicates that it is reasonable to use the physarum-inspired positive feedback model to improve ACO algorithm and provides a new research idea for solving GCP.(2)Solving the vehicle routing problem(VRP)based on physarum-inspired model: Based on the characteristics of the VRP,the distance matrix of the hybrid genetic algorithm(HGA)is replaced by the conductivity matrix generated by the physarum-inspired positive feedback model,and the physarum-HGA(PM-HGA)is proposed to solve the VRP.Simulation experiments are carried out based on the enterprise distribution example and international standards.The results show that,compared with other intelligent algorithms,the PM-HGA has stronger global optimization ability,faster convergence speed and better stability,and can better plan the distribution scheme and effectively shorten the distribution distance of enterprises.(3)Propagation source identification based on the physarum-inspired model: The Physarum_esti,which learning the theoretical time delay distribution characteristics of propagation network by the physarum protoplast network,has a lack of rigorous scientific basis in the propagation source location,and the performance needs to be further improved.Therefore,the Physarum_cov is proposed.In Physarum_cov,the theoretical propagation delay is calculated by the physarum-inspired positive feedback model,and the effective propagation distance is calculated.Then,the correlation coefficients of the effective propagation distance and the observed delay are calculated by correlation coefficient formula,and the candidate source point with the largest correlation is selected as the actual propagation source.The simulation are carried on classical network,and the results show that,the error distance obtained by the Physarum_cov is better than Physarum_esti,which has good prediction ability and stability for the propagation sources location.In summary,this paper mainly uses the physarum-inspired bionic model to solve GCP?VRP and propagation source location.A large number of simulation experiments show that the solution based on the physarum-inspired bionic model can solve the those problems more effectively.