ACO-Steiner： Ant Colony Optimization Based Rectilinear Steiner Minimal Tree Algorithm  

作　　者：胡昱 经彤 冯哲 洪先龙 胡晓东 严桂英 

机构地区：[1]Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China [2]Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing 100080, P.R. China [3]Electrical Engineering Deparment, UCLA, Los Angeles, CA 90095, U.S.A.

出　　处：《Journal of Computer Science & Technology》2006年第1期147-152,共6页计算机科学技术学报（英文版）

基　　金：This work was partially supported by the National Natural Science Foundation of China （NSFC） under Grant No. 60373012, and the Specialized Research Fund for the Doctoral Program of Higher Education （SRFDP） of China under Grant No. 20050003099. Some preliminary results of this work were presented at IEEE International Conference on Communications, Circuits and Systems （ICCCAS）, Chengdu, China, 2004.

摘　　要：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 Mso 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.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 Mso 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.

关 键 词：rectilinear Steiner minimal tree （RSMT） ROUTING physical design ant colony optimization （ACO） 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]