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Ế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

BẢNG TỪ VIẾT TẮT

STT Từ viết tắt Từ hoặc cụm từ

1 ACO

Ant Colony Optimization

(Tối ưu hóa đàn kiến)

2 AS

Ant System

(Hệ kiến AS)

3 ACS

Ant Colony System

(Hệ kiến ACS)

4 MMAS

Max-Min Ant System

(Hệ kiến MMAS)

6 MLAS

Multi-level Ant System

(Hệ kiến đa mức MLAS)

9 TSP

Travelling Salesman Problem

(Bài toán người chào hàng)

10 JSS

Job shop scheduling

(Bài toán lập lịch sản xuất)

11 g-best global-best

12 i-best iteration-best