AN ADAPTIVE MULTIFACTORIAL EVOLUTIONARY ALGORITHM FOR INTER-DOMAIN PATH COMPUTATION UNDER NODEDEFINED DOMAIN UNIQUENESS CONSTRAINT

Phạm Đình Thành

doi:10.34238/tnu-jst.5579

AN ADAPTIVE MULTIFACTORIAL EVOLUTIONARY ALGORITHM FOR INTER-DOMAIN PATH COMPUTATION UNDER NODEDEFINED DOMAIN UNIQUENESS CONSTRAINT

About this article

Received: 22/02/22 Revised: 20/04/22 Published: 21/04/22

Authors

Pham Dinh Thanh , Tay Bac University

Abstract

Nowadays, the rapid development of networks in size and complexity in architecture leads to the optimization of network routing becoming more and more important. The Inter-Domain Path Computation under Node defined Domain Uniqueness Constraint (IDPC-DU) has much attention from communication research. IDPC-DU is NP-Hard so approximation approaches are suitable to solve this problem for instances having large dimensionality. Multifactorial evolutionary algorithm (MFEA) is an effective approach to deal with the various types of problems. This paper proposed an approach based on an algorithm based on an Adaptive Multifactorial Evolutionary Algorithm (dMFEA-II) for solving IDPC-DU under node defined domain uniqueness constraint. The encoding and evaluating methods based on the permutation representation are also introduced. The proposed algorithm is evaluated on the two types of instances. The experimental results point out the effectiveness of the proposed algorithm in comparing with existing algorithms.

Keywords

Evolutinary Algorithm; Transfer Optimization; Multifactorial Optimization; Inter-Domain Path Computation; Evolutionary Multitasking

Full Text:

PDF (Tiếng Việt)

References

[1] T. T. B. Huynh, B. T. Ta, B. L. Nguyen, V. H. Nguyen, and D. T. Pham, “Multifactorial Evolutionary Algorithm for Inter-Domain Path Computation under Domain Uniqueness Constraint,” in 2020 IEEE Congress on Evolutionary Computation (CEC), 2020, pp. 1-8.

[2] F. Paolucci, F. Cugini, A. Giorgetti, N. Sambo, and P. Castoldi, “A survey on the path computation element (PCE) architecture,” IEEE Commun. Surv. Tutor., vol. 15, no. 4, pp. 1819-1841, 2013.

[3] D. King and A. Farrel, “The Application of the Path Computation Element Architecture to the Determination of a Sequence of Domains in MPLS and GMPLS,” IETF RFC 6805, 2012.

[4] L. Maggi, J. Leguay, J. Cohen, and P. Medagliani, “Domain clustering for inter‐domain path computation speed‐up,” Networks, vol. 71, no. 3, pp. 252-270, 2018.

[5] T. Bäck, D. B. Fogel, and Z. Michalewicz, Evolutionary computation 1: Basic algorithms and operators. CRC press, 2018.

[6] E. Agoston and Eiben, Introduction to Evolutionary Computing. Berlin, Springer-Verlag, 2003.

[7] K. K. Bali, Y. -S. Ong, A. Gupta, and P. S. Tan, “Multifactorial Evolutionary Algorithm with Online Transfer Parameter Estimation: MFEA-II,” IEEE Trans. Evol. Comput., vol. 24, no. 1, pp. 69-83, 2019.

[8] E. Osaba, A. D. Martinez, A. Galvez, A. Iglesias, and J. D. Ser, “dMFEA-II: An adaptive multifactorial evolutionary algorithm for permutation-based discrete optimization problems,” in Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, 2020, pp. 1690-1696.

[9] T. A. Do, H. L. Nguyen, B. T. Ta, T. T. B. Huynh, and S. Su, “A two-level strategy based on evolutionary algorithm to solve the inter-domain path computation under node-defined domain uniqueness constraint,” in Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications III, 2021, vol. 11746, p. 1174620.

[10] T. T. B. Huynh, H. L. Nguyen, B. T. Ta, and S. Simon, “A Two-level Genetic Algorithm for Inter-domain Path Computation under Node-defined Domain Uniqueness Constraints,” in 2021 IEEE Congress on Evolutionary Computation (CEC), 2021, pp. 87-94.

[11] Y. Yuan, Y. -S. Ong, A. Gupta, P. S. Tan, and H. Xu, “Evolutionary multitasking in permutation-based combinatorial optimization problems: Realization with TSP, QAP, LOP, and JSP,” in Region 10 Conference (TENCON), 2016 IEEE, 2016, pp. 3157-3164.

[12] L. Zhou, L. Feng, J. Zhong, Y.-S. Ong, Z. Zhu, and E. Sha, “Evolutionary Multitasking in Combinatorial Search Spaces: A Case Study in Capacitated Vehicle Routing Problem”, In 2016 IEEE Symposium Series on Computational Intelligence (SSCI), 2016, pp. 1-8.

[13] D. T. Pham, B. T. Ta, V. H. Ngo, and T. A. Do, “Inter-Domain Path Computation under Node-defined Domain Uniqueness Constraint Insances,” Mendeley Data, 2022, doi: 10.17632/tpg2nbcsc5.2.

[14] J. -C. Chen, “Dijkstra’s shortest path algorithm,” J. Formaliz. Math., vol. 15, no. 9, pp. 237-247, 2003.

DOI: https://doi.org/10.34238/tnu-jst.5579

Refbacks

There are currently no refbacks.



Remember me