BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC BÁCH KHOA HÀ NỘI
ĐỖ TUẤN ANH
CÁC THUẬT TOÁN METAHEURISTIC GIẢI BÀI TOÁN
ĐỊNH TUYẾN TRONG MẠNG ĐA MIỀN
Ngành: Khoa học máy tính
Mã số: 9480101
TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH
HÀ NỘI−2025
Công trình được hoàn thành tại:
Đại học Bách khoa Hà Nội
Người hướng dẫn khoa học: PGS.TS. Huỳnh Thị Thanh Bình
Phản biện 1: PGS.TS. Bùi Thu Lâm
Phản biện 2: GS.TS. Lê Sỹ Vinh
Phản biện 3: PGS.TS. Lê Hồng Phương
Luận án được bảo vệ tại Hội đồng đánh giá luận án tiến sĩ cấp Đại học Bách
khoa Hà Nội họp tại Đại học Bách khoa Hà Nội.
Vào hồi 08 giờ 30, ngày 03 tháng 06 năm 2025.
Có thể tìm hiểu luận án tại:
1. Thư viện Tạ Quang Bửu - ĐHBK Hà Nội
2. Thư viện Quốc gia Việt Nam.
MỞ ĐẦU
1. Bối cảnh nghiên cứu
Mạng đa miền (Multi-domain), một khái niệm quan trọng trong kiến trúc mạng hiện đại, đề
cập đến hệ thống mạng lớn bao gồm nhiều mạng con độc lập có khả năng tương tác với nhau.
Mỗi mạng con, hay "miền", được quản lý bởi một tổ chức sử dụng các công nghệ, chính sách
quản trị, và phương thức quản lý hác nhau. Internet, với cấu trúc từ mạng lõi cho đến mạng
biên gồm hàng trăm nghìn hệ thống tự trị (Autonomous System - AS), là một ví dụ điển hình
của mạng đa miền quy mô lớn. Cấu trúc này bao gồm các miền mạng từ Tier 1 (cấp cao nhất)
ở mạng lõi, tới các cấp Tier thấp hơn gần về phía người dùng, và cuối cùng là các AS của các
nhà cung cấp dịch vụ Internet (Internet Service Provider - ISP) trực tiếp phục vụ người dùng
cuối.
Một ứng dụng khác quan trọng của mạng đa miền trong lĩnh vực quân sự là mạng tác chiến.
Mạng tác chiến quân sự gồm nhiều mạng con thuộc các đơn vị quân đội khác nhau, mỗi mạng
đều có yêu cầu cao về bảo mật thông tin, nhưng vẫn cần kết nối và trao đổi thông tin với nhau.
Vấn đề quan trọng nhất của mạng tác chiến quân sự là giải quyết bài toán tối ưu về độ trễ
(delay), băng thông (bandwidth), độ tin cậy của đường truyền (link reliability) để nâng cao
chất lượng dịch vụ của mạng (Quality of Service - QoS), cải thiện khả năng chiến đấu và ra
quyết định nhanh nhất. Trường hợp này minh họa rõ nét tầm quan trọng của việc nghiên cứu
và phát triển các giải pháp hiệu quả cho mạng đa miền.
Hệ thống mạng đa miền, đặc biệt là mạng Internet, được cấu thành từ nhiều thành phần
phức tạp, tạo ra nhiều thách thức trong quản lý và vận hành. Xác định đường đi tối ưu đóng
vai trò then chốt, làm nền tảng cho việc định tuyến hiệu quả. Để cải thiện hiệu suất định tuyến,
cần giải quyết bài toán tối ưu đầu cuối đáp ứng các yêu cầu về độ trễ, băng thông và độ tin
cậy của kênh truyền. Song song với việc tối ưu hóa tài nguyên trên toàn hệ thống nhằm nâng
cao chất lượng dịch vụ, còn cần đảm bảo các yếu tố quan trọng về bảo mật và duy trì tính
riêng tư của mỗi miền. Tuy nhiên, việc tính toán đường đi tối ưu đầu cuối trong môi trường
đa miền gặp thách thức lớn do thiếu thông tin tổng thể và sự không đồng nhất giữa các miền.
Trong môi trường mạng đa miền, việc áp dụng các phương pháp định tuyến cần được xem
xét phù hợp với đặc thù và yêu cầu của từng loại mạng. Mạng lõi (core networks) có yêu cầu
băng thông rất lớn và độ trễ thấp, BGP (Border Gateway Protocol) luôn là giao thức được
lựa chọn chính cho định tuyến liên miền nhưng trong mỗi miền AS riêng lẻ, giao thức IS-IS
(Intermediate System to Intermediate System) thường được ưu tiên sử dụng. Tuy BGP đảm
bảo khả năng mở rộng và ổn định cho mạng lõi, nhưng giao thức này chỉ tối ưu dựa trên số
lượng AS trung gian, do đó gặp hạn chế khi cần đáp ứng các bài toán tối ưu định tuyến đầu
cuối với nhiều ràng buộc QoS phức tạp. Các phương pháp định tuyến dựa trên trạng thái liên
kết như OSPF (Open Shortest Path First) lại gặp khó khăn trong duy trì tính bảo mật và
riêng tư của từng mạng khi áp dụng cho môi trường đa miền. Nhiều nghiên cứu đã được tiến
hành nhằm giải quyết những hạn chế này. Một số tiếp cận đề xuất sử dụng các giao thức định
tuyến liên miền cải tiến, như mô hình PCE (Path Computation Element) sử dụng các thành
phần tính toán đường đi cung cấp khả năng tìm đường tối ưu định tuyến đầu cuối trong mạng
liên miền. Tuy nhiên, các giải pháp này thường đòi hỏi sự thay đổi đáng kể trong cơ sở hạ tầng
mạng. Các nghiên cứu khác thì tập trung vào việc phát triển các kỹ thuật tối ưu hóa phân tán,
nhưng khó đạt kết quả tối ưu do thiếu hình trạng của toàn mạng, đặc biệt là trong các ứng
dụng đòi hỏi hiệu suất cao và độ trễ thấp như mạng tác chiến quân sự.
Kiến trúc quản lý HPCE (Hierarchical Path Computation Element) được giới thiệu là một
giải pháp tiềm năng cho vấn đề tối ưu định tuyến trong mạng đa miền. HPCE tổ chức các
thành phần tính toán đường đi (Path Computation Element - PCE) theo cấu trúc phân cấp,
1
mỗi miền có ít nhất một PCE cấp thấp (child PCE), và một PCE cấp cao (parent PCE) quản
lý toàn bộ mạng đa miền. PCE cấp thấp thuộc mỗi miền sẽ chia sẻ thông tin tài nguyên với
PCE cấp cao. Do đó, PCE cấp cao có thể xây dựng hình trạng toàn mạng mà không cần thông
tin chi tiết nội bộ của từng miền. Cách tiếp cận này giúp duy trì tính bảo mật và tự chủ của
mỗi miền, đồng thời cho phép giải quyết vấn đề tối ưu định tuyến đầu cuối hiệu quả. Tuy nhiên,
nhược điểm của kiến trúc HPCE là tập trung tính toán PCE cấp cao, và yêu cầu băng thông
kết nối lớn đáp ứng trao đổi thông tin giữa các PCE. Để khắc phục hạn chế này phục vụ cho
khả năng mở rộng mạng, các nghiên cứu đề xuất bổ sung ràng buộc miền duy nhất, ngăn gói
tin đi lại các miền đã đi qua. Ràng buộc này giúp ngăn chặn vòng lặp, tránh tình trạng gói
tin liên tục được chuyển tiếp vào miền đã đi qua, gây tắc nghẽn mạng và lãng phí tài nguyên.
Bên cạnh đó, việc hạn chế gói tin không đi lại miền đã đi qua góp phần bảo tồn tài nguyên
mạng như: băng thông và tài nguyên tính toán. Về mặt bảo mật, việc hạn chế đường đi của
gói tin giúp giảm khả năng bị chặn bắt hoặc tấn công giả mạo, góp phần tăng cường an toàn
cho mạng. Về mặt kinh tế, nhiều ràng buộc định tuyến quan tâm đến vấn đề tiết kiệm chi phí
đường truyền tính theo lưu lượng hơn là tối ưu độ trễ, băng thông.
Bài toán tối ưu định tuyến trong mạng đa miền thỏa mãn ràng buộc đường định tuyến chỉ
đi qua mỗi miền nhiều nhất một lần (ràng buộc miền duy nhất) được Maggi và các cộng sự
giới thiệu trong nghiên cứu. Bài toán được đặt tên là IDPC-DU với hai biến thể khác nhau dựa
trên cách định nghĩa miền, và hai biến thể đều được chứng minh thuộc lớp bài toán NP-Khó.
Điều này có nghĩa là chưa có thuật toán hiệu quả để tìm ra lời giải tối ưu trong mọi trường hợp
với độ phức tạp tính toán là đa thức. Để giải quyết những bài toán này trong thực tế, các nhà
nghiên cứu thường sử dụng các thuật toán gần đúng. Thuật toán gần đúng cho phép cân bằng
thời gian tính toán và chất lượng lời giải, đáp ứng yêu cầu tìm lời giải tốt trong không gian
tìm kiếm lớn với thời gian chấp nhận được. Nhiều thuật toán gần đúng như các thuật toán xấp
xỉ đảm bảo chất lượng lời giải thông qua mô hình toán học được chứng minh, giúp đánh giá
chất lượng lời giải so với lời giải tối ưu. Tuy nhiên, các thuật toán heuristic hoặc metaheuristics
thường được đánh giá hiệu quả bằng các phương pháp thống kê thực nghiệm.
Vì vậy, luận án tập trung nghiên cứu các thuật toán gần đúng lấy cảm hứng từ tự nhiên
và đề xuất các thuật toán mới để giải bài toán định tuyến trong mạng đa miền với ràng buộc
miền duy nhất. Các nghiên cứu trong luận án khai thác các ưu điểm của các thuật toán lấy
cảm hứng từ tự nhiên trong việc xử lý bài toán NP-Khó, đồng thời thiết kế các phương pháp
mã hóa lời giải và các toán tử tìm kiếm đáp ứng ràng buộc trong bài toán của mạng đa miền.
Các thuật toán đề xuất được cài đặt và thử nghiệm trên bộ dữ liệu mô phỏng mạng để so sánh
và đánh giá hiệu suất của các thuật toán. Việc đánh giá sẽ tập trung vào hai khía cạnh chính:
thời gian thực hiện và chất lượng lời giải thu được. Kết quả của nghiên cứu đóng góp vào việc
cải thiện hiệu suất và độ tin cậy trong hoạt động của mạng đa miền, đồng thời mở ra hướng
mới trong việc áp dụng các kỹ thuật tiên tiến giải bài toán tối ưu vào lĩnh vực mạng máy tính.
2. Phạm vi và vấn đề nghiên cứu
Luận án tập trung nghiên cứu:
•Thuật toán tiến hóa giải bài toán tối ưu trên đồ thị, đặc biệt là các bài toán có tập đỉnh,
tập cạnh được chia thành các tập nhỏ.
•Các thuật toán sử dụng trí tuệ bầy đàn hiệu quả, và áp dụng giải các bài toán tìm đường
đi trên đồ thị.
•Thuật toán tiến hóa đa nhiệm đa quần thể với mỗi quần thể sử dụng các kỹ thuật tìm
kiếm khác nhau. Khai thác ưu điểm của mỗi kỹ thuật tìm kiếm để cân bằng quá trình
khám phá và khai thác lời giải trong không gian tìm kiếm.
•Thuật toán tiến hóa đa nhân tố và các kỹ thuật mã hóa, áp dụng giải các bài toán tối ưu
tìm đường trên đồ thị.
2
•Phương pháp xây dựng các bộ dữ liệu, cách đánh giá và thiết kế thực nghiệm để so sánh
độ hiệu quả của các thuật toán.
3. Đóng góp của luận án
Các kết quả nghiên cứu chính của luận án được công bố trên các tạp chí và hội nghị chuyên
ngành. Các kết quả chính đạt được của luận án có ý nghĩa khoa học bao gồm cả hai khía cạnh
lý thuyết và ứng dụng.
•Về lý thuyết:
–Đề xuất thuật toán GACOB kết hợp thuật toán di truyền và thuật toán tối ưu đàn
kiến giải bài toán IDPC-EDU.
–Đề xuất thuật toán MCACO sử dụng tìm kiếm cây Monte-Carlo Tree Search để đánh
giá một phần thứ tự miền kết hợp với tối ưu đàn kiến tìm lời giải tốt hơn so với các
thuật toán trước đó giải bài toán IDPC-EDU.
–Đề xuất hai thuật toán tiến hóa PGA và NDEGA sử dụng hai cách tìm thứ tự miền
khác nhau kết hợp với thuật toán chính xác để tìm lời giải cho bài toán IDPC-NDU.
–Đề xuất MP-PVA và pMM-VNS là hai thuật toán tiến hóa đa nhiệm đa quần thể với
các công cụ tìm kiếm khác nhau để kết hợp các ưu điểm của từng công cụ tìm kiếm
làm cân bằng quá trình khám phá và khai thác không gian lời giải hiệu quả cho bài
toán IDPC-NDU.
–Đề xuất thuật toán tiến hóa đa nhân tố NDE-MFEA cho mã hóa độ sâu và các toán
tử để giải các bài toán với lời giải là cây khung, và áp dụng giải bài toán IDPC-NDU.
•Về mặt ứng dụng: IDPC-DU là một bài toán nhằm giải quyết thách thức của mạng đa
miền - tối ưu định tuyến giữa hai điểm xác định. Do đó, thuật toán giải bài toán IDPC-DU
có thể áp dụng trực tiếp cho các bài toán thực tế trong nhiều loại mạng hiện đại. Khả
năng ứng dụng rộng rãi này cho thấy tầm quan trọng của bài toán IDPC-DU trong việc
tối ưu định tuyến trong các hệ thống mạng phức tạp và đa dạng.
4. Bố cục của luận án
Luận án gồm phần giới thiệu, ba chương và phần kết luận.
Phần giới thiệu trình bày ý nghĩa tổng quan tình hình nghiên cứu thuộc lĩnh vực luận án
quan tâm giải quyết, mục đích nghiên cứu của luận án, phương pháp nghiên cứu, phạm vi
nghiên cứu và các đóng góp của luận án.
Chương 1 trình bày cơ sở lý thuyết, giới thiệu về các thuật toán gần đúng, và bài toán định
tuyến trong mạng đa miền IDPC-DU.
Chương 2 trình bày các thuật toán đề xuất kết hợp thuật toán tiến hóa và trí tuệ bầy đàn
với các cách tiếp cận khác nhau để giải bài toán IDPC-EDU.
Chương 3 trình bày các thuật toán tiến hóa, thuật toán tiến hóa đa nhiệm đơn quần thể,
và thuật toán tiến hóa đa nhiệm đa quần thể với các phương pháp mã hóa để giải bài toán
IDPC-NDU.
3
