Skip to main content

Research Repository

Advanced Search

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

Xu, Ying; Qu, Rong; Li, Renfa

Authors

Ying Xu

Profile Image

RONG QU rong.qu@nottingham.ac.uk
Associate Professor

Renfa Li



Abstract

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.

Citation

Xu, Y., Qu, R., & Li, R. (2013). A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems. Annals of Operations Research, 260(1), doi:10.1007/s10479-013-1322-7

Journal Article Type Article
Publication Date Jul 1, 2013
Deposit Date Feb 26, 2015
Publicly Available Date Feb 26, 2015
Journal Annals of Operations Research
Print ISSN 0254-5330
Electronic ISSN 1572-9338
Publisher Humana Press
Peer Reviewed Peer Reviewed
Volume 260
Issue 1
DOI https://doi.org/10.1007/s10479-013-1322-7
Keywords Multi-objective Genetic Local Search, Simulated Annealing, Multicast Routing
Public URL http://eprints.nottingham.ac.uk/id/eprint/28284
Publisher URL http://link.springer.com/article/10.1007%2Fs10479-013-1322-7
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf
Additional Information The final publication is available at Springer via http://dx.doi.org/10.1007/s10479-013-1322-7

Files


ANOR2013-gls.pdf (638 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations