THÔNG TIN LUẬN ÁN TIẾN SĨ
Tên đề tài luận án tiến sĩ: 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
Chuyên ngành: Hệ thống thông tin
Mã số: 9.48.01.04
Họ và tên nghiên cứu sinh: Trần Việt Chương
Người hướng dẫn khoa học:
1. PGS.TS. Hà Hải Nam
2. TS. Phan Tấn Quốc
Đơn vị đào tạo: Học viện Công nghệ Bưu chính Viễn thông
Cơ sở đào tạo: Học viện Công nghệ Bưu chính Viễn thông
NHỮNG KẾT QUẢ MỚI CỦA LUẬN ÁN
– Đề xuất hai thuật toán heuristic mới: SPT-Steiner và PD-Steiner giải bài toán SMT; các thuật toán này được cài đặt thực nghiệm trên 98 bộ dữ liệu (gồm có 78 bộ dữ liệu là các đồ thị thưa trong hệ thống dữ liệu thực nghiệm chuẩn và 20 bộ dữ liệu mở rộng là các đồ thị thưa kích thước lớn lên đến 10000 đỉnh – steinf). Từ kết quả thực nghiệm, luận án tiến hành so sánh, đánh giá chi tiết hiệu quả của hai thuật toán heuristic đề xuất mới với thuật toán heuristic MST-Steiner đã được công bố trước đó. Hai thuật toán đề xuất bởi luận án cho chất lượng lời giải tốt hơn thuật toán MST-Steiner trên một số bộ dữ liệu. Thời gian chạy của các thuật toán SPT-Steiner và PD-Steiner chậm hơn so với thuật toán MST-Steiner.
– Đề xuất hai thuật toán heuristic cải tiến: i-SPT-Steiner và i-PD-Steiner giải bài toán SMT trong trường hợp đồ thị thưa kích thước lớn. Hai thuật toán heuristic cải tiến i-SPT-Steiner và i-PD-Steiner được cài đặt thực nghiệm và so sánh, đánh giá tính hiệu quả trên 80 bộ dữ liệu là các đồ thị thưa kích thước lớn lên đến 100000 đinh. Hai thuật toán heuristic cải tiến cho chất lượng lời giải tốt hơn hoặc tương đương thuật toán MST-Steiner trên một số bộ dữ liệu. Thời gian chạy của thuật toán i-PD-Steiner nhanh hơn so với thuật toán MST-Steiner và thuật toán i-SPT-Steiner. Thời gian chạy của thuật toán i-SPT-Steiner chậm hơn so với thuật toán MST-Steiner và thuật toán i-PD-Steiner.
– Đề xuất mới ba thuật toán metaheuristic dạng cá thể, quần thể giải bài toán SMT đó là: thuật toán 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 Hill climbing search (HCSMT). Ngoài ra, luận án cũng đề xuất 2 chiến lược tìm kiếm lâncận: Tham lam và có xác suất; đồng thời sử dụng chúng trong lược đồ thuật toán tìm kiếm lân cận biến đổi, nhằm nâng cao hơn nữa chất lượng cho các thuật toán metaheuristic. Các thuật toán metaheuristic đề xuất mới này được cài đặt thực nghiệm trên hệ thống dữ liệu thực nghiệm chuẩn và so sánh hiệu quả với các thuật toán metaheuristic khác hiện biết. Kết quả so sánh cho thấy các thuật toán metaheuristic đề xuất mới cho chất lượng lời giải tốt hơn hoặc bằng các thuật toán metaheuristic công bố trước đó trên một số bộ dữ liệu; và chất lượng của các thuật toán metaheuristic phụ thuộc chủ yếu vào các chiến lược tìm kiếm lân cận.
