BỘ GIÁO DỤC ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIÊN KỸ THUẬT QUÂN Sự PHAM ĐÌNH THÀNH NGHIÊN CỨU PHÁT TRIEN MỘT Số THUẬT TỐN TIẾN HĨA GIẢI BÀI TỐN CÂY KHUNG PHÂN CỤM ĐƯỜNG ĐI NGẮN NHÁT LUẬN ÁN TIẾN Sĩ TOÁN HỌC HÀ NỘI - NĂM 2021 BỘ GIÁO DỤC ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIÊN KỸ THUẬT QUÂN Sự PHAM ĐÌNH THÀNH NGHIÊN CỨU PHÁT TRIEN MỘT Số THUẬT TỐN TIẾN HĨA GIẢI BÀI TỐN CÂY KHUNG PHÂN CỤM ĐƯỜNG ĐI NGẮN NHÁT Chuyên ngành : Cơ sở toán học cho Tin học Mã số : 46 01 10 LUẬN ÁN TIẾN Sĩ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS TS Huỳnh Thị Thanh Bình HÀ NỘI - NĂM 2021 LỜI CAM ĐOAN Nghiên cứu sinh cam đoan luận án cơng trình nghiên cứu hướng dẫn PGS.TS Huỳnh Thị Thanh Bình Luận án có sử dụng thơng tin trích dẫn từ nhiều nguồn tham khảo khác thơng tin trích dẫn ghi rõ nguồn gốc Các số liệu, kết luận án trung thực chưa công bố cơng trình nghiên cứu tác giả khác GIẢNG VIÊN HƯỚNG DẪN PGS.TS Huynh Thị Thanh Bình NGHIÊN CỨU SINH Phạm Đình Thành LỜI CÁM ƠN Lời đầu tiên, nghiên cứu sinh xin gửi lời cảm ơn chân thành sâu sắc tới giáo viên hướng dẫn PGS TS Huỳnh Thị Thanh Bình tận tình dạy bảo cung cấp gợi ý quy báu giúp tơi nâng cao kiến thức hồn thành tốt luận án Nghiên cứu sinh xin bày tỏ lồng biết ơn sâu sắc tới PGS.TS Bùi Thu Lâm, Học viện Kỹ thuật Quân nhiệt tình hỗ trợ đưa định hướng, lời khuyên suốt q trình tơi thực luận án Nghiên cứu sinh xin bày tỏ lồng biết ơn tới Ban giám đốc Học viện Kỹ thuật Quân sự, Ban chủ nhiệm đặc biệt thầy cô công tác khoa Công nghệ thông tin hết lồng truyền đạt kiến thức tạo điều kiện thuận lợi để tơi hồn thành chương trình học tập thực luận án nghiên cứu Nghiên cứu sinh xin trân trọng cảm ơn Ban Giám hiệu trường Dại học Tây Bắc, Ban chủ nhiệm đồng nghiệp khoa Khoa học tự nhiên - Công nghệ, trường Dại học Tây Bắc tạo điều kiện giúp đỡ nghiên cứu sinh thời gian học tập Tôi xin trân trọng cảm ơn thầy cô trường tham gia đọc nhận xét luận án cấp Bộ môn, cấp Cơ sở, cấp phản biện độc lập, cấp Trường, cho ý kiến q báu để tơi hồn thiện luận án Tôi xin gửi lời cảm ơn tới thành viên phồng thí nghiệm Mơ hình hóa, mơ tối ưu hóa(Modelling, Simulation and Optimization lab - MSO Lab), trường Dại học Bách khoa Hà Nội, người ln nhiệt tình giúp đỡ tơi suốt trình học tập nghiên cứu Cuối cùng, nghiên cứu sinh chân thành bày tỏ lồng cám ơn tới gia đình bạn bè kiên trì, chia sẻ, động viên nghiên cứu sinh suốt trình học tập hoàn thành luận án H Nội, ngày tháng năm 2021 NGHIÊN CỨU SINH Phạm Dình Thành MỤC LỤC DANH MỤC THUẬT NGỮ VÀ TỪ VIET TÁT DANH MỤC BẢNG BIÊU DANH MỤC HÌNH ẢNH v viii x GIỚI THIÊU Chương TỔNG QUAN 1.1Thuật tốn tiến hóa 1.1.1 Tổng quan thuật tốn tiến hóa 1.1.2 Mã hóa lời giải thuật tốn tiến hóa 1.1.3 Khởi tạo quần thể 1.1.4 Chọn lọc cá thể cha mẹ 1.1.5 Toán tử lai ghép 1.1.6 Toán tử đột biến 10 1.1.7 Chọn lọc cá thể cho hệ 10 1.1.8 Điều kiện dừng thuật toán 11 1.2Thuật toán tiến hóa đa nhân tố 11 1.2.1 Bài tốn tiến hóa đa nhân tố 11 1.2.2 Cơ giải thuật tiến hóa đa nhân tố 13 1.2.3 Mã hóa cá thể 14 1.2.4 Các toán tử lai ghép đột biến 15 1.2.5 Cơ chế đánh giá có chọn lọc 16 1.3Bài toán phân cụm đường ngắn 17 1.3.1 Một số định nghĩa 17 1.3.2 Phát biểu toán 21 1.3.3 ững dụng toán .24 1.3.4 Tổng quan tình hình nghiên cứu .24 1.4Kết luận chương 30 Chương THUẬT TOÁN XAP XỈ GIẢI BÀI TOÁN CÂY PHÂN CỤM VỚI ĐƯỜNG ĐI NGAN NHẤT 31 2.1Thuật tốn xây dựng khung hình 31 2.1.1 Lược đồ thuật toán 31 2.1.2 Độ phức tạp thuật toán .33 2.1.3 Thuật tốn dạng hình đồ thị metric 34 2.2Thuật toán tham lam ngẫu nhiên 36 2.2.1 Các bước thuật toán HB-RGA 37 2.2.2 Thuật toán tham lam ngẫu nhiên tìm cạnh nối cụm 39 2.2.3 Độ phức tạp thuật toán .41 2.3Đánh giá thuật toán .43 2.4Kết luận chương 43 Chương THUẬT TỐN TIÊN HĨA GIẢI BÀI TOÁN CÂY PHÂN CỤM VỚI ĐƯỜNG ĐI NGAN NHẤT 45 3.1Thuật tốn tiến hóa dựa mã Cayley 45 3.1.1 Lược đồ thuật toán 45 3.1.2 Mã hóa cá thể 46 3.1.3 Phương pháp khởi tạo cá thể 49 3.1.4 Toán tử lai ghép 49 3.1.5 Toán tử đột biến 51 3.2Hướng tiếp cận dựa giảm khơng gian tìm kiếm thuật tốn tiến hóa 52 3.2.1 Cách tiếp cận 52 3.2.2 Phương pháp phân rã toán CluSPT 52 3.2.3 Biểu diễn cá thể 55 3.2.4 Phương pháp khởi tạo cá thể 58 3.2.5 Toán tử lai ghép 60 3.2.6 Toán tử đột biến 61 3.2.7 Cách đánh giá cá thể 62 3.3Đánh giá thuật toán .63 3.4Kết luận chương 64 Chương THUẬT BÀI TOÁN TỐN TIÊN CÂY HĨA PHÂN NGẮN NHẤT ĐA CỤM NHÂN VỚI Tố ĐƯỜNG GIẢI ĐI 65 4.1Ý tưởng đề xuất thuật toán G-MFEA 66 4.2Lược đồ thuật toán G-MFEA 68 4.3Biểu diễn cá thể 70 4.4Phương pháp khởi tạo cá thể 72 4.5Toán tử lai ghép 74 4.6Toán tử đột biến 77 4.7Phương pháp giải mã .78 4.8Cách tác vụ thứ hai cải thiện chất lượng lời giải 80 4.9Đánh giá thuật toán .83 4.10 Kết luận chương 84 Chương KẾT QUẢ THựC NGHIÊM 86 5.1Dữ liệu thực nghiệm đánh giá lời giải 86 5.1.1 Đồ thị metric 86 5.1.2 Đồ thị đầy đủ phi metric 87 5.1.3 Tiêu chí đánh giá .88 5.1.4 Môi trường, tham số thực nghiệm 89 5.2Kết thực nghiệm .89 5.2.1 Đồ thị metric 90 5.2.2 Đồ thị đầy đủ phi metric .104 5.3Kết luận chương 110 DANH MỤC CƠNG TRÌNH CƠNG Bố 116 TÀI LIÊU THAM KHẢO 117 129 PHỤ LỤC DANH MỤC THUẬT NGỮ VÀ TỪ VIET TÁT Các thuật ngữ Tiếng Anh Tiếng Việt Age based selection Chọn lọc dựa theo tuổi Assortative mating Cơ chế ghép đôi loại Chromosome Nhiễm sắc thể Clustered spanning tree Cây khung phân cụm Control algorithm Thuật toán điều khiển Cost Chi phí Critical value Giá trị tới hạn Decompose Phân rã Exploitation Khai thác Exploration Khai phá Factorial rank Xếp hạng tác vụ Factorial cost Chi phí tác vụ Fitness Giá trị thích nghi Fitness based selection Chọn lọc dựa theo giá trị thích nghi Genotype Kiểu gen Global tree Cây khung toàn cục Implicit genetic transfer Trao đổi vật chất di truyền tiềm ẩn Individual Cá thể Inter-cluster edge Cạnh liên cụm Locality Cục Local root Gốc cục Local tree Cây khung phận Metric graph Đồ thị metric Non-parametric statistic Thống kê phi tham số Phenotype Population Kiểu hình Quần thể Post-hoc statistical Thống kê hậu kiểm Random mating probability Xác suất ghép cặp ngẫu nhiên Random selection Chọn lọc ngẫu nhiên Rank selection Chọn lọc dựa theo thứ hạng quần thể Scalar fitness Giá trị thích nghi vơ hướng Tiếng Anh Tiếng Việt Selective evaluation Cơ chế đánh giá có chọn lọc Skill factor Chỉ số kỹ phù hợp Sparse graph Đồ thị thưa Termination condition Điều kiện dừng Tournament selection Chọn lọc cạnh tranh Vertical cultural transmission Truyền lại đặc tính theo chiều dọc Các từ viết tắt Từ viết tắt Ý nghĩa AAL Thuật toán xấp xỉ AAL CluSPT-Lib CluSPT Library C-MFEA Thuật tốn tiến hóa đa nhân tố C-MFEA C-EA Thuật tốn tiến hóa sử dụng mã Cayley C-EA CluSteinerTP Bài toán Steiner phân cụm CluTSP Bài toán người du lịch phân cụm CluSPT Bài toán phân cụm đường ngắn CESA Xây dựng tập cạnh lời giải EM Tiến hóa đa nhiệm EA Thuật tốn tiến hóa GTSP Bài tốn người du lịch tổng quát GMSTP Bài toán khung nhỏ tổng quát GA Thuật toán di truyền G-MFEA Thuật toán tiến hóa đa nhân tố G-MFEA HB-RGA Thuật tốn xấp xỉ dựa trẽn thuật toán tham lam ngẫu nhiên M4CRST Thuật tốn tạo khung ngẫu nhiên MCST Tìm khung có chi phí nhỏ InterCluMRCT Bài tốn khung phân cụm với chi phí định tuyến liên cụm nhỏ CluMRCT Bài tốn khung phân cụm có chi phí định tuyến nhỏ MSTP Bài tốn khung nhỏ MFO Tối ưu hóa đa nhân tố MOO Tối ưu hóa đa mục tiêu Từ viết tắt Ý nghĩa MFEA Thuật tốn tiến hóa đa nhân tố NCX Toán tử lai ghép thuật toán N-EA N-EA Thuật tốn tiến hóa N-EA NMO Tốn tử đột biến PSO Tối ưu bầy đàn RGA Thuật toán tham lam ngẫu nhiên RPD Tỉ lệ phần trăm chênh lệch tương đối SPTA Thuật toán đường ngắn SOO Tối ưu hóa đơn mục tiêu SLA Thuật tốn dạng hình SLA SLA-M Thuật tốn xác SLA-M STP Bài toán Steiner TSP Bài toán người du lịch USS Khơng gian tìm kiếm chung [1095] £ 25eil101-5x5 [1096] í 25eil51[1123] ;§ 25eil76-5x5 [1137] 25rat995x5 [1151] 0-4x7 [1165] 0-5x6 [1179] 0-5x5 [1193] 28kroA10 30kroB10 35kroB10 36eil1016x6 [1207] 42rat996x7 [1221] 4berlin522x2 [1235] 4eil512x2 [1249] 4eil762x2 [1263] 4pr76-2x2 [1277] 6berlin522x3 [1291] 6pr76-2x3 [1305] 6st70-2x3 [1319] 8berlin522x4 [1333] 9eil1013x3 [1347] 9eil513x3 [1361] 9eil763x3 [1375] 9pr76-3x3 [1389] 18pr4393x6 [1398] 20pr4394x5 [1408] 25a2805x5 [1422] 25gil2625x5 [1436] 25pcb442 [1449] -5x5 [1603] íỌ [1604] 45 [1605] s [1602] [1097] 11580 [1099] [1101] 603.5 609.1 [1103] [1105] [1107] [1109] 362 0.5 3711 3780 [1124] [1100] [1125] 12 [1102] [1126] 12 [1127] [1106] [1128] [1129] [1130] 7512 193.1 193.1 2194 0.1 2264 2312 [1138] [1139] [1140] [1141] [1142] [1143]1 [1144] 28158 11395 11400 11418.9 0.2 1754.1 11869 [1152] [1153] [1154] [1155] [1156][1157] [1158] 91859.3 33101.6 34129.0 34532.3 1.1 38682.6 41334.2 [1166] [1167] [1168] [1169] [1170][1171] [1172] 35707.1 97934.6 98976.7 99205.7 0.6 01813.7 04967.3 [1180] [1181] [1182] [1183] [1184][1185] [1186] 97029.1 [1194] 29078.7 [1195] 29122.6 [1196] 29832.3 [1197] 0.6 [1198]33662.2 [1199] 37003.4 [1200] 10294 [1208] 19472 [1222] [1117] 649.20 [1119] 670.5 [1121] 1.9 [1112] [1131][1114] [1132] 24 5.4 [1145]146.2 [1146] [1115] 8213.3 127.9 [1133] 6241.1 [1147]20993 [1118] [1134] 12 219.101 [1148] [1120] [1135] 12 245.2 [1149] [1122] [1136] 2.4 [1150] 4.2 16441.2 [1159][1160] 6.2 59023.4 [1173][1174] 3.6 25726.7 [1187][1188] 6.1 [1201]42049.9 [1202] 6[1161] 84.2 33971 9.8 155.2 [1175] 43836 2.4 121.5 [1189] 29863 3.2[1203]12391 131.4 1434.901 [1162] 36501.10 [1176] 00596.80 [1190] 30935.103 [1204] 11485.9 [1163] 38342.8 [1177] 02209.8 [1191] 32840.4 [1205] 0.8 [1164] 3.9 [1178] 2.2 [1192] 2.9 [1206] 4028 [1214] 9182.2 [1228] 4.6 [1215]446.8 [1216] 3.2 [1229] 20172 [1230] 221.8 [1217]27860 213.0 [1231]38526 929.209 [1218] 187.002 [1232] 3.4 [1220] 5.5 [1234] 3287.9 [1242] 1901 [1256] 2955.4 [1270] 0.0 31829 [1243][1244] 0.1 272.3 [1257][1258] 0.2 [1271]610.2 [1272] 65.4 [1245] 2422.7 27.6 [1259] 4052.6 37.4 [1273] 72855 3287.90 [1246] 898.50 [1260] 948.704 [1274] 981.6 [1219] 393.5 [1233] 3287.9 [1247] 1898.5 [1261] 2948.74 [1275] 46682.1 [1284] 0.5 2128.6 32354.6 [1296][1297] [1298] 1.2 48713.1 59658.8 [1310] [1311] [1312] 0.8 3478 3525 [1324] [1325]2 [1326] 0.7 27060 [1338]6783.2 [1339] [1340] 1.2 3184 3274 [1352] [1353] [1354] 0.9 [1285]38744.6 [1286] 0.7 37246.7 [1299][1300] 5.4[1287]43918 64.6 3[1301] 36.7 91785 42693.003 [1288] 2128.606 [1302] 0.0 [1290] 0.0 [1304] 1.8 28666.8 [1313][1314] 1.4 980.8 [1327] [1328] 1.0 33909.4 [1341][1342] 2.9 41.6 [1315] 5064.2 45.7 [1329]41646 55.5 [1343] 48275.70 [1316] 476.70 [1330] 6783.203 [1344] 42693 [1289] 2128.6 [1303] 48507.9 [1317] 3476.7 [1331] 26795.3 [1345] 0.7 1963 [1366] 1916 [1367] [1368] 0.7 2999 3057 [1380][1381] [1382] 1.2 58349.3 67987.4 [1393] 1.8 1525370.2 1553940.8 [1403] 1.6 2035939.4 2075349.7 [1415] [1413] [1414]4 5.0 5472.3 [1355]517.9 [1356] [1357] 75.5 2.9 2626.8 [1369]323.6 [1370] [1371] 37.7 4.1 551.5 4039.2 37.5 [1383][1384] [1385] 83529 2.6 20920.1 5.8 50.9 [1394] 5.6 5113367.5 6325195.4 329.8 [1404] 4.9 4568690.6 6543749.5 230.8 [1416] [1417] [1418] 10411 117.601 [1358] 908.002 [1372] 0.1 [1360] 0.1 [1374] 937.40 [1386] 53685.60 [1395] 483618.33 [1405] 993350.75 [1419] 120.2 [1359] 909.9 [1373] 938.6 [1387] 53849.7 [1396] 488675.8 [1406] 000099.7 [1420] 1.1 44268 [1427]3408.0 [1428]3 [1429] 1.4 2172.6 32674.8 [1441][1442] [1443] 1.6 86167.2 02854.1 6.2 149.7 [1430] 64023 [1431] 5.3[1432]78711 6.6 156.8 [1444] 52965 [1445] 1970190.2 8.4 2542620.4 243.2 2123.083 [1433] 1116.217 [1446] 42388.8 [1434] 31372.9 [1447] 1.7 [1435] 2.4 [1448] 62391.2 2.9 850.7 3852 [1209] 850.7 [1210] [1211] 0.0 [1212] 3977 [1213] 902.1 902.5 890 0.0 9093 [1223] [1224] [1225] [1226] [1227]2 70649 23287 23287 23395.9 0.5 3287.9 [1236] [1237] [1238] [1239] [1240] [1241] 5187 898.5 898.5 1915 0.9 1898 [1250] [1251] [1252] [1253] [1254] [1255] 68821 948.7 2974.4 0.9 2948.4 [1264] [1265] 948.8 [1266] [1267] [1268][1269] 607169.6 0.7 [1278] 42693.0 [1279] 42693.0 [1280] 45997.3 [1281] [1282]42693.0 [1283]3 80429.1 [1292] 269147.1 [1306] 8147 [1320] 58925 [1334] 321286 [1293] 48275.7 [1307] 476.7 [1321] 267833 [1335] 32130.6 [1295] 32295.7 [1294] 48884.9 56228.6 [1308] [1309] 476.7 3503 [1322] [1323] 26854.3 26969.8 [1336] [1337] 9560 117.6 135.4 3154 [1348] [1349] [1350] [1351] 4642 907.7 912.8 1921 [1362] [1363] [1364] [1365] 6659 937.4 938.4 2956 [1376] [1377] [1378] [1379] 344518.1 53400.6 54995.8 60230.3 [1390] [1391] 1471788.7 [1392] 827227.1 1475993.8 498114.4 [1399] [1400] [1401] [1402] 384342.3 [1409] 978001.3 [1410] 993816.3 [1411] 008663.3 [1412] 15284.3 41690 42016 42150 [1423] [1424] [1425] [1426] 95797 30649 30825 31079.7 [1437] [1438] [1439] [1440] 210900.7 40883.3 48160.1 52959.6 [1111][1113] 4.9 331.0 52573.88 0.0 [1248] 0.0 [1262] 0.0 [1276] 0.0 [1318] 0.0 [1332] 0.0 [1346] 0.0 [1388] 0.1 [1397] 1.1 [1407] 1.1 [1421] s