Tổng quan luận án

Luận án tiến sĩ kỹ thuật với đề tài "Nghiên cứu phát triển thuật toán metaheuristic giải bài toán Cây Steiner nhỏ nhất định hướng ứng dụng cho thiết kế hệ thống mạng" do nghiên cứu sinh Trần Việt Chương thực hiện tại Học viện Công nghệ Bưu chính Viễn thông (Hà Nội, năm 2023), dưới sự hướng dẫn khoa học của PGS. Hà Hải Nam và TS. Phan Tấn Quốc, thuộc chuyên ngành Hệ thống thông tin, mã số 9.04.

Tính cấp thiết và khoảng trống nghiên cứu

Kết nối một tập điểm cho trước với chi phí tối thiểu được xác định là một trong những bài toán quan trọng nhất của thiết kế mạng truyền thông. Hệ thống mạng có thể được mô hình hóa dưới dạng một đơn đồ thị vô hướng, liên thông và có trọng số. Từ những năm 1970, bài toán Cây Steiner (Steiner Tree Problem - STP) hay bài toán Cây Steiner nhỏ nhất (Steiner Minimal Trees Problem - SMT) đã trở thành một bài toán tối ưu tổ hợp kinh điển thu hút nhiều sự quan tâm.

Về mặt lý thuyết độ phức tạp, bài toán SMT ở trường hợp tổng quát đã được chứng minh thuộc lớp NP-hard. Các phương pháp toán học giải chính xác chỉ giải quyết được các bài toán có quy mô nhỏ trong thời gian cho phép, không đáp ứng được yêu cầu của các bài toán quy mô lớn phát sinh từ thực tế. Do đó, các bài toán thực tế buộc phải tiếp cận bằng phương pháp giải gần đúng (heuristic và metaheuristic) nhằm tìm kiếm giải pháp chấp nhận được trong thời gian hợp lý.

Khoảng trống nghiên cứu được tác giả xác định là: trong khi các thuật toán heuristic thường chỉ áp dụng hiệu quả cho từng bài toán cụ thể và dễ dừng ở nghiệm cục bộ, thì thuật toán metaheuristic đóng vai trò như một khung thuật toán tổng quát có khả năng khai phá không gian tìm kiếm rộng hơn và mang lại chất lượng lời giải tốt nhất trong số các phương pháp giải gần đúng hiện nay. Tuy nhiên, việc tìm kiếm các thuật toán có khả năng cân bằng tốt hơn giữa chất lượng lời giải và thời gian tính toán, đặc biệt trên các cấu trúc đồ thị thưa kích thước lớn phục vụ thiết kế hệ thống mạng, vẫn là vấn đề mở cần tiếp tục giải quyết.

Mục tiêu nghiên cứu

Mục tiêu tổng quát của luận án được xác định gồm ba nội dung cụ thể:

  1. Nghiên cứu phát triển một số thuật toán gần đúng dạng heuristic và metaheuristic hiệu quả nhằm giải bài toán SMT, hướng đến việc tạo ra chất lượng lời giải tốt hơn so với các thuật toán có cùng cỡ thời gian tính toán.
  2. Giảm thiểu thời gian tính toán khi so sánh với các thuật toán có chất lượng lời giải tương đương, hoặc tìm ra các lời giải mới tốt nhất trên một số bộ dữ liệu thực nghiệm chuẩn và mở rộng.
  3. Định hướng ứng dụng các kết quả nghiên cứu thuật toán vào bài toán quy hoạch và thiết kế hệ thống mạng truyền thông.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Bài toán Cây Steiner nhỏ nhất, các thuật toán heuristic và metaheuristic, các công trình khoa học đã công bố liên quan đến thuật toán heuristic/metaheuristic giải bài toán SMT, cùng các ứng dụng của bài toán này trong kỹ thuật.
  • Phạm vi nghiên cứu: Bài toán SMT được nghiên cứu trong y văn dưới ba dạng chính: bài toán với khoảng cách Euclide, bài toán với khoảng cách chữ nhật (rectilinear distance), và bài toán với khoảng cách giữa các đỉnh là trọng số của các cạnh (giá trị khoảng cách ngẫu nhiên). Luận án giới hạn phạm vi nghiên cứu ở dạng thứ ba: bài toán Cây Steiner trên đơn đồ thị vô hướng, liên thông, có trọng số không âm trên các cạnh (khoảng cách ngẫu nhiên), tập trung phân tích và thực nghiệm trên các cấu trúc đồ thị thưa và đồ thị thưa quy mô lớn.

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trước đây được điểm lại

