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

Nghiên Cứu Phát Triển Một Số Thuật Toán 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ác giả: Phạm Đình Thành

Lĩnh vực: Cơ sở toán học cho tin học

Nội dung tài liệu:

Tài liệu này trình bày một nghiên cứu chuyên sâu về bài toán Cây khung phân cụm đường đi ngắn nhất (CluSPT), một bài toán thuộc lớp NP-Khó có nhiều ứng dụng thực tiễn trong các lĩnh vực như tối ưu hóa mạng lưới, hệ thống dẫn nước, và logistics. Do tính phức tạp của bài toán, nghiên cứu tập trung vào việc phát triển các thuật toán xấp xỉ, đặc biệt là các thuật toán dựa trên phương pháp tiến hóa và tiến hóa đa nhân tố.

Nghiên cứu đề xuất các thuật toán mới nhằm nâng cao hiệu quả giải bài toán CluSPT, bao gồm việc cải tiến các toán tử tiến hóa, xây dựng cơ chế kết hợp thuật toán tiến hóa đa nhân tố (MFEA) với các thuật toán xấp xỉ khác, và phát triển các phương pháp đánh giá thuật toán. Các thuật toán được đề xuất hứa hẹn mang lại lời giải nhanh chóng, dễ cài đặt và có chất lượng tốt hơn so với các phương pháp hiện có. Ngoài ra, luận án còn đề cập đến các ứng dụng thực tế của các thuật toán được phát triển, mở ra tiềm năng ứng dụng trong kỹ thuật và sản xuất.

Mục lục chi tiết:

• Chương 1: Tổng quan về thuật toán di truyền, thuật toán tiến hóa đa nhân tố, và bài toán cây phân cụm đường đi ngắn nhất.
• Chương 2: Trình bày các thuật toán xấp xỉ cho bài toán CluSPT, bao gồm thuật toán SLA và thuật toán HB-RGA.
• Chương 3: Đề xuất các thuật toán tiến hóa để giải bài toán CluSPT, với các phương pháp mã hóa Cayley và hướng tiếp cận dựa trên giảm không gian tìm kiếm.