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 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 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. MỤC LỤC Chương I: TỔNG QUAN THUẬT TOÁN KIẾN I. Thuật toán kiến 1. Đà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ởi 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 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 đặ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 con 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 mố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ạ (pheromone). Nếu không có mùi lạ sẵn có, những con kiến di 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 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 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 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 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 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 con kiến đổi hướng theo mùi lạ trên đường đi, chúng được đề cập như sau: kết quả 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 đườ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 kiến tìm đường đi ngắn nhất giữa tổ và nguồn thức ăn. Kĩ thuật thế nào tập trung được kiến tới phạm vi con đường ngắn nhất được minh hoạ ở hình 1. Ở đó, không có mùi lạ nào trong môi trường và, khi kiến đến những chỗ giao nhau, chúng ngẫu nhiên lựa chọn một ngả đường. Tuy nhiên, như 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 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 ă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ả đườ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 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 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à 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 nhất. Thủ tục sau đó được bổ sung trong môi trường tự nhiên bởi thực tế mùi lạ 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ì 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 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á trình tìm kiếm thức ăn. Hình 1 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 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 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. 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, chúng ta có thể có một thuật toán nhanh hơn trở thành tối ưu. 2.Từ những con kiến tự nhiên tới thuật toán ACO Thuật toán ACO lấy ý tưởng từ việc kiếm thức ăn của đàn kiến ngoài thực tế để giải quyết các bài toán tối ưu tổ hợp. Chúng dựa trên cơ sở một đàn kiến nhân tạo, chúng được tính toán tìm kiếm thức ăn nhờ mùi lạ nhân tạo. Cấu trúc cơ bản của thuật toán ACO: trong mỗi thuật toán, tất cả kiến đi xây dựng cách giải quyết bài toán bằng cách xây dựng một đồ thị. Mỗi cạnh của đồ thị miêu tả các bước kiến có thể đi được kết hợp từ hai loại thông tin hướng dẫn kiến di chuyển: Thông tin kinh nghiệm (heuristic information): giới hạn kinh nghiệm ưu tiên di chuyển từ nút r tới s…của cạnh ars. Nó được đánh dấu bởi hrs. Thông tin này không được thay đổi bởi kiến trong suốt quá trình chạy thuật toán. Thông tin mùi lạ nhân tạo (artificial pheromone trail information), nó giới hạn “nghiên cứu sự thèm muốn” của chuyển động là kiến nhân tạo và bắt chước mùi lạ thực tế của đàn kiến tự nhiên. Thông tin này bị thay đổi trong suốt quá trình thuật toán chạy phụ thuộc vào cách giải quyết được tìm thấy bởi những con kiến. Nó được đánh dấu bởi trs. Giới thiệu các bước ảnh hưởng từ những con kiến thật vào ACO. Có hai vấn đề cần chú ý: - Chúng trừu tượng hoá vài mô hình thức ăn của kiến ngoài thực tế để tìm ra đường đi tìm kiếm thức ăn ngắn nhất. - Chúng bao gồm vài đặc điểm không giống với tự nhiên nhưng lại cho phép thuật toán phát triển chứa đựng cách giải quyết tốt tới bài toán bị cản (ví dụ: sử dụng thông tin kinh nghiệm để hướng dẫn chuyển động của kiến). Cách thức hoạt động cơ bản của một thuật toán ACO như sau: m kiến nhân tạo di chuyến, đồng thời và không đồng bộ, qua các trạng thái liền kề của bài toán. Sự di chuyển này theo một tập quy tắc làm cơ sở từ những vùng thông tin có sẵn ở các thành phần (các nút). Vùng thông tin này bao gồm thông tin kinh nghiệm và thông tin mùi lạ để hướng dẫn tìm kiếm. Qua sự di chuyển trên đồ thị kiến xây dựng được cách giải quyết. Những con kiến sẽ giải phóng mùi lạ ở mỗi lần chúng đi qua một cạnh (kết nối) trong khi xây dựng cách giải quyết (cập nhật từng bước mùi lạ trực tuyến). Mỗi lần những con kiến sinh ra cách giải quyết, nó được đánh giá và nó có thể tạo luồng mùi lạ là hoạt động của chất lượng của cách giải quyết của kiến (cập nhật lại mùi lạ trực tuyến). Thông tin này sẽ hướng dẫn tìm kiếm cho những con kiến đi sau. Hơn thế nữa, cách thức sinh hoạt động của thuật toán ACO bao gồm thêm hai thủ tục, sự bay hơi mùi lạ (pheromone trail evaporation) và hoạt động lạ (daemon actions). Sự bay hơi của mùi lạ được khởi sự từ môi trường và nó được sử dụng như là một kĩ thuật để tránh tìm kiếm bị dừng lại và cho phép kiến khảo sát vùng không gian mới. Daemon actions là những hoạt động tối ưu như một bản sao tự nhiên để thực hiện những nhiệm vụ từ một mục tiêu xa tới vùng của kiến. 3. Các loại mô hình ACO - Hệ thông kiến (AS): là thuật toán ACO đầu tiên, có ba loại: AS-density, AS-quantity và AS-cycle, khác nhau ở con đường mùi lạ được cập nhật và đề xuất. - Hệ thống đàn kiến (ACS): mở rộng của AS, cải tiến cách giải quyết của thuật toán kiến trước khi cập nhật mùi lạ. - Hệ thống kiến MAX-MIN: một trong những thuật toán mở rộng tốt nhất của AS. - Rank-based Ant System: kết hợp các loại cập nhật mùi lạ từ các thuật toán trước. - Best-Worst Ant System: khai thác hệ thống của vùng tối ưu để cải tiến cách giải quyết của thuật toán kiến. 4. Ứng dụng của ACO Thuật toán ACO được ứng dụng cho một số lượng lớn bài toán tối ưu tổ hợp. Những ứng dụng hiện nay của ACO chia thành hai lớp ứng dụng: lớp bài toán tối ưu tổ hợp NP-hard cho công nghệ cũ thường ít thức ăn. Đặc tính thành công nhất của ứng dụng ACO tới những bài toán mà ở đó kiến kết hợp với vùng tìm kiếm để có cách giải quyết tốt. Lớp ứng dụng thứ hai là bài toán tìm đường đi ngắn nhất, ở đó khoảng cách bài toán giải quyết thay đổi ở thời gian thực thi bài toán. Những thay đổi này có thể ảnh hưởng không đổi của bài toán như đã có sẵn, Nếu ảnh hưởng bị lẫn lộn, đặc tính được coi như chi phí cạnh, thay đổi theo thời gian. Trong trường hợp này, thuật toán mô phỏng theo bài toán động. Lớp ứng dụng thứ hai của ACO để kết nối đường thông tin. Thay cho việc đưa chi tiết các ứng dụng khác nhau của ACO, chúng ta mô tả ngắn lịch sử phát triển của ứng dụng, tổng quan mở rộng trong ứng dụng của ACO. Bài toán tổ hợp đầu tiên được giải quyết bởi thuật toán ACO là bài toán người du lịch (TSP) bởi vì bài toán này được biết nhiều nhất của NP-hard, tìm đường đi ngắn nhất, để dễ dàng mô phỏng sự sinh hoạt của loài kiến để giải quyết nó. Từ khi ứng dụng đầu tiên của AS trong luận án của Dorigo’sPhD năm 1991, nó trở thành một đánh giá chung của vài đóng góp tốt hơn trong mô hình thực thi ACO hơn AS. Theo trình tự, hai ứng dụng tiếp theo bài toán nhiệm vụ của phương trình bậc hai (QAP) và bài toán lập lịch cho cửa hàng năm 1994. Giữa các ứng dụng tiếp theo là đường thông tin ứng dụng đầu tiên, bắt đầu năm 1996 với công việc của Schoonderwoerd và công việc AntNet bởi Di Caro và Dorigo. Năm 1997, sau một năm công bố của nhà báo đầu tiên cho ACO năm 1996, số ứng dụng ACO bắt đầu tăng nhanh. Ứng dụng sớm nhất từ 1997 bao gồm bao toán đường xe cũ (vehicle routing), trình tự chuỗi, lập lịch trình cho cửa hàng và bài toán đồ hoạ. Sau đó, nhiều tác giả khác nhau đã sử dụng ACO metaheuristics để giải quyết số lượng lớn bài toán tối ưu tổ hợp như chuỗi chung ngắn nhất, tổng quát nhiệm vụ, tập che phủ, nhiều túi và bài toán hợp lý…Thú vị nhất của người đọc là thấy được tổng kết ứng dụng có sẵn năm 2000. Từ phần ứng dụng trước đó, ACO gần như được sử dụng cho mục đích kĩ thuật, cụ thể để thiết kế nghiên cứu thuật toán cho đọc giả biểu diễn cấu trúc như tập quy tắc lôgic classical, quy tắc logic fuzzy và thông tin Bayesian, đưa ra những kết quả hứa hẹn. Ngày nay, ACO gần kết quả trạng thái cho vài bài toán để nó áp dụng cho: QAP, trình tự chuỗi, đường đi, lập lịch và thông tin gói điều khiển…Kết quả tính toán sẵn có cho bài toán khác thường rất tốt và đóng tất cả trạng thái lại là điều đáng chú ý, bởi vì nhiều bài toán sẵn sàng bị tấn công mạnh mẽ bởi nỗ lực tìm kiếm. Bên cạnh đó, ACO metaheuristics được áp dụng để giải quyết bài toán mới của thế giới với kết quả đầy hứa hẹn. 5. Các bước để giải quyết một bài toán bởi ACO Từ những ứng dụng đã biết hiện nay, chúng ta có thể có vài hướng dẫn để giải quyết bài toán bằng ACO. Các hướng dẫn được tổng kết lại thành sáu nhiệm vụ sau: 1. Thể hiện bài toán trong khung của tập các thành phần và sự chuyển đổi hoặc bởi một đồ thị được đánh dấu bởi kiến đề xây dựng cách giải quyết. 2. Định nghĩa thích hợp cho mùi lạ trs là một xu hướng quyết định. Đó là một bước chủ yếu trong việc hình thanhg thuật toán ACO và xác định rõ mùi lạ không là một nhiệm vụ tầm thường và nó tính toán yêu cầu bên trong của bài toán sau đáp án. 3. Định nghĩa thích hợp kinh nghiệm cho mỗi quyết định để một con kiến có thể xây dựng cách giải quyết, ví dụ: định nghĩa thông tin kinh nghiệm hrs kết hợp mỗi thành phần hoặc trạng thái chuyển đổi. Thông tin kinh nghiệm chủ yếu cho việc tìm kiếm tốt nếu thuật toán tìm kiếm vùng không có sẵn hoặc không thể ứng dụng. 4. Nếu thực hiện được, tạo ra một vùng thuật toán tìm kiếm hiệu quả cho bài toán sau đáp án bởi vì kết quả của nhiều ứng dụng ACO cho bài toán tổ hợp tối ưu NP-hard thể hiện qua sự tìm kiếm tốt nhất đạt được khi ACO có vùng lạc quan. 5. Lựa chọn một thuật toán ACO và ứng dụng nó vào những bài toán cần giải quyết. 6. Các tham số phù hợp của thuật toán ACO. Một điểm bắt đầu tốt cho tham số phù hợp là sử dụng cài đặt tham số để tìm kiếm tốt khi ứng dụng thuật toán ACO vào bài toán đơn giản hoặc các bài toán khác nhau. Một vấn đề khác chi phối thời gian trong nhiệm phù hợp là để sử dụng thủ tục động cho tham số phù hợp. Nó nên xoá các bước tiếp có thể chỉ đưa ra một hướng dẫn sử dụng thuật toán ACO. Thêm nữa, việc sử dụng là sự kết hợp các quá trình ở đó với vài bài toán sâu hơn và hoạt động của thuật toán, vài lựa chọn ban đầu cần phải sửa lại. Cuối cùng, chúng ta muốn trên thực tế, điều quan trọng nhất của các bước là đầu tiên phải khớp bởi vì lựa chọn tồi ở trạng thái này tính không thể tính với một tham số gốc phù hợp tốt. II. Một số ví dụ minh hoạ 1. Bài toán người du lịch 1.1 Phát biểu bài toán Một người du lịch đi thăm n thành phố T1…Tn. Xuất phát từ thành phố nào đó, người du lịch muốn đi thăm tất cả các thnàh phố còn lại, mỗi thành phố đi đúng một lần rồi trở lại thành phố xuất phát. Gọi Cij là chi phí từ Ti đến Tj. Tìm hành trình với tổng chi phí nhỏ nhất. 1.2 Tư tưởng giải quyết bài toán người du lịch bằng thuật toán kiến - Kiến đi sau sử dụng vết mùi lạ (lớp Trail) và kinh nghiệm (lớp Heuristics) của kiến đi trước để tìm kiếm con đường đi cho mình, sau đó con đường tốt hơn sẽ được cập nhật lại. - Cứ như vậy sẽ cho ta kết quả con đường đi ngắn nhất cần tìm. 2. Xác định ma trận trọng số của mạng Neuron 1.1 Phát biểu bài toán − Giả sử có D trọng số cần phải huấn luyện. − Ký hiệu WPi là tập các giá trị có thể của tham số Pi (1 ≤ i ≤ D). − Cho một số lượng M agents lần lượt duyệt qua D tập WPi theo thứ tự mỗi lần chọn một giá trị thuộc WPi theo quy tắc lựa chọn cho trước. 1.2 Tư tưởng giải quyết bài toán người du lịch bằng thuật toán kiến − Khi mọi Agents đã duyệt xong, chúng sẽ trở về vị trí ban đầu theo đường đã đi và cho bay hơi một lượng Pheromone nhất định. Sau đó các trọng số tương ứng với sai số nhỏ nhất tìm được sẽ được tăng một Pheromone theo nguyên tắc của thủ tục PHEROMONE-UPDATE. − Quá trình tìm kiếm sẽ kết thúc khi điều kiện chấm dứt tìm kiếm được thoả mãn (Sai số của mạng nhỏ hơn một giá trị nào đó cho trước hoặc thuật toán đạt số vòng lặp nhất định.) Chương II: XÂY DỰNG KHUNG THUẬT TOÁN KIẾN * Lý do: Chúng ta phải đi xây dựng khung thuật toán vì: Hỗ trợ thiết kế tối đa và khả năng tái sử dụng code: Khung phải cung cấp cho người dùng toàn bộ kiến trúc của phương pháp giải quyết bài toán của họ. Hơn nữa các lập trình viên có thể tái sự dụng các đoạn code đã có. Do đó người dùng chỉ cần phát triển một đoạn code nhất định cho vấn đề đó. Tiện ích và khả năng mở rộng: Khung phải cho phép người dùng đi qua một số lượng lớn các giải thuật đã được giả quyết, các vấn đề, các mô hình song song đã được đưa ra. Nó có khả năng cho phép người dùng dễ dàng thêm hoặc thay đổi các đặc tính/ giải thuật mà ko cần liên quan đến các thành phần khác. Giúp cho người sau thử nghiệm bai toán trên môi trường song song. Tính linh động: Khung hỗ trợ nhiều kiến trúc phần cứng và phần mềm khác nhau nên đáp ứng được một số lượng lớn người dùng. I. Thiết kế khung thuật toán kiến * Sơ đồ chung của thuật toán kiến Chương trình khung thuật toán: 1 t = 0  2 initialize pheromone trail, PT(t) 3 initialize heuristic information, H 4 while not end do  5    t = t + 1  6    generate solutions S(t) using PT(t-1) and H 7    update PT(t) using S(t) and PT(t-1) Khi cài đặt sơ đồ ACO yêu cầu gồm ba lớp chính sau: Problem Solution Heuristic Lớp Problem tương ứng với định nghĩa một bài toán. Người viết khung phải cung cấp một định nghĩa hoàn chỉnh cho lớp này. Lớp Solution tương ứng với lời giải (tốt hoặc không tốt) một bài toán. Người viết khung phải cung cấp một định nghĩa hoàn chỉnh cho lớp này. Lớp Heuristic tương ứng các thông tin yêu cầu của bài toán. Thông tin này được lấy từ việc giải quyết các bước tiếp theo của thuật toán từ những hoạt động của con kiến. Người viết khung phải cung cấp một định nghĩa hoàn chỉnh cho lớp này. Ngoài ra, người sử dụng phải có tham số thuật toán trong file cấu hình gồm: Số phần tử thực hiện độc lập. Số phần tử phát sinh. Số lượng kiến. Thông tin vết mùi lạ (trail) gồm: kích thước(trail dimension), giá trị nhỏ nhất và lớn nhất (minimum and maximum trail values),cập nhật từng phần (local update), kích thước lựa chọn (selection size), mùi lạ ban đầu (initial trial pheromone) và q0. Alpha (mùi lạ quan trọng), beta (thông tin kinh nghiệm quan trọng). Inter operators parameters: số lượng (operator number), tỉ lệ(operator rate), số lượng cá thể và lựa chọn cá thể để gửi và thay thế (number of individuals and selection of individual to send and replace). Parallel Configuracion: khoảng thời gian phát sinh trạng thái mới (interval of generation to refresh global state), phương thức chạy (đồng bộ và không đồng bộ) (running mode(synchronized or asyncronized) và khoảng thời gian phát sinh kiểm tra lời giải từ những phần tử khác) interval of generations to check solutions from other populations. * Xây dựng cài đặt cho sơ đồ thuật toán Hệ thống gồm hai nhóm: một nhóm các lớp cung cấp (Provided) bao hàm các thủ tục chung cho thuật toán kiến (ví dụ như khung của thuật toán kiến tuần tự, khung của thuật toán kiến song song ...) và nhóm các lớp đòi hỏi (Required) bao hàm các thủ tục riêng trong thuật toán kiến của từng bài toán cụ. Dưới đây là mô hình UML tổng quan của hệ thống. 1. Lớp cung cấp (provides) - Lớp Trail (const Problem& pbm,const SetUpParams& setup): cập nhật các thông tin về vết mùi lạ. - Lớp Trail1D (const Problem& pbm,const unsigned long size,const SetUpParams& setup). Các hàm chính: clear_delta (): gán cho _delta=0.0. (Giải phóng mùi lạ sau mỗi lần kiến đi qua một cạnh). get_trail (unsigned long index): trả về giá trị của biến _trail. local_update (Solution* _sol): cập nhật từng bước mùi lạ. global_update (const Rarray *_sols): cập nhật mùi lạ update_delta (Solution* _sol) : cập nhật mùi lạ - Lớp Trail2D (const Problem& pbm,const unsigned long size,const SetUpParams& setup). Gồm 5 hàm như trong Trail1D nhưng các biến được lưu vào mảng 2 chiều vì nó cập nhật mùi lạ của mỗi con kiến ở từng con đường. - Lớp Feasibles (const unsigned long size,const SetUpParams& setup) Select_best (Trail &trail,Heuristic &heuristic,const unsigned long last_selection): với các biến thông tin mùi lạ, thông tin kinh nghiệm, sự lựa chọn sau cùng (lựa chọn tốt nhất). Sau khi tính tổng xác suất kiến đi theo một con đường, hàm trả về số lượng kiến lớn nhất đi theo một đường. Select (Trail &trail, Heuristic &heuristic,const unsigned long last_selection): tính xác suất một cách ngẫu nhiên. Hàm trả ra số lượng kiến đi theo một đường. - Lớp Colony (const Problem& pbm,const SetUpParams& setup): trả ra sự lựa chọn tốt nhất phù hợp với bài toán. - ostream& operator<< (ostream& os, const Colony& colony): đưa ra các giải pháp. - istream& operator>> (istream& is, Colony& colony): hiển thị các thông tin trên. - operator= (const Colony& colony): khởi tạo các biến: _heuristic (thông tin kinh nghiệm), _best_solution (giải pháp tốt nhất), _best_cost (chi phí tốt nhất), _worst_cost (chi phí tồi nhất).Có một vòng lặp duyệt qua tất cả các giải pháp, tìm giá trị phù hợp đối với cách giải quyết đó. - advance(): cập nhật lại thông tin mùi lạ cho hàm global_update (_sols). - generate_solution(Solution* sol): với vết mùi lạ, kinh nghiệm sẽ tìm ra được cách giải cuối cùng. - solution(const unsigned int index) const: trả về giải pháp hiện thời. - trail() const: trả về thông tin vết mùi lạ hiện tại. - fitness(const unsigned int index) const: trả về giá trị phù hợp. - Lớp Statistics ostream& operator<< (ostream& os, const Statistics& stats): hiển thị ra xâu “STATISTICS OF CURRENT TRIAL” với các thông tin Trail, Generation, Curent best cost, Global best cost. update(const Solver& solver): cập nhật cách giải quyết mới với thông tin mùi lạ, các bước hiện thời, chi phí tốt nhất, chi phí chung. - Lớp SetUpParams - istream& operator>> (istream& is, SetUpParams& setup): sscanf (buffer," %s ",command): Nhập vào một chuỗi lưu vào biến command. Sau đó so sánh chuỗi đó như sau: nếu chuỗi đó bằng “General" thì gán nb_section=0; "Heuristic" thì gán nb_section=1; "Inter-Operators" thì gán nb_section=2; "LAN-configuration" thì gán nb_section=3; Tùy vào các giá trị đoạn nb_section khác nhau mà ta lựa chọn thực hiện các công việc khác nhau: thiết lập các thông tin về vết mùi lạ lớn nhất, nhỏ nhất, thông tin kinh nghiệm lớn nhất, nhỏ nhất, cập nhật lại,… - ostream& operator<< (ostream& os, const SetUpParams& setup): đưa ra các thông tin về cấu hình bao gồm: Independent runs, Evolution steps, Size of Colony, Dimention of trail, Display State, Inter_Operators. Hiển thị các dòng chữ: "LAN configuration:”; "Refresh global state in number of generations: "; "Running in synchronous mode"; "Running in asynchronous mode"; "Interval for checking asynchronous receptions: ". - Lớp Inter_Operator - Inter_Operator, trong lớp này có 3 hàm : direction(dir), hàm này dùng để quản lí, điều khiển hướng đi của kiến. migration_rate(1), hàm này mô tả trạng thái di chuyển của kiến. migration_size(1), hàm này mô tả kích thước đường đi khi kiến di chuyển. - Setup(char line[MAX_BUFFER]). Hàm này lưu trữ thông tin đường đi của kiến. Nó gồm 3 biến: + op kiểu nguyên + new_migration_rate: mô tả trạng thái di chuyển mới của kiến, khởi tạo ban đầu bằng 1. + new_migration_size: mô tả kích thước đường đi tại thời điểm mới nhất của kiến, khởi tạo ban đầu bằng 1. Nếu new_migration_rate và new_migration_size xác nhận lớn hơn 0 thì: kiến chuyển sang trạng thái mới này và gán kích thước bằng kích thước tại trạng thái mới. - RefreshState: Hàm này nạp thêm trạng thái - UpdateFromStateCập nhật trạng thái, mỗi khi cập nhật một trạng thái mới sẽ lưu trên một danh sách và độ dài của nó. - Lớp Migration: trả ra giá trị ước lượng và kích thước của trạng thái kiến đi. - Lớp Solver: Thực hiện các chiến lược đưa ra và duy trì các thông tin có liên quan tới trạng thái tìm kiếm trong suốt quá trình thực hiện - Lớp Solver_Seq: Chứa thủ tục run() để giải quyết bài toán một cách tuần tự. - Lớp Solver_Lan: Chứa thủ tục run(int argc, char** argv) để giải quyết bài toán một cách song song trên môi trường mạng LAN. Với tham số truyền vào của hàm chính là các tên máy tham gia vào quá trình tính toán.. Người sử dụng muốn thực hiện theo phương thức nào (song song hay tuần tự) thì tạo ra một đối tượng tương ứng sau đó gọi tới thủ tục run . 2. Lớp đòi hỏi (require) - Lớp Problem: đưa ra thông số bài toán, kiểm tra tính đúng, sai của bài toán. - operator<< Đọc vào các thông số của bài toán - operator>> Hiển thị các thông số của bài toán - operator= (const Problem& pbm): Tạo ra mảng lưu một chiềucác mệnh đề –clauses gồm phần tử, sau đó tạo ra mảng 2 chiều kích cỡ [số mệnh đề, độ dài mệnh đề]. Lưu các phần tử mệnh đề vào trong đó.Tạo ra biến _dimension gán cho bằng giá trị dimension trong dimension của lớp pro. Làm sạch mảng Clause. Truyền giá trị số mệnh đề trong pbm.numclause() của lớp Pro vào _numclause trong mảng clauses. - Lớp Solution. - operator== (const Solution& sol) const: Lời giải bài toán xác định giá trị của bài toán là đúng hay sai. Và trả ra giá trị cho mệnh đề đúng. - fitness (): lời giải phù hợp của bài toán. - size() const: lấy kích thước chuỗi. - add(unsigned long element): phương thức thêm vào một lời giải phù hợp. - initialize_feasibles(Feasibles &_feasibles): khởi tạo giá trị ban đầu cho lời giải khả thi. Nếu (_freedomV[i] >0) thì thêm giá trị đó vào danh sách lời giải khả thi. - update(Feasibles &f,unsigned long &selection): cập nhật lời giải khả thi vào trong danh sách lời giải khả thi. - Lớp Heuristics: cập nhật kinh nghiệm để giải quyết bài toán. - update(): tìm kiếm ra cách giải quyết cuối cùng, cập nhật kinh nghiệm của quá trình tìm kiếm đó. - Lớp UserStatistics: đưa ra kết quả cuối cùng. II. Khung thuật toán tuần tự * Lớp Solver_Seq : giải quyết bài toán trên tuần tự - StartUp: Khởi tạo bài toán với đàn kiến hiện tại và các thông số như: giải pháp tốt nhất, chi phí tốt nhất, chi phí tồi nhất. Sau đó cập nhật trạng thái và hiển thị trạng thái đó - DoStep() : Chỉ ra các bước thực hiện Ban đầu ở bước hiện tại gọi đến hàm advance(). Sau đó thiết lập các tham số của đàn kiến: Chi phí tốt nhất = chi phí tốt nhất của đàn kiến hiện tại Giải pháp tốt nhất = giải pháp tốt nhất của đàn kiến hiện tại Chi phí tồi nhất = chi phí tồi nhất của đàn kiến hiện tại Tổng thời gian = thời gian bắt đầu + thời gian tìm kiếm mùi lạ Nếu (số bước ở trạng thái hiện tại ) chia cho (số bước ở trạng thái chung) có số dư = 0 thì cập nhật trạng thái và có thể hiển thị chúng nếu muốn . void Solver_Seq::DoStep() { current_step(current_step()+1); current_colony.advance(); best_cost=current_colony.best_cost(); best_solution=current_colony.best_solution(); worst_cost=current_colony.worst_cost(); time_spent_in_trial = _used_time(start_trial); total_time_spent = start_global + time_spent_in_trial; RefreshState(); RefreshCfgState(); if( (current_step() % params.refresh_global_state()) == 0) UpdateFromCfgState(); _stat.update(*this); _userstat.update(*this); if (display_state()) show_state(); } - Hàm run(): thực hiện các bước chạy trong bài toán. void Solver_Seq::run (const Colony& col,const unsigned long int nb_steps) { StartUp(col); while ((current_step() < nb_steps) && !(terminateQ(problem,*this,params))) DoStep(); } *Sử dụng khung thuật toán kiến trong đó file chương trình chính gọi đến các hàm lớp Solver_Seq. Main_Seq { Khai báo: SetupParams cfg; Problem pbm; Mở file f1 là “ACO.cfg” để đọc vào cấu hình Đọc file f1>>cfg; Mở file f2 để đọc “Problem.dat” Đọc file f2>>pbm; Khai báo: Solver_Seq solver (pbm,cfg); Gọi hàm solver.run(); Nếu (solver.pid()==0) thì hiển thị trạng thái. In ra lời giải tốt nhất toàn cục và giá trị hàm sức khỏe. } III. Khung thuật toán song song * Chúng ta cũng biết có hai mô hình phần cứng là: mô hình bộ nhớ phân tán và mô hình dùng chung. Mô hình bộ nhớ phân tán: - Ưu: dễ cái đặt - Nhược: tốc độ chậm Mô hình bộ nhớ dùng chung - Ưu: tốc độ nhanh - Nhược: giá thành đắt Vì lí do trên mà chúng ta lựa chọn mô hình bộ nhớ phân tán Để các máy tính dễ truyền tin với nhau chúng ta sử dụng thư viện MPI, nhưng các hàm trong MPI rất khó để người sử dụng hiểu và sử dụng, vì vậy chúng ta sử dụng thêm thư viện Netstream để: - Tạo giao diện thân thiện với người sử dụng. - Truy cập tới Lan tốt như truy cập tới Wan. - Giao diện người sử dụng hướng đối tượng *Có 3 mô hình phần mềm là: 1. Mô hình máy chủ-khách (Master-slave): có một bộ xử lý duy trì được lựa chọn, các bộ xử lý khác chỉ thay đổi và ước lượng. Thuật toán chỉ tốt với vài bộ xử lý với thời gian ước lượng, sự truyền đạt thông tin ảnh hưởng tới lợi ích của xử lý song song. 2. Mô hình đảo (Island model): tất cả các bộ xử lý chạy không phụ thuộc vào nhau, có sự trao đổi khi có kết quả tốt, mô hình này phù hợp với một nhóm máy tính nhưng truyền đạt thông tin bị giới hạn. 3. Mô hình khuếch tán (Diffusion): phù hợp với một hệ thống máy tính song song lớn với mạng nội bộ, kết nối thông tin nhanh Mô hình đảo được chọn vì nó phù hợp với thuật toán kiến nhất. * Lớp Solver_Lan: giải quyết bài toán trên môi trường song song - pid() const : Trả về số hiệu của mỗi máy từ đó có thể xác định được máy khách , máy chủ. - send_local_state_to: Gửi thông tin của trạng thái cục bộ về máy chủ - receive_local_state(): Nhận thông tin của trạng thái cục bộ từ máy khách - check_for_refresh_global_state(): Kiểm tra các thông số của trạng thái toàn cục .Hàm này chỉ thực hiện ở máy chủ. * Sử dụng khung thuật toán kiến trong đó file chương trình chính gọi đến lớp Solver_Lan Main_Lan { Sử dụng khung ACO Khai báo: SetupParams cfg; Problem pbm; Mở file f1 là “ACO.cfg” để đọc vào cấu hình Đọc file f1>>cfg; Mở file f2 để đọc “Problem.dat” Đọc file f2>>pbm; Khai báo: Solver_Seq solver (pbm,cfg, argc,argv); Gọi hàm solver.run(); Nếu (solver.pid()==0) thì hiển thị trạng thái. In ra lời giải tốt nhất toàn cục và giá trị hàm sức khỏe. } Khi chạy hàm run(): void Solver_Lan::run (const Colony& col,const unsigned long int nb_steps) { StartUp(col); if (mypid!=0) { while ((current_step() < nb_steps) && !(terminateQ(problem,*this,params))) DoStep(); send_local_state_to(-1); } else { check_for_refresh_global_state(); } - Máy chủ thực hiện nhận các yêu cầu bài toán sau đó giao nhiệm vụ tới các máy khách và thực hiện hàm check_for_refresh_global_state(); - Máy khách thực hiện nhận nhiệm vụ từ máy chủ rồi từng máy khách thực hiện tính toán như chạy tuần tự thực hiện trong hàm DoStep() Chương III: SỬ DỤNG KHUNG THUẬT TOÁN KIẾN ĐỂ GIẢI QUYẾT BÀI TOÁN MAXSAT I. Giải quyết bài toán Maxsat 1. Bài toán Maxsat Có n biến và m mệnh đề. Tìm cách phân bố trên các biến sao cho số mệnh đề true là lớn nhất. 2. Thuật toán kiến giải quyết bài toán Maxsat *Bài toán Maxsat có file cấu hình như sau: 3 // số lần chạy độc lập 128 // số được tạo ra 8 // số cá thể 1 1 2 0.005 0.8 0.5 1 0// kích thước, giá trị nhỏ nhất, giá trị lớn nhất, cập nhật, lựa chọn kích thước, vết mùi lạ ban đầu, vết mùi lạ tiếp... 1 5 // alpha, beta 1 // trạng thái hiển thị Inter-Operators // toán tử để ứng dụng giữa mẫu và những cái khác. 0 25 1 1 3 1 5 // số toán tử, ước lượng toán tử, số cá thể, lựa chọn cá thể để gửi LAN-configuration 10 // refresh trạng thái 1 // 0: chạy không đồng bộ / 1: chạy đồng bộ 1 //thời gian phát sinh để kiểm tra lời giải từ các mẫu khác * Đầu vào của bài toán là n biến và m mệnh đề được thể hiện trong một file là Sat.dat với định dạng: // số lượng biến, số lượng mệnh đề, chiều dài mỗi mệnh đề // mệnh đề 1 (kết thúc là 0), nếu vị từ < 0 thì vị từ là phủ định. ………. // mệnh đề N (kết thúc là 0), nếu vị từ < 0 thì vị từ là phủ định Ta hiểu chương trình như một con người, khung thuật toán chính là bộ khung xương. Để giải quyết bài toán Maxsat như đã nói ở trên, chúng ta sử dụng khung thuật toán kiến để giải quyết bài toán này, khung sẽ được đắp thêm (chủ yếu thay đổi trong file .req của khung), cài đặt chúng ta sẽ thu được chương trình giải quyết bài toán Maxsat. Cụ thể như sau: Trong lớp Problem: - operator<< Đọc các giá trị kích thứớc, số mệnh đề, và chiều dài mệnh để, sau đó hiện ra giá trị phần tử thứ (số mệnh đề, chiều dài mệnh đề). - operator>> Hiển thị vào giá trị kích thước, số mệnh đề, và chiều dài mệnh để, sau đó hiện ra giá trị phần tử thứ (số mệnh đề, chiều dài mệnh đề). - operator= (const Problem& pbm): Tạo ra mảng lưu một chiều các mệnh đề –clauses gồm phần tử, sau đó tạo ra mảng 2 chiều kích cỡ [số mệnh đề, độ dài mệnh đề]. Lưu các phần tử mệnh đề vào trong đó.Tạo ra biến _dimension gán cho bằng giá trị dimension trong dimension của lớp pro. Làm sạch mảng Clause. Truyền giá trị số mệnh đề trong pbm.numclause() của lớp Pro vào _numclause trong mảng clauses. Trong lớp Solution: - operator= (const Solution &sol) :Gán các giá trị trong các phương thức của lớp solution cho các biến. - operator== (const Solution& sol) const: Lời giải bài toán xác định giá trị của mệnh đề là đúng hay sai. Và trả ra giá trị cho mệnh đề đúng. - fitness (): lời giải phù hợp của bài toán. - add(unsigned long element): phương thức thêm vào một lời giải phù hợp. - initialize_feasibles: khởi tạo giá trị ban đầu cho lời giải khả thi. Nếu (_freedomV[i] > 0) thì thêm giá trị đó vào danh sách lời giải khả thi. - update(Feasibles &f,unsigned long &selection): cập nhật lời giải khả thi vào trong danh sách lời giải khả thi. Trong lớp Heuristics:cập nhật kinh nghiệm để giải quyết bài toán. - update(): tìm kiếm ra cách giải quyết cuối cùng, cập nhật kinh nghiệm của quá trình tìm kiếm đó. Lớp UserStatistics: đưa ra kết quả cuối cùng thông tin vết mùi lạ. II. Kết quả thực nghiệm (Chương trình đã chạy nhưng do tính chất của chương trình là xử lý song song cần sử dụng nhiều máy nên đến 18/04/2008 em mới mượn được phòng máy của khoa để thực hiện thực nghiệm) *Hướng phát triển Sử dụng khung thuật toán kiến để cài đặt giải quyết một bài toán khác. TÀI LIỆU THAM KHẢO 1. Oscar Cordón, Francisco Herrera, Thomas Stutzle A Review on the Ant Colony Optimization Metaheuristic: Basic, Models and New Trends, 2002. 2. Marco Dorigo, Thomas Stutzle The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances 3. Enrique Alba NetStream: a Flexible and Simple OOP Message Passing Service for LAN/WAN Utilization, 9/2001 4. Helmut Pekari and Robert Clarisó Mallba: instantiating SAT and MAXCUT … Và nhiều trang web…