Luận án đã phân loại và điểm lại các công trình nghiên cứu trong nước và quốc tế liên quan đến bài toán SMT theo các nhóm giải pháp chính:

  • Nghiên cứu trong nước: Điểm qua các công trình nghiên cứu của tác giả Vũ Đình Hòa [1] và tác giả Trần Lê Thủy [7]. Tác giả khẳng định tại thời điểm thực hiện, ở Việt Nam chưa có luận án tiến sĩ kỹ thuật chuyên ngành nào nghiên cứu trực tiếp về bài toán này.
  • Các luận án quốc tế tiêu biểu: Tác giả điểm lại các luận án tiến sĩ của Martin Zachariasen [53], Tobias Polzin [78], Pieter Oloff De Wet [61], Xinhui Wang [84], Jon William Van Laarhoven [46], và Zhiliu Zhang [87].
  • Các thuật toán rút gọn đồ thị: Gồm các công trình của Jeffrey H. Kingston và Nicholas Paul Sheppard [44], Thorsten Koch và Alexander Martin [77], C. Souza [15]. Mục tiêu chính của hướng tiếp cận này là giảm thiểu hệ số $n - |L|$ thông qua hai kỹ thuật: gia tăng số lượng đỉnh thuộc tập terminal và loại bỏ các đỉnh chắc chắn không thuộc cây Steiner nhỏ nhất cần tìm.
  • Các thuật toán tìm lời giải đúng: Điển hình là thuật toán quy hoạch động của Dreyfus và Wagner [68], phương pháp nới lỏng Lagrange của Beasley [39], và các thuật toán nhánh cận của Koch và Martin [77], Xinhui Wang [84]. Nhóm phương pháp này đảm bảo tính chính xác tuyệt đối nhưng chỉ thực thi được trên đồ thị quy mô nhỏ.
  • Các thuật toán gần đúng cận tỉ lệ: Luận án điểm lại thuật toán MST-Steiner của Bang Ye Wu và Kun-Mao Chao có cận tỉ lệ 2 [14], thuật toán Zelikovsky-Steiner có cận tỉ lệ 11/6 [14]. Cận tỉ lệ tốt nhất được lý thuyết ghi nhận hiện nay là 1.
  • Các thuật toán heuristic: Bao gồm thuật toán MST-Steiner [14], thuật toán SPH [15], thuật toán Heu [77], và thuật toán distance network heuristic của Kou, Markowsky.
  • Các thuật toán metaheuristic: Gồm thuật toán Local Search [29][43], thuật toán tìm kiếm lân cận biến đổi VNS [43], thuật toán di truyền Genetic Algorithm [22], thuật toán Tabu Search [31][72], thuật toán di truyền song song PGA [57], cùng các thuật toán bầy đàn như thuật toán Bees của D. Pham [21], Dusan Teodorovic [25][28], Xin-She Yang [83].

Khoảng trống luận án lựa chọn giải quyết

