GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing

The bandwidth-delay-constrained least-cost multicast routing is a challenging problem in high-speed multimedia networks. Computing such a constrained Steiner tree is an NP-complete problem. In this paper, we propose several novel solutions to this problem based on genetic algorithms (GA). The proposed solutions consist of six different schemes for genotype representation, and also several new heuristic algorithms for mutation, crossover, and creation of random individuals. We evaluate the performance and efficiency of the proposed algorithms in comparison with other existing heuristic and GA-based algorithms using simulation results. The most efficient combination of various proposed alternative algorithms is selected as our final solution by the simulation results. This proposed GA-based algorithm has overcome the existing algorithms considering average tree cost and running time. (C) 2003 Elsevier B.V. All rights reserved.