Hybrid of Genetic Algorithm and Particle Swarm Optimization for Multicast QoS Routing

Multicast routing is an effective way to communicate among multiple hosts in a network. For multimedia applications, the routing algorithms should consider many Quality of Service (QoS) parameters such as delay, cost and so on to find a new route. However, to find routes with two or more QoS parameters is an NP-hard problem. This paper describes a new evolutionary scheme for optimization of multicast QoS routing based on the hybrid of Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), called HGAPSO. In HGAPSO, individuals in a new generation are created, not only by crossover and mutation operation as in GA, but also by PSO. The upper-half of the best-performing individuals in a population are regarded as elites. Instead of being reproduced directly to the next generation, these elites are first enhanced. The group constituted by the elites is regarded as a swarm, and each elite corresponds to a particle within it. In this regard, the elites are enhanced by PSO, an operation which mimics the maturing phenomenon in nature. This scheme can simultaneously optimize the cost of the tree, the maximum end-to-end delay, the average delay and the maximum link utilization. In this way, a set of optimal solutions, known as Pareto set, is calculated in only one run, without a priori restrictions. It has revealed an efficient method of the reconstruction of multicast tree topology and the experimental results demonstrated better performance than the conventional GA optimization method.