Từ việc phân tích tổng quan, luận án chỉ ra rằng các thuật toán heuristic hiện hành thường đạt tốc độ nhanh nhưng chất lượng nghiệm chưa cao, trong khi các thuật toán metaheuristic hiện biết phụ thuộc chặt chẽ vào cấu trúc toán học của các chiến lược tìm kiếm lân cận. Mặt khác, đối với các đồ thị thưa kích thước lớn (hàng chục nghìn đến hàng trăm nghìn đỉnh), việc sử dụng các thuật toán tìm đường đi ngắn nhất truyền thống như Dijkstra gây suy giảm đáng kể hiệu năng thời gian tính toán. Do đó, luận án lựa chọn giải quyết bài toán phát triển các heuristic cải tiến tích hợp thuật toán tìm đường đi ngắn nhất tối ưu hơn, đồng thời thiết kế các toán tử lân cận mới (lân cận tham lam, lân cận có xác suất) nhằm nâng cao năng lực hội tụ cho các khung thuật toán metaheuristic dạng cá thể và quần thể.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và các khái niệm sử dụng

  • Mô hình toán học: Đơn đồ thị vô hướng, liên thông, có trọng số $G = (V(G), E(G))$, trong đó $V(G)$ là tập gồm $n$ đỉnh, $E(G)$ là tập gồm $m$ cạnh, $w(e) \ge 0$ là trọng số của cạnh $e \in E(G)$. Cho $L \subseteq V(G)$ là tập các đỉnh terminal. Cây $T = (V(T), E(T))$ đi qua tất cả các đỉnh trong $L$ được gọi là Cây Steiner ứng với tập $L$. Đỉnh thuộc $V(T) \setminus L$ được gọi là đỉnh Steiner.
  • Hàm mục tiêu: Chi phí của cây $T$, ký hiệu $C(T)$, là tổng trọng số các cạnh thuộc cây: $$C(T) = \sum_{e \in E(T)} w(e)$$ Bài toán SMT tìm cây $T$ sao cho $C(T)$ đạt giá trị nhỏ nhất.
  • Định lý về số đỉnh Steiner: Với đồ thị $G$ và tập terminal $L$, nếu cây Steiner $T$ của $L$ có $p$ đỉnh thì số đỉnh Steiner của $T$ không vượt quá $p - 2$.
  • Khái niệm cạnh cầu Steiner và đồ thị rút gọn: Cạnh $e_{uv}$ là cạnh cầu Steiner nếu khi loại bỏ nó, các đỉnh thuộc $L$ không cùng thuộc một thành phần liên thông. Đồ thị $G'$ là đồ thị rút gọn Steiner của $G$ nếu số đỉnh và cạnh của $G'$ nhỏ hơn hoặc bằng $G$ và trong $G'$ tồn tại ít nhất một cây Steiner nhỏ nhất ứng với tập $L$.
  • Nguyên lý metaheuristic: Dựa trên sự cân bằng giữa hai yếu tố cốt lõi: tính tăng cường (intensification - khai thác sâu vùng không gian tiềm năng qua tiếp cận tham lam) và tính đa dạng (diversification - khai phá vùng không gian mới qua yếu tố ngẫu nhiên/xác suất để tránh bẫy tối ưu cục bộ).

Phương pháp nghiên cứu thực tế

Luận án sử dụng phương pháp kết hợp phân tích lý thuyết và thực nghiệm định lượng:

  • Phân tích lý thuyết: Đánh giá độ phức tạp tính toán thời gian của các thuật toán đề xuất thông qua ký pháp tiệm cận $O$ lớn.
  • Phương pháp thực nghiệm: Cài đặt các thuật toán và tiến hành đo đạc trực tiếp trên máy tính. Các chỉ số thu thập gồm: giá trị hàm mục tiêu (chi phí cây $C(T)$) so sánh với nghiệm tối ưu $Opt$ hoặc các thuật toán công bố trước đó, thời gian chạy thực nghiệm trung bình.
  • Đánh giá hiệu năng phần cứng: Để đảm bảo tính khách quan khi so sánh với các nghiên cứu trước chạy trên hạ tầng khác nhau, luận án dẫn chiếu phương pháp đo lường Mflop/s (triệu phép tính dấu phẩy động trên giây) từ công trình của Dongarra [42].

Nguồn tư liệu và dữ liệu thực nghiệm

Hệ thống dữ liệu phục vụ nghiên cứu gồm hai nguồn:

  1. Dữ liệu thực nghiệm chuẩn: Gồm 78 bộ dữ liệu đồ thị thưa được khai thác từ thư viện OR-Library (Beasley), địa chỉ http://people.uk/~mastjjb/jeb/orlib/steininfo, phân thành các nhóm: steinb, steinc, steind, steine.
  2. Dữ liệu thực nghiệm mở rộng: Gồm 80 bộ dữ liệu đồ thị thưa kích thước lớn do tác giả tự xây dựng, phân thành 4 nhóm: steinf (kích thước lên tới 10.000 đỉnh), steing, steinh, và steini (kích thước lên tới 100.000 đỉnh). Phương pháp sinh dữ liệu: tạo một cây khung ngẫu nhiên qua $n$ đỉnh, sau đó sinh ngẫu nhiên thêm các cạnh cho đến khi đạt $m$ cạnh và gán trọng số ngẫu nhiên cho từng cạnh.

Nội dung chính theo từng chương

Chương 1: Tổng quan về bài toán Cây Steiner nhỏ nhất và định hướng ứng dụng cho thiết kế hệ thống mạng

