# A Novel Hybrid Ant Colony Optimization for a Multicast Routing Problem
###### Abstract  
Quality of service multicast routing is an important research topic in networks. Research has sought to obtain a multicast routing tree at the lowest cost that satisfies bandwidth, delay and delay jitter constraints. Due to its non-deterministic polynomial complete problem, many meta-heuristic algorithms have been adopted to solve this kind of problem. The paper presents a new hybrid algorithm, namely ACO&CM, to solve the problem. The primary innovative point is to combine the solution generation process of ant colony optimization (ACO) algorithm with the Cloud model (CM). Moreover, within the framework structure of the ACO, we embed the cloud model in the ACO algorithm to enhance the performance of the ACO algorithm by adjusting the pheromone trail on the edges. Although a high pheromone trail intensity on some edges may trap into local optimum, the pheromone updating strategy based on the CM is used to search for high-quality areas. In order to avoid the possibility of loop formation, we devise a memory detection search (MDS) strategy, and integrate it into the path construction process. Finally, computational results demonstrate that the hybrid algorithm has advantages of an efficient and excellent performance for the solution quality. ant colony optimization; multicast routing; memory detection search; cloud model +
Footnote †: journal:  
0000-0001-4500-3399-223]X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. learning into common Internet activities. The key issues of these multimedia applications need to develop efficient and fast multicast routing algorithms. Under severe QoS constraints, multicasting technology provides convenience for these services, and simultaneously makes full use of resource utilization [1; 2]. Providing a high demand of better QoS is essential for many real-time applications. The guaranteed QoS in various network applications usually considers constraints such as bandwidth constraints, delay and delay jitter constraints in order to ensure smooth transmission to destinations. The establishment of the efficient QoS multicast routing problem has increasingly become one of the most critical technologies for ensuring QoS in modern integrated networks. The main objective function is to establish the optimal multicast routing tree covering the source and the multiple destinations while satisfying all QoS requirements. The cost of a QoS multicast tree is equal to the cost sum of all the edges in this tree. A Steiner tree is needed to seek such a tree QoS multicast tree in the network. It is proved that an NP Complete can build a feasible Steiner tree [3] belongs to a NP Complete. A Steiner tree that considers QoS constraints is defined as a constrained Steiner tree. Therefore, it is also an NP complete problem [4] to construct a constrained Steiner tree. Many researchers have been interested in using different methods to solve the QoS multicast routing problem [5]. Generally, there are exact methods and heuristic algorithms to solve this problem. Although important advances have been made in the development of exact and heuristic algorithms for solving the QoS multicast tree, the exact methods to solve the multicast routing problem are a dynamic programming algorithm by Chow [6] and a branch-and-bound algorithm [7]. These two algorithms are the more practically exact methods to solve the multicast routing problem. However, exact algorithms are still unable to solve large scale problems because of the high computational complexity, so in practice, researchers have to pay more attention to heuristic algorithms in the search for a near optimal solution. Heuristic algorithms such as meta-heuristic algorithms are actually the best choice to address the multi-constrained routing problem. They are characterized by simplicity, flexibility, and significant effectiveness. Since meta-heuristics are generally easy to implement, many researchers often adopt them to solve many complex combinatorial optimization problems.