Euclidean Steiner Minimum Tree Problem Intelligent Optimization Algorithms

The Euclidean Steiner minimum tree problem, concerning the construction of a tree that connects a given set of terminal points in Euclidean space with the minimal total length, is an NP-hard combinatorial optimization problem. Because of the intrinsic characteristic of hard computability, it cannot be solved accurately by efficient algorithms up to now. Since this problem has many applications in real situations, it is quite important to find some heuristics and approximation algorithms. In recent years, there appeared several intelligent optimization algorithms, such as simulated annealing, genetic algorithm, taboo search, artificial neural network,ant algorithm etc. Their unique merits and mechanisms have attracted world's attention. Therefore, besides discussing traditional heuristics, this dissertation mainly pays attention to intelligent optimization algorithms.Generally, the traditional heuristics are obtained on the basis of all-over understanding of the specific problems. Insertion algorithm and incremental optimization algorithm in this dissertation are with no exception. They are designed according to Euclidean Steiner minimum tree's characteristic. The results show their effectiveness, but there are also some defects. So genetic algorithm, simulated annealing and ant algorithm are put forward.Genetic algorithm is a high parallel, stochastic and adaptive optimization algorithm. Each chromosome represents a candidate solution to a problem. With the fittest surviving, the best solution remains. Simulated annealing is a stochastic searching optimization approach. By analogy between physical annealing process and combinatorial problems, this method based on generalization of Monte Carlo approach is straight forward. Ant algorithm, imitating real ant colony's behavior to find the shortest path between their nest and a food source, is a recently developed bionic algorithm. Though with short history, it has already been wildly used in optimization field.The contents of the dissertation include:Chapter 1 put forward the background, content and meaning of studying this problem.Chapter 2 introduce kinds of Steiner Tree problems, mainly discussing the Euclidean Steiner minimum tree.Chapter 3 give heuristic tools, including neighbor function, local search, minimum spanning tree etc. The steps of insertion algorithm and incremental optimization algorithm are offered in detail. With the instances'test results, a comparison of these two algorithms is discussed. Later present kinds of intelligent optimization algorithms, as well as the brief introductions of them.Chapter 4,5,6 describe the conditions of genetic algorithm, simulated annealing and ant algorithm in detail, including historical development, principles, flow, components, characteristics, advantages, disadvantages and so on. The steps of these three algorithms are offered later.Chapter 7 apply genetic algorithm, simulated annealing and ant algorithm to instances with different scales. With the test results, compare the performances of these three algorithms and that between intelligent optimization algorithm and traditional algorithm from the aspects of running time, results and stability.Chapter 8 conclude the content, briefly evaluate all algorithms in this dissertation, and propose methods for further improvement.All 5 algorithms are implemented on PC-compatibles. Most test results are better than minimum spanning tree, showing algorithms'good performances. Due to its computing difficulty, theories and solutions about Euclidean Steiner minimum tree have not been completely developed and need to further studying.