Đồ Án Phương pháp tối ưu hoá đàn kiến

TÓM TẮT


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 Problem - 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ột cả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ỤC








TÓM TẮT BẢNG TỪ VIẾT TẮT . MỞ ĐẦU 1
CHƯƠ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 . 25
CHƯƠ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 26
CHƯƠ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 29
CHƯƠ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 34
PHẦN 5. KẾT LUẬN 37
THAM KHẢO .38