Tài liệu Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất.

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHAN TẤN QUỐC CÁC THUẬT TOÁN GẦN ĐÚNG GIẢI BÀI TOÁN CÂY KHUNG VỚI CHI PHÍ ĐỊNH TUYẾN NHỎ NHẤT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội –2015 i BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHAN TẤN QUỐC CÁC THUẬT TOÁN GẦN ĐÚNG GIẢI BÀI TOÁN CÂY KHUNG VỚI CHI PHÍ ĐỊNH TUYẾN NHỎ NHẤT Chuyên ngành: Khoa học máy tính Mã số: 62480101 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Nguyễn Đức Nghĩa Hà Nội –2015 ii LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nghiên cứu được trình bày trong luận án là hoàn toàn trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. GIẢNG VIÊN HƯỚNG DẪN NGHIÊN CỨU SINH PGS.TS Nguyễn Đức Nghĩa Phan Tấn Quốc i LỜI CẢM ƠN Tôi xin trân trọng cảm ơn thầy Nguyễn Đức Nghĩa đã nhiệt tình hướng dẫn tôi học tập, nghiên cứu và thực hiện luận án này. Tôi xin trân trọng cảm ơn lãnh đạo và các chuyên viên Viện Công nghệ Thông tin và Truyền thông, Viện Đào tạo Sau Đại học - trường Đại học Bách khoa Hà Nội đã quan tâm, hỗ trợ tôi trong quá trình tôi làm nghiên cứu sinh tại Trường. Tôi xin trân trọng cảm ơn các thầy cô ở Bộ môn Khoa học máy tính Viện Công nghệ Thông tin và Truyền thông trường Đại học Bách khoa Hà Nội đã giúp đỡ tôi trong hơn 5 năm làm nghiên cứu sinh tại Bộ môn. Các thầy cô đã nhiệt tình hướng dẫn tôi thực hiện các học phần tiến sĩ, các chuyên đề tiến sĩ, tiểu luận tổng quan; tham dự các buổi seminar định kỳ, các buổi bảo vệ luận án tiến sĩ các cấp và có những góp ý quý báu để tôi hoàn thiện luận án này. Tôi xin trân trọng cảm ơn các thầy cô trong và ngoài trường đã tham gia đọc và nhận xét luận án ở các cấp Bộ môn, cấp Cơ sở, cấp phản biện độc lập, cấp Trường; đã cho tôi những ý kiến quý báu để tôi hoàn thiện luận án này. Trân trọng cảm ơn Ban Giám hiệu trường Đại học Sài Gòn, các đồng nghiệp tại khoa Công nghệ Thông tin trường Đại học Sài Gòn và gia đình đã tạo điều kiện và giúp đỡ tôi trong thời gian tôi làm nghiên cứu sinh. Hà Nội, tháng 5-2015 Tác giả luận án Phan Tấn Quốc ii MỤC LỤC LỜI CAM ĐOAN ........................................................................................................................ i LỜI CẢM ƠN............................................................................................................................. ii MỤC LỤC .................................................................................................................................iii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT............................................................... vii DANH MỤC CÁC BẢNG ........................................................................................................ ix DANH MỤC CÁC HÌNH VẼ ................................................................................................... xi MỞ ĐẦU .................................................................................................................................... 1 Chương 1. TỔNG QUAN........................................................................................................... 5 1.1.BÀI TOÁN MRCST ...................................................................................................... 5 1.1.1.Một số định nghĩa ................................................................................................ 5 1.1.2.Thuật toán tính chi phí định tuyến của cây khung .............................................. 7 1.1.3.Đánh giá chi phí định tuyến của cây khung ........................................................ 9 1.2.ỨNG DỤNG ................................................................................................................ 11 1.2.1.Ứng dụng của bài toán MRCST trong lĩnh vực thiết kế mạng .......................... 11 1.2.2.Ứng dụng của bài toán MRCST trong lĩnh vực tin sinh học.............................. 11 1.3.CÁC NGHIÊN CỨU LIÊN QUAN BÀI TOÁN MRCST........................................... 12 1.3.1.Thuật toán giải đúng .......................................................................................... 12 1.3.2.Thuật toán gần đúng cận tỉ lệ ............................................................................ 13 1.3.3.Thuật toán heuristic ........................................................................................... 16 1.3.4.Thuật toán metaheuristic ................................................................................... 18 1.3.5.Danh sách các thuật toán giải bài toán MRCST hiện biết .................................. 25 1.4.TIÊU CHÍ ĐÁNH GIÁ THUẬT TOÁN ..................................................................... 26 1.5.HỆ THỐNG DỮ LIỆU THỰC NGHIỆM CHUẨN ................................................... 29 1.5.1.Đồ thị đầy đủ Euclid .......................................................................................... 30 1.5.2.Đồ thị đầy đủ ngẫu nhiên .................................................................................. 30 1.5.1.Đồ thị thưa ......................................................................................................... 31 1.6.KHẢO SÁT THỰC NGHIỆM CÁC THUẬT TOÁN GIẢI BÀI TOÁN MRCST ..... 32 1.6.1.Cấu hình máy tính thực nghiệm các thuật toán ................................................. 32 1.6.2.Chất lượng lời giải ............................................................................................. 32 1.6.3.Thời gian tính .................................................................................................... 34 1.6.4.Hình vẽ minh họa so sánh chất lượng của các thuật toán hiện biết ................... 36 iii 1.7.KẾT LUẬN CHƯƠNG 1 ............................................................................................ 37 Chương 2. THUẬT TOÁN TÌM KIẾM LEO ĐỒI .................................................................. 39 2.1.CÂY KHUNG LÂN CẬN........................................................................................... 39 2.2.THUẬT TOÁN HCSRI ............................................................................................... 40 2.2.1.Ý tưởng thuật toán HCSRI ................................................................................ 40 2.2.2.Sơ đồ thuật toán HCSRI .................................................................................... 41 2.2.3.Độ phức tạp của thuật toán HCSRI ................................................................... 42 2.3.THUẬT TOÁN HCSIR ............................................................................................... 42 2.3.1.Ý tưởng thuật toán HCSIR ................................................................................ 42 2.3.2.Sơ đồ thuật toán HCSIR .................................................................................... 43 2.3.3.Độ phức tạp của thuật toán HCSIR ................................................................... 44 2.4.THỰC NGHIỆM VÀ ĐÁNH GIÁ.............................................................................. 45 2.4.1.Môi trường thực nghiệm.................................................................................... 45 2.4.2.Tham số thực nghiệm ........................................................................................ 45 2.4.3.Chất lượng lời giải ............................................................................................. 45 2.4.4.Thời gian tính .................................................................................................... 51 2.4.5.Hình vẽ minh họa chất lượng HCSRI, HCSIR với các thuật toán khác ............ 53 2.5.KẾT LUẬN CHƯƠNG 2 ............................................................................................ 55 Chương 3. THUẬT TOÁN DI TRUYỀN ................................................................................ 56 3.1.THUẬT TOÁN GST ................................................................................................... 56 3.1.1.Tạo quần thể ban đầu......................................................................................... 56 3.1.2.Phép lai .............................................................................................................. 57 3.1.3.Phép đột biến ..................................................................................................... 60 3.1.4.Phép chọn lọc .................................................................................................... 62 3.1.5.Sơ đồ thuật toán GST......................................................................................... 63 3.1.6.Độ phức tạp của thuật toán GST ........................................................................ 64 3.2.THỰC NGHIỆM VÀ ĐÁNH GIÁ.............................................................................. 64 3.2.1.Môi trường thực nghiệm.................................................................................... 64 3.2.2.Tham số thực nghiệm ........................................................................................ 65 3.2.3.Chất lượng lời giải ............................................................................................. 65 3.2.4.Thời gian tính .................................................................................................... 69 3.2.5.Hình vẽ minh họa chất lượng thuật toán GST với các thuật toán khác ............. 70 3.3.KẾT LUẬN CHƯƠNG 3 ............................................................................................ 73 Chương 4. THUẬT TOÁN TÌM KIẾM TABU ....................................................................... 74 iv 4.1.THUẬT TOÁN TST .................................................................................................... 74 4.1.1.Ý tưởng và một số khái niệm của thuật toán tìm kiếm Tabu ............................ 74 4.1.2.Thuật toán TST tìm bước chuyển tốt nhất ......................................................... 75 4.1.3.Thuật toán TST cập nhật danh sách Tabu .......................................................... 76 4.1.4.Chiến lược đa dạng hóa lời giải của thuật toán TST .......................................... 76 4.1.5.Sơ đồ của thuật toán TST ................................................................................... 77 4.1.6.Độ phức tạp của thuật toán TST ........................................................................ 79 4.2.THỰC NGHIỆM VÀ ĐÁNH GIÁ.............................................................................. 79 4.2.1.Môi trường thực nghiệm.................................................................................... 79 4.2.2.Tham số thực nghiệm ........................................................................................ 79 4.2.3.Chất lượng lời giải ............................................................................................. 80 4.2.4.Thời gian tính .................................................................................................... 84 4.2.5.Hình vẽ minh họa chất lượng thuật toán TST với các thuật toán khác .............. 86 4.3.KẾT LUẬN CHƯƠNG 4 ............................................................................................ 88 Chương 5. THUẬT TOÁN BẦY ONG ................................................................................... 89 5.1.THUẬT TOÁN BẦY ONG CƠ BẢN ........................................................................ 89 5.2.THUẬT TOÁN BST .................................................................................................... 91 5.2.1.Tạo quần thể ban đầu......................................................................................... 91 5.2.2.Phân nhóm các cá thể ........................................................................................ 92 5.2.3.Tìm cây khung lân cận ...................................................................................... 93 5.2.4.Chiến lược đa dạng hóa lời giải......................................................................... 95 5.2.5.Sơ đồ của thuật toán BST................................................................................... 96 5.2.6.Độ phức tạp của thuật toán BST ........................................................................ 98 5.3.THỰC NGHIỆM VÀ ĐÁNH GIÁ.............................................................................. 98 5.3.1.Môi trường thực nghiệm.................................................................................... 98 5.3.2.Tham số thực nghiệm ........................................................................................ 98 5.3.3.Chất lượng lời giải ............................................................................................. 99 5.3.4.Thời gian tính .................................................................................................. 104 5.3.5.Hình vẽ minh họa chất lượng thuật toán BST với các thuật toán khác............ 106 5.3.6.Hình vẽ minh họa độ lệch chuẩn của các thuật toán ....................................... 109 5.4.KẾT LUẬN CHƯƠNG 5 .......................................................................................... 111 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.............................................................................. 112 KẾT LUẬN ..................................................................................................................... 112 HƯỚNG PHÁT TRIỂN .................................................................................................. 113 v DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN ................................... 114 TÀI LIỆU THAM KHẢO ...................................................................................................... 115 PHỤ LỤC. KẾT QUẢ THỰC NGHIỆM TỪ CÁC CÔNG TRÌNH LIÊN QUAN ............... 119 PL1. KẾT QUẢ THỰC NGHIỆM CÁC THUẬT TOÁN WONG, ADD, CAMPOS ..... 119 PL2. KẾT QUẢ THỰC NGHIỆM CÁC THUẬT TOÁN ESCGA, BCGA .................... 122 PL3. KẾT QUẢ THỰC NGHIỆM CÁC THUẬT TOÁN SHC, PBLS .......................... 123 PL4. KẾT QUẢ THỰC NGHIỆM CÁC THUẬT TOÁN PABC, ABC+LS................... 126 PL5. SO SÁNH CHI PHÍ ĐỊNH TUYẾN CỦA CÁC THUẬT TOÁN ......................... 128 vi DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Từ viết tắt MRCST Tiếng Anh Tiếng Việt Minimum Routing Cost Spanning Cây khung chi phí định tuyến nhỏ nhất Tree OCST Optimal Communication Cây khung truyền thông tối ưu Spanning Tree BDMRCST Benchmark Data For MRCST Bộ dữ liệu chuẩn cho bài toán MRCST SPT Shortest Path Tree Cây đường đi ngắn nhất C(T) Routing Cost Chi phí định tuyến cây khung T l(e) Routing Load Tải định tuyến của cạnh e SHC Stochastic Hill Climber Search Thuật toán tìm kiếm leo đồi ngẫu nhiên Algorithm LS Local Search Algorithm Thuật toán tìm kiếm địa phương TABU Tabu Search Algorithm Thuật toán tìm kiếm Tabu Genetic Algorithm Thuật toán di truyền Artificial Bee Colony Algorithm Thuật toán bầy ong nhân tạo GA PABC ABC+LS BEE PTAS Artificial Bee Colony Algorithm + Thuật toán bầy ong nhân tạo kết hợp với Local Search thuật toán tìm kiếm địa phương. Bee Algorithm Thuật toán bầy ong Branch and Bound Algorithm Thuật toán nhánh cận Column Generation Method Phương pháp sinh cột Polynomial Time Approximation Sơ đồ xấp xỉ thời gian đa thức Scheme SD MSA HCSRI α -Approximation Algorithm Thuật toán gần đúng cận tỉ lệ α Network Optimization Tối ưu hóa mạng Standard Deviation Độ lệch chuẩn Bioinformatics Tin sinh học Multiple Sequence Alignments So sánh đa trình tự HCSRI-MRCST Thuật toán tìm kiếm leo đồi dạng loại trước-chèn sau giải bài toán MRCST vii HCSIR HCSIR-MRCST Thuật toán tìm kiếm leo đồi dạng chèn trước-loại sau giải bài toán MRCST GST GA-MRCST Thuật toán di truyền giải bài toán MRCST TST TABU-MRCST Thuật toán Tabu giải bài toán MRCST BST BEE-MRCST Thuật toán bầy ong giải bài toán MRCST viii DANH MỤC CÁC BẢNG Bảng 1.1. Danh sách các thuật toán điển hình giải bài toán MRCST .............................. 26 Bảng 1.2.a. Thông tin các đồ thị đầy đủ Euclid trong BDMRCST..................................... 30 Bảng 1.2.b. Thông tin các đồ thị đầy đủ ngẫu nhiên trong BDMRCST ............................. 31 Bảng 1.2.c. Thông tin các đồ thị thưa trong BDMRCST .................................................... 31 Bảng 1.3. Cấu hình máy tính thực nghiệm các thuật toán............................................... 32 Bảng 1.4.a. Thời gian tính các thuật toán trước khi quy đổi .............................................. 35 Bảng 1.4.b. Thời gian tính các thuật toán sau khi quy đổi ................................................. 35 Bảng 2.1. Kết quả thực nghiệm thuật toán HCSRI, HCSIR trên đồ thị đầy đủ Euclid .... 48 Bảng 2.2. Kết quả thực nghiệm HCSRI, HCSIR trên đồ thị đầy đủ ngẫu nhiên ............. 49 Bảng 2.3. Kết quả thực nghiệm các thuật toán HCSRI, HCSIR trên đồ thị thưa ............ 49 Bảng 2.4. So sánh chi phí định tuyến thuật toán HCSRI với các thuật toán khác ........... 50 Bảng 2.5. So sánh chi phí định tuyến thuật toán HCSIR với các thuật toán khác ........... 51 Bảng 2.6. So sánh thời gian tính thuật toán HCSRI với các thuật toán khác .................. 52 Bảng 2.7. So sánh thời gian tính thuật toán HCSIR với các thuật toán khác .................. 53 Bảng 3.1. Kết quả thực nghiệm thuật toán GST trên đồ thị đầy đủ Euclid ..................... 67 Bảng 3.2. Kết quả thực nghiệm thuật toán GST trên đồ thị đầy đủ ngẫu nhiên .............. 68 Bảng 3.3. Kết quả thực nghiệm thuật toán GST trên đồ thị thưa .................................... 68 Bảng 3.4. So sánh chi phí định tuyến thuật toán GST với các thuật toán khác ............... 69 Bảng 3.5. So sánh thời gian tính thuật toán GST với các thuật toán khác ...................... 70 Bảng 4.1. Kết quả thực nghiệm thuật toán TST trên đồ thị đầy đủ Euclid ...................... 82 Bảng 4.2. Kết quả thực nghiệm TST trên đồ thị đầy đủ ngẫu nhiên................................ 83 Bảng 4.3. Kết quả thực nghiệm thuật toán TST trên đồ thưa .......................................... 83 Bảng 4.4. So sánh chi phí định tuyến thuật toán TST với các thuật toán khác................ 84 Bảng 4.5.a. So sánh thời gian tính của thuật toán TST với các thuật toán dạng cá thể ...... 85 Bảng 4.5.b. So sánh thời gian tính của thuật toán TST với các thuật toán dạng quần thể .. 85 Bảng 5.1. Kết quả thực nghiệm thuật toán BST trên đồ thị đầy đủ Euclid .................... 101 Bảng 5.2. Kết quả thực nghiệm thuật toán BST trên đồ thị đầy đủ ngẫu nhiên ............ 102 Bảng 5.3. Kết quả thực nghiệm thuật toán BST trên đồ thị thưa ................................... 102 Bảng 5.4. So sánh thực nghiệm của thuật toán BST với các thuật toán đơn lời giải ..... 103 Bảng 5.5. So sánh thực nghiệm của thuật toán BST với các thuật toán đa lời giải ....... 104 Bảng 5.6. Các bộ dữ liệu BST cho lời giải chất lượng tốt hơn thuật toán ABC+LS...... 104 ix Bảng 5.7. So sánh thời gian tính thuật toán BST với các thuật toán đơn lời giải .......... 106 Bảng 5.8. So sánh thời gian tính thuật toán BST với các thuật toán đa lời giải ............ 106 PL1.a. Thực nghiệm WONG, ADD, CAMPOS trên đồ thị đầy đủ Euclid ................ 120 PL1.b. Thực nghiệm WONG, ADD, CAMPOS trên đồ thị đầy đủ ngẫu nhiên ........ 121 PL1.c. Thực nghiệm thuật toán WONG, ADD, CAMPOS trên đồ thị thưa. ............. 121 PL2.a. Thực nghiệm thuật toán ESCGA, BCGA trên đồ thị đầy đủ Euclid. ............. 122 PL2.b. Kết quả thực nghiệm ESCGA, BCGA trên đồ thị đầy đủ ngẫu nhiên ........... 123 PL3.a. Kết quả thực nghiệm thuật toán SHC, PBLS trên đồ thị đầy đủ Euclid. ....... 124 PL3.b. Kết quả thực nghiệm thuật toán SHC, PBLS trên đồ thị đầy đủ ngẫu nhiên. 125 PL3.c. Kết quả thực nghiệm các thuật toán SHC, PBLS trên đồ thị thưa................. 125 PL4.a. Kết quả thực nghiệm thuật toán PABC, ABC+LS trên đồ thị đầy đủ Euclid 126 PL4.b. Kết quả thực nghiệm PABC, ABC+LS trên đồ thị đầy đủ ngẫu nhiên.......... 127 PL4.c. Kết quả thực nghiệm thuật toán ABC+LS trên đồ thị thưa. .......................... 127 PL5. So sánh chi phí định tuyến cho tất cả các thuật toán .................................... 129 x DANH MỤC CÁC HÌNH VẼ Hình 1.1. Minh họa cách tính chi phí định tuyến của một cây theo định nghĩa ................... 6 Hình 1.2. Minh họa cho thuật toán tìm chi phí định tuyến của một cây khung ................... 8 Hình 1.3. Đồ thị vô hướng liên thông có trọng số .............................................................. 14 Hình 1.4. Cây đường đi ngắn nhất xuất phát từ v1............................................................. 15 Hình 1.5. Minh họa chất lượng của các thuật toán qua bộ dữ liệu e50-01 ......................... 36 Hình 1.6. Minh họa chất lượng của các thuật toán qua bộ dữ liệu e100-01 ....................... 36 Hình 1.7. Minh họa chất lượng của các thuật toán qua bộ dữ liệu e250-01 ....................... 36 Hình 1.8. Minh họa chất lượng của các thuật toán qua bộ dữ liệu rand100-01 ................. 37 Hình 1.9. Minh họa chất lượng của các thuật toán qua bộ dữ liệu rand300-01 ................. 37 Hình 2.1. Minh họa chất lượng HCSRI, HCSIR và các thuật toán khác qua e50-01 .......... 53 Hình 2.2. Minh họa chất lượng HCSRI, HCSIR và các thuật toán khác qua e100-01 ........ 53 Hình 2.3. Minh họa chất lượng HCSRI, HCSIR và các thuật toán khác qua e250-01 ........ 54 Hình 2.4. Minh họa chất lượng HCSRI, HCSIR và các thuật toán khác qua rand100-01 .. 54 Hình 2.5. Minh họa chất lượng HCSRI, HCSIR và các thuật toán khác qua rand300-01 .. 54 Hình 2.6. Minh họa chất lượng HCSRI, HCSIR và các thuật toán khác qua steinc-01 ...... 55 Hình 2.7. Minh họa chất lượng HCSRI, HCSIR và các thuật toán khác qua steind-01 ...... 55 Hình 3.1. Minh họa chất lượng GST và các thuật toán khác qua bộ dữ liệu e50-01 .......... 70 Hình 3.2. Minh họa chất lượng GST và các thuật toán khác qua bộ dữ liệu e100-01 ........ 71 Hình 3.3. Minh họa chất lượng GST và các thuật toán khác qua bộ dữ liệu e250-01 ........ 71 Hình 3.4. Minh họa chất lượng GST và các thuật toán khác qua bộ dữ liệu rand100-01 .. 71 Hình 3.5. Minh họa chất lượng GST và các thuật toán khác qua bộ dữ liệu rand300-01 .. 72 Hình 3.6. Minh họa chất lượng GST và các thuật toán khác qua bộ dữ liệu steinc-01 ...... 72 Hình 3.7. Minh họa chất lượng GST và các thuật toán khác qua bộ dữ liệu steind-01 ...... 72 Hình 4.1. Minh họa chất lượng TST và các thuật toán khác qua bộ dữ liệu e50-01 ........... 86 Hình 4.2. Minh họa chất lượng TST và các thuật toán khác qua bộ dữ liệu e100-01 ......... 86 Hình 4.3. Minh họa chất lượng TST và các thuật toán khác qua bộ dữ liệu e250-01 ......... 86 Hình 4.4. Minh họa chất lượng TST và các thuật toán khác qua bộ dữ liệu rand100-01 ... 87 Hình 4.5. Minh họa chất lượng TST và các thuật toán khác qua bộ dữ liệu rand300-01 ... 87 Hình 4.6. Minh họa chất lượng TST và các thuật toán khác qua bộ dữ liệu steinc-01 ....... 87 Hình 4.7. Minh họa chất lượng TST và các thuật toán khác qua bộ dữ liệu steind-01 ....... 88 Hình 5.1. Minh họa chất lượng BST và các thuật toán khác qua bộ dữ liệu e50-01 ........ 106 xi Hình 5.2. Minh họa chất lượng BST và các thuật toán khác qua bộ dữ liệu e100-01 ...... 107 Hình 5.3. Minh họa chất lượng BST và các thuật toán khác qua bộ dữ liệu e250-01 ...... 107 Hình 5.4. Minh họa chất lượng BST và các thuật toán khác qua bộ dữ liệu rand100-01. 107 Hình 5.5. Minh họa chất lượng BST và các thuật toán khác qua bộ dữ liệu rand300-01. 108 Hình 5.6. Minh họa chất lượng BST và các thuật toán khác qua bộ dữ liệu steinc-01 ..... 108 Hình 5.7. Minh họa chất lượng BST và các thuật toán khác qua bộ dữ liệu steind-01 ..... 108 Hình 5.8. Minh họa độ lệch chuẩn của các thuật toán qua bộ dữ liệu e50-01 .................. 109 Hình 5.9. Minh họa độ lệch chuẩn của các thuật toán qua bộ dữ liệu e100-01 ................ 109 Hình 5.10. Minh họa độ lệch chuẩn của các thuật toán qua bộ dữ liệu e250-01 ................ 109 Hình 5.11. Minh họa độ lệch chuẩn của các thuật toán qua bộ dữ liệu rand100-01 .......... 110 Hình 5.12. Minh họa độ lệch chuẩn của các thuật toán qua bộ dữ liệu rand300-01 .......... 110 Hình 5.13. Minh họa độ lệch chuẩn của các thuật toán qua bộ dữ liệu steinc-01 .............. 110 Hình 5.14. Minh họa độ lệch chuẩn của các thuật toán qua bộ dữ liệu steind-01 .............. 111 xii MỞ ĐẦU Tối ưu hóa mạng liên quan đến nhiều lĩnh vực như toán ứng dụng, khoa học máy tính, vận trù học, kỹ thuật, mạng truyền thông,… Nhiều bài toán thực tế trong lĩnh vực mạng truyền thông, chẳng hạn như bài toán cây khung truyền thông tối ưu (Optimal Communication Spanning Trees - OCST), bài toán cây Steiner nhỏ nhất (Steiner Minimal Trees - SMT), bài toán cây khung nhỏ nhất với đường kính bị chặn (Bounded Diameter Minimum Spanning Trees - BDMST) [20], bài toán cây khung với chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Trees MRCST) đã được chứng minh thuộc lớp bài toán NP-khó hoặc NP-đầy đủ. MRCST là một bài toán tối ưu đồ thị nổi tiếng; bài toán này lần đầu tiên được giới thiệu bởi T. C. Hu vào năm 1974 qua bài báo “Optimum communication spanning trees” [37]. Bài toán MRCST được xem là một trường hợp đặc biệt của bài toán cây khung truyền thông tối ưu khi mà lượng cầu truyền thông giữa tất cả mọi cặp đỉnh của bài toán OCST đều bằng nhau [9,10,37]. Mô hình toán học của bài toán MRCST có thể phát biểu như sau: Cho G là một đồ thị vô hướng liên thông có chi phí định tuyến không âm trên cạnh. Giả sử T là một cây khung của G. Chi phí định tuyến cho mỗi cặp đỉnh trên T được định nghĩa là tổng các chi phí định tuyến trên các cạnh của đường đi đơn nối chúng trên T và chi phí định tuyến của T được định nghĩa là tổng của tất cả các chi phí định tuyến giữa mọi cặp đỉnh của T. Bài toán MRCST đặt ra là tìm một cây khung có chi phí định tuyến nhỏ nhất trong số tất cả các cây khung của G [10]. Bài toán MRCST đã được chứng minh thuộc lớp bài toán NP-khó [10,13,37]. Bài toán MRCST có nhiều ứng dụng trong lĩnh vực thiết kế mạng truyền thông [7,10,15,27,31,33], chẳng hạn bài toán xây dựng các hệ thống mạng nhằm tối ưu chi phí đường đi trung bình giữa các nút mạng; đặc biệt là ở các mạng ngang hàng – khi mà các nút có xác suất truyền tin và độ ưu tiên là như nhau. Bài toán MRCST cũng tìm được những ứng dụng quan trọng trong lĩnh vực tin sinh học [10,41]. Việc đề xuất thuật toán dạng metaheuristic giải bài toán MRCST có ý nghĩa quan trọng, một mặt, nhằm giải quyết những bài toán ứng dụng thực tiễn vừa nêu; mặt khác, còn là cơ sở để giải quyết những bài toán cây khung tối ưu dạng NP-khó khác trên đồ thị. 1 Bài toán MRCST đã thu hút được sự quan tâm nghiên cứu của nhiều nhà khoa học trong hơn bốn mươi năm qua. Hiện nay đã có hàng loạt thuật toán giải bài toán MRCST được đề xuất và có thể chia chúng làm các hướng tiếp cận sau: Hướng thứ nhất là các thuật toán tìm lời giải đúng. Hướng tiếp cận giải đúng phát triển trên thuật toán nhánh cận được đề xuất bởi R. Dionne và M. Florian vào năm 1979 [30], thuật toán nhánh cận kết hợp với phương pháp sinh cột được đề xuất bởi Matteo Fischetti, Giuseppe Lancia, Paolo Serafini vào năm 2002 [24]. Các thuật toán giải đúng chỉ có thể giải được bài toán MRCST đối với đồ thị có không quá 40 đỉnh và do đó tính ứng dụng thực tiễn của nó không cao [1,24,30]. Hướng thứ hai là các thuật toán tìm lời giải gần đúng cận tỉ lệ, như thuật toán WONG được đề xuất bởi Richard T. Wong vào năm 1980 [31], thuật toán GENERAL STAR được đề xuất bởi Bang Ye Wu và Kun-Mao Chao vào năm 1999 [8], sơ đồ xấp xỉ thời gian đa thức – PTAS được đề xuất bởi Bang Ye Wu và Kun-Mao Chao vào năm 2004 [10], thuật toán xấp xỉ xử lý song song được đề xuất bởi Ching-Lueh Chang và Yuh-Dauh Lyuu vào năm 2008 [12], thuật toán gần đúng cận tỉ lệ được đề xuất bởi Alexandra Hochuli, Stephan Holzer, Roger Wattenhofer năm 2014 [4]. Ưu điểm của các thuật toán này là có sự đảm bảo về mặt toán học theo nghĩa lời giải tìm được gần đúng một cận tỉ lệ α nào đó so với lời giải tối ưu. Hướng thứ ba là các thuật toán heuristic, bao gồm thuật toán ADD được đề xuất bởi Vic Grout vào năm 2005 [41], thuật toán CAMPOS được đề xuất bởi Rui Campos và Manuel Ricardo vào năm 2008 [33]. Các thuật toán ADD, CAMPOS có độ phức tạp thời gian tính tốt nhất trong số tất cả các thuật toán giải bài toán MRCST hiện biết. Thuật toán CAMPOS tìm được lời giải với chất lượng tốt hơn so với các thuật toán WONG ở một số loại đồ thị cụ thể. Hướng thứ tư là các thuật toán metaheuristic. Hướng tiếp cận metaheuristic phát triển trên các thuật toán di truyền, thuật toán tìm kiếm địa phương và thuật toán bầy ong. Hướng tiếp cận này bao gồm thuật toán di truyền mã hóa dạng cạnh – ESCGA được đề xuất bởi Bryant A. Julstrom vào năm 2005 [11], thuật toán di truyền mã hóa dạng dãy số Prüfer – BCGA được đề xuất bởi Bryant A. Julstrom vào năm 2005 [11], thuật toán tìm kiếm leo đồi ngẫu nhiên – SHC được đề xuất bởi Bryant A. Julstrom vào năm 2005 [11], thuật toán tìm kiếm địa phương có sử dụng chiến lược đa dạng hóa lời giải – PBLS được đề xuất bởi Alok Singh vào năm 2008 [5], thuật toán tìm kiếm địa phương– CYCLELS được đề xuất bởi Steffen Wolf và Peter Merz vào năm 2010 [36], thuật toán bầy ong (Artificial Bee Colony - PABC) [6] và thuật toán bầy ong kết hợp với thuật toán tìm kiếm địa phương (ABC+LS) cùng được đề xuất bởi Alok Singh vào năm 2011 [6] – hai thuật toán này được phát triển dựa vào sơ đồ của thuật toán Artificial Bee Colony (ABC) [16,17]. Các thuật toán metaheuristic này cho lời giải với chất lượng tốt hơn các thuật toán giải gần đúng còn lại. Tuy nhiên, hiệu quả của các thuật toán metaheuristic chủ yếu được đánh giá thông qua thực nghiệm mà chưa chứng minh được về mặt toán học. Thời gian tính các 2 thuật toán metaheuristic là chậm hơn rất nhiều so với các thuật toán WONG [10,31], ADD [41], CAMPOS [33]. Mục đích của luận án là phát triển một số thuật toán gần đúng dạng metaheuristic giải bài toán MRCST cho chất lượng lời giải tốt hơn so với các thuật toán có cùng cỡ thời gian tính hoặc đòi hỏi thời gian tính ít hơn khi so sánh với các thuật toán có chất lượng lời giải tương đương hoặc đưa ra lời giải tốt nhất mới cho một số bộ dữ liệu thực nghiệm chuẩn. Các kết quả nghiên cứu của luận án đã được công bố ở 4 bài báo tạp chí và 2 bài báo hội nghị chuyên ngành. Các kết quả chính đạt được của luận án là: Thứ nhất, đề xuất hai thuật toán dạng tìm kiếm leo đồi giải bài toán MRCST là thuật toán HCSRI-MRCST (viết tắt là HCSRI) và thuật toán HCSIR-MRCST (viết tắt là HCSIR); các đề xuất này nhằm giải quyết hiệu quả bài toán MRCST ứng với các loại đồ thị thưa và đồ thị đầy đủ ngẫu nhiên. Các thuật toán HCSRI, HCSIR cho chất lượng lời giải tương đương với các thuật toán metaheuristic mới nhất nhưng với thời gian tính nhanh hơn; xét trên toàn bộ hệ thống dữ liệu thực nghiệm chuẩn; các thuật toán HCSRI, HCSIR cho chất lượng lời giải luôn tốt hơn các thuật toán trước đó WONG, ADD, CAMPOS, ESCGA, BCGA. Thứ hai, đề xuất một thuật toán dạng thuật toán di truyền giải bài toán MRCST là GAMRCST (viết tắt là GST). Thuật toán GST đề xuất phép lai và phép đột biến mới, có định hướng cao đến chi phí định tuyến; các phép lai và phép đột biến này có tính đa dạng và tính tăng cường cao hơn so với các thuật toán di truyền đã được công bố trước đó như ESCGA, BCGA. Thuật toán GST cho lời giải với chất lượng tốt hơn và thời gian tính nhanh hơn các thuật toán di truyền ESCGA, BCGA; thuật toán GST cho lời giải với chất lượng tốt hơn các thuật toán WONG, ADD, CAMPOS, SHC. Thứ ba, đề xuất một thuật toán dạng tìm kiếm Tabu giải bài toán MRCST là TABU-MRCST (viết tắt là TST); đây là vận dụng đầu tiên của tìm kiếm Tabu vào việc giải bài toán MRSCT. Thuật toán TST thừa kế được những ưu điểm của thuật toán tìm kiếm Tabu trong việc giải bài toán tối ưu, thuật toán TST đề xuất một chiến lược đa dạng mới. Thuật toán TST cho chất lượng lời giải tốt hơn các thuật toán đã được công bố trước đó như WONG, ADD, CAMPOS, SHC, PBLS, ESCGA, BCGA trên mọi bộ dữ liệu; thuật toán TST cho lời giải chất lượng tương đương thuật toán PBLS trên các đồ thị đầy đủ Euclid nhưng với thời gian tính nhanh hơn. Thứ tư, đề xuất một thuật toán dạng thuật toán bầy ong giải bài toán MRCST là BEEMRCST (viết tắt là BST). Thuật toán BST đề xuất mới các chiến lược tăng cường hóa và đa dạng hóa; thuật toán BST là vận dụng đầu tiên của thuật toán bầy ong cơ bản [14] vào việc giải bài 3 toán MRCST. Thuật toán BST cho chất lượng lời giải tốt hơn và thời gian tính nhanh hơn các thuật toán metaheuristic đã công bố như ESCGA, BCGA, PABC, ABC+LS trên hệ thống dữ liệu thực nghiệm chuẩn. Luận án được trình bày trong 5 chương. Chương 1 trình bày tổng quan về bài toán MRCST, các ứng dụng của bài toán MRCST, khảo sát các công trình nghiên cứu liên quan và hệ thống dữ liệu thực nghiệm chuẩn cho bài toán MRCST. Chương 2 đề xuất các thuật toán dạng tìm kiếm leo đồi HCSRI, HCSIR giải bài toán MRCST. Chương 3 đề xuất thuật toán di truyền GST giải bài toán MRCST. Chương 4 đề xuất thuật toán tìm kiếm Tabu TST giải bài toán MRCST. Chương 5 đề xuất thuật toán bầy ong BST giải bài toán MRCST. Luận án cũng phân tích ưu nhược điểm của từng thuật toán đối với từng loại dữ liệu thực nghiệm cụ thể và qua đó định hướng phạm vi áp dụng cho từng thuật toán đề xuất. Phụ lục của luận án ghi nhận kết quả thực nghiệm của các công trình nghiên cứu liên quan cho đến thời điểm hiện tại. 4 Chương 1. TỔNG QUAN Chương này giới thiệu tổng quan về bài toán cây khung với chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Tree – MRCST), các ứng dụng của bài toán MRCST, khảo sát các thuật toán giải bài toán MRCST, các tiêu chí đánh giá chất lượng một thuật toán giải gần đúng và hệ thống dữ liệu thực nghiệm chuẩn được sử dụng cho bài toán MRCST. 1.1.BÀI TOÁN MRCST 1.1.1.Một số định nghĩa Cho G = (V(G), E(G)) là một đồ thị vô hướng, liên thông, có trọng số không âm trên cạnh; trong đó V(G) là tập gồm n đỉnh, E(G) là tập gồm m cạnh, w(e) là trọng số của cạnh e, e  E(G). Trong suốt luận án này, nếu G là đồ thị, thì ký hiệu V(G) sẽ được sử dụng để chỉ tập đỉnh, còn E(G) sẽ được sử dụng để chỉ tập cạnh của đồ thị G. Định nghĩa 1.1 [10] (Chi phí định tuyến giữa một cặp đỉnh). Cho T = (V(T), E(T)) là một cây khung của G, trọng số trên cạnh e được hiểu là chi phí định tuyến của cạnh e, ta gọi chi phí định tuyến (routing cost) của một cặp đỉnh (u,v) trên T, ký hiệu là dT(u,v), là tổng chi phí định tuyến của các cạnh trên đường đi đơn (duy nhất) nối đỉnh u với đỉnh v trên cây T. Định nghĩa 1.2 [10] (Chi phí định tuyến của một cây khung). Cho T = (V(T), E(T)) là một cây khung của G, chi phí định tuyến của T, ký hiệu là C(T), là tổng chi phí định tuyến giữa mọi cặp đỉnh thuộc cây T, tức là: C (T )   u ,vV (T ) dT (u, v). (1-1) Bài toán MRCST: Cho đồ thị G được định nghĩa như trên, bài toán đặt ra là trong số tất cả các cây khung của đồ thị G cần tìm một cây khung có chi phí định tuyến nhỏ nhất. 5 Bài toán này được đặt tên là bài toán cây khung với chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Tree-MRCST) [10]. Bài toán MRCST đã được chứng minh thuộc lớp bài toán NP-khó, nghĩa là ngoại trừ P = NP, không tồn tại thuật toán đa thức để giải nó [10,13,31]. Ví dụ 1.1. Xét cây T ở hình 1.1. 1Hình 1.1. Minh họa cách tính chi phí định tuyến của một cây theo định nghĩa Theo công thức (1-1), ta có: dT(v1,v2) + dT(v1,v3) + dT(v1,v4) + dT(v1,v5) + dT(v1,v6) + dT(v2,v3) + dT(v2,v4) + dT(v2,v5) + dT(v2,v6) + dT(v3,v4) + dT(v3,v5) + dT(v3,v6) + dT(v4,v5) + dT(v4,v6) + dT(v5,v6) = 117. Do dT(vi,vj) = dT(vj,vi), nên C(T) = 117  2 = 234. Việc tính chi phí định tuyến của một cây khung trực tiếp theo công thức (1-1) đòi hỏi thời gian tính O(n2) theo cấu trúc dữ liệu ma trận trọng số. Tuy nhiên, trên cơ sở đưa ra khái niệm tải định tuyến (routing load), công trình [10] đã chỉ ra cách tính chi phí định tuyến của một cây khung với độ phức tạp tuyến tính theo cấu trúc dữ liệu cây có gốc. Định nghĩa 1.3 [10] (Tải định tuyến một cạnh của cây khung) Cho T = (V(T), E(T)) là một cây khung của đồ thị G. Nếu loại khỏi cây T một cạnh e thì T sẽ được tách ra thành hai cây con T1 và T2 với hai tập đỉnh tương ứng là V(T1) và V(T2). Ta gọi tải định tuyến của cạnh e, ký hiệu là l(T,e), là giá trị 2×V(T1)×V(T2). Từ định nghĩa, dễ thấy rằng tải định tuyến của cạnh e chính bằng số lượng đường đi trên cây T có chứa cạnh e. 6