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 TAN QUOC CAC THUAT 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 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHAN TAN QUOC CAC THUAT TOAN GAN DUNG GIAI BAI TOAN 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. Nguyễn Đức Nghĩa Hà Nội -2015 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 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 dé 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 TT AM T DU N ro na cư hrrrf ft tt at ötgưn: tê tri tư tiitgrrffEc tEctrrrtfertittgrririeittrtrrrterrsitrrrei i 0919.Ỏ ii MUC LUC weseesssssssssssescssseesssseesssssssessssssssvesssseseessensesssecesssseesssessassvestssuiseessesesnsveeesseseetsneesssseseease iii DANH MUC CAC KY HIEU VA CHU VIET TAT.esssscssssssessosesssssseesosseeessseesessveseasinessavesees vii DANH MUC CAC BANG wiveeessssssssssssssssesssssssesssessssssecsssssessssecsarsvesessesssssseseessueeessussessueesssieeeeave ix DANH MUG CACHING, VE ssccrensenncamearanmmnnmacnamannmnmaa xi 62.Một số định nghĩa.Thuật toán tinh chi phí định tuyến của cây khung .Đánh giá chỉ phí định tuyến của cây khung.- 22 cce222:eccrseeerrx 9 ;30/e6)/c ma.Ứng dụng của bài toán MRCST trong lĩnh vực thiết kế mạng .Ung dung cua bai toan MRCST trong linh vực tin sinh học.CÁC NGHIÊN CỨU LIÊN QUAN BÀI TOÁN Ä⁄#CST7.--©ccs¿+ccscrsceei 12 ToS PU SGA S188 CUT croyons12x456/7603012/0072008/012168800903013/0073090⁄412R02i0000310EHP20m0A04V02E0//1021 12 1. Thuat toán gần đúng cận tỉ lệ. Thuật toán heuristic.

Thuật toán metaheuristic .Danh sách các thuật toán giải bài toán Ä4RCS7 hiện biẾT.TIÊU CHÍ ĐÁNH GIÁ THUẬT TOÁN.----¿--2¿£©22+++tc+xve+tzkxrcrrvrecer 26 1.HỆ THÓNG DỮ LIỆU THỰC NGHIỆM CHUẢN.Đồ thị đầy đủ Euelid.Đồ thị đầy đủ ngẫu nhiên.KHẢO SÁT THỰC NGHIỆM CÁC THUẬT TOÁN GIẢI BÀI TOÁN MRCST.Cấu hình máy tính thực nghiệm các thuật toán.Chất lượng lời giải.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.KÊẾT LUẬN CHƯNG l.--2-+¿++£t©E+2EEE£EEEEt2EEEtEEEEEEEEEEEEEtEEEkrrrrrrrrrree 37 Chương 2. THUẬT TOÁN TÌM KIẾM LEO ĐÔI.CÂY KHUNG LÂN CẬN. THUAT TOAN HCSRI -.Ý tưởng thuật toán #CSRI.Sơ đồ thuật toán HŒSRI.Độ phức tạp của thuật toán HCSRI 42 bcN))0/.Y tưởng thuật toán fCSSÏR .Sơ đồ thuật toán ZC/SïR.Độ phức tạp của thuật toán #TCS7Ñ. ¿St tk nhiệt 44 2.THỰC NGHIỆM VÀ ĐÁNH GIÁ.Môi trường thực nghiệm.Tham số thực nghiệm.Chất lượng lời giải.Hinh vé minh hoa chat lượng HCSRI, HCSIR voi cac thuat toan khac .KÉT LUẬN CHƯƠNG 2.

Xe 55 Chương 3. THUẬT TOÁN DI TRUYN.- 22-52 SSt2EESESEE222EE1227121221. 56 ki ?00vïe cv.Phép chọn ÏỌC .--- ¿ch vn HH HH HT HH He 62 3.Sơ đồ thuật toán GS7.Độ phức tạp của thuật toán ŒS7.THUC NGHIEM VA DANH GIA.Môi trường thực nghiỆm. + + + 3 S3 xxx về ng HH rệt 64 3.Chất lượng lời giải.

