RONG QU rong.qu@nottingham.ac.uk
Professor of Computer Science
Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems
Qu, Rong; Xu, Ying; Castro-Gutierrez, Juan; Landa-Silva, Dario
Authors
Ying Xu
Juan Castro-Gutierrez
DARIO LANDA SILVA DARIO.LANDASILVA@NOTTINGHAM.AC.UK
Professor of Computational Optimisation
Abstract
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.
Citation
Qu, R., Xu, Y., Castro-Gutierrez, J., & Landa-Silva, D. (2013). Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems. Journal of Heuristics, 19(2), https://doi.org/10.1007/s10732-012-9198-2
Journal Article Type | Article |
---|---|
Publication Date | Apr 1, 2013 |
Deposit Date | Feb 26, 2015 |
Publicly Available Date | Feb 26, 2015 |
Journal | Journal of Heuristics |
Print ISSN | 1381-1231 |
Electronic ISSN | 1381-1231 |
Publisher | Springer Verlag |
Peer Reviewed | Peer Reviewed |
Volume | 19 |
Issue | 2 |
DOI | https://doi.org/10.1007/s10732-012-9198-2 |
Keywords | delay constrained multicast routing, Steiner tree problems, particle swarm optimization |
Public URL | https://nottingham-repository.worktribe.com/output/1002485 |
Publisher URL | http://link.springer.com/article/10.1007%2Fs10732-012-9198-2 |
Additional Information | The final publication is available at Springer via http://dx.doi.org/10.1007/s10732-012-9198-2 |
Files
JOH12-JPSOmrp.pdf
(464 Kb)
PDF
You might also like
Models of Representation in Computational Intelligence [Guest Editorial]
(2023)
Journal Article
Automated algorithm design using proximal policy optimisation with identified features
(2022)
Journal Article
An Efficient Federated Distillation Learning System for Multitask Time Series Classification
(2022)
Journal Article
A Collaborative Learning Tracking Network for Remote Sensing Videos
(2022)
Journal Article
Adaptive Fuzzy Learning Superpixel Representation for PolSAR Image Classification
(2021)
Journal Article
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: digital-library-support@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search