A new genetic algorithm based on modified Physarum network model for bandwidth-delay constrained least-cost multicast routing

详细信息    查看全文

• 作者：Mingxin Liang ; Chao Gao ; Zili Zhang
• 关键词：Multicast routing ; Genetic algorithm ; Physarum network model
• 刊名：Natural Computing
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：16
• 期：1
• 页码：85-98
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Evolutionary Biology; Processor Architectures; Artificial Intelligence (incl. Robotics); Complex Systems;
• 出版者：Springer Netherlands
• ISSN：1572-9796
• 卷排序：16

文摘

A mobile ad hoc network is a kind of popular self-configuring network, in which multicast routing under the quality of service constraints, is a significant challenge. Many researchers have proved that such problem can be formulated as a NP-complete problem and proposed some swarm-based intelligent algorithms to solve the optimal solution, such as the genetic algorithm (GA), bees algorithm. However, a lower efficiency of local search ability and weak robustness still limit the computational effectiveness. Aiming to those shortcomings, a new hybrid algorithm inspired by the self-organization of Physarum, is proposed in this paper. In our algorithm, an updating scheme based on Physarum network model (PM) is used for improving the crossover operator of traditional GAs, in which the same parts of parent chromosomes are reserved and the new offspring by the PM is generated. In order to estimate the effectiveness of our proposed optimized scheme, some typical genetic algorithms and their updating algorithms (PMGAs) are compared for solving the multicast routing on four different datasets. The simulation experiments show that PMGAs are more efficient than original GAs. More importantly, the PMGAs are more robustness that is very important for solving the multicast routing problem. Moreover, a series of parameter analyses is used to find a set of better setting for realizing the maximal efficiency of our algorithm.