Kết hợp thuật toán tiến hóa và tìm kiếm biến đổi lân cận để 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

2
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nghiên cứu này mô tả cách kết hợp giữa thuật toán EA và tìm kiếm biến đổi lân cận (VNS). Trong đó, VNS được sử dụng đối với cá thể tốt nhất của mỗi th hệ. Để áp dụng được VNS vào giải bài toán IDPC-NDU, nghiên cứu cũng mô tả phương pháp biểu diễn lời giải bài toán IDPC-NDU dưới dạng biểu diễn hoán vị.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kết hợp thuật toán tiến hóa và tìm kiếm biến đổi lân cận để 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

TẠP CHÍ KHOA HỌC Phạm Đình Thành và cs. (2023) Khoa học Tự nhiên và Công nghệ (30): 68 - 75 KẾT HỢP THUẬT TOÁN TIẾN HÓA VÀ TÌM KIẾM BIẾN ĐỔI LÂN CẬN ĐỂ 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, Nguyễn Duy Hiếu, Đ ng Thị Vân Chi, Phan Trung Kiên Trường Đại học Tây Bắc Tóm tắt: 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 (IDPC-NDU) là một trong những bài toán tối ưu mạng mới được quan tâm nghiên cứu gần đây. Mặc dù đã có các nghiên cứu sử dụng thuật toán ti n hóa (E ) để giải bài toán IDPC- NDU, tuy nhiên hiện chưa có nhiều nghiên cứu về k t hợp giữa thuật toán EA và thuật toán tìm ki m cục bộ. Vì vậy nghiên cứu này mô tả cách k t hợp giữa thuật toán EA và tìm ki m bi n đổi lân cận (VNS). Trong đó, VNS được sử dụng đối với cá thể tốt nhất của mỗi th hệ. Để áp dụng được VNS vào giải bài toán IDPC-NDU, nghiên cứu cũng m tả phương pháp biểu diễn lời giải bài toán IDPC-NDU dưới dạng biểu diễn hoán vị. Thuật toán đề xuất được đánh giá trên các tập dữ liệu với 53 bộ dữ liệu khác nhau. K t quả thực nghiệm cho thấy thuật toán đề xuất tốt hơn thuật toán so sánh trên 39 bộ dữ liệu. Từ khóa: Thuật toán ti n hóa, thuật toán tìm ki m bi n đổi lân cận, tìm đường đi liên miền với ràng buộc miền duy nhất. 1. MỞ ĐẦU IDPC-EDU) - với ràng uộc trên tập cạnh; Ngày nay, sự phát triển nhanh chóng của Inter-Domain Path Computation under Node- mạng Internet và nhu cầu kết nối dẫn tới sự defined Domain Uniqueness Constraint (ký hình thành các hệ thống mạng ngày càng lớn hiệu là IDPC-NDU) - với ràng uộc trên tập hơn. Các hệ thống mạng lớn thường được đỉnh. Mặc dù các tác giả đã đề xuất thuật toán chia thành nhiều miền nhỏ, khi đó các mạng lập trình động để tìm lời giải ài toán IDPC- được gọi là mạng đa miền [1]. Trong lịch sử DU [2], nhưng do IDPC-DU là bài toán NP- hình thành, các mạng đa miền an đầu được Khó nên hướng tiếp cận này không phù hợp phát triển để đảm ảo yêu cầu về khả năng khi các ộ dữ liệu đầu vào có kích thước lớn. mở rộng và tính ảo mật [1]. Tuy nhiên hiện Do đó, các nghiên cứu gần đ y đã sử nay, ên cạnh các yêu cầu trên, việc xác dụng các thuật toán xấp xỉ để giải ài toán định được các thuật toán định tuyến hiệu IDPC-DU như: Trong nghiên cứu [3], tác quả trong mạng đa miền là một trong các giả đã đề xuất thuật toán tiến hóa thích nghi thách thức nhận được nhiều sự quan t m đa nh n tố với phương pháp mã hóa lời giải nghiên cứu. Gần đ y, tác giả L. Maggi và ằng iểu di n hoán vị. Nghiên cứu đã phát các đồng nghiệp [5] đã phát iểu mô hình huy được các thế mạnh của thuật toán tiến hóa một trong các thách thức trên thành ài hóa đa nh n tố và phương pháp mã hóa hoán toán tìm đường đi ngắn nhất giữa hai nút vị để n ng cao chất lượng lời giải tìm được. trong mạng liên miền (Inter-Domain Path Trong nghiên cứu [4], các tác giả cũng mô Computation under Domain Uniqueness tả việc áp dụng thuật toán di truyền (Two- constraint - IDPC-DU) [2]. Tùy theo ràng level Genetic Algorithm, k hiệu là PGA) uộc về miền duy nhất được xác định trên dựa trên phương pháp mã hóa thứ tự ưu tiên. tập cạnh hay trên tập đỉnh mà ài toán Một trong các ưu điểm của thuật toán PGA IDPC-DU có hai iến thể là: Inter-Domain là có thể sử dụng các toán tử tiến hóa dùng Path Computation under Edge-defined cho mã hóa hoán vị nên d dàng cài đặt. Tuy Domain Uniqueness Constraint (k hiệu là nhiên, lời giải tìm được ởi thuật toán PGA 68
chưa tốt do phương pháp mã hóa lời giải 2. PHÁT BIỂU BÀI TOÁN trong PGA chú trọng vào việc đáp ứng các Gọi G = (V, E, w, D) là đa đồ thị có ràng uộc của ài toán IDPC-NDU. Tác giả hướng, có trọng số. Trong đó, các tập các Đỗ Tuấn Anh và các đồng nghiệp [5] đã mô đỉnh (nút), tập các cạnh và ma trận trọng số tả cách áp dụng thuật toán di truyền (two- cạnh của đồ thị G được lần lượt ký hiệu là level strategy based on evolutionary V, E và w. Tập đỉnh V được phân hoạch algorithm, k hiệu là TLGA) để giải ài toán thành k tập con (mỗi tập con gọi là một IDPC-NDU. Trong thuật toán TLGA, các tác miền) đôi một không giao nhau giả đã đề xuất phương pháp mã hóa lời giải { }. hai mức cũng như các toán tử tiến hóa dựa Định nghĩa 1 (miền duy nhất trên tập trên phương pháp mã hóa này. Tuy nhiên, đỉnh [2]). Đường đi } trên do thông tin được lưu trữ ở hai mức nên yêu đồ thị G được gọi là thỏa mãn ràng buộc cầu ộ nhớ lưu trữ nhiều và các toán tử lai miền duy nhất trên tập đỉnh nếu đường đi p ghép, đột iến cũng phức tạp hơn. Mặc dù đi ra một miền thì không đi vào lại miền đó việc áp dụng các thuật toán EA đã giúp cải nữa. Tức là, nếu và thì thiện chất lượng lời giải ài toán IDPC- { }. NDU tìm được nhưng do các thuật toán này Định nghĩa 2 (bài toán IDPC-NDU [2], vẫn sử dụng phương pháp khởi tạo quần thể [7]). Cho trước hai đỉnh s, t V (lần lượt gọi ngẫu nhiên nên chất lượng quần thể an đầu là đỉnh nguồn và đỉnh đích), mục tiêu của chưa cao, từ đó ảnh hưởng tới chất lượng bài toán IDPC-NDU là tìm đường đi p từ s kết quả cuối cùng. tới t trên đồ thị G có chi phí nhỏ nhất, sao Mặc dù đã có các nghiên cứu sử dụng cho đường đi p thỏa mãn điều kiện ràng thuật toán tiến hóa giải ài toán IDPC-NDU, buộc về miền duy nhất trên tập đỉnh. Hay tuy nhiên, theo hiểu iết của nhóm tác giả, nói cách khác, bài toán IDPC-NDU được hiện chưa có nghiên cứu nào kết hợp giữa định ngh a như sau: thuật toán tiến hóa và thuật toán tìm kiếm Đầu - Đa đồ thị có hướng, có trọng số cục ộ trên một quần thể. Cho nên nghiên vào: . cứu này thử nghiệm hướng kết giữa thuật - Tập đỉnh V được phân hoạch toán EA và thuật toán VNS. Đóng góp chính thành k miền { } của nghiên cứu gồm: { } - X y dựng cách kết hợp giữa thuật toán - Đỉnh nguồn , đỉnh đích t EA và thuật toán VNS sử dụng một quần thể . [6]. Đầu Đường đi } với - X y dựng hướng sử dụng thuật toán ra: và thỏa mãn điều VNS vào giải ài toán IDPC-NDU. kiện miền duy nhất trên tập đỉnh. Các phần tiếp theo của nghiên cứu gồm: Hàm Phần 2 trình ày về định ngh a ài toán mục ∑ tiêu: IDPC-NDU và các khái niệm liên quan; Chi Hình 1 minh họa định ngh a ài toán IDPC- tiết về thuật toán đề xuất được mô tả trong NDU với đồ thị đầu vào gồm 6 miền (mỗi Phần 3; Các kết quả thực nghiệm cũng như màu của đỉnh tương ứng với một miền) và 7 các so sánh, ph n tích về hiệu quả thuật toán đỉnh. Hình 1(a) minh họa đồ thị đầu vào với đề xuất được trình ày trong Phần 4; Cuối các số ghi trên mỗi cạnh là trọng số của cùng, Phần 5 trình ày các kết quả chính của cạnh đó; đỉnh s là đỉnh nguồn; đỉnh t là đỉnh nghiên cứu cũng như hướng phát triển tiếp đích. Hình 1( ) minh họa đường đi d1 = (s, theo của nghiên cứu trong thời gian tới. 1, 5, t) là một lời giải hợp lệ với chi phí f(d1)=33. Đường đi d2 = (s, 1, 2, 4, 5, t) trong Hình 1(c) là lời giải không hợp lệ do vi phạm ràng uộc về miền duy nhất: khi đi 69
ra miền màu vàng tại nút 1 nhưng vào lại dựng lời giải ài toán IDPC-NDU từ hoán vị miền này tại nút 4. Lời giải tối ưu của đồ thị của cá thể đó, sau đó mới tính chi phí của lời đầu vào như trong Hình 1(a) là đường đi d3 giải và giá trị thích nghi của cá thể (dòng = (s, 4, 5, t) với chi phí f(d3)=21 (xem Hình lệnh 4–7 và 14–17). 1(d)). Thuật toán VNS được áp dụng chỉ cho một cá thể tốt nhất của thế hệ hiện tại. 3. THUẬT TOÁN ĐỀ XUẤT (a) (b) (c) (d) Hình 1. Ví dụ về định nghĩa bài toán IDPC-NDU là đồ thị có 6 miền và 7 đỉnh Phần này mô tả thuật toán đề xuất (k hiệu P-MEM) dựa trên việc áp dụng thuật 3.2. Phương pháp mã hóa lời giải toán EA và thuật toán VNS để giải ài toán Nếu đồ thị đầu vào có số miền Nd thì mỗi IDPC-NDU. cá thể là một hoán vị của tập {1,..., Nd}. 3.1. ược đồ thuật toán Do lời giải của bài toán IDPC-NDU có thể được tạo ra từ thứ tự của các miền nên (a) nghiên cứu này mã hóa mỗi lời giải của ài toán IDPC-NDU ằng một hoán vị của các miền. Do đó, để đánh giá mỗi cá thể, thuật toán (b) P-MEM sẽ phải tạo đồ thị G’ (gọi là đồ thị Hình 2. Ví dụ về phương pháp mã hóa lời giải toàn cục) dựa trên thông tin từ hoán vị của 0minh họa ví dụ về phương pháp mã hóa các miền mà cá thể đó iểu di n và đồ thị đầu vào G, sau đó áp dụng thuật toán tìm lời giải được sử dụng trong thuật toán được đi ngắn nhất từ đỉnh nguồn tới đỉnh P-MEM với đồ thị đầu vào như trong Hình đích để tính chi phí của lời giải. 1(a). Giả sử các miền có màu “Xanh lá cây, Các ước chính của thuật toán P-MEM Vàng, Tím, Hồng, Cam, Xanh nước biển” được mô tả ằng mã giả trong 0Do mỗi lời được gán nhãn lần lượt là: 1, 2, 3, 4, 5 và 6. giải của ài toán IDPC-NDU được mã hóa Hình 2(a) minh họa một cá thể với độ ưu ằng hoán vị của các miền nên các toán tử tiên các miền là 2–5–3–1–4–6. Hình 2(b) của thuật toán P-MEM chỉ xử l trên các minh họa đường đi qua các miền tương ứng hoán vị này và để tính giá trị thích nghi của mỗi cá thể, thuật toán P-MEM phải x y 70
với thứ tự các miền của cá thể trong Hình 0và 0lần lượt minh họa toán tử lai ghép 2(a). OX và toán tử đột iến SM cho cá thể có độ dài ằng 6. 3.3. Phương pháp khởi tạo quần thể Do mỗi lời giải của ài toán IDPC-NDU được mã hóa ởi một hoán vị của các cụm nên thuật toán P-MEM sử dụng phương pháp tạo ngẫu nhiên một hoán vị của một tập hợp để tạo cá thể trong quần thể an đầu. Hình 3. Lược đồ các bước chính của thuật toán P-MEM giải bài toán IDPC-NDU 3.4. Toán tử lai ghép và đột biến Do sử dụng phương pháp mã hóa nên thuật toán P-MEM có thể sử dụng các toán tử tiến hóa cho iểu di n hoán vị. Thuật toán P-MEM sử dụng toán tử lai ghép thứ tự (Order Crossover - OX) [8] và toán tử đột iến đổi vị trí (Swaping Mutation - SM) [8]. Hình 4. Minh họa phép lai ghép OX 71
Hình 6 minh họa phương pháp đánh giá cá thể sử dụng trong thuật toán P-MEM. Hình 6(a) minh họa đồ thị G’ được tạo với đồ thị đầu vào như trong Hình 1 và cá thể ind như trong 0Hình 6( ) minh họa lời giải Hình 5. Minh họa phép đột bi n SM bài toán IDPC-NDU tìm được sau khi áp dụng thuật toán Dijkstra tìm đường đi ngắn 3.5. Đánh giá cá thể nhất từ đỉnh s tới đỉnh t trên đồ thị trong Do mỗi cá thể trong thuật toán P-MEM là Hình 6(a). một hoán vị của tập các miền nên để đánh 3.6. Thuật toán tìm kiếm biến đổi lân cận giá cá thể ind cần thực hiện: Nghiên cứu này sử dụng thuật toán tìm - Bƣớc 1: Xác định thứ tự của các miền kiếm cục ộ là thuật toán iến đổi l n cận dựa theo thứ tự của các gen trên cá thể ind. [6] với cấu trúc l n cận là 2-opt [6], [11], - Bƣớc 2: Tạo đồ thị có hướng G’ dưa [12]. Các ước chính của thuật toán tìm trên đồ thị đầu vào G và thứ tự các miền kiếm iến đổi l n cận được trình ày trong 0 trong Bước 1 như sau: 4. KẾT QUẢ THỰC NGHIỆM + Tập đỉnh của G’ trùng với tập đỉnh của 4.1. Dữ liệu thực nghiêm và tiêu chí đánh giá G. Nghiên cứu chọn hai tập dữ liệu (có tên + Cạnh liên miền ao gồm các cạnh nối là Type 1, Type 2) được sử dụng trong các miền indi tới miền indi+1 hoặc từ miền indk nghiên cứu trước, để đánh giá hiệu quả của tới miền ind1. thuật toán P-MEM. Mỗi tập Type 1 và Type + Cạnh trong mỗi miền của G’ trùng với 2 lại được chia thành các tập dữ liệu nhỏ cạnh trong mỗi miền của G. hơn Type 1 Small, Type 1 Large, Type 2 - Bƣớc 3: X y dựng lời giải sol của ài Small và Type 2 Large). Bảng mô tả thông toán IDPC-NDU từ cá thể ind. tin về tập dữ liệu sử dụng để đánh giá thuật - Bƣớc 4: p dụng thuật toán Dijkstra toán P-MEM. [9], [10] để tìm được đi ngắn nhất từ đỉnh Bảng 1. Bảng mô tả thông tin về tập dữ liệu sử nguồn tới đỉnh đích. Độ dài đường đi ngắn dụng để đánh giá thuật toán P-MEM nhất tìm được chính là chi phí của cá thể ind. Tập dữ liệu Số Số Số cạnh Số bộ đỉnh miền dữ liệu Type 1 Nhỏ nh t 427 7 14927 Small 16 Lớn nh t 2002 30 178026 Type 1 Nhỏ nh t 2102 12 164811 Large 9 Lớn nh t 7352 42 1461349 Type 2 Nhỏ nh t 52 6 204 Small 20 Lớn nh t 1902 32 137407 (a) Đồ thị G‟ Type 2 Nhỏ nh t 2002 17 128021 Large Lớn nh t 8 2902 32 229375 Thông tin tóm tắt về các tập dữ liệu này được mô tả trong Bảng 1. Các ộ dữ liệu thực nghiệm được lưu trữ tại [13]. Chất lượng lời giải tìm được của các ( ) Lời giải ài toán IDPC-NDU thuật toán được đánh giá theo các tiêu chí: giá trị tốt nhất tìm được trong các lần thực Hình 6. Minh họa phương pháp đánh giá cá thể hiện (BF), giá trị trung ình cộng (Avg) và trong thuật toán P-MEM độ lệch tiêu chuẩn (Std). 72
Hình 7. Các bước chính của thuật toán tìm ki m bi n đổi lân cận VNS Bảng 2. Bảng so sánh lời giải của P-MEM, dMFEA và kết quả tối ƣu trên tập dữ liệu Type 1. 4.2. Môi trường tiến hành thực nghiệm và tham số thực nghiệm dMFEA P-MEM Opt Bộ dữ liệu BF Avg BF Avg Để đánh giá thuật toán P-MEM, các tác 1002_12_82252 14,0 14,0 8 13,8 8 giả so sánh lời giải tìm được ằng thuật toán 1002_22_36564 35,0 38,2 30 37,0 18 P-MEM với lời giải tìm được ởi một trong 1192_19_37744 40,0 53,4 40 51,0 18 các thuật toán tiến hóa mới được nghiên cứu 1202_22_65521 22,0 22,0 22 22,1 16 trong công ố [3] (k hiệu dMFEA) và kết 1256_21_44446 43,0 54,5 42 48,5 26 Kích thước nhỏ (small) quả tối ưu (k hiệu Opt). 1322_22_48821 44,0 45,7 44 44,7 26 Các tham số thực nghiệm của thuật toán 1506_9_130556 11,0 16,6 11 12,6 11 P-MEM gồm: kích thước quần thể: 100; tỉ lệ 1514_16_78292 33,0 33,4 33 33,1 21 đột iến: 0,05; tỉ lệ lai ghép: 0,9; thuật toán 1514_30_78351 30,0 34,8 30 31,7 21 sẽ dừng khi đạt số lần đánh giá là 50.000. 1602_22_60574 46,0 51,7 46 48,9 24 1682_23_67612 46,0 74,2 46 61,1 24 Tác giả sử dụng ngôn ngữ lập trình C# để 1730_20_88509 39,0 41,9 39 41,4 24 cài đặt thuật toán P-MEM. Thực nghiệm 2002_22_178026 24,0 24,0 24 24,0 16 được tiến hành trên máy tính có cấu hình là 427_7_14927 8,0 8,2 8 8,0 8 CPU: Intel Xeon E5620, RAM: 8GB. Máy 704_15_16990 31,0 33,2 31 31,3 21 tính sử dụng hệ điều hành MS Windows 10 842_23_31617 22,0 22,0 22 22,1 16 Home (64 it). Thuật toán P-MEM được 2102_23_164811 27,0 27,0 27 27,1 18 thực nghiệm 30 lần trên mỗi ộ dữ liệu. Kích thước lớn (large) 2402_22_260967 24,0 24,1 24 24,0 16 4.3. ết quả thực nghiệm 2494_12_276620 23,0 23,0 23 23,0 16 2502_22_229601 29,0 30,1 29 29,5 18 0và 0trình ày kết quả so sánh của thuật 2522_20_171940 41,0 41,3 41 41,6 18 toán P-MEM với các thuật toán dMFEA và 2715_22_592246 13,0 13,0 13 13,0 8 kết quả tối ưu. Trong đó, tên các ộ dữ liệu 2918_29_293109 30,0 30,2 30 30,6 21 chỉ hiển thị phần cuối, phần đầu 3161_15_339881 30,0 30,0 30 30,0 21 “idpc_ndu_” được ỏ đi để tiết kiệm không 3602_32_406192 35,0 49,8 35 45,6 21 gian ảng. 73
Bảng 3. Bảng so sánh lời giải của P-MEM, Thuật toán P-MEM có 11 trường hợp tìm dMFEA và kết quả tối ƣu trên tập dữ liệu Type 2. được lời giải có giá trị tối ưu. Các lời giải có dMFEA P-MEM giá trị tối ưu thuộc các ộ dữ liệu có số miền Bộ dữ liệu Opt BF Avg BF Avg nhỏ và đều thuộc các ộ dữ liệu thuộc tập 1002_32_60942 19,0 22,8 19 24,8 13 Type 1 small và Type 2 small. Điều đó có 102_10_834 7,0 8,0 7 7,0 7 ngh a là P-MEM hiệu quả hơn với các ộ dữ 1102_17_56280 25,0 27,0 25 26,2 14 1202_18_68002 24,0 24,7 24 25,7 15 liệu có số miền é. Nguyên nh n của kết quả 1302_22_78953 25,0 27,8 26 26,4 17 này là do P-MEM mã hóa mỗi cá thể là một 1402_24_92365 24,0 28,8 24 27,0 16 hoán vị của số miền. 5. KẾT LUẬN Kích thước nhỏ (small) 1502_27_104878 27,0 33,2 27 30,7 16 152_14_1869 16,0 16,0 8 15,5 8 1602_14_96765 32,0 32,9 17 30,7 17 Bài toán IDPC-NDU là một trong những 1702_18_110993 20,0 24,4 20 29,8 20 ài toán mới được nghiên cứu trong tối ưu 1802_21_123666 33,0 43,7 33 36,3 21 mạng đa miền. Bài toán IDPC-NDU có 1902_27_137407 30,0 47,9 30 35,8 21 nhiều ứng dụng trong cả nghiên cứu l 202_22_2341 20,0 32,4 20 26,6 9 thuyết và ứng dụng thực ti n. Nghiên cứu 252_11_3513 11,0 11,0 11 17,5 11 302_12_4930 11,0 24,6 11 16,3 11 này mô tả cách kết hợp giữa thuật toán EA và thuật toán VNS để giải ài toán IDPC- 352_17_6667 26,0 30,4 13 29,5 13 402_22_8220 26,0 32,3 26 29,4 13 NDU, trong đó sử dụng thuật toán VNS vào 452_32_10406 22,0 30,6 22 29,0 13 giải ài toán IDPC-NDU. Kết quả thực 502_12_10949 11,0 27,2 11 18,2 7 nghiệm đã ước đầu chỉ ra tính hiệu quả của 52_6_204 6,0 6,0 6 6,0 6 hướng kết hợp giữa hai thuật toán. 2002_17_128021 37,0 43,0 37 41,4 16 Trong thời gian tới, các tác giả sẽ tiếp tục Kích thước lớn (large) 2102_19_141155 36,0 37,5 36 37,0 20 cải thiện hiệu quả của việc kết hợp giữa 2202_22_153764 36,0 38,3 36 37,4 21 thuật toán EA và thuật toán tìm kiếm cục ộ 2302_27_169859 42,0 62,8 42 56,5 22 khác. 2402_29_186438 37,0 55,7 38 51,9 23 2502_32_201852 34,0 75,7 34 59,2 25 Lời cám ơn 2602_19_185818 41,0 54,8 42 48,4 21 Nghiên cứu này được tài trợ ởi Bộ Giáo 2802_30_215589 59,0 83,4 50 80,6 25 dục và Đào tạo trong đề tài mã số: B2021- Bên cạnh đó, trong hai ảng này, tại mỗi TTB-01. dòng của thuật toán dMFEA và P-MEM, lời giải có giá trị tốt hơn thuật toán còn lại được TÀI LIỆU THAM KHẢO in nghiêng; lời giải có giá trị ằng giá trị tối [1] F. Paolucci, F. Cugini, A. Giorgetti, N. ưu được in đậm ở cột giá trị tối ưu. Sam o, and P. Castoldi, “A survey on the path computation element (PCE) Kết quả của các thuật toán tại các ảng architecture,” IEEE Communications trên cho thấy thuật toán P-MEM tốt hơn Surveys & Tutorials, vol. 15, no. 4, pp. thuật toán dMFEA trên 39 trong tổng số 53 1819–1841, 2013. trường hợp. Đặc iệt, thuật toán P-MEM tốt [2] L. Maggi, J. Leguay, J. Cohen, and P. hơn dMFEA trên tất cả ộ dữ liệu thuộc tập Medagliani, “Domain clustering for inter‐ Type 2 large. Thuật toán dMFEA chỉ tốt hơn domain path computation speed‐ up,” thuật toán P-MEM trên 9 ộ dữ liệu. Cụ thể Networks, vol. 71, no. 3, pp. 252–270, 2018. [3] P. D. Thanh, “An adaptive multifactorial hơn: evolutionary algorithm for Inter-domain - Thuật toán P-MEM có kết quả trội hơn path computation under node-defined thuật toán dMFEA trên 14 trong tổng số 16 domain uniqueness constraint,” TNU ộ dữ liệu thuộc Type 1 small. Trong khi chỉ Journal of Science and Technology, vol. tốt hơn 4 trên tổng số 9 ộ dữ liệu thuộc 227, no. 08, pp. 114–122, 2022. [3] P. D. Thanh, “An adaptive multifactorial Type 2 large. evolutionary algorithm for Inter-domain - Thuật toán P-MEM có kết quả trội hơn path computation under node-defined thuật toán dMFEA trên 14 trong tổng số 20 domain uniqueness constraint,” TNU ộ dữ liệu thuộc Type 2 small. Journal of Science and Technology, vol. 227, no. 08, pp. 114–122, 2022. 74
[4] H. T. T. Binh, N. H. Long, T. B. Thang, and [8] A. E. Eiben and J. E. Smith, Introduction to S. Simon, “A Two-level Genetic Algorithm evolutionary computing, vol. 53. Springer, for Inter-domain Path Computation under 2003. Node-defined Domain Uniqueness [9] E. W. Dijkstra, “A note on two pro lems in Constraints,” in 2021 IEEE Congress on connexion with graphs,” Numerische Evolutionary Computation (CEC), 2021, pp. mathematik, vol. 1, no. 1, pp. 269–271, 1959. 87–94. [10] J.-C. Chen, “Dijkstra‟s shortest path [5] A. Do Tuan, L. N. Hoang, T. T. Bao, H. T. T. algorithm,” Journal of Formalized Binh, and S. Su, “A two-level strategy based Mathematics, vol. 15, no. 9, pp. 237–247, on evolutionary algorithm to solve the inter- 2003. domain path computation under node-defined [11] P. Hansen and N. Mladenović, “Varia le domain uniqueness constraint,” in Artificial neighborhood search: Principles and Intelligence and Machine Learning for Multi- applications,” European Journal of Domain Operations Applications III, 2021, Operational Research, vol. 130, no. 3, pp. vol. 11746, pp. 687–700. 449–467, May 2001, doi: 10.1016/S0377- [6] P. Hansen and N. Mladenović, “Varia le 2217(00)00100-4. neigh orhood search methods,” in [12] P. Hansen, N. Mladenović, and JoséA. Encyclopedia of Optimization, C. A. Floudas Moreno Pérez, “Varia le neigh ourhood and P. M. Pardalos, Eds. Springer US, 2009, search: methods and applications,” 4OR, vol. pp. 3975–3989. [Online]. Available: 6, no. 4, pp. 319–360, Dec. 2008, doi: http://dx.doi.org/10.1007/978-0-387-74759- 10.1007/s10288-008-0089-1. 0_694 [13] T. Pham Dinh, T. Ta Bao, H. Ngo Viet, and [7] D. King and A. Farrel, “The Application of A. Do Tuan, “Inter-Domain Path the Path Computation Element Architecture Computation under Node-defined Domain to the Determination of a Sequence of Uniqueness Constraint Insances,” Mendeley Domains in MPLS and GMPLS,” IETF RFC Data, vol. 2, 2021, doi: 6805, 2012. 10.17632/tpg2nbcsc5.2. A COMBINATION OF EVOLUTIONARY ALGORITHM AND VARIABLE NEIGHBOURHOOD SEA RCH FOR INTER-DOMAIN PATH COMPUTATION WITH A NODE-DEFINED DOMAIN UNIQUENESS CONSTRAINT Pham Dinh Thanh, Nguyen Duy Hieu, Dang Thi Van Chi, Phan Trung Kien Tay Bac University Abstract: There has recently been an increasing interest in conducting a research on the inter- domain path computation under node-defined domain uniqueness constraint (IDPC-NDU). Although there have been some studies using evolutionary algorithm (EA) to solve the IDPC-NDU problem, there are a few studies on the combination of EA and a local search algorithm. Therefore, this study was carried out to describes a combination of EA and variable neighbourhood search (VNS). In order to apply the VNS to solve the IDPC-NDU, the study also provided a description of a solution encoding method for the IDPC-NDU based on the permutation representation. The proposed algorithm was evaluated on the datasets with 53 different instances. The findings showed that the proposed algorithm is better than the counterparts in 39 cases. Keywords: Evolutionary algorithm, variable neighbourhood search, inter-domain path computation under node-defined domain uniqueness constraints. Ngày nhận bài: 03/02/2023. Ngày nhận đăng: 05/03/2023 Liên lạc: Phạm Đình Thành, e-mail: thanhpd@utb.edu.vn 75