Immune algorithm for minimal Steiner tree problems
| Autor: | Li-Ping Zhang, Zong-Xiao Yang, He Qingyun, Cai Daming |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Convex hull
020502 materials 020209 energy 02 engineering and technology Minimum spanning tree Steiner tree problem Nonlinear programming symbols.namesake Tree traversal 0205 materials engineering TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Path (graph theory) 0202 electrical engineering electronic engineering information engineering symbols Combinatorial optimization Time complexity Algorithm MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | 2017 International Conference on Advanced Mechatronic Systems (ICAMechS). |
| DOI: | 10.1109/icamechs.2017.8316560 |
| Popis: | The minimum Steiner tree (MST) problem is a nonlinear programming hard (NP-hard) problem in the Euclidean plane, polynomial time algorithm is absent for solving MST for a group of arbitrary terminal points, and the most difficult thing is how to determine the position and number of Steiner points. A new method is proposed by using an immune algorithm to solve MST problem in this paper. According to the breadth — first traversal sequence of minimum spanning tree and Melzak method, the terminal points can be divided into different convex hull sets, and the full Steiner tree can be structured from the convex hull. A non-full Steiner tree can be decomposed into some full Steiner trees which terminal point appears in full Steiner tree, it is the most critical issue. We put Steiner points as a vaccine, the vaccine tries inoculation corresponding to the location of the minimum spanning tree, after several iterations, the final optimal Steiner tree is the MST. We choose the path of three cases to verify the effectiveness of the proposed algorithm, the results showed that it can reduce by 21.16%, 19.68% and 18.78% respectively. And we used the visual experimental instrument to verify the results of immune algorithm, the ratio of the length obtained by the immune algorithm and the visualization experiment is 99.95%, it is very close and the performance of algorithm is remarkable and outstanding effectively. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|