Solving the Steiner tree problem in graphs by chaotic search

摘要

The Steiner tree problem in graphs is an NP -hard combinatorial optimization problem. To solve the NP -hard combinatorial optimization problems, such as the traveling salesman problems, the quadratic assignment problems, and the vehicle routing problems, an algorithm for searching solutions by chaotic dynamics, or the chaotic search, exhibits good performance. From this viewpoint, this paper proposes an algorithm for solving the Steiner tree problem in graphs with chaotic dynamics. Comparing the performance of the chaotic search with that of the tabu search, we analyze the searching characteristics of the chaotic search. From the results of numerical experiments, we found that if parameters of the chaotic search are set to appropriate values, the chaotic search exhibits good performance and the chaotic search outputs optimal solutions more frequently than the tabu search during the searching processes, which implies that the chaotic search has higher ability than the tabu search as metaheuristics.