Research On Multicriteria Minimum Spanning Tree Model In Time-dependent Environment

The minimum spanning tree problem is one of the classic network optimization problems,and it has a wide range of applications in the fields of communication networks,Internet of Things,and transportation networks.Unlike traditional algorithms that abstract the real network as a static model,we consider the time-varying nature of the real network and introduce time variables into the static network model to build a multicriteria minimum spanning tree model in a time-varying environment.The main work is summarized as follows:(1)A store-and-forward neural network(SFNN)algorithm is proposed to solve the multicriteria shortest path problem in a time-varying environment.First,the SFNN neural network constructed by this algorithm uses the TDNN framework(TDNN: Time and Delay Neural Network)and designs a store-and-forward neuron,so that the neuron does not lose the optimal solution in the process of transmitting signals.Second,the algorithm can not only handle multiple time-varying objective functions,but also constrained objective functions;third,the SFNN algorithm is applied in the path planning of the transportation network,and experiments show that it can solve high-quality solutions.(2)A filtered store-and-forward neural network(FSFNN)algorithm is proposed to solve the multicriteria minimum spanning tree problem.First,the algorithm converts the structure of the static network to construct the topology of the neural network,which simplifies the problem into a multi-objective shortest path problem and provides a new solution for solving such problems.Second,a novel neuron structure is designed.,so that it can filter the signals transmitted between each other,thereby effectively reducing the complexity of the problem.Thirdly,the algorithm is applied to the construction of urban communication networks,and experiments show that it can obtain a complete set of Pareto optimal solutions.(3)A dynamic store-and-forward neural network(DSFNN)algorithm is proposed to solve the multicriteria minimum spanning tree problem in a time-varying environment.First,the algorithm uses the utility function to transform the problem into a single-objective minimum spanning tree problem in a time-varying environment,which reduces the complexity of the problem.Second,the neural network topology constructed by the algorithm further simplifies the problem into a shortest path problem in a time-varying environment.Third,the algorithm is applied to the construction of urban communication network.The results show that the DSFNN algorithm can obtain the Pareto optimal solution of the user's preference for the multi-objective minimum spanning tree in the time-varying environment.This paper adopts the neural network framework,combines the characteristics of three network optimization problems,designs three neural networks and their operation algorithms,and successfully applies them to various data sets.The effectiveness of the algorithms is proved in the comparative experiments.