Thông tin về luận án tiến sỹ trước bảo vệ cấp Học viện của NCS Trần Việt Chương

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. TS. Hà Hải Nam
2. 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 đỉnh. 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 iSPT-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 MSTSteiner 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ân cậ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.

CÁC ỨNG DỤNG VÀ KHẢ NĂNG ỨNG DỤNG TRONG THỰC TIỄN HOẶC NHỮNG

VẤN ĐỀ CÒN BỎ NGỎ CẦN TIẾP TỤC NGHIÊN CỨU

Hiện nay, các hướng tiếp cận giải chính xác hoặc giải gần đúng bài toán Cây Steiner nhỏ nhất nói chung đang được các nhà khoa học, các tập toàn công nghệ lớn quan tâm, đầu tư nghiên cứu. Do là bài toán tối ưu thuộc lớp NP-hard, nên mỗi phương án mới đưa ra có nhiều ưu điểm và ngày càng hiệu quả hơn.

Theo hướng này, trong thời gian tới luận án sẽ tiếp tục phát triển các nội dung sau:

• Tiếp tục phát triển mới các chiến lược tăng cường hóa, đa dạng hóa lời giải (các chiến lược tìm kiếm lân cận), áp dụng vào sơ đồ các thuật toán đề xuất, nhằm nâng cao hơn nữa chất lượng lời giải cho các thuật toán.
• Tiếp tục cải tiến cấu trúc dữ liệu, kỹ thuật lập trình khi cài đặt thực nghiệm thuật toán với hy vọng rút ngắn thời gian chạy các thuật toán khi làm việc với các đồ thị thưa kích thước lớn (cỡ 100 000 đỉnh).
• Dựa vào sơ đồ các thuật toán đề xuất và các thuật toán hiện biết của tác giả khác, phát triển một thuật toán mới dạng metaheuristic giải quyết một số bài toán cây khung truyền thông tối ưu, hoặc các bài toán định tuyến trên đồ thị thuộc lớp NP-hard khác.
• Dựa vào các kết quả nghiên cứu đạt được, xây dựng một phần mềm ứng dụng giải bài toán Cây Steiner nhỏ nhất và áp dụng kết quả đạt được vào thiết kế một hệ thống mạng cụ thể trong thực tế.

Trang quyết định
Tóm tắt luận án tiến sỹ
Trang thông tin Luận án tiến sỹ Tiếng Việt
Trang thông tin Luận án tiến sỹ Tiếng Anh
Luận án tiến sỹ