ĐẠI HỌC QUỐC GIA HÀ NỘI<br />
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br />
<br />
<br />
<br />
<br />
<br />
VŨ ĐỨC QUANG<br />
<br />
ÁP DỤNG THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN<br />
ĐỂ GIẢI QUYẾT BÀI TOÁN VỊ TRÍ CƠ SỞ<br />
<br />
LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN<br />
<br />
Hà Nội, năm 2016<br />
<br />
[3<br />
<br />
ĐẠI HỌC QUỐC GIA HÀ NỘI<br />
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br />
<br />
<br />
<br />
<br />
<br />
VŨ ĐỨC QUANG<br />
<br />
ÁP DỤNG THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN<br />
ĐỂ GIẢI QUYẾT BÀI TOÁN VỊ TRÍ CƠ SỞ<br />
<br />
Ngành<br />
<br />
: Công nghệ thông tin<br />
<br />
Chuyên ngành : Hệ thống thông tin<br />
Mã số<br />
<br />
: 60480104<br />
<br />
LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN<br />
<br />
Người hướng dẫn khoa học: PGS. TS Hoàng Xuân Huấn<br />
<br />
Hà Nội, năm 2016<br />
<br />
LỜI CAM ĐOAN<br />
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ự<br />
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<br />
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<br />
trích dẫn và chú thích đầy đủ.<br />
<br />
TÁC GIẢ LUẬN VĂN<br />
<br />
Vũ Đức Quang<br />
<br />
LỜI CẢM ƠN<br />
<br />
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<br />
Đạ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<br />
suốt quá trình học tập chương trình cao học tại trường.<br />
Đặ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<br />
Xuân Huấn, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã quan<br />
tâm, định hướng và đưa ra những góp ý, gợi ý, chỉnh sửa quý báu cho em trong<br />
quá trình làm luận văn tốt nghiệp.<br />
Cuối cùng, em xin chân thành cảm ơn các bạn bè đồng nghiệp, gia đình<br />
và người thân đã quan tâm, giúp đỡ và chia sẻ với em trong suốt quá trình làm<br />
luận văn tốt nghiệp.<br />
Em xin chân thành cảm ơn!<br />
Hà Nội, tháng 11 năm 2016<br />
Học viên<br />
<br />
Vũ Đức Quang<br />
<br />
MỤC LỤC<br />
<br />
Trang<br />
MỞ ĐẦU ................................................................................................................................... 1<br />
CHƯƠNG 1 MỘT SỐ KIẾN THỨC TỔNG QUAN VÀ BÀI TOÁN VỊ TRÍ CƠ SỞ . 3<br />
1.1. Độ phức tạp tính toán của bài toán .............................................................................3<br />
1.2. NP- đầy đủ .....................................................................................................................4<br />
1.2.1. Bài toán quyết định ..............................................................................................4<br />
1.2.2. Bằng chứng ngắn gọn để kiểm tra .....................................................................4<br />
1.2.3. Lớp bài toán P, NP và co-NP .............................................................................6<br />
1.2.4. Lớp bài toán NP-khó và NP-đầy đủ...................................................................7<br />
1.3. Bài toán vị trí cơ sở không hạn chế khả năng ...........................................................8<br />
1.4. Bài toán vị trí cơ sở có hạn chế khả năng ..................................................................9<br />
1.5. Bài toán vị trí cơ sở cạnh tranh ................................................................................ 11<br />
1.6. Bài toán bố trí vị trí xây dựng .................................................................................. 14<br />
1.6.1. Hàm mục tiêu thứ nhất ..................................................................................... 14<br />
1.6.2. Hàm mục tiêu thứ hai ....................................................................................... 17<br />
1.7. Bài toán bố trí cơ sở theo hàng................................................................................. 22<br />
1.8. Kết luận chương ......................................................................................................... 23<br />
CHƯƠNG 2 THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN ...............................................24<br />
2.1. Từ kiến thực đến kiến nhân tạo ................................................................................ 24<br />
2.1.1. Kiến thực ............................................................................................................ 24<br />
2.1.2. Kiến nhân tạo ..................................................................................................... 26<br />
2.2. Phương pháp ACO cho bài toán TƯTH tổng quát ................................................ 27<br />
2.2.1. Đồ thị cấu trúc ................................................................................................... 27<br />
2.2.2. Mô tả thuật toán ACO tổng quát. .................................................................... 29<br />
2.3. Phương pháp ACO giải bài toán TSP ...................................................................... 31<br />
2.3.1. Bài toán TSP và đồ thị cấu trúc ....................................................................... 31<br />
2.3.2. Các thuật toán ACO cho bài toán TSP ........................................................... 32<br />
2.4. Một số vấn đề khác khi áp dụng ACO .................................................................... 41<br />
2.4.1. Đặc tính hội tụ ................................................................................................... 41<br />
2.4.2. Thực hiện song song ......................................................................................... 42<br />
2.4.3. ACO kết hợp với tìm kiếm cục bộ .................................................................. 43<br />
2.5. Kết luận chương ......................................................................................................... 44<br />
CHƯƠNG 3 CÀI ĐẶT THỬ NGHIỆM .............................................................................46<br />
3.1. Thuật toán r|p-ACO giải bài toán r|p trung tâm ..................................................... 46<br />
3.1.1. Lược đồ tổng quát ............................................................................................. 46<br />
3.1.2. Thủ tục ACO ..................................................................................................... 47<br />
3.1.3. Kết quả thử nghiệm........................................................................................... 50<br />
<br />
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
