Luận án Nghiên cứu phát triển một số thuật toán tiến hóa giải bài toán cây khung phân cụm đường đi ngắn nhất

Tên luận án:

NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁN TIẾN HÓA GIẢI BÀI TOÁN CÂY KHUNG PHÂN CỤM ĐƯỜNG ĐI NGẮN NHẤT

Ngành:

Cơ sở toán học cho tin học

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

Luận án này tập trung nghiên cứu và phát triển các thuật toán tiến hóa để giải quyết Bài toán Cây khung Phân cụm Đường đi ngắn nhất (Clustered Shortest-Path Tree Problem - CluSPT), một bài toán thuộc lớp NP-Khó nhưng có nhiều ứng dụng thực tiễn quan trọng trong các lĩnh vực như mạng lưới, nông nghiệp, bưu chính và giao vận. Mục tiêu chính của luận án là xây dựng các thuật toán xấp xỉ hiệu quả, đặc biệt là dựa trên thuật toán tiến hóa (Evolutionary Algorithm - EA) và thuật toán tiến hóa đa nhân tố (Multi-Factorial Evolutionary Algorithm - MFEA).

Luận án đã đề xuất một số thuật toán mới theo ba hướng tiếp cận. Đối với hướng tiếp cận đúng, thuật toán chính xác SLA-M được phát triển để giải bài toán CluSPT trên đồ thị metric. Đối với hướng heuristic, thuật toán HB-RGA (kết hợp thuật toán tham lam ngẫu nhiên và thuật toán cây đường đi ngắn nhất) được đề xuất, mang lại lời giải chất lượng tốt trong thời gian ngắn. Trong hướng meta-heuristic, luận án giới thiệu hai thuật toán tiến hóa là C-EA và N-EA, cùng với các toán tử tiến hóa mới như lai ghép, đột biến, mã hóa lời giải và phương pháp giảm chi phí tính toán. Đặc biệt, thuật toán tiến hóa đa nhân tố G-MFEA, dựa trên sự kết hợp giữa MFEA và HB-RGA, được phát triển để giải bài toán CluSPT, với cơ chế phân rã bài toán đầu vào thành hai tác vụ riêng biệt và quá trình trao đổi tri thức giữa chúng, giúp tiệm cận lời giải tối ưu.

Kết quả thực nghiệm trên nhiều bộ dữ liệu (metric và phi metric) cho thấy thuật toán G-MFEA đạt chất lượng lời giải tốt nhất, tiệm cận kết quả tối ưu. Các thuật toán HB-RGA và N-EA có chất lượng lời giải gần nhau và tốt hơn đáng kể so với C-EA và AAL. Luận án cũng phân tích ảnh hưởng của số cụm và số đỉnh của đồ thị đầu vào tới hiệu quả của các thuật toán. Các đóng góp của luận án có thể áp dụng trực tiếp vào các bài toán thực tế trong kỹ thuật và sản xuất.

Mục lục chi tiết:

CHƯƠNG 1: TỔNG QUAN

• 1.1. Thuật toán di truyền
• 1.2. Thuật toán tiến hóa đa nhân tố
• 1.3. Bài toán cây phân cụm đường đi ngắn nhất
  • 1.3.1. Một số định nghĩa
  • 1.3.2. Phát biểu bài toán
  • 1.3.3. Tổng quan tình hình nghiên cứu
• 1.4. Kết luận chương

CHƯƠNG 2: THUẬT TOÁN XẤP XỈ GIẢI BÀI TOÁN CÂY PHÂN CỤM VỚI ĐƯỜNG ĐI NGẮN NHẤT

• 2.1. Thuật toán xây dựng cây khung hình sao
  • 2.1.1. Lược đồ thuật toán
  • 2.1.2. Thuật toán dạng hình sao trên đồ thị metric
• 2.2. Thuật toán tham lam ngẫu nhiên
• 2.3. Kết luận chương

CHƯƠNG 3: THUẬT TOÁN TIẾN HÓA GIẢI BÀI TOÁN CÂY PHÂN CỤM VỚI ĐƯỜNG ĐI NGẮN NHẤT

• 3.1. Thuật toán tiến hóa dựa trên mã Cayley
  • 3.1.1. Phương pháp phân rã bài toán CluSPT
  • 3.1.2. Mã hóa cá thể
  • 3.1.3. Phương pháp khởi tạo cá thể
  • 3.1.4. Toán tử lai ghép
  • 3.1.5. Toán tử đột biến
• 3.2. Hướng tiếp cận dựa trên giảm không gian tìm kiếm của thuật toán tiến hóa
  • 3.2.1. Cách tiếp cận
  • 3.2.2. Phương pháp phân rã bài toán CluSPT
  • 3.2.3. Biểu diễn cá thể
  • 3.2.4. Phương pháp khởi tạo cá thể
  • 3.2.5. Toán tử lai ghép
  • 3.2.6. Toán tử đột biến
  • 3.2.7. Cách đánh giá cá thể mới
• 3.3. Kết luận chương

CHƯƠNG 4: THUẬT TOÁN TIẾN HÓA ĐA NHÂN TỐ GIẢI BÀI TOÁN CÂY PHÂN CỤM VỚI ĐƯỜNG ĐI NGẮN NHẤT

• 4.1. Ý tưởng đề xuất thuật toán G-MFEA
• 4.2. Lược đồ của thuật toán G-MFEA
• 4.3. Biểu diễn cá thể
• 4.4. Phương pháp khởi tạo cá thể
• 4.5. Toán tử lai ghép
• 4.6. Toán tử đột biến
• 4.7. Phương pháp giải mã
• 4.8. Cách tác vụ thứ hai cải thiện chất lượng lời giải
• 4.9. Kết luận chương

CHƯƠNG 5: KẾT QUẢ THỰC NGHIỆM

• 5.1. Dữ liệu thực nghiệm và đánh giá lời giải
  • 5.1.1. Đồ thị metric
  • 5.1.2. Đồ thị đầy đủ phi metric
  • 5.1.3. Tiêu chí đánh giá
  • 5.1.4. Môi trường, tham số thực nghiệm
• 5.2. Kết quả thực nghiệm
  • 5.2.1. Đồ thị metric
  • 5.2.2. Đồ thị đầy đủ phi metric
• 5.3. Kết luận chương

KẾT LUẬN

DANH MỤC CÔNG TRÌNH CÔNG BỐ