Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp tối ưu đàn kiến cho bài toán điều phối xe

Mục tiêu nghiên cứu của đề tài là tìm lời giải tốt nhất trong các lời giải có thể và không gian tìm kiếm lời giải của bài toán là rời rạc. Nhiều bài toán tối ưu tổ hợp có độ phức tạp tính toán cao và được phân loại thuộc lớp NP khó. Việc tìm ra lời giải tối ưu cho các bài toán này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ ) trong giới hạn thời gian cho phép. Bài toán người du lịch (TSP) là một bài toán cổ điển thuộc lớp NP được nghiên cứu sâu trong lĩnh vực tối ưu tổ hợp.
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: Phương pháp tối ưu đàn kiến cho bài toán điều phối xe ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LÊ MỸ HẠNH PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN CHO BÀI TOÁN ĐIỀU PHỐI XE LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội-2014 2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LÊ MỸ HẠNH PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN CHO BÀI TOÁN ĐIỀU PHỐI XE Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60480103 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS.HOÀNG XUÂN HUẤN TS.ĐỖ ĐỨC ĐÔNG Hà Nội-2014 3 Lời cam đoan Với mục đích học tập, nghiên cứu để nâng cao kiến thức và trình độ chuyên môn nên tôi đã làm luận văn này. Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của cá nhân tôi, thực hiện dưới sự hướng dẫn của PGS. TS Hoàng Xuân Huấn và TS Đỗ Đức Đông. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn đúng quy định. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà nội, ngày ….. tháng ….. năm 2014 Học viên Lê Mỹ Hạnh 4 LỜI CẢM ƠN Với những dòng chữ đầu tiên này, tôi xin dành để gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy giáo, PGS. TS. Hoàng Xuân Huấn, Thầy giáo TS. Đỗ Đức Đông- hai người thầy đã tận tình hướng dẫn, chỉ bảo và tạo cho tôi những điều kiện tốt nhất từ khi bắt đầu cho tới khi hoàn thành công việc của mình. Đồng thời, tôi xin gửi lời cảm ơn tới các thầy cô giáo khoa Công nghệ thông tin - trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo cho tôi một môi trường học tập thuận lợi, cung cấp nhiều kiến thức bổ ích để tôi có thể thực hiện công việc của mình. Tôi xin cảm ơn các nhà khoa học, các tác giả của các bài báo, báo cáo kỹ thuật và báo cáo hội thảo đã ghi ở phần tài liệu tham khảo, nhờ những tài liệu hữu ích này mà tôi có thêm sự phong phú và đa dạng trong khóa luận của mình. Cuối cùng, xin cảm ơn tất cả những người thân yêu trong gia đình tôi và bạn bè, những người đã luôn động viên và giúp đỡ tôi mỗi khi tôi gặp khó khăn trong quá trình làm luận văn. 5 MỤC LỤC MỤC LỤC ............................................................................................................ 5 DANH SÁCH CÁC HÌNH.................................................................................. 6 BẢNG TỪ VIẾT TẮT ........................................................................................ 7 MỞ ĐẦU .............................................................................................................. 8 TỐI ƢU HÓA ĐÀN KIẾN VÀ ỨNG DỤNG ................................................. 10 1.1 Lịch sử phát triển: ......................................................................................... 12 1.2 Phương pháp tối ưu hóa đàn kiến.................................................................. 13 1.2.1 Bài toán tối ưu hóa tổ hợp ...................................................................... 13 1.2.2 Bài toán tổng quát ................................................................................... 14 1.2.3 Thuật toán tổng quát ............................................................................... 15 1.2.4 Các ứng dụng của ACO .......................................................................... 19 1.3 Các nguyên tắc khi áp dụng tối ưu đàn kiến ................................................. 20 1.3.1 Nồng độ vệt mùi ..................................................................................... 20 1.3.2 Thông tin heuristic .................................................................................. 20 1.3.3 ACO và Local search .............................................................................. 21 1.3.4 Số lượng kiến .......................................................................................... 22 1.3.5 Điều chỉnh sự học tăng cường và sự khám phá ...................................... 22 1.3.6 Sử dụng giới hạn danh sách láng giềng .................................................. 24 1.4 Đánh giá về phương pháp ACO .................................................................... 24 CHƢƠNG 2........................................................................................................ 26 BÀI TOÁN ĐIỀU PHỐI XE ............................................................................ 26 VÀ CÁC CÁCH GIẢI HIỆN NAY.................................................................. 26 2.1 Giới thiệu về bài toán điều phối xe ............................................................... 26 2.1.1 Lịch sử phát triển .................................................................................... 26 2.1.2 Các biến thể của bài toán điều phối xe ................................................... 26 2.2 Tóm tắt nội dung bài toán ............................................................................. 28 2.3 Mô hình hóa bài toán: ................................................................................... 28 2.4 Các cách tiếp cận bài toán : ........................ ...