# A Novel Hybrid Ant Colony Optimization for a Multicast Routing Problem
## 5 Computational Results  
We present an experimental study to verify the performance of the hybrid algorithm. We have implemented a basic ACO algorithm and hybrid algorithm using visual C++. To evaluate the effectiveness of the ACO&CM algorithm, we have carried out numerical experiments on the network topology for the QoS routing problem. Figure 6 shows a test network topology with 30 nodes. Some parameter values in the ACO&CM algorithm directly or indirectly influence the final results. Therefore, these parameter values may be measured on the test instance. We set parameter values as follows: \(q_{0}\)\(\in\)[0.65, 0.80], \(\beta\)\(\in\)[3, 4, 5], \(\alpha=\)\(\rho\)\(\in\)[0.35, 0.50], \(TreeNum=30\). Notably, for each edge, the initial value of \(\tau_{ij}\) is a very small constant, \(\tau_{ij}=(n\cdot L_{\text{best}})^{-1}\), where \(n\) denotes the node number of multicast tree, and \(L_{\text{best}}\) represents the minimum cost of QoS multicast tree, and. All the experiments should be executed for \(CN_{\max}=1000\). The edges are generated randomly. \(c(e)\) is defined as actual distance between two nodes of the edge \(e\). \(d(e)\) and \(b(e)\) of the edge \(e\) are set to sqrt(\(c(e)\)), \(c(e)/2\), respectively. To investigate the convergence properties of ACO and ACO&CM algorithms, we test their convergence performance on the 30 nodes. Due to publishing space restrictions, we only provide the convergence performance of two algorithms averaged over 20 runs on this test problem. Figure 7 traces the dynamic changes of best cost with the iteration variation for two algorithms. From the results in Figure 7, the convergence process of ACO&CM is shown to be faster than that of ACO. It demonstrates that ACO&CM algorithm has a higher search ability than the ACO  
Figure 6: A test network topology. To evaluate the stability of our proposed ACO&CM algorithm, we further test the algorithm independently 20 runs on the problem instances with 30 nodes. For each independent run, the best cost values of the objective function are depicted in Figure 8. From the result in Figure 8, it can also be observed that ACO&CM yields a much lower cost than that produced by ACO. Both of ACO&CM and ACO algorithms can obtain a feasible solution in 20 runs. Once again, this result illustrates the effectiveness of ACO&CM. To give further evidence concerning the conclusion, we evaluated scalability of algorithms with the instance size according to the execution time in seconds and the corresponding best cost of a multicast tree. Table 1 shows the best cost and corresponding run time of ACO and ACO&CM algorithms for the problem instance. The node number column shows the number of testing instance nodes. These testing instances are from small size with 30 nodes to large size with 175 nodes. In Table 1, ACO represents the basic ant colony optimization without combining with some other algorithms, and ACO&CM refers to the proposed algorithm. Table 1 has also shown the gap between the ACO and ACO&CM algorithms. The gap is specified as percentage improvement in the cost values of the two algorithms. Form Table 1, we discover that the hybrid proposed algorithm can yield best performance of the minimum cost objective. Concerning solution quality, we can conclude that the  
Figure 8: Comparison of the cost of ACO and ACO&CM. Figure 7: Comparison of the convergence of ACO and ACO&CM. average cost of multicast tree obtained by ACO&CM is much less than that by basic ACO, and the ACO&CM algorithm can easily find the better solution with significantly shorter computation times. The average improvement gap is 2.78%, and the percentage shows that our proposed ACO&CM algorithm is much better and more efficient than ACO algorithm for the minimum cost objective to solve the QoS multicast routing problem. In order to a make further comparative analysis of the proposed algorithm's performance on the QoS routing problem, the proposed algorithm is also compared with performance of GA. The GA proposed by [PERSON] et al.