Tên đề tài: Các thuật toán gần đúng giải bài toán cực tiểu hóa độ trễ.
Chuyên ngành: Khoa học Máy tính
Mã số: 62480101
Người hướng dẫn khoa học: PGS.TS. Nguyễn Đức Nghĩa
Thời gian: 14h00 ngày 16 tháng 06 năm 2014
Địa điểm:Nhà C1 phòng 318 ĐHBKHN

Luận án tập trung nghiên cứu phát triển các thuật toán hiệu quả để giải bài toán cực tiểu hóa độ trễ, là một bài toán tối ưu hóa tổ hợp có nhiều ứng dụng trong thực tiễn. Luận án đạt được những kết quả chính sau đây:
·                 Đề xuất thuật toán nhánh cận dựa trên một số tiêu chuẩn cắt nhánh hiệu quả. Thuật toán đề xuất cho phép giải các bài toán MLP trên đồthị với 40 đỉnh (thuật toán đúng do Wu et al. [49] đề xuất chỉ làm việc được với những đồ thị dưới 30 đỉnh). Thời gian chạy của thuật toán đềxuất là nhanh hơn thuật toán của Wu et al. trên nhiều bộ dữ liệu.
·                 Khảo sát thực nghiệm để đánh giá và so sánh hiệu quả của các thuật toán gần đúng cận tỷ lệ trên ba khía cạnh cận tỷ lệ, thời gian chạy và chất lượng của cận dưới.
·                 Đề xuất thuật toán gần đúng dựa trên phương pháp Subgradient với cận tỷ lệ được đánh giá bởi thực nghiệm là tốt hơn so với các thuật toán gần đúng cận tỷ lệ hiện biết trên nhiều bộ dữ liệu.
·                 Đề xuất thuật toán meta–heuristic dựa trên lược đồ của thuật toán di truyền (Genetic Algorithm – GA) để giải bài toán MLP. Kết quả thực nghiệm cho thấy thuật toán đề xuất đưa ra lời giải với cận tỷ lệ tốt hơn cận tỷ lệ của các thuật toán gần đúng cận tỷ lệ hiện biết đối với tất cả các bộ dữ liệu.
·                 Đề xuất thuật toán meta-heuristic (ACO-GA) lai ghép giữa thuật toán di truyền (GA) và thuật toán đàn kiến (ACO). Kết quả thực nghiệm cho thấy thuật toán đề xuất đưa ra lời giải với cận tỷ lệ tốt hơn cận tỷ lệ của các thuật toán meta-heuristic hiện biết trên nhiềubộ dữ liệu.
·                 Đề xuất thuật toán meta-heuristic đơn lời giải TS-VNS lai ghép giữa thuật toán Tabu (TS) và thuật toán đa lân cận (VNS), trong đó các thuật toán khảo sát lân cận được tăng tốc nhờ việc chỉ ra các thuật toán thời gian tính hằng số để tính độ trễ của các lời giải lân cận. Kết quả thực nghiệm cho thấy, đối với các bài toán kích thước nhỏ, thuật toán luôn cho ra lời giải tối ưu, trong khi, đối với các bài toán kích thước lớn, thuật toán cho lời giải tốt hơn lời giải tìm được bởi các thuật toán meta-heuristic hiện biết trên nhiều bộ dữ liệu.
Các kết quả chính của luận án đã được công bố trong 7 bài báo khoa học tại các tạp chí khoa học chuyên ngành quốc gia và quốc tế và các hội thảo khoa học chuyên ngành quốc tế. Ba bài báo công bố trên tạp chí bao gồm: 1 bài trên tạp chí Tin học và Điều khiển học, 1 bài trên tạp chí Progress of Informatics của NII, Nhật Bản, 1 bài trên tạp chí Khoa học và công nghệ các trường đại học kỹ thuật; Bốn bài được công bố tại các hội nghị quốc tế: RIVF (2 bài), KSE (1 bài), Soict(1 bài).