Khai Thác Tập Mục Lợi Ích Cao Sử Dụng Phương Pháp Tối Ưu Đàn Kiến

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN ĐỨC DŨNG

KHAI THÁC TẬP MỤC LỢI ÍCH CAO

SỬ DỤNG PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN

Ngành: Khoa học máy tính

Chuyên ngành: Khoa học máy tính

Mã số: 8480101.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC:

PGS.TS Hoàng Xuân Huấn

Hà Nội - 2019

2

LỜI CẢM ƠN

Tôi xin gửi lời cảm ơn chân thành nhất tới PGS.TS Hoàng Xuân Huấn, người

thầy đáng kính đã tận tình chỉ bảo, hướng dẫn tôi trong suốt quá trình tìm hiểu,

nghiên cứu và hoàn thiện luận văn. Với kiến thức sâu rộng, nhiều năm nghiên cứu

trong lĩnh vực tối ưu hóa cũng như phương pháp tối ưu hệ kiến của thầy đã giúp tôi

hiểu rõ, sâu sắc nhiều khó khăn gặp phải trong quá trình nghiên cứu. Thầy cũng đưa

ra những góp ý chi tiết, tỉ mỉ hết sức quý báu giúp cho tôi có thể hoàn thành quyển

luận văn này.

Tôi cũng xin được bày tỏ lòng biết ơn tới các thầy cô trường Đại học Công nghệ

đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tập thể và cá nhân

tôi nói riêng. Tôi xin cảm ơn tới các thầy và các anh chị đã thường xuyên giúp đỡ, trao

đổi, góp ý về những vấn đề khoa học liên quan tới luận văn.

Hà Nội, tháng 3 năm 2019

HỌC VIÊN

Nguyễn Đức Dũng

3

LỜI CAM ĐOAN

Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi dưới sự

hướng dẫn giúp đỡ của PGS.TS Hoàng Xuân Huấn. Các kết quả được viết chung với

các tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn. Trong

toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những

tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn từ các nguồn tài

liệu có ghi tham khảo rõ ràng, hợp pháp.

Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả được

liệt kê tại mục tài liệu tham khảo.

Hà Nội, tháng 3 năm 2019

HỌC VIÊN

Nguyễn Đức Dũng

4

MỤC LỤC

LỜI CẢM ƠN......................................................................................................................2

LỜI CAM ĐOAN................................................................................................................3

DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT......................................................................6

DANH SÁCH CÁC BẢNG ................................................................................................7

DANH SÁCH HÌNH VẼ.....................................................................................................8

MỞ ĐẦU .............................................................................................................................9

CHƯƠNG 1: TỐI ƯU TỔ HỢP VÀ BÀI TOÁN TỐI ƯU ĐÀN KIẾN..........................12

1.1. Giới thiệu bài toán tối ưu tổ hợp ............................................................................12

1.2. Giới thiệu bài toán người chào hàng ......................................................................13

1.3. Các cách tiếp cận giải quyết bài toán tối ưu tổ hợp................................................13

1.3.1. Heuristic cấu trúc.............................................................................................13

1.3.2. Tìm kiếm địa phương ......................................................................................14

1.3.3. Phương pháp meta-heuristic............................................................................15

1.3.4. Phương pháp memetic .....................................................................................15

1.4. Phương pháp tối ưu đàn kiến..................................................................................16

1.4.1. Từ kiến tự nhiên đến kiến nhân tạo .....................................................................16

1.4.1.1. Kiến tự nhiên ................................................................................................16

1.4.1.2. Kiến nhân tạo (Artificial Ant) ......................................................................19

1.4.2. Phương pháp tối ưu đàn kiến...............................................................................19

1.4.3. Mô tả thuật toán ACO tổng quát .........................................................................20

1.4.4. Các hệ kiến ..........................................................................................................22

1.4.4.1. Hệ kiến AS ...................................................................................................22

1.4.4.2. Hệ kiến ACS.................................................................................................23

1.4.4.3. Hệ kiến Max-Min .........................................................................................25

1.4.4.4. Hệ kiến Max-Min trơn..................................................................................26

CHƯƠNG 2: KHAI THÁC TẬP MỤC CAO TIỆN ÍCH BẰNG PHƯƠNG PHÁP TỐI

ƯU ĐÀN KIẾN.................................................................................................................27

2.1. Bài toán khai thác tập mục lợi ích cao....................................................................27

2.2. Một số phương pháp tiếp cận để giải bài toán........................................................30

2.3. Thuật toán HUIM-ACS. .........................................................................................31