Báo cáo nghiên cứu khoa học: Thuật toán kiến song song giải quyết bài toán Maxsat
Số trang: 25
Loại file: pdf
Dung lượng: 437.03 KB
Lượt xem: 9
Lượt tải: 0
Xem trước 3 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
Đề 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, mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: Thuật toán kiến song song giải quyết bài toán MaxsatTRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘIKhoa Công nghệ thông tin-------- --------BÁO CÁO NGHIÊN CỨU KHOA HỌCĐề tàiTHUẬT TOÁN KIẾN SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSATGiáo viên hướng dẫn: Thầy Đỗ Trung KiênSinh viên thực hiện : Quách Thị Hái Oanh _K54ANguyễn Thị Hiện_K55BTrần Thị Hằng_K55BNguyễn Thị Hương _K55BHà Nội, 04-20081LỜI MỞ ĐẦUSự 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ựckhá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ựctế như một số bài toán đã biết là NP-hard, ở đó không có thuật toán đã biết giảiquyế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ư ditruyề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ủametaheuristics 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ậttoá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 conkiến khác nhau. Tuy nhiên từ công việc ban đầu của Dorigo, Maniezzo, và Colornitrong hệ thống kiến (Ant System), ACO nhanh chóng trở thành tìm kiếm hoànthiệ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ảiquyế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.2MỤC LỤCChương I: TỔNG QUAN THUẬT TOÁN KIẾN ........................................................ 4I. Thuật toán kiến......................................................................................................... 41. Đàn kiến tự nhiên (natural ant colonies) .............................................................. 42.Từ những con kiến tự nhiên tới thuật toán ACO .................................................... 63. Các loại mô hình ACO ......................................................................................... 74. Ứng dụng của ACO.............................................................................................. 75. Các bước để giải quyết một bài toán bởi ACO ..................................................... 9II. Một số ví dụ minh hoạ .......................................................................................... 101. Bài toán người du lịch ....................................................................................... 102. Xác định ma trận trọng số của mạng Neuron ..................................................... 10Chương II: XÂY DỰNG KHUNG THUẬT TOÁN KIẾN ....................................... 11I. Thiết kế khung thuật toán kiến................................................................................ 11* Sơ đồ chung của thuật toán kiến ......................................................................... 112. Lớp đòi hỏi (require) ......................................................................................... 16II. Khung thuật toán tuần tự ....................................................................................... 17III. Khung thuật toán song song ................................................................................. 19Chương III: SỬ DỤNG KHUNG THUẬT TOÁN KIẾN ĐỂ GIẢI QUYẾT BÀITOÁN MAXSAT ......................................................................................................... 22I. Giải quyết bài toán Maxsat ..................................................................................... 221. Bài toán Maxsat ................................................................................................. 22II. Kết quả thực nghiệm ............................................................................................. 243Chương I: TỔNG QUAN THUẬT TOÁN KIẾNI. Thuật toán kiến1. Đàn kiến tự nhiên (natural ant colonies)Loài kiến là loài sâu bọ có tính chất xã hội, chúng sống thành từng đàn, bởivậy có sự tác động lẫn nhau, chúng thạo tìm kiếm thức ăn và hoàn thành nhữngnhiệm vụ từ kiến chỉ huy. Một điều thú vị trong tìm kiếm thức ăn của vài con kiếnđặc biệt là khả năng của chúng để tìm kiếm đường đi ngắn nhất giữa tổ kiến vànguồn thức ăn. Trên thực tế, điều dễ nhận thấy có trong suy nghĩ nhưng nhiều conkiến hầu hết không nhận ra vì chúng không dùng thị giác để tìm kiếm những đầumối thức ăn.Trong quá trình đi giữa tổ và nguồn thức ăn, vài con kiến tích tụ một chấtđược gọi là mùi lạ (ph ...
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: Thuật toán kiến song song giải quyết bài toán MaxsatTRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘIKhoa Công nghệ thông tin-------- --------BÁO CÁO NGHIÊN CỨU KHOA HỌCĐề tàiTHUẬT TOÁN KIẾN SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSATGiáo viên hướng dẫn: Thầy Đỗ Trung KiênSinh viên thực hiện : Quách Thị Hái Oanh _K54ANguyễn Thị Hiện_K55BTrần Thị Hằng_K55BNguyễn Thị Hương _K55BHà Nội, 04-20081LỜI MỞ ĐẦUSự 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ựckhá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ựctế như một số bài toán đã biết là NP-hard, ở đó không có thuật toán đã biết giảiquyế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ư ditruyề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ủametaheuristics 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ậttoá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 conkiến khác nhau. Tuy nhiên từ công việc ban đầu của Dorigo, Maniezzo, và Colornitrong hệ thống kiến (Ant System), ACO nhanh chóng trở thành tìm kiếm hoànthiệ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ảiquyế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.2MỤC LỤCChương I: TỔNG QUAN THUẬT TOÁN KIẾN ........................................................ 4I. Thuật toán kiến......................................................................................................... 41. Đàn kiến tự nhiên (natural ant colonies) .............................................................. 42.Từ những con kiến tự nhiên tới thuật toán ACO .................................................... 63. Các loại mô hình ACO ......................................................................................... 74. Ứng dụng của ACO.............................................................................................. 75. Các bước để giải quyết một bài toán bởi ACO ..................................................... 9II. Một số ví dụ minh hoạ .......................................................................................... 101. Bài toán người du lịch ....................................................................................... 102. Xác định ma trận trọng số của mạng Neuron ..................................................... 10Chương II: XÂY DỰNG KHUNG THUẬT TOÁN KIẾN ....................................... 11I. Thiết kế khung thuật toán kiến................................................................................ 11* Sơ đồ chung của thuật toán kiến ......................................................................... 112. Lớp đòi hỏi (require) ......................................................................................... 16II. Khung thuật toán tuần tự ....................................................................................... 17III. Khung thuật toán song song ................................................................................. 19Chương III: SỬ DỤNG KHUNG THUẬT TOÁN KIẾN ĐỂ GIẢI QUYẾT BÀITOÁN MAXSAT ......................................................................................................... 22I. Giải quyết bài toán Maxsat ..................................................................................... 221. Bài toán Maxsat ................................................................................................. 22II. Kết quả thực nghiệm ............................................................................................. 243Chương I: TỔNG QUAN THUẬT TOÁN KIẾNI. Thuật toán kiến1. Đàn kiến tự nhiên (natural ant colonies)Loài kiến là loài sâu bọ có tính chất xã hội, chúng sống thành từng đàn, bởivậy có sự tác động lẫn nhau, chúng thạo tìm kiếm thức ăn và hoàn thành nhữngnhiệm vụ từ kiến chỉ huy. Một điều thú vị trong tìm kiếm thức ăn của vài con kiếnđặc biệt là khả năng của chúng để tìm kiếm đường đi ngắn nhất giữa tổ kiến vànguồn thức ăn. Trên thực tế, điều dễ nhận thấy có trong suy nghĩ nhưng nhiều conkiến hầu hết không nhận ra vì chúng không dùng thị giác để tìm kiếm những đầumối thức ăn.Trong quá trình đi giữa tổ và nguồn thức ăn, vài con kiến tích tụ một chấtđược gọi là mùi lạ (ph ...
Tìm kiếm theo từ khóa liên quan:
Báo cáo nghiên cứu khoa học Cấu trúc dữ liệu và giải thuật Thuật toán kiến song song Khung thuật toán tuần tự Khung thuật toán song song Bài toán MaxsatGợi ý tài liệu liên quan:
-
Đề cương chi tiết học phần Cấu trúc dữ liệu và giải thuật (Data structures and algorithms)
10 trang 304 0 0 -
80 trang 258 0 0
-
Đồ án nghiên cứu khoa học: Ứng dụng công nghệ cảm biến IoT vào mô hình thủy canh
30 trang 199 0 0 -
8 trang 193 0 0
-
3 trang 157 3 0
-
Giáo trình cấu trúc dữ liệu và giải thuât part 2
16 trang 156 0 0 -
Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - Trần Hạnh Nhi
123 trang 155 0 0 -
45 trang 144 0 0
-
Giải thuật và cấu trúc dữ liệu
305 trang 142 0 0 -
51 trang 139 0 0