Chương 1 hệ thống hóa cơ sở toán học của bài toán SMT, phân tích các dạng khoảng cách và điểm luận các hướng tiếp cận. Chương này phân tích chi tiết sơ đồ vận hành của các thuật toán metaheuristic: Local Search, Hill Climbing Search, Variable Neighborhood Search (VNS), và thuật toán Bees cơ bản.

Tác giả thực hiện khảo sát thực nghiệm các thuật toán hiện biết trên các nhóm dữ liệu chuẩn steinb, steinc, steind, steine để đánh giá tương quan giữa phương pháp giải chính xác ($Opt$ theo Beasley [39]), phương pháp heuristic (SPH [15], Heu [77]), và phương pháp metaheuristic (Node-Based NB [69], Path-Based PB [69], Tabu Search TS [15], Parallel Genetic Algorithm PGA [57]).

Bộ dữ liệu Opt SPH [15] Heu [77] NB [69] PB [69] TS [15] PGA [57]
steinc1 85 105 85 85 85 85 85
steinc2 144 165 144 144 144 144 144
steinc3 754 776 755 754 754 754 754
steinc18 113 125 120 116 116 117 113
steind1 106 109 106 106 106 106 106
steind6 67 85 70 68 70 70 67
steind18 223 250 238 228 228 230 225
steine1 111 152 111 111 111 111 111
steine3 4013 4121 4052 4016 4018 4018 4015
steine18 564 627 608 584 584 595 572

Kết quả khảo sát khẳng định: metaheuristic dạng quần thể đạt chất lượng nghiệm tiệm cận tối ưu tốt hơn heuristic và metaheuristic dạng cá thể, nhưng trên đồ thị kích thước lớn thì metaheuristic dạng cá thể có ưu thế về thời gian thực thi.

Về mặt ứng dụng, tác giả phân tích bài toán quy hoạch mạng theo quy trình 3 bước (Khảo sát thực địa $\rightarrow$ Xây dựng kết nối tôpô tối ưu chi phí $\rightarrow$ Phân tích và đánh giá kết quả) và xây dựng 8 mô hình định hướng ứng dụng thực tế của SMT:

  1. Mô hình 1 - Thiết kế mạng cục bộ: Tận dụng hệ thống mạng có dây (LAN) để bố trí các điểm phát không dây (WLAN) với chi phí kết nối tối thiểu.
  2. Mô hình 2 - Cung cấp dịch vụ mạng riêng ảo (VPN): Nhà cung cấp dịch vụ Internet (ISP) tối ưu chi phí thuê băng thông từ nhà mạng viễn thông để kết nối các điểm phân tán của khách hàng.
  3. Mô hình 3 - Truyền thông đa hướng (Multicast): Thiết lập cấu trúc tôpô kết nối máy nguồn với nhóm các máy nhận với tổng số kênh truyền là nhỏ nhất.
  4. Mô hình 4 - Thiết kế vi mạch cỡ cực lớn (VLSI): Bài toán đi dây ngang dọc trên bảng mạch lưới nối các khối linh kiện với tổng chiều dài ngắn nhất.
  5. Mô hình 5 - Kết nối nhóm: Tìm đồ thị con cực tiểu hóa chiều dài chứa ít nhất một điểm thuộc mỗi tập con đỉnh cho trước.
  6. Mô hình 6 - Bài toán Steiner nhiều pha: Mở rộng bài toán kết nối nhóm, tìm đồ thị liên thông cực tiểu chứa tất cả các đồ thị con liên thông thành phần.
  7. Mô hình 7 - Bài toán mạng Steiner nhiều pha: Tìm đồ thị con chứa các cây Steiner thành phần với điều kiện các điểm Steiner chỉ được chọn từ các tập đỉnh trung gian quy định.
  8. Mô hình 8 - Bài toán phát sinh loài: Xây dựng cây tiến hóa sinh học dựa trên ma trận nhị phân tính trạng loài với khoảng cách giữa các loài đo bằng khoảng cách Hamming.

Chương 2: Đề xuất thuật toán heuristic giải bài toán Cây Steiner nhỏ nhất