65 3:2:4;ThHối gian tinh cns6s0550561166053.Hình vẽ minh họa chất lượng thuật toán ŒS7 với các thuật toán khác .KÉT LUẬN CHƯƠNG 3. 22-2222 222++222E+ESEEEEtESEEEEetEEEEreErkvrrrrrrrrrrrrrree 73 Chương 4. THUẬT TOÁN TÌM KIẾM TA BU .- 22 222 ©2S+22CS+S2EEtSEExErEeesrxrerrei 74 iv F00009): ae.Ý tưởng và một số khái niệm của thuật toán tìm kiếm Tabu.Thuật toán 757 tìm bước chuyển tốt nhất .-----¿- -¿©csz+vxe+rxsesrxrerree 75 4.Thuật toán 7S7 cập nhật danh sách Tabu.Chiến lược đa dạng hóa lời giải của thuật toán 7S7.----2+:cse+rsccree 76 4:1:5:Sơ đô của thuật LIấn TT tssxss tá nhai ton ga ta tha Hững ltlØgG3A Gia tsggthöygagug34 77 4.Độ phite tap ctia thuat toan TST.THỰC NGHIỆM VÀ ĐÁNH GIIÁ.2--©2222+222+t2S2EAEEE2EEEEEEEEererrkrrrrrrrcee 79 L VAN (00 0303 1.Tham số thực nghiệm.2--22©+++2SVE+2EEE2E122221522731E12713122121E 222 Xe 79 1:273:Chái lượng lời giẾi:eeresgtriotriatotrittgtttlqi4SÐ9qSDIIGSRSHRERHSGSIRGIdãGttagi 80 ' 5w 8n ẽ ẽ.Hình vẽ minh họa chat lượng thuật toán 7%7 với các thuật toán khác.KÉT LUẬN CHƯƠNG 4. THUAT TOAN BAY ONG o.

THUAT TOAN BAY ONG CƠ BẢN. THUAT TOAN BST .Tạo quần thể ban đầu.Phan nhOm ac Ca thé. Timedy hung Yan Cty eissicesessversseeseirersnrerenenversenerrnnnnnnnnin enn 93 5.Chiến lược đa dang héa 160i gidi.Sơ đồ của thuật toán BS7.Độ phức tạp của thuật toán BST.THỰC NGHIỆM VÀ ĐÁNH GIÁ .Tham số thực nghiệm. ee 98 Sĩ313:Cháf Tương lời gÌÃÌ:sesprestititiattttiGINTSIOALGESĐRtBSGIISERHGRIGiStRSRSiĐlBSStrtuqieat 99 5.

THO: gian Sẽ.Hinh vé minh hoa chat lugng thuat toan BST với các thuật toán khác.Hinh vé minh họa độ lệch chuẩn của các thuật toán .KÉT LUẬN CHƯƠNG 5.--222 222222 2222Z222E2222213222221E1233E2221 ezErrrcrrkr 111 KET LUAN VÀ HƯỚNG PHÁTT TRIÊN.ÒÒỎ 113 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BÔ CỦA LUẬN ÁN. KÉT QUẢ THỰC NGHIỆM TỪ CÁC CÔNG TRÌNH LIÊN QUAN. KET QUA THUC NGHIEM CAC THUAT TOAN WONG, ADD, CAMPOS. KET QUA THUC NGHIEM CAC THUAT TOAN ESCGA, BCGA.

KET QUA THUC NGHIEM CAC THUAT TOAN SHC, PBLS. KET QUA THUC NGHIEM CAC THUAT TOAN PABC, ABC+LS. SO SANH CHI PHI ĐỊ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 Tiếng Anh Tiếng Việt MRCST | 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Œ) Routing Cost Chỉ phí định tuyên cây khung 7 Ke) Routing Load Tai dinh tuyén cua canh 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 dia phương TABU Tabu Search Algorithm Thuật toán tìm kiêm Tabu GA Genetic Algorithm Thuật toán di truyền PABC Artificial Bee Colony Algorithm | Thuật toán bây ong nhân tạo ABC+LS | 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 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 PTAS Polynomial Time Approximation | Sơ đô xâp xi thời gian đa thức Scheme a.

