A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. APPLICATION OF ACO 1) APPLYING ACO TO SMT CONSTRUCTION <s> The rectilinear Steiner minimum 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 a practical heuristic for RSMT construction based on ant colony optimization (ACO). This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the GeoSteiner 3.1 and a recent work using batched greedy triple construction (BGTC). Experimental results show that our algorithm, named ACO-Steiner, can get a very short run time and keep the high performance. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. APPLICATION OF ACO 1) APPLYING ACO TO SMT CONSTRUCTION <s> Routing is one of the important steps in VLSI/ULSI physical design. The rectilinear Steiner minimum tree (RSMT) construction is an essential part of routing. Since macrocells, IP blocks, and prerouted nets are often regarded as obstacles in the routing phase, obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. This paper focuses on the OARSMT problem and presents an algorithm, named An-OARSMan, based on ant colony optimization. A greedy obstacle penalty distance (OP-distance) local heuristic is used in the algorithm and performed on the track graph. The algorithm has been implemented and tested on different kinds of obstacles. Experimental results show that An-OARSMan can handle complex obstacle cases including both convex and concave polygon obstacles with good length performance. It can always achieve the optimal solution in the cases with no more than 7 terminals. <s> BIB002
ACO algorithm is widely used to construct SMTs BIB001  BIB002 . In general, we generate the Hanan grid of the terminal set T . Then place the ants in each terminal that needs to be connected. An ant will determine a new vertex by some rules and move to that vertex via an edge in Hanan grid. Each ant maintains its own tabu-list, which records the visited vertices to avoid revisiting it again BIB001 . Every time the ants move, the ants will leave a footprint called pheromone on the edge that has just passed, which will evaporate at a constant rate. The process of an ant moving to the next vertex depends on a higher value p i,j , which is a trade-off between the desirability and the trail intensity. Given ant m in vertex i, the desirability of vertex j is defined as follows: where γ is a constant, ψ m j is the shortest distance from vertex i to all the vertices in the tabu-list of others as quickly as possible. We use Eq. (2) to update the trail intensity in Hanan edge (i, j), where the increment of updating is given by the following formula: where c(S t ) is the total cost of the current result tree S t , E t is the edge set of it, and Q is a constant which matches the quantity of the tree cost. Based on Eq. (1), the probability of an ant using edge (i, j) to move is defined as follows: 4 Select an ant m randomly; where A is the set made up of all vertices, which are connected with i and are not in the tabu-list of ant m BIB001 . The process of constructing an RST using ACO is shown in Algorithm 1  . In Step 5, function AntMove(m) decides the next vertex that the current ant m will move to. And the encounter between two ants is described in Step 7 to 10. When ant m encounters ant m 1 , ant m dies, and the vertices in the m's tabu-list are added into m 1 's. If m 1 is still in the original position, Relocate(m 1 ) will re-create its position. When there is only one ant left, the tree is built. At the same time, Prune(t) is used to delete all 1-degree non-terminal vertices in the tree. However, using ACO to find SMT is still time consuming because the ant's movement is based on the Hanan grid, and only a small segment can be moved per iteration. So  extends the tabu-list of each ant to record the edges instead of the vertices that this ant has visited so that every movement is not constrained by Hanan grid. They defined the distance between the two sides as follows: The distances between edge L 1 and L 2 in Figure 5 (a), 5(b), 5(c), and 5(d) are h, h+w, h and h + w, respectively. And there are two possible ways to move when the shortest path is L-shape, which are TOP_ORIENT and BOTTOM_ORIENT. One orientation is chosen to move based on both the trail intensity and the topology. For a given edge orientation, the rules we find the closest vertex to the edge are shown in Figure 6 . In Figure 6 (c) and 6(d), vertex B represents the current location of an ant, and the closest vertex out of its tabu-list is vertex C. Next, the ant needs to decide the orientation of edge (B, C). Figure 6 (c) shows that the closest vertex to edge (B 1 , C 1 ) is A 1 with distance |A 1 A 1 | for BOTTOM_ORIENT. While for TOP_ORIENT, the distance between A 2 and edge (B 2 , C 2 ) is |A 2 A 2 |, which is shown in Figure 6  The authors rewrote Eq. (23) according to this rule as follows: where d is the two orientations (BOTTOM_ORIENT and TOP_ORIENT), gain d is the gain in orientation d, dist d is the distance from the closest vertex out of its tabu-list to the edge in orientation d, and λ is a constant that is the trade-off between the closest distance and gain. In this way, an ant can cross several edges of Hanan grid in each iteration and one ant will be removed from the set of alive ants in each movement. This ACO-Steiner algorithm  can be used to construct initial trees for all nets and optimize the routing tree iteratively to further reduce wirelength. Moreover, this algorithm can generate different topologies with the same wirelength for a net, which is beneficial to reduce congestion scarifying only a little wirelength. Reference BIB002 presents an Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) algorithm based on ACO. In this algorithm, an efficient graph reduction method, called T-Reduction, is adopted to reduce the searching space. This method is implemented by maintaining an FIFO queue. Firstly all 2-degree vertices are pushed into the queue. Then pop the first vertex from the queue, delete the vertex and its adjacent edges, and its adjacent non-terminal vertices are pushed into the queue while the queue is not empty. Later, non-terminal convex corner points are reduced. And finally reduce 1-degree terminals. Such terminals can be deleted along with their adjacent edges. It's worth mentioning that T-Reduction method is very efficient when the case scale is not large and is also suitable for escape graph reduction. And a greedy obstacle penalty distance (OP-distance) local heuristic is used in this OARSMT algorithm at the same time, where the OP-distance is used to estimate the distance between two vertices in the presence of obstacles. The proposed algorithm has a high optimization capability of wirelength and can handle complex obstacle cases including both convex and concave polygon obstacles.