.png){kind=icon}
返回
Node-depth based Genetic Algorithm to solve Inter-Domain path computation problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.knosys.2023.111168.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Inter-Domain Path Computation problem under Node-defined Domain Uniqueness Constraint (IDPC-NDU) is an NP-Hard problem that applies to packet routing in multi-domain networks, particularly Hierarchical Path Computation Element (h-PCE) architecture. Its objective is to determine the shortest route between two specified nodes that visit each domain no more than once. In recent years, many proposals have been made to tackle this problem and improve existing algorithms. However, most of these strategies retain a potential weakness that lies in the complex encoding and decoding methods, which consume a lot of computer resources and computation time, especially for large-scale problems. For this reason, this paper introduces an effective Node-depth based Genetic Algorithm (NDEGA) for IDPC-NDU. We propose a novel solution encoding for the problem by using tree representation that helps to satisfy the domain constraint and makes the corresponding solution construction more practical. Instead of conventional encoding techniques, NDEGA is equipped with an improved Node-depth encoding, which is famous for its low time complexity and efficiency for tree problems. Besides, a corresponding decoding method, as well as node-depth search operators, are also well-developed for the problem. To examine the efficiency of NDEGA, we carefully conduct extensive experiments and compare our approach to many competitive baselines on a wide range of synthetic datasets. The empirical results demonstrate that our proposed algorithm significantly outperforms all compared algorithms regarding solution quality, convergence trend, and computation time and obtains the state-of-the-art performance for IDPC-NDU. Notably, our NDEGA achieves 65.17-85.66% solution quality improvement on average compared to the previous approaches while running faster, approximately 50 - 70 times.
Keyword:
Node-depth encoding
Genetic algorithm
Evolutionary algorithm
Inter-domain path computation
Multi-domain network
期刊
K
IF:
7.6
论文数:
1.3W
被引数:
4.5W
机构
引用论文
.png){kind=icon}
A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms关于使用非参数统计检验作为比较进化和群体智能算法的方法的实用教程
PREAI
分享收藏Electrochemical synthesis of phosphorus-doped graphene quantum dots for free radical scavenging电化学合成磷掺杂石墨烯量子点及其自由基清除性能
PREAI
分享收藏
查看更多内容