An effective genetic algorithm for multicast routing tree with degree delay constrain
Lin Chen, Zhengquan Xu · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2005
With the advent of many new multimedia applications with Quality of Service (QoS), the issue of multicast routing has become more and more important. Some previous researches in this area mainly take bounded end-to-end delay into account and neglect the ability of router in supporting multicasting, therefore a new multicast routing algorithm based on genetic algorithm (GA) is proposed to construct Degree-Delay-Constrained least-cost multicast routing Tree (DDCT problem). Our proposed algorithms adopt pruefer coding and decoding technique which is very suitable for crossover and mutation operation and can save runtime; Otherwise because pruning and grafting techniques are used to adjust node degree and repair tree structure, this algorithms may also be employed when taking dynamic adjusting tree or keeping load balance into consideration. Simulations were conducted on a random graph to evaluate the performance of the proposed algorithm compared with that of the other algorithms such as CSPT and Wang_GA. The experimental result shows that the proposed algorithm performs well.