THUẬT TOÁN TIẾN HÓA ĐA NHÂN TỐ THÍCH NGHI  GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI LIÊN MIỀN  VỚI RÀNG BUỘC MIỀN DUY NHẤT TRÊN NÚT MẠNG

Phạm Đình Thành

doi:10.34238/tnu-jst.5579

THUẬT TOÁN TIẾN HÓA ĐA NHÂN TỐ THÍCH NGHI GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI LIÊN MIỀN VỚI RÀNG BUỘC MIỀN DUY NHẤT TRÊN NÚT MẠNG

Thông tin bài báo

Ngày nhận bài: 22/02/22 Ngày hoàn thiện: 20/04/22 Ngày đăng: 21/04/22

Các tác giả

Phạm Đình Thành , Trường Đại học Tây Bắc

Tóm tắt

Ngày nay, cùng với sự phát triển nhanh chóng của các mạng thông tin về cả kích thước và độ phức tạp, vấn đề tối ưu chi phí định tuyến trong mạng ngày càng trở nên cấp thiết. Bài toán tìm đường đi liên miền với ràng buộc miền duy nhất (IDPC-DU) là một trong các bài toán tối ưu chi phí định tuyến nhận được nhiều sự quan tâm của các nhà nghiên cứu. Do IDPC-DU thuộc lớp bài toán NP-Khó nên hướng tiếp cận gần đúng được đánh giá là phù hợp khi kích thước dữ liệu đầu vào lớn. Trong các thuật toán gần đúng, thuật toán tiến hóa đa nhân tố (MFEA) là một trong những thuật toán hiệu quả để giải nhiều lớp bài toán khác nhau. Nghiên cứu này đề xuất áp dụng thuật toán tiến hóa đa nhân tố thích nghi (dMFEA-II) vào giải bài toán IDPC-DU với ràng buộc được xét trên các nút mạng. Nghiên cứu cũng đề xuất phương pháp mã hóa và đánh giá cá thể dựa trên biểu diễn hóa vị. Thuật toán đề xuất được đánh giá trên hai tập dữ liệu khác nhau. Kết quả thực nghiệm đã cho thấy tính hiệu quả của thuật toán đề xuất so với các thuật toán đã có.

Từ khóa

Thuật toán tiến hóa; Tối ưu hóa chuyển giao; Tối ưu hóa đa nhân tố; Tối ưu đường liên miền; Tiến hóa đa tác vụ

Toàn văn:

PDF

Tài liệu tham khảo

[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

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu



Ghi nhớ