đề tài:“Nghiên cứu ứng dụng thuật toán đàn kiến để giải bài toán người du lịch”
100,000 ₫
- Mô tả
- Đánh giá (0)
- Demo thử
Mô tả
1.1. CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ. 6
1.1.3. Tính liên thông của đồ thị. 8
1.1.4. Biểu diễn đồ thị trên máy tính.. 9
1.1.5. Đồ thị Euler và đồ thị Hamilton.. 11
1.2. BÀI TOÁN TỐI ƯU TỔ HỢP.. 14
1.3. BÀI TOÁN NGƯỜI DU LỊCH.. 14
1.3.1. Giới thiệu bài toán. 14
1.3.2. Lịch sử bài toán TSP. 15
1.3.4. Phân loại bài toán TSP. 18
1.4. CÁC THUẬT TOÁN GIẢI BÀI TOÁN TSP.. 19
1.4.1. Thuật giải chính xác. 19
1.4.2. Thuật giải gần đúng heuristic. 19
- Thuật toán láng giềng gần nhất 20
- Thuật toán tìm kiếm cục bộ. 22
- Thuật toán nhánh cận. 24
- Thuật toán di truyền. 31
1.5. CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN.. 35
CHƯƠNG 2. THUẬT TOÁN TỐI ƯU ĐÀN KIẾN ACO.. 36
2.1.1. Hoàn cảnh ra đời và lịch sử phát triển của thuật toán ACO.. 36
2.1.2. Tư tưởng thuật toán. 38
2.2. THUẬT TOÁN TỐI ƯU ĐÀN KIẾN ACO.. 44
2.2.1. Thuật toán Ant System (AS). 44
2.2.2. Thuật toán Max-Min Ant System (MMAS). 46
2.2.3. Thuật toán Ant Colony System (ACS). 49
2.3. THUẬT TOÁN ĐÀN KIẾN GIẢI BÀI TOÁN TSP.. 52
2.4. NÂNG CAO HIỆU QUẢ CỦA THUẬT TOÁN ACO.. 54
2.4.2. Xác định các vệt mùi 55
2.4.3. Các thông tin heuristic. 56
2.4.4. Kết hợp tìm kiếm cục bộ. 57
2.4.5. Điều chỉnh giữa sự học tăng cường và sự khám phá. 57
2.4.6. Sử dụng giới hạn danh sách láng giềng. 59
2.5. CÁC ỨNG DỤNG CỦA ACO.. 60
CHƯƠNG 3. ỨNG DỤNG THUẬT TOÁN ACO VÀO BÀI TOÁN NGƯỜI DU LỊCH 61
3.2. ĐẶC TẢ CẤU TRÚC DỮ LIỆU.. 61
3.2.1. Biểu diễn thông tin các thành phố. 62
3.2.2. Biểu diễn thông tin vệt mùi trên các con đường. 63
3.2.3. Biểu diễn sự kết hợp thông tin vệt mùi và thông tin heuristic. 63
3.2.4. Biểu diễn thông tin kiến. 63
3.3. THIẾT KẾ VÀ XÂY DỰNG CHƯƠNG TRÌNH.. 65
3.3.1. Phân tích chức năng. 66
3.3.2. Xây dựng thuật toán. 67
3.4. KẾT QUẢ THỰC NGHIỆM CHƯƠNG TRÌNH.. 72
3.5.1. Kết quả thực hiện của thuật toán ACO.. 76
3.5.2.Đánh giá hiệu quả thuật toán ACO.. 81
3.5.3. So sánh thuật toán ACO với thuật toán di truyền GA.. 81
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.. 85
DANH MỤC TÀI LIỆU THAM KHẢO.. 88
QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (bản sao)
Đánh giá
Chưa có đánh giá nào.