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

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI<br /> Khoa Công nghệ thông tin<br /> --------  --------<br /> <br /> BÁO CÁO NGHIÊN CỨU KHOA HỌC<br /> <br /> Đề tài<br /> <br /> THUẬT TOÁN KIẾN SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT<br /> <br /> Giáo viên hướng dẫn: Thầy Đỗ Trung Kiên<br /> Sinh viên thực hiện : Quách Thị Hái Oanh _K54A<br /> Nguyễn Thị Hiện_K55B<br /> Trần Thị Hằng_K55B<br /> Nguyễn Thị Hương _K55B<br /> <br /> Hà Nội, 04-2008<br /> <br /> 1<br /> <br /> LỜI MỞ ĐẦU<br /> <br /> 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<br /> khác nhau như: kinh tế, thương mại, khoa học, công nghiệp và y học. Tuy nhiên,<br /> 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à<br /> 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<br /> 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<br /> quyết chúng trong thời gian đa thức.<br /> Metaheuristics hợp nhất các khái niệm từ nhiều lĩnh vực khác nhau như di<br /> 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<br /> 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,<br /> 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<br /> toán tiến hoá. Thuật toán metaheuristics gần đây nhất là thuật toán kiến (ACO),<br /> đượ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<br /> kiến khác nhau. Tuy nhiên từ công việc ban đầu của Dorigo, Maniezzo, và Colorni<br /> trong hệ thống kiến (Ant System), ACO nhanh chóng trở thành tìm kiếm hoàn<br /> 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 để<br /> 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à<br /> đi sâu vào lý thuyết thuật toán bây giờ trở thành cái sẵn có.<br /> Ở đây, em đã tìm hiểu thuật toán kiến và sử dụng thuật toán này để giải<br /> 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ổ<br /> 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.<br /> <br /> 2<br /> <br /> MỤC LỤC<br /> <br /> Chương I: TỔNG QUAN THUẬT TOÁN KIẾN ........................................................ 4<br /> I. Thuật toán kiến......................................................................................................... 4<br /> 1. Đàn kiến tự nhiên (natural ant colonies) .............................................................. 4<br /> 2.Từ những con kiến tự nhiên tới thuật toán ACO .................................................... 6<br /> 3. Các loại mô hình ACO ......................................................................................... 7<br /> 4. Ứng dụng của ACO.............................................................................................. 7<br /> 5. Các bước để giải quyết một bài toán bởi ACO ..................................................... 9<br /> II. Một số ví dụ minh hoạ .......................................................................................... 10<br /> 1. Bài toán người du lịch ....................................................................................... 10<br /> 2. Xác định ma trận trọng số của mạng Neuron ..................................................... 10<br /> Chương II: XÂY DỰNG KHUNG THUẬT TOÁN KIẾN ....................................... 11<br /> I. Thiết kế khung thuật toán kiến................................................................................ 11<br /> * Sơ đồ chung của thuật toán kiến ......................................................................... 11<br /> 2. Lớp đòi hỏi (require) ......................................................................................... 16<br /> II. Khung thuật toán tuần tự ....................................................................................... 17<br /> III. Khung thuật toán song song ................................................................................. 19<br /> Chương III: SỬ DỤNG KHUNG THUẬT TOÁN KIẾN ĐỂ GIẢI QUYẾT BÀI<br /> TOÁN MAXSAT ......................................................................................................... 22<br /> I. Giải quyết bài toán Maxsat ..................................................................................... 22<br /> 1. Bài toán Maxsat ................................................................................................. 22<br /> II. Kết quả thực nghiệm ............................................................................................. 24<br /> <br /> 3<br /> <br /> Chương I: TỔNG QUAN THUẬT TOÁN KIẾN<br /> I. Thuật toán kiến<br /> 1. Đàn kiến tự nhiên (natural ant colonies)<br /> 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ởi<br /> vậ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ững<br /> nhiệ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<br /> đặ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à<br /> 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 con<br /> kiế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 đầu<br /> mối thức ăn.<br /> 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<br /> được gọi là mùi lạ (pheromone). Nếu không có mùi lạ sẵn có, những con kiến di<br /> chuyển ngẫu nhiên, nhưng khi có mặt của mùi lạ này chúng có xu hướng đi theo<br /> mùi lạ. Trên thực tế, cuộc thí nghiệm của nhà nghiên cứu sinh là những con kiến<br /> theo thuyết tự nhiên thích những con đường được đánh dấu bởi tập hợp nhiều mùi<br /> lạ. Trong qúa trình thực hiện, lựa chọn giữa những con đường tìm thấy khác nhau<br /> khi có vài con đường phân cách. Sau đó kiến sẽ lựa chọn xác suất một con đường<br /> qua số lượng mùi lạ: mùi lạ càng nhiều thì sự lựa chọn càng cao. Bởi vậy những<br /> con kiến đổi hướng theo mùi lạ trên đường đi, chúng được đề cập như sau: kết quả<br /> tìm kiếm thức ăn trong quá trình tăng cường ảnh hưởng từ sự hình thành của con<br /> đường được đánh dấu bởi tập hợp nhiều mùi lạ. Cách tìm thức ăn này tập trung<br /> kiến tìm đường đi ngắn nhất giữa tổ và nguồn thức ăn.<br /> Kĩ thuật thế nào tập trung được kiến tới phạm vi con đường ngắn nhất được<br /> minh hoạ ở hình 1. Ở đó, không có mùi lạ nào trong môi trường và, khi kiến đến<br /> những chỗ giao nhau, chúng ngẫu nhiên lựa chọn một ngả đường. Tuy nhiên, như<br /> kiến đi du lịch, con đường triển vọng nhất tiếp nhận số lượng mùi lạ nhiều hơn sau<br /> vài lần đi. Nhờ đó, những con đường ngắn hơn, kiến sẽ lựa chọn chúng để tới thức<br /> ăn nhanh hơn và để bắt đầu trở lại hành trình kiếm thức ăn sớm hơn. Từ khi ngả<br /> 4<br /> <br /> đường ngắn hơn được chọn mùi lạ tồn tại nhiều hơn, quyết định của kiến có xu<br /> hướng tiến về ngả đường ngắn hơn, vì thế, lựa chọn con đường nhiều mùi hơn khi<br /> kiến trở lại nhiều hơn ngả đường dài hơn. Kết quả cuối cùng của quá trình này là<br /> sự tăng xu hướng tiến tới ngả đường ngắn và kết thúc, hội tụ lại là con đường ngắn<br /> nhất.<br /> Thủ tục sau đó được bổ sung trong môi trường tự nhiên bởi thực tế mùi lạ<br /> sẽ bị bay hơi sau vài lần. Con đường này triển vọng ít dần vì mất dần mùi lạ bởi vì<br /> nó được kiến đi ngày càng ít. Tuy nhiên vài nhà sinh vật học đã nghiên cứu chỉ ra<br /> mùi lạ rất bền, vì thế ít ảnh hưởng của sự bay hơi trên đường đi ngăn nhất của quá<br /> trình tìm kiếm thức ăn.<br /> <br /> Hình 1<br /> Vài cuộc thí nghiệm được báo cáo cho thấy số đông lấy thêm trong tự nhiên<br /> với một giới hạn, như kết quả tồn tại lâu dài của mùi lạ, nó là điều khó để kiến<br /> quên đường đi với nhiều mùi lạ, mặc dù chúng tìm thấy được đường đi ngắn hơn.<br /> Chú ý, nếu thức ăn trực tiếp dịch trong máy để thiết kế một thuật toán tìm kiếm,<br /> chúng ta có thể có một thuật toán nhanh hơn trở thành tối ưu.<br /> <br /> 5<br /> <br />