A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> C. APPLICATION OF DE 1) APPLYING DE TO SMT CONSTRUCTION <s> The Rectilinear Steiner Minimal Tree (RSMT) problem is an NP-hard problem, which is one of the key problems in VLSI/ULSI physical design. Particle Swarm Optimization (PSO) has been proved to be an efficient intelligent algorithm for optimization designs. This paper presents a RSMT algorithm based on discrete PSO (DPSO), namely BRRA_DPSO, to minimize the wiring length and reduce the number of bends, which is helpful for via reduction and reliability increment in the routing phase. In order to solve the problem of the slow convergence rate of PSO used for a high-dimensional space optimization, a self-adapting strategy that can adjust the learning factors, and combine with the crossover and mutation operators of Genetic Algorithm (GA) is proposed. The experimental results show that the proposed algorithm can efficiently provide the solution of RSMT problem with good quality and converge more rapidly than GA. Moreover, the algorithm can also reduce the number of bends. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> C. APPLICATION OF DE 1) APPLYING DE TO SMT CONSTRUCTION <s> The Octagonal Steiner Minimal Tree (OSMT) problem is an NP-hard problem, which is one of the key problems in non-Manhattan routing. Particle Swarm Optimization (PSO) has been proved to be an efficient intelligent algorithm for optimization designs. This paper presents an OSMT algorithm based on discrete PSO (DPSO), namely OSMT_DPSO, to optimize the wire length. In order to solve the problem of the slow convergence rate of PSO used for a high-dimensional space optimization, a self-adapting strategy that can adjust the learning factors, and combine with the crossover and mutation operators of Genetic Algorithm (GA) is proposed. The experimental results show that the proposed algorithm can efficiently provide the solution of OSMT problem with good quality. Moreover, the algorithm can obtain several topologies of OSMTs which is beneficial for optimizing congestion in VLSI global routing stage. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> C. APPLICATION OF DE 1) APPLYING DE TO SMT CONSTRUCTION <s> Global routing in VLSI design is a difficult discrete optimization problem. This paper describes the global VLSI routing using Differential Evolution based optimization technique to find out the minimum routing wire length. The routing process determines the precise paths to interconnect the chip components. The geometrical layout of the path connected in the chip must be satisfied its design requirements. This paper proposes a novel approach to apply of Differential Evolution algorithm for solving the optimization problems in discrete spaces. Performance of this approach in VLSI routing is effective and it can be efficiently used in other discrete optimization problems. The results obtained in this work are compared with other evolutionary computing techniques like Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC) and FLUTE algorithm which are frequently used in routing problems. <s> BIB003 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> C. APPLICATION OF DE 1) APPLYING DE TO SMT CONSTRUCTION <s> As the best connection model for the multi-pin net of the non-Manhattan architecture global routing problem, the X-architecture Steiner Minimum Tree (XSMT) construction is a Non-deterministic Polynomial hard (NP-hard) problem. The Differential Evolution (DE) algorithm has shown good application effect in solving various NP-hard problems. For this reason, based on the idea of DE algorithm, this paper proposes an XSMT construction algorithm for solving this problem. First of all, because the traditional DE algorithm is designed for continuous problems, the optimization ability is limited in solving discrete problems. This paper proposes a novel crossover operator and mutation operator. At the same time, in order to maintain the effectiveness of the evolutionary algorithm, an Edge-to-Point coding strategy suitable for evolutionary algorithms is proposed to better preserve the optimal substructure of the population. Finally, in order to speed up the convergence speed and quality of the algorithm, this paper proposes an initial solution based on the minimum tree generation algorithm. Experiments show that the effectiveness of the proposed algorithm and related strategies can construct a high-quality XSMT solution. <s> BIB004
Manna et al. BIB003 described an improved DE for finding RSMT. The entire search space is represented by an n-by-n null matrix, where n is the dimension of search space. Then randomly change the element from '0' to '1' to produce an initial population. In order to better solve the discrete problem, they redesigned the three links of DE as follows: (1) Mutation. Choose one particle randomly, then change the elements of the matrix randomly from '0' to '1'. The elements which are already equal to 1 are kept intact. This new matrix is treated as mutant matrix. (2) Crossover. Crossover is performed between mutant matrix and target matrix to generate a trial Matrix using Eq. (13) . If a generated random number is greater than the CR then an entire row (or column) is copied from target particle's position matrix to newly formed trial particle's position matrix. Otherwise the row (or column) is copied from the mutant matrix. (3) Selection. The fitness values of trial matrix and target matrix are compared. The target matrix will be replaced by a matrix with better fitness value. The proposed algorithm works well in both small and large dimensional routing problems. And because of DE's simplicity and flexibility, it can also be used in other discrete optimization problems. In 2019, Wu et al. BIB004 proposed a feasible and effective X-architecture SMT construction algorithm based on Discrete Differential Evolution (DDE). And they designed new mutation and crossover operators combined with UFS for DDE. In this work, every particle is encoded as a numerical string by Edge-to-Point encoding like BIB002 . And the last bit represents the length of OSMT, while the fitness is set to the function of the length. Eqs. (8) , (13) and (14) are adopted as particle updating formulas, respectively representing mutation, crossover and selection operations. They designed novel operators and the corresponding evolution of using DE to search for OSMT is shown in Figure 12 . (1) Mutation. The subtraction operation in Eq. (8) refers to the difference set operation, and the addition operation refers to the union operation of the set. Choose three particles randomly, respectively p 1 , p 2 , p 3 . So the subtraction operation can be divided into two cases: • One is that the result of p 2 − p 3 is empty set. Edge m 1 to be mutated is randomly selected from particle p 1 , then delete this edge, and p 1 is divided into two sub trees. Combining with UFS, two points are randomly selected from the two sub trees respectively and reconnected as the mutation particle (as shown in Figure 12(a) ). • The other is that the result of p 2 − p 3 is not empty. The elements of the difference set are as part of the edges of mutation result. Then select the remaining from the edge set of p 1 to reconstruct a new tree as the final mutation particle (as shown in Figure 12(b) ). (2) Crossover. When the mutated particle m crosses with the current particle i, the following action is performed: The common edges of the two trees are used as the starting set, and the remaining edges are used as the candidate set. Combining with UFS, constantly extract the remaining edges from candidate set until the crossover result is a legal tree (as shown in Figure 12(c) ). (3) Selection. A greedy strategy based on fitness is adopted in selection operation. Compared with DPSO-based RSMT BIB001 and OSMT BIB002 construction algorithms, this kind of DDE can achieve a greater wirelength reduction on solving RSMT problem and in terms of constructing OSMT, the wirelength optimization ability is similar to that in BIB002 . It can be seen that DE has certain advantages over PSO in finding RSMT.