Danh mục

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    
Hoai.2512

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 ...

Tài liệu được xem nhiều:

Gợi ý tài liệu liên quan: