Đề tài nghiên cứu khoa học "Thuật toán kiến song song giải quyết bài toán Maxsat" trình bày nội dung tổng quan thuật toán kiến, xây dựng khung thuật kiến và sử dụng thuật toán kiến để giải quyết bài toán Maxsat. Để biết rõ hơn về nội dung chi tiết, . | TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI Khoa Công nghệ thông tin -------- -------- BÁO CÁO NGHIÊN CỨU KHOA HỌC Đề tài THUẬT TOÁN KIẾN SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT Giáo viên hướng dẫn: Thầy Đỗ Trung Kiên Sinh viên thực hiện : Quách Thị Hái Oanh _K54A Nguyễn Thị Hiện_K55B Trần Thị Hằng_K55B Nguyễn Thị Hương _K55B Hà Nội, 04-2008 1 LỜI MỞ ĐẦU Sự phức tạp của các bài toán tối ưu tổ hợp xuất hiện trong nhiều lĩnh vực khác nhau như: kinh tế, thương mại, khoa học, công nghiệp và y học. Tuy nhiên, có một số bài toán khi giải quyết gặp khó khăn trong ứng dụng. Cái khó vốn có là việc giải quyết các bài toán đã nêu ra trong lý thuyết khoa học máy tính trong thực tế như một số bài toán đã biết là NP-hard, ở đó không có thuật toán đã biết giải quyết chúng trong thời gian đa thức. Metaheuristics hợp nhất các khái niệm từ nhiều lĩnh vực khác nhau như di truyền học, sinh vật học, trí tuệ nhân tạo, toán học và vật lý Ví dụ của metaheuristics bao gồm thuật toán luyện thép, ngăn cản tìm kiếm, tìm kiếm lặp, tìm kiếm biến gần đúng, thủ tục tìm kiếm thích ứng tham lam ngẫu nhiên và thuật toán tiến hoá. Thuật toán metaheuristics gần đây nhất là thuật toán kiến (ACO), được sáng tạo bởi đường tìm kiếm ngắn nhất trong cách kiếm ăn của những con kiến khác nhau. Tuy nhiên từ công việc ban đầu của Dorigo, Maniezzo, và Colorni trong hệ thống kiến (Ant System), ACO nhanh chóng trở thành tìm kiếm hoàn thiện trong lĩnh vực: một số lượng lớn tác giả phát triển mô hình phức tạp hơn để sử dụng thành công giải quyết một lượng lớn kết hợp bài toán tối ưu phức tạp và đi sâu vào lý thuyết thuật toán bây giờ trở thành cái sẵn có. Ở đây, em đã tìm hiểu thuật toán kiến và sử dụng thuật toán này để giải quyết bài toán Maxsat. Thuật toán này có ứng dụng để giải quyết các bài toán tổ hợp tối ưu, đặc biệt là một số bài toán đang gặp khó khăn trong việc tìm lời giải. 2 MỤC LỤC Chương I: TỔNG QUAN THUẬT TOÁN KIẾN 4 I. Thuật toán .
