Research On Solution Of Network Optimization Problem Based On Supervised Learning

With the rise of artificial intelligence technology,machine learning,as an important technology of artificial intelligence,plays an increasingly important role in solving traditional problems.Among them,supervised learning methods are the most widely used.Supervised learning uses empirical data to model,and when modeling is complete,when new inputs are available,the output can be predicted quickly and accurately.Due to the successful use of supervised learning in many fields,people are pushing this method to try other fields.Many network optimization problems such as resource allocation and task scheduling can be transformed into Combinational Optimization Problem.The combinatorial optimization problem has a long history and wide application.Since most combinatorial optimization problems are NP-hard,traditional algorithms are often based on heuristic search algorithms,and can not give approximate solutions of optimal solutions in a short time.Moreover,the algorithm that can give the optimal solution often produces a "combination explosion" phenomenon due to the expansion of the problem scale,so that the combinatorial optimization problem cannot be solved efficiently.This thesis chooses the more common problems in network design to model,and uses the supervised learning method to solve the problem.The direction of the attempt includes direct prediction or assisting the traditional algorithm to reduce the solution space.These two problems are: k center problem and Task Placement Problem(TPP).The k-center problem is the basic problem of facility placement.In the scenario where the CDN cache is placed,for example,a solution needs to be given quickly,and the traditional method often does not work well.The k-center problem can be transformed into a two-class problem for each point in the graph.In this thesis,five supervised learning models are used to solve the problem,and two solutions are constructed.Finally,using the neural network algorithm,the optimal solution can be obtained 100%.For the task placement problem,this thesis abstracts the model from the Mobile Edge Computing(MEC)scenario,takes the task delay as the optimization goal,and solves the placement scheme that makes the total delay the shortest.The problem is also abstracted into a classification problem,and the neural network method is used to model the constraint relationship between tasks,and the optimal solution algorithm and greedy algorithm are compared.Experiments show that,except for a few(5%)outliers,the neural network achieves a 1.5 approximation of the optimal solution on different test sets.By verifying the two combinatorial optimization problems,supervised learning can effectively solve or assist in solving combinatorial optimization problems.The core of the solution is to represent the combinational optimization problem in vector form.According to the nature of different combination optimization problems,choosing the applicable supervised learning model is also the key to smooth solution.In this thesis,the feasibility of supervised learning method in solving network optimization problems is verified to some extent.