ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm

CSpace > 应用数学研究所

	ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm
	Hu, Y ; Jing, T ; Feng, Z ; Hong, XL ; Hu, XD; Yan, GY
	2006
发表期刊	JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
ISSN	1000-9000
卷号	21 期号:1 页码:147-152
摘要	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.
关键词	rectilinear Steiner minimal tree (RSMT) routing physical design ant colony optimization (ACO)
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Software Engineering
WOS记录号	WOS:000235342400017
出版者	SCIENCE PRESS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/2606
专题	应用数学研究所
通讯作者	Hu, Y
作者单位	1.Tsing Hua Univ, Dept Comp Sci & Technol, Beijing 100084, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China 3.Univ Calif Los Angeles, Dept Elect Engn, Los Angeles, CA 90095 USA
推荐引用方式 GB/T 7714	Hu, Y,Jing, T,Feng, Z,et al. ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2006,21(1):147-152.
APA	Hu, Y,Jing, T,Feng, Z,Hong, XL,Hu, XD,&Yan, GY.(2006).ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,21(1),147-152.
MLA	Hu, Y,et al."ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 21.1(2006):147-152.