We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A unified algorithm based on HTS and self-adapting PSO for the construction of octagonal and rectilinear SMT.
- Authors
Liu, Genggeng; Chen, Zhisheng; Zhuang, Zhen; Guo, Wenzhong; Chen, Guolong
- Abstract
The Steiner minimal tree (SMT) problem is an NP-hard problem, which is the best connection model for a multi-terminal net in global routing problem. This paper presents a unified algorithm for octagonal and rectilinear SMT construction based on hybrid transformation strategy (HTS) and self-adapting particle swarm optimization. Firstly, an effective HTS is proposed to enlarge the search space and improve the convergence speed. Secondly, the proposed HTS in the evolutionary process may produce an ineffective solution, and consequently the crossover and mutation operators of genetic algorithm (GA) based on union-find sets is proposed. Thirdly, a self-adapting strategy that can adjust the acceleration coefficients is proposed to further improve the convergence and the quality of the proposed algorithm. Finally, the hybrid transformation can be applied to GA and the proposed algorithm can be applied to rectilinear architecture. To our best knowledge, the proposed algorithm is the first unified algorithm to solve the SMT construction under both octagonal and rectilinear architecture. The experimental results show that the proposed algorithm can efficiently provide a better solution for SMT problem both in octagonal and rectilinear architectures than others. Moreover, the algorithm can obtain several topologies of SMT, which is beneficial for optimizing congestion in VLSI global routing stage.
- Subjects
PARTICLE swarm optimization; NP-hard problems; ALGORITHMS; GENETIC algorithms
- Publication
Soft Computing - A Fusion of Foundations, Methodologies & Applications, 2020, Vol 24, Issue 6, p3943
- ISSN
1432-7643
- Publication type
Article
- DOI
10.1007/s00500-019-04165-2