# A Novel Hybrid Ant Colony Optimization for a Multicast Routing Problem
## 4 ACO&CM Algorithm
### Path Construction  
In the process of constructing paths, ants sequentially find the minimum cost path proceeding from a source node \(s\) to destination nodes. It is necessary for one path to determine a nice sequence of nodes with the least cost. Each individual ant starting at the source node \(s\) simulates a path. The ants sequentially choose nodes to construct paths. Initially, the ant \(k\) successively chooses the node \(j\) and forms the sequence of nodes in the path until the ant completes the path. The selected nodes should first satisfy QoS multicast route constraints in the delay, residual bandwidth and the delay jitter as defined in constraints (3), (4) and (5), and then packet loss as described in constraints (6). If a node violates one or more of the constraints, the node should not be chosen, and the next node will be  
Figure 4: An instance of producing the inter-loop. selected to check whether the constraint condition is satisfied. When ant \(k\) is building the path, at the node \(i\) the ant would select node \(j\) according to the following rules:  
\[j=\left\{ \begin{array}{c}\operatorname*{argmax}_{u\
otin M_{k}}\{\tau_{il} \cdot[\eta_{il}]^{\beta}\},\text{ if }q\leq q_{0}\\ S,\text{ otherwise}\end{array} \right. \tag{8}\]  
in which \(\tau_{il}\) represents pheromone trail concentration between \(i\) and \(j\) nodes, and \(\beta\) represents a parameter determining the comparative effect of visibility. The value \(q\) denotes a random variable, and it is a uniform value in [0, 1]. \(q_{0}\)\(\in\)[0, 1] is a user-specified parameter value. The visibility \(\eta_{il}\) is an inverse of an edge. \(M_{k}\) is the collection set including all the nodes that the ant \(k\) has already visited. Other ants cannot select the nodes in the set \(M_{k}\). If the \(q\leq q_{0}\) condition is satisfied, an edge with the minimum cost is determined according to Equation (8); otherwise, choose an edge depending on \(S\). \(S\) is a random variable using the random distribution given as the following:  
\[P_{ij}^{k}=\left\{ \begin{array}{c}\frac{\left[\tau_{ij}\right]^{\alpha} \left[\eta_{ij}\right]^{\beta}}{\sum\limits_{t\in M_{k}}\left[\tau_{il} \right]^{\alpha}\left[\eta_{il}\right]^{\beta}},j\
otin M_{k}\\ 0,\text{ otherwise}\end{array} \right. \tag{9}\]  
where \(\alpha\) is a parameter. \(\alpha\) denotes the relative effect of the pheromone concentration, indicating the influence of accumulated pheromone trail in the process of ant movement. The bigger the value of \(\alpha\), the more inclined other ants are to choose the same paths. \(p_{ij}^{k}\) is the transition probability of the ant \(k\). In ACO algorithms, the path construction process is similar to a greedy rule, except for choosing the next node by the probabilistic formula rule rather than the deterministic one. In the process of constructing the node sequence of the path, each individual ant not only considers the QoS constraint conditions, but also adopts the MDS strategy to avoid the generation of a loop. The MDS strategy uses the current list (\(CL\)), and the path list (\(PL\)) memory structures to avoid the generation of a loop. The \(CL\) records current path nodes in case of forming the self-loop, and the \(PL\) stores all the routing paths to avoid the generation of the inter-loop. Every path is put in \(PL\) set and every element represents a path in this set. \(N_{ant}\) denotes the number of ants, which is the same with a destination node number. Every ant simulates a path starting from a given source node to a destination. In the process of constructing the paths, these paths are searched by the ACO mechanism and every path should satisfy the QoS constraint.