Áp Dụng Thuật Toán Tối Ưu Hóa Đàn Kiến Để Giải Quyết Bài Toán Vị Trí Cơ Sở

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

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







VŨ ĐỨC QUANG

ÁP DỤNG THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN

ĐỂ GIẢI QUYẾT BÀI TOÁN VỊ TRÍ CƠ SỞ

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

Hà Nội, năm 2016

[3

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

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







VŨ ĐỨC QUANG

ÁP DỤNG THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN

ĐỂ GIẢI QUYẾT BÀI TOÁN VỊ TRÍ CƠ SỞ

Ngành : Công nghệ thông tin

Chuyên ngành : Hệ thống thông tin

Mã số : 60480104

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

Người hướng dẫn khoa học: PGS. TS Hoàng Xuân Huấn

Hà Nội, năm 2016

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn này của tự bản thân tôi tìm hiểu, nghiên cứu dưới sự

hướng dẫn của PGS.TS Hoàng Xuân Huấn. Các chương trình thực nghiệm do chính bản

thân tôi lập trình, các kết quả là hoàn toàn trung thực. Các tài liệu tham khảo được

trích dẫn và chú thích đầy đủ.

TÁC GIẢ LUẬN VĂN

Vũ Đức Quang

LỜI CẢM ƠN

Em xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo trường

Đại học công nghệ - Đại học Quốc gia Hà Nội và Viện công nghệ thông tin -

Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã dạy dỗ chúng em trong

suốt quá trình học tập chương trình cao học tại trường.

Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS Hoàng

Xuân Huấn, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã quan

tâm, định hướng và đưa ra những góp ý, gợi ý, chỉnh sửa quý báu cho em trong

quá trình làm luận văn tốt nghiệp.

Cuối cùng, em xin chân thành cảm ơn các bạn bè đồng nghiệp, gia đình

và người thân đã quan tâm, giúp đỡ và chia sẻ với em trong suốt quá trình làm

luận văn tốt nghiệp.

Em xin chân thành cảm ơn!

Hà Nội, tháng 11 năm 2016

Học viên

Vũ Đức Quang

MỤC LỤC

Trang

MỞ ĐẦU...................................................................................................................................1

CHƯƠNG 1 MỘT SỐ KIẾN THỨC TỔNG QUAN VÀ BÀI TOÁN VỊ TRÍ CƠ SỞ .3

1.1. Độ phức tạp tính toán của bài toán .............................................................................3

1.2. NP- đầy đủ .....................................................................................................................4

1.2.1. Bài toán quyết định..............................................................................................4

1.2.2. Bằng chứng ngắn gọn để kiểm tra .....................................................................4

1.2.3. Lớp bài toán P, NP và co-NP .............................................................................6

1.2.4. Lớp bài toán NP-khó và NP-đầy đủ...................................................................7

1.3. Bài toán vị trí cơ sở không hạn chế khả năng ...........................................................8

1.4. Bài toán vị trí cơ sở có hạn chế khả năng ..................................................................9

1.5. Bài toán vị trí cơ sở cạnh tranh ................................................................................ 11

1.6. Bài toán bố trí vị trí xây dựng .................................................................................. 14

1.6.1. Hàm mục tiêu thứ nhất ..................................................................................... 14

1.6.2. Hàm mục tiêu thứ hai ....................................................................................... 17

1.7. Bài toán bố trí cơ sở theo hàng................................................................................. 22

1.8. Kết luận chương ......................................................................................................... 23

CHƯƠNG 2 THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN ...............................................24

2.1. Từ kiến thực đến kiến nhân tạo ................................................................................ 24

2.1.1. Kiến thực ............................................................................................................ 24

2.1.2. Kiến nhân tạo..................................................................................................... 26

2.2. Phương pháp ACO cho bài toán TƯTH tổng quát ................................................ 27

2.2.1. Đồ thị cấu trúc ................................................................................................... 27

2.2.2. Mô tả thuật toán ACO tổng quát. .................................................................... 29

2.3. Phương pháp ACO giải bài toán TSP...................................................................... 31

2.3.1. Bài toán TSP và đồ thị cấu trúc ....................................................................... 31

2.3.2. Các thuật toán ACO cho bài toán TSP ........................................................... 32

2.4. Một số vấn đề khác khi áp dụng ACO .................................................................... 41

2.4.1. Đặc tính hội tụ ................................................................................................... 41

2.4.2. Thực hiện song song......................................................................................... 42

2.4.3. ACO kết hợp với tìm kiếm cục bộ .................................................................. 43

2.5. Kết luận chương ......................................................................................................... 44

CHƯƠNG 3 CÀI ĐẶT THỬ NGHIỆM .............................................................................46

3.1. Thuật toán r|p-ACO giải bài toán r|p trung tâm ..................................................... 46

3.1.1. Lược đồ tổng quát ............................................................................................. 46

3.1.2. Thủ tục ACO ..................................................................................................... 47

3.1.3. Kết quả thử nghiệm........................................................................................... 50

3.2. So sánh các thuật toán giải bài toán CSLP ............................................................. 53

3.3. Áp dụng thuật toán ACO-SRFL giải bài toán SRFL............................................. 55

3.3.1. Mô tả thuật toán................................................................................................. 55

3.3.2. Đồ thị cấu trúc và thủ tục xây dựng lời giải .................................................. 55

3.3.3 Quy tắc cập nhật vết mùi................................................................................... 56

3.3.4. Tìm kiếm địa phương ....................................................................................... 56

3.3.5. Kết quả thử nghiệm........................................................................................... 56

3.4. Kết luận chương ......................................................................................................... 58

KẾT LUẬN.............................................................................................................................59

DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA TÁC GIẢ.............................60

TÀI LIỆU THAM KHẢO.....................................................................................................61

DANH SÁCH KÍ HIỆU, TỪ VIẾT TẮT

Viết tắt Viết đầy đủ

ACO

Ant Colony Optimization

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

ACS

Ant Colony System

(Hệ kiến ACS)

aiNet

Artificial Immune Network

(Thuật toán mạng miễn dịch)

AS

Ant System

(Hệ kiến AS)

CFLP

Capacitated Facility Location Problem

(Bài toán vị trí cơ sở có hạn chế khả năng)

CSLP

Construction Site Layout Problem

(Bài toán bố trí vị trí xây dựng)

GA

Genetic Algorithm

(Giải thuật di truyền)

IEM Iterative Exact Method

MEM Modified Exact Method

MLAS

Multi-level Ant System

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

MMAS

Max-Min Ant System

(Hệ kiến MMAS)

PSO

Particle Swarm Optimization

(Tối ưu hóa bầy đàn)

r|p-centroid r|p-trung tâm

SMMAS

Smooth-Max Min Ant System

(Hệ kiến MMAS trơn)

SRFL

Single Row Facility Layout

(Bài toán bố trí cơ sở theo hàng)

STS Stochastic Tabu Search

TƯTH Tối ưu tổ hợp

UPLP

Uncapacitated Facility Location Problem

(Bài toán vị trí cơ sở không hạn chế khả năng)

VNS Variable Neighborhood Search