Chương 2 tập trung giải quyết vấn đề thiết kế các thuật toán heuristic mới và cải tiến:

  • Đề xuất hai thuật toán heuristic mới:
    • Thuật toán SPT-Steiner (Shortest Path Tree Steiner): Hoạt động dựa trên nguyên lý tìm cây đường đi ngắn nhất xuất phát từ các đỉnh thuộc tập terminal, sau đó thực hiện thủ tục tỉa bỏ các cạnh dư thừa không nằm trên đường đi kết nối các đỉnh terminal.
    • Thuật toán PD-Steiner (Prim Dijkstra Steiner): Kết hợp cơ chế kết nạp cạnh liên thông của thuật toán Prim với cơ chế tìm đường đi ngắn nhất của thuật toán Dijkstra để mở rộng cây kết nối.
    • Thực nghiệm trên 98 bộ dữ liệu: Gồm 78 bộ chuẩn (steinb, steinc, steind, steine) và 20 bộ mở rộng thuộc nhóm steinf (kích thước đồ thị lên đến 10.000 đỉnh). Kết quả so sánh với thuật toán MST-Steiner [14] cho thấy SPT-Steiner và PD-Steiner cho chất lượng lời giải tốt hơn trên một số bộ dữ liệu cụ thể, dù thời gian chạy thực nghiệm chậm hơn MST-Steiner.
  • Đề xuất hai thuật toán heuristic cải tiến cho đồ thị thưa kích thước lớn:
    • Thuật toán i-SPT-Steiner và i-PD-Steiner: Tác giả nhận diện nút thắt cổ chai về thời gian của Dijkstra trên đồ thị quy mô lớn. Do đó, hai thuật toán cải tiến này thay thế thuật toán Dijkstra bằng thuật toán Dial (một biến thể cấu trúc bucket của Dijkstra) trong khâu tìm đường đi ngắn nhất.
    • Thực nghiệm trên 80 bộ dữ liệu mở rộng: Tiến hành trên các đồ thị thưa có kích thước từ 10.000 đến 100.000 đỉnh (nhóm steinf, steing, steinh, steini).
    • Đánh giá hiệu năng: Cả hai thuật toán cải tiến đạt chất lượng nghiệm tương đương hoặc tốt hơn MST-Steiner [14]. Về tốc độ, thuật toán i-PD-Steiner có thời gian chạy nhanh hơn cả MST-Steiner và i-SPT-Steiner; trong khi đó, i-SPT-Steiner có thời gian thực thi chậm hơn. Phân tích độ phức tạp thời gian xác nhận tính khả thi của các thuật toán đề xuất trên đồ thị thưa quy mô lớn.

Chương 3: Đề xuất thuật toán metaheuristic giải bài toán Cây Steiner nhỏ nhất

