An improved EDA for solving Steiner tree problem
An improved EDA for solving Steiner tree problem
复制标题
DOI：
10.1002/cpe.3466
复制
发表时间：
2015-09
期刊：
影响因子：
--
通讯作者：
Lei Liu;Hua Wang;Guohong Kong
中科院分区：
文献类型：
--
作者：
Lei Liu;Hua Wang;Guohong Kong
斯坦纳树问题及其衍生问题被广泛应用于交通运输、通信网络、生物工程和QoS组播路由问题的优化设计。这是一个明确定义的开放问题，吸引了许多研究努力。与已有的研究不同，本文提出了一种利用改进的分布估计算法（EDA）求解Steiner树问题的新方法。最后，将该方法应用于组播路由优化，验证了其性能。该方法随机初始化n棵包含源节点和目的节点的树。一些个体随机选择交叉操作，增加种群多样性，避免算法过早收敛。该算法根据选择的精英构建概率模型，能够估计解的概率分布。根据新的总体更新概率模型。根据概率模型生成新的树。此过程迭代，直到满足指定的终止标准。改进的EDA算法逐步进化树以获得更好的解。仿真验证表明，该方法具有较好的性能。特别是与其他算法相比，在收敛速度方面的复杂性有了显著提高。版权所有©2015 John Wiley & Sons， Ltd
Steiner tree problem and its derivations are widely employed to optimize the design of transportation, communication networks, biological engineering and the QoS multicast routing problem. It is one of well‐defined open issues which have attracted many research efforts. Different from the existing works, this paper develops a new method of solving Steiner tree problem by using the improved estimation of distribution algorithms (EDA). Further, the performance of developed method is validated by applying on multicast routing optimization. The developed method randomly initializes n trees which contain the source node and the destination nodes. And some individuals select the crossover operation randomly to add the population diversity and avoid the algorithm premature convergence. The algorithm constructs a probabilistic model according to the selected elites, which is capable of estimating the probability distribution of the solution. The probabilistic model is updated according to the new population. New trees are generated based on the probabilistic model. This process iterated until designated termination criteria are met. The improved EDA algorithm gradually evolves trees to obtain a better solution. Simulation validations suggest that the developed method leads to better performance. In particular, the complexity in terms of the converging speed improves significantly compared to other algorithms. Copyright © 2015 John Wiley & Sons, Ltd.