-Approximation Algorithm Thuật toán gân đúng cận tỉ lệ ø Network Optimization Tôi ưu hóa mạng SD Standard Deviation Độ lệch chuân Bioinformatics Tin sinh hoc MSA Multiple Sequence Alignments So sánh đa trình tự HCSRI 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 MRCS7 vii HCSIR HCSIR-MRCST Thuật toán tìm kiêm leo đôi dạng chèn trudc-loai sau giai bai toan MRCST GST GA-MRCST Thuat toan di truyén giai bai toan MRCST TST TABU-MRCST Thuat toan Tabu giai bai toan MRCST BST BEE-MRCST Thuật toán bây ong giải bài toán M/RCS7 Vili Bang 1. DANH MUC CAC BANG Danh sách các thuật toán điển hình giải bài toán ACST.-----: 26 Thông tin các đồ thị đầy đủ Euclid trong 8jMRCST.--- 2c: 30 Thông tin các đồ thị đầy đủ ngẫu nhiên trong 8DRCS7.--- 31 Thông tin các đồ thị thưa trong ÿARCST.---¿- 22s se+cEvetzEvrrseee 31 Cấu hình máy tính thực nghiệm các thuật toán. - -:- 5c c+ssxsvssesx 32 Thời gian tính các thuật toán trước khi quy đồi.--s5¿©5s+¿ 35 Thời gian tính các thuật toán sau khi quy đổi.---:--:2:scecccscc: 35 Kết quả thực nghiệm thuật toán /CSR1, HCSIR trên đồ thị đầy đủ Euclid. 48 Kết quả thực nghiệm /7CSR1, ICSIR trên đồ thị đầy đủ ngẫu nhiên.

49 Kết quả thực nghiệm các thuật toán HCSRI, HCSIR trên đồ thị thưa. 49 So sánh chi phí định tuyến thuật toán #CSÑ/ với các thuật toán khác. 50 So sanh chi phi dinh tuyén thuat toan HCS/R voi cac thuat toan khac. 51 So sanh thoi gian tinh thuat toan HCSRI voi cac thuat toan khác.

32 So sánh thời gian tính thuật toán CS7# với các thuật toán khác. 33 Kết quả thực nghiệm thuật toán G$7 trên đồ thị đầy đủ Euelid. 67 Kết quả thực nghiệm thuật toán GS7 trên đô thị day đủ ngẫu nhiên. 68 Kết quả thực nghiệm thuật toán ŒS7 trên đồ thị thưa.------: 68 So sánh chỉ phí định tuyến thuật toan GST với các thuật toán khác.

69 So sanh thoi gian tinh thuat toan GST với các thuật toán khác. 70 Két quả thực nghiệm thuật toán 757 trên đồ thị đầy đủ Euclid. 82 Kết quả thực nghiệm 757 trên đồ thị đầy đủ ngẫu nhiên.----: 83 Kết quả thực nghiệm thuật toán 757 trên ñm voecccecseccseccecessecssecsecesneeeveeses 83 So sánh chi phí định tuyến thuật toán 7S7 với các thuật toán khác. 84 So sánh thời gian tính của thuật toán T57 với các thuật toán dang ca thé.

85 So sánh thời gian tính của thuật toán TS7 với các thuật toán dạng quần thê. 85 Kết quả thực nghiệm thuật toan BST trén dé thi day du Euclid Kết quả thực nghiệm thuật toán BST trén dé thi day đủ ngẫu nhiên. Kết quả thực nghiệm thuật toan BST trên đồ thị thưa. So sánh thực nghiệm của thuật toán 8S7 với các thuật toán đơn lời gi So sánh thực nghiệm của thuật toán 8S7 với các thuật toán đa lời giải.

104 Các bộ dữ liệu 8S7 cho lời giải chất lượng tốt hơn thuat toan ABC+LS. So sánh thời gian tính thuật toán BST vdi cac thuat toan don 10i giải. 106 So sánh thời gian tính thuật toán S7 với các thuật toán đa lời giải. 106 Thực nghiệm WONG, 4DD, CAMPOS trên đồ thị đầy đủ Euclid.

120 Thực nghiệm WONG, ADD, CAMPOS trén đồ thị đầy đủ ngẫu nhiên. 121 Thuc nghiém thuat toan WONG, ADD, CAMPOS trén đồ thị thưa. 121 Thực nghiệm thuật toán ESCG4, BCG4 trên đồ thị đầy đủ Euelid. 122 Kết quả thực nghiệm ZSCG4, 8CG4 trên đồ thị đầy đủ ngẫu nhiên.

123 Kết quả thực nghiệm thuật toan SHC, PBLS trén dé thi day đủ Euclid. 124 Kết quả thực nghiệm thuật toán SHC, PBLS trén đồ thị đầy đủ ngẫu nhiên. 125 Kết quả thực nghiệm các thuật toán S⁄C, PBLS trên đồ thị thưa.