Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks

Meie Shen, Zhi-Hui Zhan, Wei-Neng Chen, Yue-Jiao Gong, Jun Zhang, Yun Li

Research output: Contribution to journalArticle

72 Citations (Scopus)

Abstract

This paper proposes a novel bi-velocity discrete particle swarm optimization (BVDPSO) approach and extends its application to the nondeterministic polynomial (NP) complete multicast routing problem (MRP). The main contribution is the extension of particle swarm optimization (PSO) from the continuous domain to the binary or discrete domain. First, a novel bi-velocity strategy is developed to represent the possibilities of each dimension being 1 and 0. This strategy is suitable to describe the binary characteristic of the MRP, where 1 stands for a node being selected to construct the multicast tree, whereas 0 stands for being otherwise. Second, BVDPSO updates the velocity and position according to the learning mechanism of the original PSO in the continuous domain. This maintains the fast convergence speed and global search ability of the original PSO. Experiments are comprehensively conducted on all of the 58 instances with small, medium, and large scales in the Operation Research Library (OR-library). The results confirm that BVDPSO can obtain optimal or near-optimal solutions rapidly since it only needs to generate a few multicast trees. BVDPSO outperforms not only several state-of-the-art and recent heuristic algorithms for the MRP problems, but also algorithms based on genetic algorithms, ant colony optimization, and PSO.

LanguageEnglish
Article number6779598
Pages7141-7151
Number of pages11
JournalIEEE Transactions on Industrial Electronics
Volume61
Issue number12
Early online date27 Mar 2014
DOIs
Publication statusPublished - 31 Dec 2014

Fingerprint

Particle swarm optimization (PSO)
Telecommunication networks
Operations research
Ant colony optimization
Heuristic algorithms
Genetic algorithms
Polynomials
Experiments

Keywords

  • communication networks
  • multicast routing problem (MRP)
  • particle swarm optimization (PSO)
  • Steiner tree problem (STP)

Cite this

Shen, Meie ; Zhan, Zhi-Hui ; Chen, Wei-Neng ; Gong, Yue-Jiao ; Zhang, Jun ; Li, Yun. / Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks. In: IEEE Transactions on Industrial Electronics. 2014 ; Vol. 61, No. 12. pp. 7141-7151.
@article{fc868325dc754310b30ae2c945183e06,
title = "Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks",
abstract = "This paper proposes a novel bi-velocity discrete particle swarm optimization (BVDPSO) approach and extends its application to the nondeterministic polynomial (NP) complete multicast routing problem (MRP). The main contribution is the extension of particle swarm optimization (PSO) from the continuous domain to the binary or discrete domain. First, a novel bi-velocity strategy is developed to represent the possibilities of each dimension being 1 and 0. This strategy is suitable to describe the binary characteristic of the MRP, where 1 stands for a node being selected to construct the multicast tree, whereas 0 stands for being otherwise. Second, BVDPSO updates the velocity and position according to the learning mechanism of the original PSO in the continuous domain. This maintains the fast convergence speed and global search ability of the original PSO. Experiments are comprehensively conducted on all of the 58 instances with small, medium, and large scales in the Operation Research Library (OR-library). The results confirm that BVDPSO can obtain optimal or near-optimal solutions rapidly since it only needs to generate a few multicast trees. BVDPSO outperforms not only several state-of-the-art and recent heuristic algorithms for the MRP problems, but also algorithms based on genetic algorithms, ant colony optimization, and PSO.",
keywords = "communication networks, multicast routing problem (MRP), particle swarm optimization (PSO), Steiner tree problem (STP)",
author = "Meie Shen and Zhi-Hui Zhan and Wei-Neng Chen and Yue-Jiao Gong and Jun Zhang and Yun Li",
year = "2014",
month = "12",
day = "31",
doi = "10.1109/TIE.2014.2314075",
language = "English",
volume = "61",
pages = "7141--7151",
journal = "IEEE Transactions on Industrial Electronics",
issn = "0278-0046",
number = "12",

}

Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks. / Shen, Meie; Zhan, Zhi-Hui; Chen, Wei-Neng; Gong, Yue-Jiao; Zhang, Jun; Li, Yun.

In: IEEE Transactions on Industrial Electronics, Vol. 61, No. 12, 6779598, 31.12.2014, p. 7141-7151.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks

AU - Shen, Meie

AU - Zhan, Zhi-Hui

AU - Chen, Wei-Neng

AU - Gong, Yue-Jiao

AU - Zhang, Jun

AU - Li, Yun

PY - 2014/12/31

Y1 - 2014/12/31

N2 - This paper proposes a novel bi-velocity discrete particle swarm optimization (BVDPSO) approach and extends its application to the nondeterministic polynomial (NP) complete multicast routing problem (MRP). The main contribution is the extension of particle swarm optimization (PSO) from the continuous domain to the binary or discrete domain. First, a novel bi-velocity strategy is developed to represent the possibilities of each dimension being 1 and 0. This strategy is suitable to describe the binary characteristic of the MRP, where 1 stands for a node being selected to construct the multicast tree, whereas 0 stands for being otherwise. Second, BVDPSO updates the velocity and position according to the learning mechanism of the original PSO in the continuous domain. This maintains the fast convergence speed and global search ability of the original PSO. Experiments are comprehensively conducted on all of the 58 instances with small, medium, and large scales in the Operation Research Library (OR-library). The results confirm that BVDPSO can obtain optimal or near-optimal solutions rapidly since it only needs to generate a few multicast trees. BVDPSO outperforms not only several state-of-the-art and recent heuristic algorithms for the MRP problems, but also algorithms based on genetic algorithms, ant colony optimization, and PSO.

AB - This paper proposes a novel bi-velocity discrete particle swarm optimization (BVDPSO) approach and extends its application to the nondeterministic polynomial (NP) complete multicast routing problem (MRP). The main contribution is the extension of particle swarm optimization (PSO) from the continuous domain to the binary or discrete domain. First, a novel bi-velocity strategy is developed to represent the possibilities of each dimension being 1 and 0. This strategy is suitable to describe the binary characteristic of the MRP, where 1 stands for a node being selected to construct the multicast tree, whereas 0 stands for being otherwise. Second, BVDPSO updates the velocity and position according to the learning mechanism of the original PSO in the continuous domain. This maintains the fast convergence speed and global search ability of the original PSO. Experiments are comprehensively conducted on all of the 58 instances with small, medium, and large scales in the Operation Research Library (OR-library). The results confirm that BVDPSO can obtain optimal or near-optimal solutions rapidly since it only needs to generate a few multicast trees. BVDPSO outperforms not only several state-of-the-art and recent heuristic algorithms for the MRP problems, but also algorithms based on genetic algorithms, ant colony optimization, and PSO.

KW - communication networks

KW - multicast routing problem (MRP)

KW - particle swarm optimization (PSO)

KW - Steiner tree problem (STP)

UR - http://www.scopus.com/inward/record.url?scp=84905655565&partnerID=8YFLogxK

U2 - 10.1109/TIE.2014.2314075

DO - 10.1109/TIE.2014.2314075

M3 - Article

VL - 61

SP - 7141

EP - 7151

JO - IEEE Transactions on Industrial Electronics

T2 - IEEE Transactions on Industrial Electronics

JF - IEEE Transactions on Industrial Electronics

SN - 0278-0046

IS - 12

M1 - 6779598

ER -