caa a22 4500 606159746 CHVBK 20210128100626.0 cr unu---uuuuu 210128e20150501xx s 000 0 eng 10.1007/s00521-014-1760-4 doi (NATIONALLICENCE)springer-10.1007/s00521-014-1760-4 Key-node-based local search discrete artificial bee colony algorithm for obstacle-avoiding rectilinear Steiner tree construction [Elektronische Daten] [Hao Zhang, Dong-Yi Ye] The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem is a fundamental problem in very large-scale integrated circuit physical design and can be reduced to the Steiner tree problem in graphs (GSTP), which can be solved by using three types of common methods: classic heuristics, local search algorithms, or computational intelligence algorithms. However, classic heuristics have poor solution qualities; local search algorithms easily fall into the problem of the local optimum; and the searching effects of the existing computational intelligence algorithms are poor for this problem. In order to improve the solution quality, we propose a novel discrete artificial bee colony algorithm for constructing an obstacle-avoiding rectilinear Steiner tree. We first generate the escape graph for the OARSMT problem. Then, we search for a near-optimal solution consisting of some edges of escape graph by using the discrete ABC algorithm. We apply a key-node neighborhood configuration for the local search strategy and introduce two local search operators. We then naturally use a key-node-based encoding scheme for representing the feasible solution and obtain a tight searching scope. We employ a modified classic heuristic as the encoder that can produce a feasible solution. Experiments conducted on both general GSTP and very large-scale integrated circuit instances reveal the superior performance of the proposed method in terms of the solution quality among the state-of-the-art algorithms. The Natural Computing Applications Forum, 2014 NP-complete problem nationallicence Obstacle-avoiding rectilinear Steiner minimal tree problem nationallicence Steiner tree problem in graphs nationallicence Local search nationallicence Artificial bee colony algorithm nationallicence VLSI physical design nationallicence Zhang Hao Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, No. 2 Xueyuan Road, District of Universities, 350108, Fuzhou, People's Republic of China aut Ye Dong-Yi Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, No. 2 Xueyuan Road, District of Universities, 350108, Fuzhou, People's Republic of China aut Neural Computing and Applications Springer London 26/4(2015-05-01), 875-898 0941-0643 26:4<875 2015 26 521 https://doi.org/10.1007/s00521-014-1760-4 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00521-014-1760-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Zhang Hao Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, No. 2 Xueyuan Road, District of Universities, 350108, Fuzhou, People's Republic of China aut NATIONALLICENCE 700 1- Ye Dong-Yi Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, No. 2 Xueyuan Road, District of Universities, 350108, Fuzhou, People's Republic of China aut NATIONALLICENCE 773 0- Neural Computing and Applications Springer London 26/4(2015-05-01), 875-898 0941-0643 26:4<875 2015 26 521