# A Novel Hybrid Ant Colony Optimization for a Multicast Routing Problem
## 4 ACO&CM Algorithm
### Solution Improvement  
After the feasible solution has been obtained, we try to enhance the solution quality by using improvement strategies. Figure 5 illustrates the process of solution improvement. Figure 5a illustrates an example where a multicast tree has been built. The primary concept behind improvement strategies is trying to seek improved solutions by deleting an edge with the maximum cost. Then a multicast tree is split into two parts of {0, 2, 1, 4, \(d_{2}\), 3, 5, \(d_{3}\)} and {\(d_{1}\)} by deleting edge (2, \(d_{1}\)) with the maximum cost as shown in Figure 5b. Choose a node from the part, in which there is no source node. Extend the node to link the part in which the source node exists until a new tree is produced, see Figure 5c. The new tree must satisfy the multicast constraint. Although the new tree spans all the source node and destination nodes, it does not belong to a multicast tree because there are some excrescent edges after connecting the tree, and the nodes connected by excrescent edges have some leaf nodes which are not multicast members. Therefore, to obtain a true multicast tree, we should prune the leaf nodes, which do not belong to the multicast members in Figure 5d.  
The framework of the ACO&CM algorithm consists of two main procedures which connect the parts together, including as the MDS strategy, pheromone updating, and solution improvement. In this study, the two main procedures are called path construction and tree construction, respectively, which are developed to build feasible multicast trees. The first procedure basically starts from a source node to search for the paths of destinations and each path should satisfy the Qos constraint. Then, the second procedure integrates \(m\) routing paths obtained by applying the first one to build a multicast tree \(T\). The stopping criterion consists of the convergence rule and the maximum iterations. The process stops when the stopping criterion is satisfied. The main steps of hybrid algorithm would be formulated as below:  
**Step 1**: Initialization. Input the pheromone trails on all edges, edge cost \(c(e)\), link delay \(d(e)\), link bandwidth \(b(e)\), and \(D_{d}\), \(B_{d}\), \(J_{d}\), and \(PL_{d}\) parameters. Let \(s\) be the starting node, and \(M=\{d_{1}\), \(d_{2}\),..., \(d_{m}\)} as destination nodes. Set population number as \(TreeNum\). Set \(iter=0\) where \(iter\) counts the number of iteration and will be compared to the maximum number of iterations, \(CN_{\max}\).  
Figure 5: Illustration of solution improvement process.  
**Step 2**: Initialize the tree set \(S_{T}=\emptyset\);  
**Step 3**: Execute path construction procedure to obtain \(m\) routing paths starting from the node \(s\) to destination nodes. Record the completed routing path in \(PL\).  
**Step 4**: Execute tree construction procedure to produce a multicast tree \(T\), which is created by merging \(m\) paths. Store the multicast tree in \(T\). Update local pheromone trail accord to formula (10).  
**Step 5**: Improvement solutions.  
**Step 6**: Calculate the fitness values of \(T\) and check whether to update the current best solution \(T_{bestsol}\). If condition \(C(T)<C(T_{bestsol})\) then \(T_{bestsol}=T\).  
**Step 7**: Add \(T\) to \(S_{T}\), i.e., \(S_{T}=S_{T}\cup T\).  
**Step 8**: Repeat Steps 3-7 until \(\mid\)\(S_{T}\)\(\mid\)?_TreeNum_.  
**Step 9**: Update global pheromone trail on the edges of \(T_{bestsol}\) using formula (12).  
**Step 10**: Set \(iter=iter+1\);  
**Step 11**: Repeat Steps 2-11 until the algorithm converges or \(iter>CN_{\max}\).