Research On Global Optimization Algorithm For Steiner Tree Problem Based On Visualization Experiment

System global shortest path is one of the classic nonlinear combinatorialoptimization problems. It has extensive applications in engineering practices. Theminimum Steiner tree theory is the basis theory of global shortest path. So researchedthe global optimization algorithm for the minimum Steiner tree has importanttheoretical significance and wide application. Since the minimum Steiner tree problemhas been proved to be NP-hard problem, unless P=NP, orelse Steiner tree problemdoes not exist polynomial-time algorithm, so find the suitable intelligent optimizationalgorithms is an effective way to solve this problem.Based on the physical visualization experiment, we use experiment approach-algorithm-experiment approach-project application as our research route,analysisand research visualization experiment unit, experiment process, as well asexperimentresult detailed, explore the relationship between construction of the Steinerminimaltree and the distributed shape of given points, as well as the relationshipbetween thelocation and the number of Steiner points and the distributed shape ofgiven points. The minimum Steiner tree problem is divided into two circumstances tosolve. When the fixed point set is convex, Melzak method is used to construct theminimum Steiner tree; when the fixed point is non-convex set, solved it by improvedgenetic algorithm. For the existing obstacles Steiner tree problems, we also carried outsome experiments and analysis the relationship between the shape and location ofobstacles with Steiner fictive points.The genetic algorithms proposed utilize test selection algorithm to choose initialpopulation and struct cross-factor which meet the adaptive process in this paper.Utilize test selection algorithm to choose initial population can improve theconvergence rate of genetic algorithm. The struct cross-factor which meets theadaptive process is advantageous to genetic algorithm for getting its best crossing probability, and can promote algorithm accuracy and convergence rate. The optimalsolution which was got by genetic algorithm is existing in the form of hypotheticalpoint, this can compensates the shortage of international SteinLib test database whichis not include Steiner hypothetical point.It verified the feasibility of algorithm by simple graphical examplein this paper.By several detailed examples, such as heat supply pipeline of a universities teachingand administrative staff housing area, site selection of five provinces and onemunicipality, route planning of transmission network, we analysed the geneticalgorithm and visual experiment results, and verified practicality and effectiveness ofalgorithm. Many examples verified that the algorithm used with visual experiment cansolve engineering practical problems, and lay the foundation for further methodimproving.