- TÓM TẮT NỘI DUNG LUẬN VĂN THẠC SĨ Đề tài: Ứng dụng thuật toán lai giải bài toán cây khung truyền thông tối ưu Tác giả luận văn: Nguyễn Duy Hiệp Lớp: CNTT Khóa Người hướng dẫn: PGS.TS. - Nguyễn Đức Nghĩa Tóm tắt nội dung Bài toán cây khung truyền thông tối ưu (Optimal Communication Spanning Tree - OCST) là bài toán trên đồ thị thuộc lớp NP-khó có nhiều ứng dụng trong thực tế đặc biệt là trong việc thiết kế vi mạch và các mô hình mạng. - Do tầm quan trọng của bài toán đã có rất nhiều hướng tiếp cận để giải bài toán. - Các hướng tiếp cận ban đầu là giải chính xác hoặc giải gần đúng không cho kết quả tốt trên những đồ thị có kích thước lớn hơn 10 đỉnh. - Các hướng tiếp cận gần đây đều tập trung vào sử dụng các kỹ thuật trong tính toán tiến hóa như giải thuật di truyền, tối ưu hóa bầy đàn hoặc các giải thuật lai giữa di truyền kết hợp với các kỹ thuật tìm kiếm địa phương để cải thiện chất lượng lời giải. - Luận văn này tập trung vào nghiên cứu hướng giải quyết bài toán sử dụng giải thuật di truyền kết hợp với một số kỹ thuật trong tính toán tiến hóa khác. - Trong thuật toán di truyền gốc thì mỗi cá thể (ta gọi phần tử thứ i trong quần thể là cá thể thứ i) chỉ lưu được trạng thái hiện tại của nó. - Nếu có những gen tốt đã được tìm ra trong những thế hệ đầu tiên nếu mà không được lan truyền qua thế hệ sau thì sẽ bị mất đi. - Do đó cả quần thể có thể phải mất nhiều lần lặp để tìm lại gen bị mất đi đó. - Vì thế trong giải thuật lai này, một phương pháp để lưu trữ và kết hợp các gen tốt trong quá khứ của cá thể để tạo ra quần thể mới được đề xuất. - Ý tưởng của việc lưu trữ kết hợp thông tin quá khứ này dựa trên ý tưởng trong thuật toán tối ưu hóa bầy đàn, khi mà các cá thể quyết định hướng chuyển động tiếp theo dựa trên vị trí hiện tại, vị trí tốt nhất trong quá khứ và vị trí tốt nhất cả cả quần thể. - Thuật toán đã được chạy thử nghiệm sử dụng 6 phương pháp mã hóa cây khung thông dụng, và 2 phương pháp lai ghép của thuật toán di truyền chuẩn, và thực hiện trên hai loại dữ liệu test : (1) các bộ dữ liệu mẫu thường sử dụng để đánh giá các thuật toán giải bài toán này, và (2) hai bộ dữ liệu được sinh ngẫu nhiên. - Kết quả thử nghiệm cho thấy thời gian thực hiện và chất lượng kết quả thu được cải thiện rõ rệt so với thuật toán GA truyền thống cùng để giải bài toán này. - Một số vấn đề mở chưa được giải quyết trong luận văn là: cải thiện chất lượng của quần thể khởi tạo ban đầu bằng các thuật toán gần đúng, cải thiện chất lượng lời giải bằng cách kết hợp thêm các kỹ thuật tìm kiếm địa phương, song song hóa thuật toán… Hà nội, ngày 31 tháng 10 năm 2010
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt