%0 Journal Article
%T ACO-Steiner: Ant Colony Optimization Based Rectilinear Steiner Minimal Tree Algorithm
%A Yu Hu
%A Tong Jing
%A Zhe Feng
%A Xian-Long Hong
%A Xiao-Dong Hu
%A Gui-Ying Yan
%A <br>Yu Hu
%A Tong Jing
%A Zhe Feng
%A Xian-Long Hong
%A Xiao-Dong Hu
%A and Gui-Ying Yan
%J 计算机科学技术学报
%D 2006
%I 
%X The 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). An RSMT is constructed with ants' movements in Hanan grid, and then the constraint of Hanan grid is broken 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, GeoSteiner 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, it is also found that the ACO-Steiner can be easily extended to be used to some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in global routing.
%K rectilinear Steiner minimal tree (RSMT)
%K routing
%K physical design
%K ant colony optimization (ACO)<br>Steiner最小树
%K RSMT算法
%K 邮件路由
%K 群体优化
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=F833A96D695379E5326F16FC16C1CA2C&yid=37904DC365DD7266&vid=659D3B06EBF534A7&iid=CA4FD0336C81A37A&sid=2922B27A3177030F&eid=D59111839E7C8BDF&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=4&reference_num=23