Luận án 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

Tên luận án:

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

Ngành:

Hệ thống thông tin

Tóm tắt nội dung tài liệu:

Luận án "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" giải quyết một trong những bài toán tối ưu tổ hợp quan trọng nhất trong thiết kế mạng truyền thông: Bài toán Cây Steiner nhỏ nhất (SMT). Đây là một bài toán thuộc lớp NP-hard, không thể giải chính xác trong thời gian đa thức với quy mô lớn, do đó đòi hỏi các phương pháp xấp xỉ hiệu quả như heuristic và metaheuristic. Luận án nhấn mạnh rằng các thuật toán metaheuristic hiện tại 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.

Mục tiêu chính của luận án là nghiên cứu và phát triển các thuật toán heuristic và metaheuristic nhằm giải bài toán SMT một cách hiệu quả, đặc biệt định hướng ứng dụng vào thiết kế hệ thống mạng. Phương pháp nghiên cứu kết hợp chặt chẽ giữa lý thuyết và thực nghiệm, bao gồm khảo sát các công trình khoa học liên quan, đề xuất và cải tiến thuật toán, sau đó thực nghiệm và đánh giá trên các hệ thống dữ liệu chuẩn và mở rộng. Việc đánh giá dựa trên độ phức tạp thuật toán, chất lượng lời giải và thời gian chạy thực nghiệm.

Luận án đã đạt được nhiều đóng góp đáng kể. Cụ thể, đã đề xuất hai thuật toán heuristic mới là SPT-Steiner và PD-Steiner để giải bài toán SMT trên đồ thị thưa. Tiếp theo, hai thuật toán heuristic cải tiến là i-SPT-Steiner và i-PD-Steiner được phát triển để xử lý các đồ thị thưa có kích thước lớn, lên đến 100.000 đỉnh. Luận án cũng giới thiệu ba thuật toán metaheuristic mới thuộc dạng cá thể và quần thể, bao gồm Bees-Steiner, thuật toán tìm kiếm lân cận biến đổi (VNS) và thuật toán tìm kiếm leo đồi (HCSMT) để giải bài toán SMT. Ngoài ra, luận án còn đề xuất các chiến lược tìm kiếm lân cận (tham lam và có xác suất) nhằm nâng cao hiệu quả của các thuật toán metaheuristic. Dựa trên kết quả thực nghiệm, luận án phân tích chi tiết đặc tính của các thuật toán metaheuristic và đề xuất hướng áp dụng cụ thể cho từng loại đồ thị trong thiết kế hệ thống mạng. Các kết quả này không chỉ giải quyết các bài toán ứng dụng thực tiễn mà còn tạo cơ sở cho việc giải các bài toán tối ưu NP-hard khác.

Mục lục chi tiết:

• 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

  • 1.1. Cơ sở lý thuyết
    • 1.1.1. Một số định nghĩa
    • 1.1.2. Một số dạng của bài toán SMT
    • 1.1.3. Tổng quan các nghiên cứu liên quan đến bài toán SMT
  • 1.2. Tiếp cận thuật toán metaheuristic giải bài toán SMT
    • 1.2.1. Thuật toán metaheuristic
    • 1.2.2. Tính tăng cường và tính đa dạng
    • 1.2.3. Tiêu chí đánh giá chất lượng thuật toán metaheuristic
    • 1.2.4. Phân tích các thành phần của một thuật toán metaheuristic
    • 1.2.5. Giới thiệu sơ đồ một số thuật toán metaheuristic thường gặp
  • 1.3. Khảo sát một số thuật toán tiêu biểu giải bài toán SMT
  • 1.4. Định hướng ứng dụng kết quả nghiên cứu cho thiết kế hệ thống mạng
    • 1.4.1. Giới thiệu bài toán quy hoạch mạng
    • 1.4.2. Giới thiệu bài toán quy hoạch mạng
  • 1.5. Lựa chọn dữ liệu thực nghiệm

• CHƯƠNG 2: ĐỀ XUẤT THUẬT TOÁN HEURISTIC GIẢI BÀI TOÁN CÂY STEINER NHỎ NHẤT

  • 2.1. Giới thiệu hướng tiếp cận heuristic giải bài toán SMT
  • 2.2. Thuật toán SPT-Steiner
  • 2.3. Thuật toán PD-Steiner
  • 2.4. Thực nghiệm và đánh giá
  • 2.5. Cải tiến thuật toán heuristic giải bài toán SMT trong trường hợp đồ thị thưa kích thước lớn
    • 2.5.1. Thuật toán i-SPT-Steiner
    • 2.5.2. Thuật toán i-PD-Steiner
  • 2.6. Thực nghiệm và đánh giá
  • 2.7. Đánh giá các thuật toán thông qua độ phức tạp

• CHƯƠNG 3: ĐỀ XUẤT THUẬT TOÁN METAHEURISTIC GIẢI BÀI TOÁN CÂY STEINER NHỎ NHẤT

  • 3.1. Giới thiệu hướng tiếp cận metaheuristic giải bài toán SMT
  • 3.2. Khởi tạo lời giải ban đầu
  • 3.3. Các chiến lược tìm kiếm Cây Steiner lân cận
  • 3.4. Thuật toán Bees giải bài toán SMT
  • 3.5. Thuật toán tìm kiếm lân cận biến đổi giải bài toán SMT
  • 3.6. Thuật toán Hill climbing search giải bài toán SMT
  • 3.7. Thực nghiệm và đánh giá các thuật toán metaheuristic giải bài toán SMT
    • 3.7.1. Thuật toán Bees-Steiner
    • 3.7.2. Thuật toán tìm kiếm lân cận biến đổi (VNS)
    • 3.7.3. Thuật toán Hill Climbing Search (HCSMT)
  • 3.8. Đánh giá các thuật toán thông qua độ phức tạp

• KẾT LUẬN

  • 1. Các đóng góp chính của luận án
    • 1.1. Đề xuất hai thuật toán heuristic mới giải bài toán SMT trong trường hợp đồ thị thưa
    • 1.2. Đề xuất hai thuật toán heuristic cải tiến giải bài toán SMT trong trường hợp đồ thị thưa kích thước lớn lên đến 100000 đỉnh
    • 1.3. Đề xuất ba thuật toán metaheuristic dạng cá thể, quần thể giải bài toán SMT trong trường hợp đồ thị thưa
    • 1.4. Đề xuất các chiến lược tìm kiếm lân cận sử dụng trong lược đồ thuật toán metaheuristic nhằm nâng cao hiệu quả của thuật toán metaheuristic trong việc giải bài toán SMT.
  • 2. Những nội dung nghiên cứu tiếp theo