Chương 3 trình bày các đề xuất thuật toán metaheuristic dựa trên các cấu trúc tìm kiếm mới:

  • Phương pháp khởi tạo lời giải ban đầu: Khảo sát ba phương thức: khởi tạo theo heuristic đặc thù, khởi tạo ngẫu nhiên, và khởi tạo dựa vào phân bố xác suất.
  • Các chiến lược tìm kiếm lân cận: Khảo sát các cơ chế: chèn cạnh - xóa cạnh, tìm lân cận tốt hơn, tìm lân cận ngẫu nhiên, Node-Based (NB), Path-Based (PB). Đồng thời, tác giả đề xuất 2 chiến lược mới:
    1. Chiến lược tìm kiếm lân cận tham lam: Ưu tiên lựa chọn các biến đổi lân cận làm giảm mạnh nhất chi phí cây.
    2. Chiến lược tìm kiếm lân cận có xác suất: Lựa chọn các toán tử lân cận dựa trên phân phối xác suất nhằm duy trì tính đa dạng và hạn chế hội tụ sớm.
  • Ba thuật toán metaheuristic đề xuất:
    • Thuật toán Bees-Steiner: Ứng dụng khung thuật toán bầy ong (Bees Algorithm). Quần thể $N$ cá thể được phân lớp: chọn $p$ cá thể để tìm kiếm lân cận, trong đó $h$ cá thể tốt nhất được điều động thêm $nep$ ong thợ để khai thác sâu (tăng cường hóa), $p - h$ cá thể còn lại được điều động $nsp$ ong thợ ($nsp < nep$), và $N - p$ cá thể không được chọn sẽ bị thay thế bằng các cá thể ngẫu nhiên mới (đa dạng hóa).
    • Thuật toán tìm kiếm lân cận biến đổi (VNS giải SMT): Tích hợp các chiến lược lân cận đề xuất (tham lam và xác suất) vào lược đồ VNS. Thuật toán tuần tự chuyển đổi qua các cấu trúc lân cận khác nhau; khi tìm thấy nghiệm kỷ lục mới sẽ quay lại cấu trúc lân cận ban đầu.
    • Thuật toán tìm kiếm leo đồi (HCSMT): Kết hợp thuật toán Hill Climbing Search với chiến lược tìm kiếm lân cận ngẫu nhiên và kỹ thuật khởi động lại từ nhiều điểm xuất phát ngẫu nhiên khác nhau nhằm thoát khỏi các cực trị địa phương.
  • Kết quả thực nghiệm: Triển khai trên các nhóm dữ liệu chuẩn steinb, steinc, steind, steine. Kết quả đối sánh với các thuật toán Opt, SPH, Heu, NB, PB, TS, PGA cho thấy các thuật toán đề xuất đạt chất lượng nghiệm bằng hoặc tốt hơn các thuật toán metaheuristic đã công bố trên nhiều bộ dữ liệu thử nghiệm. Luận án kết luận rằng chất lượng của các thuật toán metaheuristic phụ thuộc mang tính quyết định vào việc thiết kế và phối hợp các chiến lược tìm kiếm lân cận.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và khoa học

  1. Phát triển hai thuật toán heuristic mới: Xây dựng thành công thuật toán SPT-Steiner (dựa trên cây đường đi ngắn nhất) và PD-Steiner (kết hợp nguyên lý Prim và Dijkstra) cho bài toán SMT, chứng minh được khả năng nâng cao chất lượng nghiệm so với thuật toán kinh điển MST-Steiner [14] trên các bộ dữ liệu đồ thị thưa.
  2. Cải tiến thuật toán heuristic cho đồ thị quy mô lớn: Đề xuất hai thuật toán cải tiến i-SPT-Steiner và i-PD-Steiner thông qua việc ứng dụng thuật toán Dial. Kết quả chứng minh i-PD-Steiner đạt tốc độ thực thi vượt trội hơn MST-Steiner trên các đồ thị có kích thước lên đến 100.000 đỉnh.
  3. Phát triển ba thuật toán metaheuristic và cấu trúc lân cận mới: Đề xuất thành công thuật toán Bees-Steiner, thuật toán VNS và thuật toán HCSMT giải bài toán SMT. Đề xuất hai chiến lược tìm kiếm lân cận mới gồm chiến lược tham lam và chiến lược có xác suất, tạo ra sự phối hợp hiệu quả giữa tính tăng cường và tính đa dạng trong không gian tìm kiếm.
  4. Xây dựng hệ thống dữ liệu thực nghiệm mở rộng: Đóng góp bộ dữ liệu gồm 80 đồ thị thưa quy mô lớn (từ 10.000 đến 100.000 đỉnh) thuộc các nhóm steinf, steing, steinh, steini, cung cấp thêm công cụ kiểm thử chuẩn cho các nghiên cứu tiếp theo về bài toán SMT.

Đóng góp về mặt thực tiễn và ứng dụng

  1. Định hình quy trình quy hoạch mạng: Đề xuất quy trình giải quyết bài toán quy hoạch mạng gồm 3 bước logic từ khảo sát, tối ưu hóa tôpô đến đánh giá khả thi.
  2. Hệ thống hóa 8 mô hình ứng dụng: Cụ thể hóa bài toán SMT vào 8 bài toán kỹ thuật thực tế (WLAN/LAN, VPN, Multicast, thiết kế vi mạch VLSI, kết nối nhóm, Steiner nhiều pha, mạng Steiner nhiều pha, xây dựng cây phát sinh loài).
  3. Cung cấp tiêu chí lựa chọn thuật toán theo bài toán thực tế:
    • Với bài toán thiết kế hệ thống mạng (ưu tiên chất lượng tối ưu chi phí hạ tầng): khuyến nghị sử dụng các thuật toán metaheuristic như Bees-Steiner, VNS hoặc heuristic PD-Steiner.
    • Với bài toán vận hành và điều khiển mạng thời gian thực hoặc đồ thị quy mô cực lớn (ưu tiên thời gian đáp ứng): khuyến nghị sử dụng thuật toán cải tiến i-PD-Steiner.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của nghiên cứu

  • Phạm vi dạng bài toán: Luận án chỉ tập trung giải quyết bài toán SMT trên đồ thị với trọng số cạnh ngẫu nhiên không âm, chưa mở rộng giải quyết dạng bài toán Cây Steiner với khoảng cách Euclide và khoảng cách chữ nhật.
  • Thời gian tính toán của một số thuật toán: Thuật toán SPT-Steiner và thuật toán cải tiến i-SPT-Steiner vẫn có thời gian chạy chậm hơn so với thuật toán MST-Steiner.
  • Đặc tính tài nguyên của metaheuristic: Các thuật toán metaheuristic dạng quần thể (như Bees-Steiner) đòi hỏi chi phí tính toán và bộ nhớ lớn hơn đáng kể so với các thuật toán dạng cá thể khi kích thước đồ thị tăng cao.

