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

- 1TÓM TẮT LUẬN VĂN THẠC SĨ Đề tài: 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 Tác giả luận văn: Nguyễn Sơn Tùng.
- Lý do lựa chọn đề tài: 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 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 Đàn Kiến, thuật toá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 để giải các bài toán NP-khó là rất phù hợp.
- Tuy nhiên thuật toán Đàn 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 Đàn Kiến là hết sức tự nhiên.
- Mục đích, phạm vi nghiên cứu 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 và bài toán TSP, sau đó tiến hành song song hóa thuật toán Đàn Kiến và áp dụng nó để giải bài toán TSP.
- 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 Luận văn được trình bày bao gồm 04 chương: Chương 1.
- Giới thiệu bài toán.
- Phần này của tài liệu sẽ giới thiệu về bài toán TSP, trình bầy các khái niệm cơ bản về giải thuật và các ứng dụng của bài toán TSP.
- Tìm hiểu về thuật toán Đàn Kiến và tính toán song song.
- Tìm hiểu về lớp thuật toán Metaheuristics qua đó tìm hiểu sâu về thuật toán Đàn Kiến, tìm hiểu về tính toán song song.
- Song song hóa giải thuật Đàn Kiến giải bài toán TSP.
- Áp dụng thuật toán Đàn Kiến giải bài toán TSP, song song hóa thuật toán.
- Các kết quả nhận được khi thực hiện chạy chương trình demo giải thuật trên các bộ dữ liệu mẫu, đánh giá kết quả cũng như hướng phát triển của giải thuật.
- Song song hóa thuật toán Đàn Kiến.
- Kết luận: Sau khi hoàn thành luận văn, ta đã đạt được những kết quả nhất định về lý thuyết và thực nghiệm, chúng ta đã tìm hiểu về bài toán Người Du Lịch và các ứng dụng của bài toán trong thực tế, nghiên cứu sâu hơn về tính toán song song và giải thuật song song Đàn Kiến để giải bài toán Người Du Lịch, trong đó nghiên cứu.
- Mô hình cluster  Cách xây dựng một cluster trong thực tế  Các mô hình của giải thuật ACO  Các thông số ảnh hưởng đến giải thuật Về mặt lý thuyết giải thuật song song Đàn Kiến có hiệu năng cao, song trên thực nghiệm vì không có điều kiện test trên máy thật và hệ thống cluster ảo được tạo từ các máy tính không đồng bộ về mặt cấu hình lên dẫn đến kết quả thực nghiệm không được tối ưu.
- Ngoài ra, trong giải thuật ACO có rất nhiều thông số ảnh hưởng đến kết quả giải thuật, vì vậy để chọn được một bộ thông số tốt nhất cho giải thuật đòi hỏi phải có thời gian thực nghiệm và phân tích giải thuật thật kĩ.
- Về hướng phát triển của giải thuật, ta cần cài chương trình trên hệ thống cluster thật có cấu hình mạnh, như thế giải thuật sẽ có hiệu năng cao hơn, về mặt mô hình trong phạm vi luận văn này chỉ cài đặt mô hình Ants System để chạy song song, ta cần cài đặt các mô hình khác của giải thuật ACO để có thể so sánh và đánh giá kết quả

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