基于并行遗传蚁群算法的组播路由调度算法

Multicast routing algorithm based on paralleling genetic ant colony algorithm

组播是将信息从源节点同时发送到网络中多个目的节点的通信方式,这是网络规模日益增大,信息流量增大的必然结果。组播路由是用一点到多点的方式传送信息,组播路由问题已被证明是NP-Complete问题。文中结合遗传算法GA和蚁群算法ACA的优点,提出了一种并行的遗传蚁群算法GACA,并把该算法应用到求解组播路由问题中。GACA算法利用遗传算法的快速性、随机性、全局收敛性产生求解问题的初始信息素分布,通过选择,交叉,变异等遗传操作产生一组新的个体,然后再利用蚂蚁算法群体并行性、正反馈性、求解效率高的特点,实现组播路由优化选择。仿真实验结果表明,该算法不但实现了组播路由的全局优化,而且在时间效率上优于现有的组播路由算法。

Multicast routing is a source node sends the same message to a group of destination nodes, which has been proved to be a NP-Complete problem. In the present paper, we concentrate on those questions above and give a genetic ant colony algorithm （GACA） based on the combining with the advantages of genetic algorithm and ant colony algorithm. And we applied the GACA to the application of solving the multicast routing. GACA algorithm uses the speediness, randomicity and whole astringency of genetic algorithm to generate the distribution of the initial information element to the solving problems, then generates a group of new units though genetic operations such as reproduction, crossover and mutation. After that, it utilizes the parallel, feed-back and high solving efficiency of ant algorithm to realize the optimized selection to Multicast routing. Shown by the results of the simulation experiment, this algorithm can realize the whole optimization of the Multicast routing with a higher efficiency in time compared to the existing multicasting routing algorithm.