Hướng nghiên cứu tiếp theo

  • Triển khai áp dụng trực tiếp các thuật toán đề xuất để giải quyết các bài toán thiết kế mạng viễn thông và mạng máy tính cụ thể tại các địa phương và doanh nghiệp viễn thông.
  • Tiếp tục nghiên cứu mở rộng thuật toán để giải quyết các biến thể phức tạp hơn của bài toán Cây Steiner trong mạng truyền thông như: bài toán Cây Steiner có ràng buộc độ trễ (delay-constrained), bài toán Cây Steiner có ràng buộc băng thông, hoặc bài toán trên đồ thị có hướng.
  • Nghiên cứu tối ưu hóa cấu trúc dữ liệu lưu trữ và tính toán song song nhằm rút ngắn thời gian thực thi của các thuật toán metaheuristic trên các đồ thị quy mô siêu lớn.

Giá trị tham khảo

Đối tượng thụ hưởng

  • Nghiên cứu sinh, học viên cao học, giảng viên: Thuộc các chuyên ngành Hệ thống thông tin, Khoa học máy tính, Công nghệ mạng, và Toán tin ứng dụng quan tâm đến tối ưu tổ hợp, lý thuyết đồ thị và thiết kế thuật toán xấp xỉ.
  • Kỹ sư mạng và chuyên viên quy hoạch hạ tầng viễn thông: Cán bộ kỹ thuật tại các nhà cung cấp dịch vụ Internet (ISP), trung tâm dữ liệu, cơ quan quản lý công nghệ thông tin cần giải pháp tối ưu hóa chi phí đường truyền và cấu trúc tôpô kết nối.
  • Kỹ sư thiết kế vi mạch (VLSI): Tham khảo các biến thể thuật toán phục vụ tối ưu hóa đường đi dây trên chip bán dẫn.

Phần nội dung đáng tham khảo chuyên sâu

  • Chương 2 và Chương 3: Toàn bộ mã giả, sơ đồ khối và phân tích độ phức tạp của các thuật toán SPT-Steiner, PD-Steiner, i-PD-Steiner, Bees-Steiner, VNS, HCSMT cùng các toán tử tìm kiếm lân cận tham lam và xác suất.
  • Mục 1.4 (Chương 1): Nội dung mô hình hóa toán học 8 bài toán ứng dụng thực tế trong mạng và kỹ thuật viễn thông.
  • Phụ lục 1 và Phụ lục 2: Hệ thống bảng số liệu thực nghiệm chi tiết và đặc tả thông số kỹ thuật của 80 bộ dữ liệu mở rộng (steinf, steing, steinh, steini) làm cơ sở dữ liệu đối chuẩn (benchmark) cho các nghiên cứu tối ưu hóa sau này.

Câu hỏi thường gặp

1. Điểm khác biệt căn bản giữa bài toán Cây Steiner nhỏ nhất (SMT) và bài toán Cây khung nhỏ nhất (MST) là gì?

Trong bài toán Cây khung nhỏ nhất (MST), cây kết quả bắt buộc phải đi qua toàn bộ $n$ đỉnh thuộc tập đỉnh $V(G)$ của đồ thị. Ngược lại, trong bài toán Cây Steiner nhỏ nhất (SMT), cây kết quả chỉ bắt buộc phải đi qua một tập con các đỉnh cho trước gọi là tập terminal $L \subseteq V(G)$ và có thể bổ sung thêm một số đỉnh trung gian khác (gọi là đỉnh Steiner) nếu việc thêm các đỉnh này giúp giảm tổng trọng số của cây. Khi $L = V(G)$, bài toán SMT trở thành bài toán MST.

2. Thuật toán cải tiến i-PD-Steiner sử dụng giải pháp kỹ thuật nào để vượt trội về thời gian chạy trên đồ thị kích thước lên đến 100.000 đỉnh?

