Solving the Steiner tree problem in graphs by chaotic search

被引:2
作者
Fujita, Misa [1 ]
Kimura, Takayuki [2 ]
Ikeguchi, Tohru [1 ,3 ]
机构
[1] Tokyo Univ Sci, Grad Sch Engn, Dept Management Sci, 6-3-1 Niijuku, Tokyo 1258585, Japan
[2] Nippon Inst Technol, Fac Fundamental Engn, Dept Elect Elect & Commun Engn, 4-1 Gakuendai, Saitama 3458501, Japan
[3] Tokyo Univ Sci, Fac Engn, Dept Informat & Comp Technol, 6-3-1 Niijuku, Tokyo 1258585, Japan
来源
IEICE NONLINEAR THEORY AND ITS APPLICATIONS | 2020年 / 11卷 / 01期
关键词
the Steiner tree problem in graphs; combinatorial optimization; metaheuristics; the chaotic search; neural network; PACKET ROUTING-PROBLEMS; NEURODYNAMICS; ALGORITHM; STRATEGY;
D O I
10.1587/nolta.11.90
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:90 / 108
页数:19
相关论文
共 50 条
[31]   Variable neighborhood search for solving the k-domination problem [J].
Predojevic, Milan ;
Kartelj, Aleksandar ;
Djukanovic, Marko .
PROCEEDINGS OF THE 2023 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION, GECCO 2023 COMPANION, 2023, :239-242
[32]   A construction heuristic for the capacitated Steiner tree problem [J].
Van den Eynde, Simon ;
Audenaert, Pieter ;
Colle, Didier ;
Pickavet, Mario .
PLOS ONE, 2022, 17 (06)
[33]   The Steiner cycle and path cover problem on interval graphs [J].
Custic, Ante ;
Lendl, Stefan .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 43 (01) :226-234
[34]   Scatter Search for solving the Course Timetabling Problem [J].
Jaradat, Ghaith M. ;
Ayob, Masri .
2011 3RD CONFERENCE ON DATA MINING AND OPTIMIZATION (DMO), 2011, :213-218
[35]   A practical greedy approximation for the directed Steiner tree problem [J].
Watel, Dimitri ;
Weisser, Marc-Antoine .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (04) :1327-1370
[36]   A Practical Greedy Approximation for the Directed Steiner Tree Problem [J].
Watel, Dimitri ;
Weisser, Marc-Antoine .
COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014), 2014, 8881 :200-215
[37]   A Heuristic Algorithm for the Prize Collecting Steiner Tree Problem [J].
Hosokawa, Y. ;
Chiba, E. .
2014 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2014, :99-102
[38]   An Artificial Fish Swarm Algorithm for Steiner Tree Problem [J].
Ma, Xuan ;
Liu, Qing .
2009 IEEE INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS, VOLS 1-3, 2009, :59-+
[39]   Node-weighted Steiner tree approximation in unit disk graphs [J].
Zou, Feng ;
Li, Xianyue ;
Gao, Suogang ;
Wu, Weili .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (04) :342-349
[40]   Approximations for node-weighted Steiner tree in unit disk graphs [J].
Xu, X. ;
Wang, Y. ;
Du, H. ;
Wan, P. -J. ;
Zou, F. ;
Li, X. ;
Wu, W. .
OPTIMIZATION LETTERS, 2010, 4 (03) :405-416