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

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


Authors

Ying Xu

Profile Image

RONG QU rong.qu@nottingham.ac.uk
Professor of Computer Science

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.

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 Springer Verlag
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 https://nottingham-repository.worktribe.com/output/1001859
Publisher URL http://link.springer.com/article/10.1007%2Fs10479-013-1322-7
Additional Information The final publication is available at Springer via http://dx.doi.org/10.1007/s10479-013-1322-7

Files





You might also like



Downloadable Citations