A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) APPLYING DE TO GLOBAL AND DETAILED ROUTING <s> Differential Evolut ion (DE) algorithm is a heuristic approach that gains more interest in today's research. It finds the true global minimum regardless of the initial parameter values, fast convergence, and using few control parameters. DE algorithm is a population based algorithm like genetic algorithm using similar operators; crossover, mutation and selection. This paper addresses the restrictive channel routing problem based on the Differential Evolution algorithm. This algorithm advances over other approaches to this problem by using the horizontal and vertical constraints in the solution vector encoding which eliminates unfeasible solutions. This representation leads to lower complexity, because repairing procedures become unnecessary; in addition the search space is reduced greatly. Competitive experimental results proving the consistency of the approach were obtained. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) APPLYING DE TO GLOBAL AND DETAILED ROUTING <s> The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem is a fundamental problem in very large-scale integrated circuit physical design and can be reduced to the Steiner tree problem in graphs (GSTP), which can be solved by using three types of common methods: classic heuristics, local search algorithms, or computational intelligence algorithms. However, classic heuristics have poor solution qualities; local search algorithms easily fall into the problem of the local optimum; and the searching effects of the existing computational intelligence algorithms are poor for this problem. In order to improve the solution quality, we propose a novel discrete artificial bee colony algorithm for constructing an obstacle-avoiding rectilinear Steiner tree. We first generate the escape graph for the OARSMT problem. Then, we search for a near-optimal solution consisting of some edges of escape graph by using the discrete ABC algorithm. We apply a key-node neighborhood configuration for the local search strategy and introduce two local search operators. We then naturally use a key-node-based encoding scheme for representing the feasible solution and obtain a tight searching scope. We employ a modified classic heuristic as the encoder that can produce a feasible solution. Experiments conducted on both general GSTP and very large-scale integrated circuit instances reveal the superior performance of the proposed method in terms of the solution quality among the state-of-the-art algorithms. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) APPLYING DE TO GLOBAL AND DETAILED ROUTING <s> The wire-length of vertically stacked ICs plays a vital role. The wire-length is minimized by using differential evolutionary algorithms withIBM Benchmark inputs. Moreover this wire length is minimized with the respect to the length of the Through Silicon via (TSVs). As a result, the wire-length has been minimized using this algorithm with various parameters. Experimental result shows that the total wirelength can be reduced. <s> BIB003
DE is also widely used in VLSI global routing. Reference BIB003 uses DE for 3D IC global routing to minimize wirelength with respect to Through Silicon Vias (TSV). The mutation operation of the algorithm uses Eq. (8) , that is, the mutation operator creates mutant vectors by perturbing a randomly chosen vector X r 1 with the distinction of two other randomly chosen vectors X r 2 and X r 3 . The crossover and selection operations are performed by Eqs. (13) and (14), respectively. And BIB001 uses DE for restrictive channel routing and use the horizontal and vertical constraints in the solution vector encoding to eliminate unfeasible solution, which leads to lower complexity and reducing search space. D. APPLICATION OF ABC 1) APPLYING ABC TO SMT CONSTRUCTION  presents an ABC algorithm for solving the routing optimization problem, showing noteworthy improvements in reduction of the total interconnected length. The problem is to find a RSMT to connect all terminals or pins, without any severe loss of generality from a grid graph. And the search space is also represented by Steiner Matrix. Since ABC is good at exploration but poor at exploitation, they introduced two steps in the algorithm to improve the exploitation. One is to design a new probabilistic function for selecting food sources that takes into account the type and complexity of the problem, which is described as follows: where ρ is a constant depending on the type and complexity of the problem dealt. The other is a new equation to exploit the food sources in onlooker bee phase of the algorithm, which is described as follows: where x best is the best solution in the current iteration. Using Eq. (41), the worst solution will get the best chance for local search and the best solution in the current population can modify all other solutions in next generation. The specific procedures for solving RSMT problem with ABC are shown in Algorithm 3. Later in 2015, Zhang and Ye BIB002 proposed a discrete ABC for the OARSMT construction which is used for routing the multi-terminal nets in VLSI design. The algorithm generates the escape segments for OARSMT firstly, and then use the discrete ABC to search a near-optimal solution. Compared with the basic ABC algorithm, their algorithm has the following improvements: (1) A key-node-based encoding scheme is adopted to build a tight searching scope for representing the feasible solution; (2) For Steiner tree construction, a modified classic heuristic is presented as the encoder that can construct the Steiner tree with a good solution quality; (3) A key-node neighborhood configuration and two local search operators with an indefinite search step length are applied to the local search strategy; (4) In addition, a global search operator is designed to avoid the generation of the same initial solution every time and a merging operation is used to enhance the global search.