- TÓM TẮT NỘI DUNG LUẬN VĂN THẠC SĨ Đề tài: Giải thuật di truyền giải bài toán phủ đỉnh nhỏ nhất Tác giả luận văn: Hoàng Thị Hải Yến 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 phủ đỉnh nhỏ nhất (MVCP – Minimum Vertex Cover Problem) thuộc lớp bài toán NP – khó nổi tiếng trong tối ưu hóa trên đồ thị. - Bởi vì, một mặt, có nhiều bài toán NP – khó trong lý thuyết đồ thị như bài toán tập độc lập, bài toán bè,…có thể quy dẫn về MVCP, mặt khác bản thân bài toán phủ đỉnh nhỏ nhất cũng tìm được ứng dụng trong nhiều lĩnh vực thực tế như trong truyền thông, tin sinh học,… Do vậy, việc phát triển thuật toán giải bài toán phủ đỉnh nhỏ nhất đã và đang là mối quan tâm của nhiều nhà khoa học. - MVCP nằm trong danh sách 21 bài toán NP – đầy đủ được đưa ra bởi Karp từ năm 1970 và cho tới nay vẫn chưa có thuật toán hiệu quả tìm lời giải tối ưu cho nó. - Tuy đã có một số thuật toán thời gian đa thức để giải gần đúng bài toán được đề xuất song chất lượng của các lời giải tìm được chưa cao. - Hơn ba thập kỷ qua, đã có rất nhiều phương pháp được đề xuất để giải quyết các bài toán tối ưu hóa. - Một trong những phương pháp được áp dụng hiệu quả cho nhiều bài toán tối ưu tổ hợp đó là thuật toán di truyền. - Thuật toán di truyền được đề xuất bởi Holland vào những năm 1970 và đã được áp dụng rộng rãi trong nhiều ngành, nhiều lĩnh vực. - Bởi những thành tựu mà thuật toán di truyền đã đem lại, có rất nhiều nhà nghiên cứu đã và đang tập trung vào việc áp dụng thuật toán di truyền để giải bài toán phủ đỉnh nhỏ nhất. - Với mục đích nâng cao chất lượng lời giải, tác giả luận văn này cũng chọn hướng tiếp cận thuật toán di truyền để phát triển thuật toán giải bài toán phủ đỉnh nhỏ nhất. - Việc áp dụng GA là một hướng tiếp cận mới để đưa ra lời giải chất lượng tốt hơn cho bài toán MVCP. - Ở đây, luận văn đã thực hiện cài đặt ba thuật toán di truyền : GA của Ketan Kotecha, thuật toán GA của Hou Hongwei và thuật toán GA cải tiến, để giải bài toán MVCP. - Thuật toán GA cải tiến là sự kết hợp giữa hai thuật toán GA Ketan Kotecha và Hou Hongwei. - Tuy nhiên, GA cải tiến đã đưa vào một số cải tiến để nâng cao chất lượng lời giải, ví dụ như thuật toán khởi tạo quần thể ban đầu dựa trên việc kết hợp các phương pháp heuristic (greedy1 và greedy2). - Cả ba thuật toán được cài đặt và chạy thử nghiệm trên cùng một bộ dữ liệu để so sánh đánh giá kết quả của các thuật toá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ủa thuật toán GA cải tiến tốt hơn rõ rệt so với hai thuật toán GA của Ketan Kotecha và GA của Hou Hongwei. - Một số hướng phát triển của bài toán trong tương lai – Khảo sát các đặc trưng mới cho thuật toán di truyền lai để từ đó kết hợp các heuristic định hướng khác nhau nhằm đa dạng hóa các chiến lược tìm kiếm trên miền không gian lời giải sẽ được khảo sát. - Phát triển thuật toán để có thể giải được các biến thể của bài toán MVCP như: o Bài toán phủ đỉnh nhỏ nhất trên đồ thị có trọng số
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt