A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems
A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems
复制标题
DOI：
10.1007/s10479-013-1322-7
复制
发表时间：
2013-02
影响因子：
4.8
通讯作者：
Ying Xu;R. Qu;Renfa Li
中科院分区：
文献类型：
--
作者：
Ying Xu;R. Qu;Renfa Li
针对电信网络中的多目标组播路由问题，提出了一种新的混合进化算法。该算法将基于模拟退火的策略与遗传局部搜索相结合，旨在对复杂问题的搜索空间进行更灵活有效的探索和开发，以寻找Pareto Front中更多的非支配解。由于组播树结构复杂，针对该问题的特点和约束条件，专门设计了交叉和变异算子。在混合算法中提出了一种新的基于模拟退火的自适应突变概率，在进化过程中根据新解对当前种群平均质量的适应度自适应调整突变率。为了提高混合进化算法的效率和有效性，采用了两种基于模拟退火的搜索方向调整策略。本文以电信网络中的成本、时延、链路利用率、平均时延和时延变化等5个实际目标，对一些基准多目标组播路由实例和大量随机网络进行了仿真。实验结果表明，与其他多目标进化算法相比，所提出的多目标算法中基于模拟退火的策略和遗传局部搜索都能有效地识别多目标组播路由问题的高质量非支配解集，优于文献中其他传统的多目标进化算法。
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.