Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems
Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems
复制标题
DOI：
10.1007/s10732-012-9198-2
复制
发表时间：
2013-04
影响因子：
2.7
通讯作者：
R. Qu;Ying Xu;J. P. Castro;Dario Landa Silva
中科院分区：
文献类型：
--
作者：
R. Qu;Ying Xu;J. P. Castro;Dario Landa Silva
本文首次将粒子群优化(PSO)算法应用于Steiner树问题和时延受限组播路由问题。Steiner树问题，作为许多应用的基础模型，在元启发式社区中受到了极大的研究关注。关于元启发式算法在多播路由问题中的应用的文献较少，但包括几种很有前途的方法。许多有趣的研究问题仍有待研究，例如，在寻找代价最小的组播树时，如何包含不同的约束条件，如延迟界。在Moreno-Perez等人新近提出的跳跃PSO(JPSO)算法的基础上，提出了一种新的PSO算法。(程序2007年第七届元启发式国际会议)，并在我们的JPSO框架内提出了两种新的局部搜索启发式算法。在粒子移动中使用了路径替换操作符，以改善粒子相对于树结构的位置。通过对OR库中的多播路由基准问题和Steiner树问题的大量实验，我们测试了JPSO算法的性能和集成局部搜索启发式算法的效果。实验结果表明，所提出的JPSO算法的性能优于其他一些先进的算法。
This paper presents the first investigation on applying a particle swarm optimization (PSO) algorithm to both the Steiner tree problem and the delay constrained multicast routing problem. Steiner tree problems, being the underlining models of many applications, have received significant research attention within the meta-heuristics community. The literature on the application of meta-heuristics to multicast routing problems is less extensive but includes several promising approaches. Many interesting research issues still remain to be investigated, for example, the inclusion of different constraints, such as delay bounds, when finding multicast trees with minimum cost. In this paper, we develop a novel PSO algorithm based on the jumping PSO (JPSO) algorithm recently developed by Moreno-Perez et al. (Proc. of the 7th Metaheuristics International Conference, 2007), and also propose two novel local search heuristics within our JPSO framework. A path replacement operator has been used in particle moves to improve the positions of the particle with regard to the structure of the tree. We test the performance of our JPSO algorithm, and the effect of the integrated local search heuristics by an extensive set of experiments on multicast routing benchmark problems and Steiner tree problems from the OR library. The experimental results show the superior performance of the proposed JPSO algorithm over a number of other state-of-the-art approaches.