Nghiên cứu giải thuật đàn kiến để giải quyết các bài toán phức tạp

- NGUYỄN SƠN TÙNG NGHIÊN CỨU GIẢI THUẬT ĐÀN KIẾN ĐỂ GIẢI QUYẾT CÁC BÀI TOÁN PHỨC TẠP Chuyên ngành Công nghệ thông tin LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS.
- Nguyễn Thanh Thuỷ Hà Nội 3-2012 Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng ii MỤC LỤC DANH MỤC CÁC KÍ HIỆU VÀ TỪ VIẾT TẮT.
- 2 1.1 Các khái niệm cơ bản về lớp bài toán NP-Khó.
- 2 1.1.1 Thuật toán và độ phức tạp của thuật toán.
- 2 1.1.2 Giới thiệu chung về lớp bài toán P, NP, NP- đầy đủ, NP- khó.
- 8 1.2.2 Cấu trúc dữ liệu biểu diễn đồ thị.
- 9 1.3 Thuật toán chính xác.
- 13 1.4 Thuật toán gần đúng.
- 14 1.5 Bài toán tối ưu tổ hợp.
- 14 2 Bài toán Người du lịch.
- 15 2.1 Giới thiệu bài toán.
- 15 2.2 Các ứng dụng của bài toán.
- 16 2.3 Các hướng giải quyết bài toán.
- 16 2.3.1 Giải thuật di truyền.
- 16 2.3.2 Giải thuật đàn kiến.
- 18 CHƯƠNG 2 TÌM HIỂU VỀ THUẬT TOÁN ĐÀN KIẾN VÀ TÍNH TOÁN SONG SONG.
- 25 1.5 Tối ưu hóa đàn kiến (Ant colony optimization.
- Giới thiệu về thuật toán.
- Nội dung thuật toán.
- Các sơ đồ thuật toán.
- 31 Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng iii 1.5.4.
- Các dạng bài toán áp dụng thuật toán ACO.
- Các vấn đề cần chú ý của thuật toán.
- 54 2.3.2 Các ưu điểm của hệ thống server cluster.
- 54 2.3.3 Các thuật ngữ trong hệ thống server cluster.
- 63 3.2 Phân tách bài toán.
- 64 3.2.1 Phân tách dữ liệu.
- 65 3.3 Song song hóa dữ liệu và mô hình truyền tin.
- 66 3.4.2 Tối thiểu hóa trao đổi dữ liệu.
- 69 3.5.3 Các đặc tính cơ bản của một chương trình MPI.
- 69 CHƯƠNG 3: GIẢI THUẬT SONG SONG ĐÀN KIẾN GIẢI BÀI TOÁN NGƯỜI DU LỊCH.
- 71 2 Giải thuật đàn kiến giải bài toán TSP.
- 85 Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng iv 1.7 Cài đặt OpenMPI.
- 96 Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng v DANH MỤC CÁC KÍ HIỆU VÀ TỪ VIẾT TẮT KÝ TỰ VIẾT TẮT Ý NGHĨA TSP Traveling Saleman Problem – bài toán người du lịch ACO Ant colony optimization – tối ưu hóa đàn kiến MPI Message Passing Interface – giao thức truyền gói tin Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng vi DANH MỤC HÌNH ẢNH VÀ BẢNG Hình 1: Mô hình phân lớp các bài toán.
- 13 Hình 5:Sơ đồ chung của giải thuật ACO.
- 89 Hình 12: Biểu đồ mối quan hệ giữa thời gian chạy và số thành phố.
- 91 Hình 13: Biểu đồ mối quan hệ giữa số process và thời gian chạy.
- 93 Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng Trang 1 LỜI MỞ ĐẦU Các bài toán tối ưu hóa tổ hợp xuất hiện ngày càng nhiều và áp dụng trong rất nhiều các lĩnh vực như kinh tế, thương mại, công nghiệp, y tế.
- Tuy nhiên các bài toán này rất khó để giải quyết trong thực tế.
- Chúng được biết đến với tên gọi là lớp bài toán NP-khó.
- Nghĩa là không có thuật toán thời gian tính đa thức để giải nó, ngoại trừ P = NP.
- Bài toán Người Du Lịch (Travelling Salesman Problem- TSP) được chứng minh thuộc loại NP-khó.
- Thường các thuật toán để giải bài toán NP-khó được chia làm hai loại: Thuật toán chính xác và thuật toán gần đúng.
- Cho tới nay đã có rất nhiều nghiên cứu và thuật toán được đưa ra để giải các bài toán NP-khó.
- Một trong những thuật toán được nghiên cứu rất nhiều gần đây và đã được áp dụng khá hiệu quả để giải bài toán NP-khó là thuật toán bầy kiến.
- Thuật toán bầy kiến có những đặc tính tìm kiếm rất mạnh mẽ và tỏ ra đặc biệt thích hợp với những bài toán có không gian tìm kiếm cực lớn.
- Với đặc điểm này, việc ứng dụng thuật toán bầy kiến để giải các bài toán NP-khó là rất phù hợp.
- Tuy nhiên thuật toán bày kiến khi ứng dụng thực tế cũng đòi hỏi thời gian tính khá dài.
- Vì vậy nhu cầu song song hóa thuật toán bầy kiến là hết sức tự nhiên.
- Trong phạm vi luận văn tốt nghiệp, em tập trung nghiên cứu về thuật toán đàn kiến,song song hóa thuật toán đàn kiến và áp dụng nó để giải một bài toán thuộc lớp bài toán NP-khó là bài toán Người Du Lịch.
- Các nội dung cơ bản thực hiện trong quá trình nghiên cứu.
- Nghiên cứu thuật toán đàn kiến và bài toán TSP  Song song hóa thuật toán đàn kiến để giải bài toán TSP Phương pháp thực hiện.
- Xây dựng hệ thống cluster để song song hóa thuật toán  Thực hiện kiểm nghiệm và đánh giá kết quả trên các bộ dữ liệu mẫu Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng Trang 2 CHƯƠNG 1 GIỚI THIỆU BÀI TOÁN 1 Các khái niệm cơ sở 1.1 Các khái niệm cơ bản về lớp bài toán NP-Khó 1.1.1 Thuật toán và độ phức tạp của thuật toán Thuật toán để giải bài toán đặt ra là một thủ tục xác định bao gồm một dãy hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của bài toán.
- Các đặc trưng của thuật toán.
- Đầu vào: Thuật toán nhận dữ liệu vào từ một tập nào đó.
- Đầu ra: Với mỗi bộ dữ liệu đầu vào, thuật toán đưa ra các dữ liệu tương ứng với lời giải của bài toán.
- Chính xác: Các bước của thuật toán được mô tả chính xác.
- Hữu hạn: Thuật toán phải đưa ra câu trả lời cho mọi dữ liệu đầu vào sau một số hữu hạn các bước.
- Đơn trị: Các kết quả trung gian của từng bước thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào và các kết quả của các bước trước.
- Tổng quát: Thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho.
- Độ phức tạp tính toán của bài toán là thời gian tính của thuật toán tốt nhất trong số tất cả các thuật toán giải bài toán kể cả các thuật toán đã biết, lẫn các thuật toán còn chưa biết.
- Có ba loại thời gian tính.
- Thời gian tính tốt nhất: Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng Trang 3 Thời gian tối thiểu cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n.
- Thời gian như vậy sẽ được gọi là thời gian tính tốt nhất của thuật toán với đầu vào kích thước n.
- Thời gian tính tồi nhất: Thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n.
- Thời gian như vậy được gọi là thời gian tính tồi nhất của thuật toán với đầu vào kích thước n.
- Thời gian tính trung bình: Thời gian trung bình cần thiết để thực hiện thuật toán trên tập hữu hạn các dữ liệu đầu vào kích thước n.
- Thời gian như vậy được gọi là thời gian tính trung bình của thuật toán với đầu vào kích thước n.
- Hiện nay có hai cách tiếp cận với việc tính toán độ phức tạp của một bài toán.
- Trong cách thứ nhất, ta tìm ra cách đánh giá cận dưới độ phức tạp của bài toán.
- Cách tiếp cận thứ hai tập trung vào việc chỉ ra mức độ khó của bài toán đang xét tương đương với độ khó của những bài toán khó hiện biết.
- Việc đánh giá được độ phức tạp của bài toán sẽ giữ vai trò định hướng trong việc thiết kế ra các thuật toán để giải bài toán đó.
- 1.1.1.1 Đánh giá cận dưới Gọi )(XTAlà thời gian tính của thuật toán A đối với đầu vào X.
- Khi đó, thời gian tính trong tình huống tồi nhất của thuật toán A đối với dữ liệu đầu vào kích thước n được định nghĩa như là )(max)( XTnTAnXA Độ phức tạp của bài toán P là thời gian tính trong tình huống tồi nhất của thuật toán nhanh nhất để giải nó: ))(max(min)(min XTnTTPAnXAAA.
- trong đó  là tập tất cả các thuật toán giải bài toán P.
- Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng Trang 4 Việc đánh giá đúng độ phức tạp của bài toán là một vấn đề rất phức tạp, có một số phương pháp được đưa ra để đánh giá cận dưới cho độ khó của bài toán như phương pháp cây quyết định, lập luận phản biện.
- Độ phức tạp tính toán về mặt thời gian của thuật toán giải các bài toán cho phép so sánh sự nhanh chậm của các giải thuật.
- Việc so sánh thời gian thực hiện của các thuật toán giải các bài toán khác nhau cũng phần nào hé mở cho ta biết về độ khó của nó.
- Để cho ngắn gọn, từ nay về sau ta sẽ gọi độ phức tạp của thuật toán thay cho độ phức tạp tính toán về mặt thời gian của thuật toán.
- Xét thời gian thi hành của một thuật toán, một điều dễ nhận thấy là thời gian này phụ thuộc vào kích thước của dữ liệu đầu vào.
- Ví dụ, thời gian sắp xếp hay tìm kiếm một số trong một dãy số phải chịu ảnh hưởng của số lượng các số trong dãy số đó.
- Nếu gọi kích thước của dữ liệu vào là n, thì thời gian thực hiện của thuật toán phải được biểu diễn như một hàm của n: )(nT .
- Ngoài ra, tốc độ thực hiện này còn phụ thuộc vào ngôn ngữ cài đặt chương trình, chương trình dịch, tốc độ xử lý của máy tính mà trên đó thuật toán được chạy và các yếu tố này sẽ gây ra sự khập khiễng khi so sánh thời gian chạy của cùng một thuật toán trên các môi trường khác nhau.
- Hơn thế nữa, thời gian chạy của thuật toán tính bằng giây bằng phút hay bằng giờ chưa thể nói hết được mức độ phức tạp về mặt tính toán mà thuật toán đó phải thực hiện.
- Vì vậy, ta sẽ không đánh giá độ phức tạp của thuật toán thông qua thời gian tuyệt đối.
- Nếu thời gian thực hiện một giải thuật là 2)( cnnT  (với c là hằng số) thì ta nói độ phức tạp tính toán của giải thuật này có cấp là n2 và ký hiệu )()(2nOnT.
- Thông thường, các hàm thể hiện độ phức tạp tính toán của giải thuật có dạng log2n, n, nlog2n, n2, n3, 2n, n!, và nn.
- Các hàm như 0n, n!, nn được gọi là hàm loại mũ còn Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng Trang 5 các hàm n2, n3, nlog2n, n, log2n được gọi là các hàm loại đa thức, ngoài ra còn có độ phức tạp tính toán hằng số O(1) dùng để đánh giá những thuật toán có thời gian chạy không phụ thuộc vào kích thước dữ liệu đầu vào và O(n) gọi là độ phức tạp tuyến tính dùng để đánh giá những thuật toán có thời gian chạy tỉ lệ tuyến tính với dữ liệu đầu vào.
- Ta nói giải thuật có thời gian thực hiện là hàm mũ khi thời gian thực hiện của nó sẽ tăng lên theo hàm mũ đối với kích cỡ dữ liệu đầu vào.
- Nói chung, những thuật toán có độ phức tạp đa thức là những thuật toán có tốc độ thi hành chấp nhận được và thường được sử dụng trong thực tế, còn những thuật toán có độ phức tạp hàm mũ thường chạy rất chậm.
- 1.1.1.2 Các quy tắc cơ bản để đánh giá độ phức tạp của thuật toán Không có quy tắc tổng quát nào cho việc xác định độ phức tạp của một giải thuật bất kỳ.
- Tuy nhiên, trong thực tế có hai quy tắc đơn giản thường được dùng để đánh giá độ phức tạp của các thuật toán.
- Quy tắc nhân: Nếu thời gian chạy của hai đoạn chương trình P1 và P2 tương ứng là T1(n)=O(f(n)) và T2(n)=O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau là T1(n)T2(n)=O(f(n)g(n.
- 1.1.2 Giới thiệu chung về lớp bài toán P, NP, NP- đầy đủ, NP- khó 1.1.2.1 Bài toán quyết định Trước khi tìm hiểu xem lớp các bài toán P, NP… là gì ta cần tìm hiểu sơ qua về khái niệm các bài toán quyết định: Bài toán quyết định là bài toán có đầu ra chỉ có thể là ‘yes’ hoặc ‘no’(đúng/sai, 0/1).
- Đối với một bài toán quyết định, có những bộ dữ liệu vào của nó cho ra câu trả lời (đầu ra) là ‘yes’, ta gọi đây là bộ dữ liệu ‘yes’, nhưng cũng có những bộ dữ liệu vào cho ra câu trả lời là ‘no’, ta gọi những bộ dữ liệu này là bộ dữ liệu ‘no’.
- Luận văn tốt nghiệp Nghiên cứu giải thuật đàn kiến giải quyết các bài toán phức tạp Nguyễn Sơn Tùng Trang 6 Tác dụng của những bài toán quyết định này thể hiện ở chỗ tuy rằng nó chỉ là một dạng đặc biệt của các bài toán trong thực tế nhưng nó cũng đủ tổng quát để biểu diễn cho nhiều lớp bài toán trong ứng dụng.
- Hơn thế nữa, nếu một bài toán quyết định tương ứng với một bài toán tối ưu hóa có thể giải được bằng thuật toán đa thức thì bài toán tối ưu hóa ban đầu cũng có thể giải được bằng một thuật toán đa thức.
- 1.1.2.2 Bằng chứng ngắn gọn dễ kiểm tra Rất nhiều các bài toán quyết định có một đặc điểm chung, đó là để xác nhận câu trả lời ‘yes’ đối với bộ dữ liệu vào ‘yes’ của chúng, ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời ‘yes’ cho bộ dữ liệu vào ‘yes’ đó.
- Ví dụ về những bài toán quyết định kiểu này rất nhiều, sau đây là một số ví dụ.
- Bài toán kiểm tra tính hợp số: “Có phải số n là hợp số

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt