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

Abstract

Bố cục của luận án được tổ chức thành 3 chương và phần kết luận, cụ thể: - Chương 1: Trình bày tổng quan về cơ sở lý thuyết bài toán SMT với các nội dung: Một số định nghĩa, định lý cơ bản liên quan; các dạng của bài toán SMT; sơ lược một số hướng tiếp cận. Tiếp theo, khảo sát một số thuật toán metaheuristic giải bài toán SMT, cụ thể như: giới thiệu sơ đồ một số thuật toán metaheuristic thường gặp gồm thuật toán local search, thuật toán leo đồi, thuật toán tìm kiếm lân cận biến đổi, thuật toán bầy ong; các tiêu chí đánh giá chất lượng thuật toán metaheuristic; khảo sát kết quả một số thuật toán heuristic, metaheuristic hiện biết giải bài toán SMT; định hướng ứng dụng bài toán SMT trong thiết kế hệ thống mạng và cuối cùng là giới thiệu hệ thống dữ liệu thực nghiệm chuẩn và mở rộng cho bài toán. - Chương 2: Đề xuất 2 thuật toán heuristic mới SPTSteiner, PD-Steiner giải bài toán SMT trong trường hợp đồ thị thưa và 2 thuật toán heuristic cải tiến i-SPT-Steiner, i-PDSteiner giải bài toán SMT trong trường hợp đồ thị thưa kích thước lớn. - Chương 3: Đề xuất 3 thuật toán metaheuristic giải bài toán SMT; các thuật toán này dựa trên khung thuật toán metaheuristic gồm: thuật toán Bees-Steiner, VNS và HCSMT. Luận án cũng đề xuất thêm một số chiến lược tìm kiếm lân cận cho bài toán SMT, đồng thời phân tích ưu nhược điểm của từng thuật toán cụ thể và qua đó định hướng áp dụng vào thực tế cho từng thuật toán đề xuất. Trong phần Kết luận, luận án trình bày những kết quả đạt được và định hướng phát triển cho nghiên cứu trong tương lai khi áp dụng kết quả luận án vào thực tiễn.