ACO-Steiner: Ant Colony Optimization Based Efficient Rectilinear Steiner Minimal Tree Construction
首发时间:2005-01-31
Abstract:he rectilinear Steiner minimal tree (RSMT) problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents an algorithm, called ACO-Steiner, for RSMT construction based on ant colony optimization (ACO). We construct a RSMT with ants’ movements in Hanan grid, and then we break the constraint of Hanan grid to accelerate ants’ movements to improve the performance of the algorithm. This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the fastest exact RSMT algorithm, Geo-Steiner 3.1 and a recent heuristic using batched greedy triple construction (BGTC). Experimental results show that ACO-Steiner can get a short running time and keep the high performance. Furthermore, we also find that our ACO-Steiner is easily extended to be used into some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in g
keywords: physical design, rectilinear Steiner minimal tree (RSMT), routing, ant colony optimization (ACO)
点击查看论文中文信息
ACO-Steiner: Ant Colony Optimization Based Efficient Rectilinear Steiner Minimal Tree Construction
摘要:he rectilinear Steiner minimal tree (RSMT) problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents an algorithm, called ACO-Steiner, for RSMT construction based on ant colony optimization (ACO). We construct a RSMT with ants’ movements in Hanan grid, and then we break the constraint of Hanan grid to accelerate ants’ movements to improve the performance of the algorithm. This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the fastest exact RSMT algorithm, Geo-Steiner 3.1 and a recent heuristic using batched greedy triple construction (BGTC). Experimental results show that ACO-Steiner can get a short running time and keep the high performance. Furthermore, we also find that our ACO-Steiner is easily extended to be used into some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in g
关键词: physical design, rectilinear Steiner minimal tree (RSMT), routing, ant colony optimization (ACO)
论文图表:
引用
No.1517177341107136****
同行评议
共计0人参与
勘误表
ACO-Steiner: Ant Colony Optimization Based Efficient Rectilinear Steiner Minimal Tree Construction
评论
全部评论0/1000