LUẬN VĂN: PHƯƠNG PHÁP TỐI ƯU HOÁ ĐÀN KIẾN

Phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization – ACO) là một phương pháp mới mà ngày nay người ta rất quan tâm vì những hiệu quả nổi trội của nó so với các phuoeng pháp khác trong giải quyết các bài toán tối ưu hóa tổ hợp (Combinatorial optimization problems). Khóa luận này trình bày một cách khái quát về phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization), và trình bày một phương pháp áp dụng của thuật toán tối ưu hóa đàn kiến cho bài toán người chào hàng động (Dynamic Travelling Salesman...
Nội dung trích xuất từ tài liệu:
LUẬN VĂN:PHƯƠNG PHÁP TỐI ƯU HOÁ ĐÀN KIẾN TRƯỜNG …………………. KHOA………………………. ---------- Báo cáo tốt nghiệpĐề tài: PHƯƠNG PHÁP TỐI ƯU HOÁ ĐÀN KIẾNTÓM TẮT Phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization – ACO) là mộtphương pháp mới mà ngày nay người ta rất quan tâm vì những hiệu quả nổi trội của nóso với các phuoeng pháp khác trong giải quyết các bài toán tối ưu hóa tổ hợp(Combinatorial optimization problems). Khóa luận này trình bày một cách khái quát về phương pháp tối ưu hóa đàn kiến(Ant Colony Optimization), và trình bày một phương pháp áp dụng của thuật toán tốiưu hóa đàn kiến cho bài toán người chào hàng động (Dynamic Travelling SalesmanProblem - DTSP) đã được công bố. Khóa luận đã cài đặt và kiểm chứng hiệu quả của thuật toán đồng thời đưa ra mộtcải tiến đối với thuật toán để nâng cao hiệu quả trong trường hợp bài toán đầu vào cókích thước lớn.MỤC LỤCTÓM TẮT ....................................................................................................................BẢNG TỪ VIẾT TẮT .................................................................................................MỞ ĐẦU .................................................................................................................... 1CHƯƠNG 1. GIỚI THIỆU PHƯƠNG PHÁP ACO................................................. 3 1.1. Giới thiệu .......................................................................................................... 3 1.2. Quá trình phát triển............................................................................................ 6 1.3. Một số thuật toán ACO áp dụng cho bài toán TSP ............................................. 9 1.3.1. Bài toán TSP ............................................................................................. 10 1.3.2. Ant System (AS)......................................................................................... 12 1.3.3. Max-Min Ant System (MMAS) ................................................................... 15 1.3.4. Ant Colony System (ACS) ......................................................................... 17 1.3.5. Hệ kiến đa mức (xem [15]) ....................................................................... 19 1.4. Các nguyên tắc khi áp dụng tối ưu đàn kiến..................................................... 20 1.4.2. Xác định các vệt mùi................................................................................. 21 1.4.3. Các thông tin heuristic .............................................................................. 22 1.4.4. Kết hợp tìm kiếm địa phương.................................................................... 22 1.4.5. Điều chỉnh giữa sự học tăng cường và sự khám phá .................................. 23 1.4.6. Sử dụng giới hạn danh sách láng giềng ..................................................... 24 1.5. Các ứng dụng của ACO ................................................................................... 25CHƯƠNG 2. GIỚI THIỆU BÀI TOÁN DTSP....................................................... 26 2.1. Bài toán DTSP ................................................................................................. 26 2.2. Các phương pháp giải bài toán DTSP .............................................................. 26CHƯƠNG 3. SỬ DỤNG THUẬT TOÁN AS ĐỂ GIẢI QUYẾT BÀI TOÁN DTSP.................................................................................................................................. 28 3.1. Phân tích bài toán ............................................................................................ 28 3.2. Cải tiến AS cho phù hợp .................................................................................. 29CHƯƠNG 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ .................................................... 31 4.1. Thực nghiệm trên tsplib eil51 .......................................................................... 32 4.2. Nhận xét .......................................................................................................... 34PHẦN 5. KẾT LUẬN .............................................................................................. 37THAM KHẢO ......................................................................................................... 38 BẢNG TỪ VIẾT TẮTSTT Từ viết tắt Từ hoặc cụm từ Ant Colony Optimization ACO1 (Tối ưu hóa đàn kiến) Ant System AS2 (Hệ kiến AS) Ant Colony System ACS3 (Hệ kiến ACS) Max-Min Ant System MMAS4 (Hệ kiến MMAS) Multi-level Ant System MLAS6 ...