Luận văn Thạc sĩ Công nghệ thông tin: Áp dụng thuật toán tối ưu hóa đàn kiến để giải quyết bài toán vị trí cơ sở

Nội dung chính của luận văn được chia thành 3 chương như sau: Chương 1/ Tìm hiểu tổng quan về các kiến thức cơ sở về độ phức tạp thuật toán, lớp các bài toán P, NP và NP-khó và các bài toán thuộc lớp bài toán vị trí cơ sở cũng như các công bố gần đây. Chương 2/ Trình bày chi tiết về thuật toán tối ưu hóa đàn kiến. Chương 3/ Trình bày về cài đặt chương trình, thử nghiệm và so sánh kết quả với một số công trình đã công bố gần đây.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Công nghệ thông tin: Áp dụng thuật toán tối ưu hóa đàn kiến để giải quyết bài toán vị trí cơ sởĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆVŨ ĐỨC QUANGÁP DỤNG THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾNĐỂ GIẢI QUYẾT BÀI TOÁN VỊ TRÍ CƠ SỞLUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TINHà Nội, năm 2016[3ĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆVŨ ĐỨC QUANGÁP DỤNG THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾNĐỂ GIẢI QUYẾT BÀI TOÁN VỊ TRÍ CƠ SỞNgành: Công nghệ thông tinChuyên ngành : Hệ thống thông tinMã số: 60480104LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TINNgười hướng dẫn khoa học: PGS. TS Hoàng Xuân HuấnHà Nội, năm 2016LỜI CAM ĐOANTôi xin cam đoan luận văn này của tự bản thân tôi tìm hiểu, nghiên cứu dưới sựhướng dẫn của PGS.TS Hoàng Xuân Huấn. Các chương trình thực nghiệm do chính bảnthân tôi lập trình, các kết quả là hoàn toàn trung thực. Các tài liệu tham khảo đượctrích dẫn và chú thích đầy đủ.TÁC GIẢ LUẬN VĂNVũ Đức QuangLỜI CẢM ƠNEm xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo trườngĐại học công nghệ - Đại học Quốc gia Hà Nội và Viện công nghệ thông tin Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã dạy dỗ chúng em trongsuốt quá trình học tập chương trình cao học tại trường.Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS HoàngXuân Huấn, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã quantâm, định hướng và đưa ra những góp ý, gợi ý, chỉnh sửa quý báu cho em trongquá trình làm luận văn tốt nghiệp.Cuối cùng, em xin chân thành cảm ơn các bạn bè đồng nghiệp, gia đìnhvà người thân đã quan tâm, giúp đỡ và chia sẻ với em trong suốt quá trình làmluận văn tốt nghiệp.Em xin chân thành cảm ơn!Hà Nội, tháng 11 năm 2016Học viênVũ Đức QuangMỤC LỤCTrangMỞ ĐẦU ................................................................................................................................... 1CHƯƠNG 1 MỘT SỐ KIẾN THỨC TỔNG QUAN VÀ BÀI TOÁN VỊ TRÍ CƠ SỞ . 31.1. Độ phức tạp tính toán của bài toán .............................................................................31.2. NP- đầy đủ .....................................................................................................................41.2.1. Bài toán quyết định ..............................................................................................41.2.2. Bằng chứng ngắn gọn để kiểm tra .....................................................................41.2.3. Lớp bài toán P, NP và co-NP .............................................................................61.2.4. Lớp bài toán NP-khó và NP-đầy đủ...................................................................71.3. Bài toán vị trí cơ sở không hạn chế khả năng ...........................................................81.4. Bài toán vị trí cơ sở có hạn chế khả năng ..................................................................91.5. Bài toán vị trí cơ sở cạnh tranh ................................................................................ 111.6. Bài toán bố trí vị trí xây dựng .................................................................................. 141.6.1. Hàm mục tiêu thứ nhất ..................................................................................... 141.6.2. Hàm mục tiêu thứ hai ....................................................................................... 171.7. Bài toán bố trí cơ sở theo hàng................................................................................. 221.8. Kết luận chương ......................................................................................................... 23CHƯƠNG 2 THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN ...............................................242.1. Từ kiến thực đến kiến nhân tạo ................................................................................ 242.1.1. Kiến thực ............................................................................................................ 242.1.2. Kiến nhân tạo ..................................................................................................... 262.2. Phương pháp ACO cho bài toán TƯTH tổng quát ................................................ 272.2.1. Đồ thị cấu trúc ................................................................................................... 272.2.2. Mô tả thuật toán ACO tổng quát. .................................................................... 292.3. Phương pháp ACO giải bài toán TSP ...................................................................... 312.3.1. Bài toán TSP và đồ thị cấu trúc ....................................................................... 312.3.2. Các thuật toán ACO cho bài toán TSP ........................................................... 322.4. Một số vấn đề khác khi áp dụng ACO .................................................................... 412.4.1. Đặc tính hội tụ ............................. ...