Thuật toán i-PD-Steiner thay thế thuật toán tìm đường đi ngắn nhất Dijkstra nguyên bản bằng thuật toán Dial (một biến thể tối ưu của Dijkstra sử dụng cấu trúc bucket). Việc thay thế này giúp giảm thiểu đáng kể chi phí tìm kiếm đỉnh có khoảng cách nhỏ nhất trên các đồ thị thưa kích thước lớn, nhờ đó i-PD-Steiner đạt thời gian chạy nhanh hơn cả thuật toán MST-Steiner kinh điển và thuật toán i-SPT-Steiner trên cùng bộ dữ liệu thực nghiệm mở rộng.

3. Hai yếu tố mấu chốt quyết định chất lượng của một thuật toán metaheuristic được luận án phân tích và xử lý ra sao?

Hai yếu tố quan trọng nhất là tính tăng cường (intensification) và tính đa dạng (diversification). Tính tăng cường giúp khai thác sâu các vùng nghiệm tiềm năng thông qua các toán tử lân cận tham lam; nếu quá cao sẽ dẫn đến hội tụ sớm vào cực trị địa phương. Tính đa dạng giúp khám phá các vùng không gian mới để thoát khỏi bẫy tối ưu cục bộ thông qua yếu tố ngẫu nhiên hoặc xác suất; nếu quá cao sẽ làm chậm tốc độ hội tụ. Luận án đã giải quyết sự cân bằng này bằng cách đề xuất 2 chiến lược lân cận mới (tham lam và có xác suất) tích hợp linh hoạt trong các thuật toán Bees-Steiner, VNS và HCSMT.

4. Quy trình giải quyết bài toán quy hoạch mạng và các mô hình ứng dụng SMT tiêu biểu được luận án xác định như thế nào?

Quy trình quy hoạch mạng gồm 3 bước: Khảo sát thực địa xác định nút mạng và yêu cầu kỹ thuật $\rightarrow$ Xây dựng tôpô mạng tối ưu chi phí bằng thuật toán $\rightarrow$ Phân tích, đánh giá khả thi. Tác giả đã định hướng ứng dụng SMT vào 8 mô hình thực tế: thiết kế mạng WLAN trên hạ tầng LAN, cung cấp mạng riêng ảo VPN của ISP, truyền thông đa hướng (multicast), thiết kế đường đi dây vi mạch VLSI, kết nối nhóm, bài toán Steiner nhiều pha, bài toán mạng Steiner nhiều pha, và xây dựng cây phát sinh loài trong sinh học tính toán.

5. Hệ thống dữ liệu thực nghiệm trong luận án gồm những nguồn nào và quy mô ra sao?

Hệ thống dữ liệu gồm 158 bộ dữ liệu đồ thị thưa:

  • 78 bộ dữ liệu chuẩn lấy từ thư viện OR-Library của J. Beasley, thuộc các nhóm đồ thị steinb, steinc, steind, steine.
  • 80 bộ dữ liệu mở rộng do chính tác giả sinh ngẫu nhiên, thuộc các nhóm steinf, steing, steinh, steini, với quy mô đồ thị thưa mở rộng từ 10.000 đỉnh lên đến 100.000 đỉnh.

Kết luận

Luận án tiến sĩ của tác giả Trần Việt Chương đã nghiên cứu toàn diện bài toán Cây Steiner nhỏ nhất trên đồ thị thưa có trọng số ngẫu nhiên phục vụ thiết kế hệ thống mạng. Công trình đã đề xuất thành công các thuật toán heuristic mới (SPT-Steiner, PD-Steiner) và cải tiến (i-SPT-Steiner, i-PD-Steiner với thuật toán Dial), giúp giải quyết hiệu quả bài toán trên đồ thị quy mô lớn lên đến 100.000 đỉnh. Bên cạnh đó, luận án phát triển ba thuật toán metaheuristic (Bees-Steiner, VNS, HCSMT) cùng hai chiến lược tìm kiếm lân cận mới (tham lam và xác suất), đạt chất lượng nghiệm tương đương hoặc vượt trội các công bố trước trên nhiều bộ dữ liệu thử nghiệm. Luận án đã hệ thống hóa quy trình quy hoạch mạng và xác lập 8 mô hình ứng dụng thực tiễn, đóng góp giá trị khoa học về mặt thuật toán tối ưu tổ hợp và giá trị ứng dụng trong kỹ thuật thiết kế mạng truyền thông.