Steiner Minimum Tree Problem Based On Binary Particle Swarm Optimization Algorithm

The Steiner Minimum Tree problem is a classical NP-hard problem in combinatorial optimization.In real life,many problems can be transformed into the Steiner Minimum Tree problems.Such as the best location of rubbish disposal station,monitor the large network with as few points as possible,wireless network node setting problems,optimal network logistics and large-scale integrated circuit chip defect repair and so on.At present,the application of the Steiner Minimum Tree problem has been greatly developed,and it mainly uses the Ant Colony Algorithm,the Genetic Algorithm,the Particle Swarm Optimization Algorithm and the Simulated Algorithm to solve the Steiner Minimum Tree problem.However,there are few researches on solving this problem based on the Binary Particle Swarm Algorithm and the Genetic Algorithm,the Binary Particle Swarm Algorithm and the Clustering Algorithm.Therefore,it is significant to solve the Steiner Minimum Tree problem by integrating these algorithms.The Binary Particle Swarm Optimization Algorithm,the Genetic Algorithm and K-means Clustering Algorithm are used in this paper.Based on the combination of these three algorithms,the concrete problem of laying network cable is transformed into the Steiner Minimum Tree problem,and the optimal solution of the practical problem is obtained,which proves the practicability and effectiveness,and verifies the feasibility of this algorithm too.The main contents of this paper are as follows:(1)This paper analyzes the current situation of Steiner minimum spanning tree and studies its absolute distance property using various algorithms.It describes the research content,purpose,and significance of the paper and presents related concepts and properties of minimum spanning tree and minimum Steiner spanning tree.The paper outlines the basic steps and flow of the Binary Particle Swarm Optimization,the Ant Colony Optimization,and Clustering Algorithm.(2)To solve the Steiner minimum spanning tree problem,the paper applies the Binary Particle Swarm Algorithm and Genetic Algorithm.In the Binary Particle Swarm Algorithm,the velocity update is similar to the basic Particle Swarm Algorithm,while the position update introduces the Sigmoid function.The selection and coding of particles involve scaling the rectangular area on a unit square,calculating the length,and fitness function of the encoding.The Binary Particle Swarm Algorithm designs an algorithm program for the Steiner minimum spanning tree problem,and an actual example proves its feasibility.Additionally,the paper introduces the K-means Clustering Algorithm to find the optimal Steiner point in each class.It conducts cluster analysis on logarithm data points and iteratively finds the optimal Steiner minimum spanning tree and Steiner point of absolute distance.(3)To derive the Steiner minimum tree,we can either adjust the number of known points or determine the number of Steiner points based on available data.We can then compute the Steiner ratio and compare it between two algorithms.After analyzing the results of both methods,we conclude that the second algorithm,which integrates the Clustering and Binary Particle Swarm techniques,yields more accurate and stable solutions.Therefore,it is a more suitable approach for solving the absolute value Steiner minimum tree problem.