Luận án Tiến sĩ Toán học: Nghiên cứu phát triển một số thuật toán tiến hóa giải bài toán cây khung phân cụm đường đi ngắn nhất

Mục tiêu nghiên cứu chính của luận án là xây dựng các thuật toán xấp xỉ để giải bài toán cây phân cụm đường đi ngắn nhất (Clustered ShortestPath Tree Problem - CluSPT), trong đó luận án tập trung vào hai hướng: sử dụng thuật toán tiến hóa (chương 3) và thuật toán tiến hóa đa nhân tố (chương 4).
Nội dung trích xuất từ tài liệu:
Luận án Tiến sĩ Toán học: Nghiên cứu phát triển một số thuật toán tiến hóa giải bài toán cây khung phân cụm đường đi ngắn nhất BỘ GIÁO DỤC ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ PHẠM ĐÌNH THÀNH NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁNTIẾN HÓA GIẢI BÀI TOÁ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Ự PHẠM ĐÌNH THÀNH NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁNTIẾN HÓA GIẢI BÀI TOÁ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ố : 9 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 là công trình nghiên cứu của chínhmình dưới sự hướng dẫn của 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 nhau và cácthông tin trích dẫn được ghi rõ nguồn gốc. Các số liệu, kết quả trong luậnán là trung thực và chưa từng được công bố trong các công trình nghiêncứu của bất kỳ tác giả nào khác. GIẢNG VIÊN HƯỚNG DẪN NGHIÊN CỨU SINH PGS.TS. Huỳnh Thị Thanh Bình 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 và sâu sắctới giáo viên hướng dẫn PGS. TS. Huỳnh Thị Thanh Bình đã tận tình dạybảo và cung cấp những gợi ý quý báu giúp tôi nâng cao kiến thức và hoànthành tốt luận án này. Nghiên cứu sinh cũng xin bày tỏ lòng biết ơn sâusắc tới PGS.TS. Bùi Thu Lâm, Học viện Kỹ thuật Quân sự đã nhiệt tìnhhỗ trợ và đưa ra những định hướng, những lời khuyên trong suốt quá trìnhtôi thực hiện 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 và đặc biệt các thầy cô đang công tác tạikhoa Công nghệ thông tin đã hết lòng truyền đạt kiến thức và tạo điều kiệnthuận lợi nhất để tôi hoàn thành chương trình học tập và thực hiện luậnán nghiên cứu của mình. Nghiên cứu sinh cũng xin trân trọng cảm ơn Ban Giám hiệu trường Đạihọc Tây Bắc, Ban chủ nhiệm và các đồng nghiệp tại khoa Khoa học tựnhiên - Công nghệ, trường Đại học Tây Bắc đã tạo điều kiện và giúp đỡnghiên cứu sinh trong thời gian học tập. Tôi xin trân trọng cảm ơn các thầy cô trong và ngoài trường đã thamgia đọ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ệnluận án này. Tôi cũng xin gửi lời cảm ơn tới các thành viên của phòng thí nghiệm Môhình hóa, mô phỏng và tối ưu hóa(Modelling, Simulation and Optimizationlab – MSO Lab), trường Đại học Bách khoa Hà Nội, những người đã luônnhiệt tình giúp đỡ tôi trong suốt quá trình học tập và 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 đìnhvà bạn bè đã kiên trì, chia sẻ, động viên nghiên cứu sinh trong suốt quátrình học tập và hoàn thành luận án này. Hà Nội, ngày tháng năm 2021 NGHIÊN CỨU SINH Phạm Đình Thành i MỤC LỤCDANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT vDANH MỤC BẢNG BIỂU viiiDANH MỤC HÌNH ẢNH xGIỚI THIỆU 1Chương 1 TỔNG QUAN 7 1.1 Thuật toán tiến hóa . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Tổng quan về thuật toán tiến hóa . . . . . . . . . . . . 7 1.1.2 Mã hóa lời giải trong thuật toán tiến hóa . . . . . . . . 8 1.1.3 Khởi tạo quần thể . . . . . . . . . . . . . . . . . . . . . 8 1.1.4 Chọn lọc cá thể cha mẹ . . . . . . . . . . . . . . . . . . 8 1.1.5 Toán tử lai ghép . . . . . . . . . . . . . . . . . . . . . . 9 1.1.6 Toán tử đột biến . . . . . . . . . . . . . . . . . . . . . 10 1.1.7 Chọn lọc cá thể cho thế hệ tiếp theo . . . . . . . . . . . 10 1.1.8 Điều kiện dừng của thuật toán . . . . . . . . . . . . . . 11 1.2 Thuật toán tiến hóa đa nhân tố . . . . . . . . . . . . . . . . 11 1.2.1 Bài toán tiến hóa đa nhân tố . . . . . . . . . . . . . . . 11 1.2.2 Cơ bản về 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 và đột biến . . ...