Luận án Tiến sĩ Toán học: Một số kỹ thuật chỉ dẫn cho giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện cho các bài toán chi phí lớn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:150

Thêm vào BST

Báo xấu

37
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của luận án nhằm nghiên cứu, phát triển một số kỹ thuật chỉ dẫn cho giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện để nâng cao chất lượng, hiệu quả của giải thuật cho bài toán chi phí lớn, tập trung vào độ hội tụ và độ đa dạng.Từ đó, luận án đề xuất cải tiến hai giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện tiêu biểu gần đây, là K-RVEA và CSEA với các kỹ thuật chỉ dẫn. Mời các bạn tham khảo nội dung chi tiết đề tài!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: Một số kỹ thuật chỉ dẫn cho giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện cho các bài toán chi phí lớn

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÕNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ ---------------------------------- NGUYỄN ĐỨC ĐỊNH MỘT SỐ KỸ THUẬT CHỈ DẪN CHO GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU SỬ DỤNG MÔ HÌNH ĐẠI DIỆN CHO CÁC BÀI TOÁN CHI PHÍ LỚN LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2021
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÕNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ ---------------------------------- NGUYỄN ĐỨC ĐỊNH MỘT SỐ KỸ THUẬT CHỈ DẪN CHO GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU SỬ DỤNG MÔ HÌNH ĐẠI DIỆN CHO CÁC BÀI TOÁN CHI PHÍ LỚN 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: 1. PGS.TS. Nguyễn Xuân Hoài 2. TS. Thái Trung Kiên Hà Nội - 2021
i 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ả 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 khoa học nào khác, các dữ liệu tham khảo được trích dẫn đầy đủ. Hà Nội, ngày tháng năm 2021 Tác giả luận án Nguyễn Đức Định
ii LỜI CẢM ƠN Trước tiên, tôi xin tỏ lòng biết ơn chân thành đến PGS.TS. Nguyễn Xuân Hoài và TS. Thái Trung Kiên, đã tận tình định hướng nghiên cứu, chỉ bảo, hướng dẫn, giúp đỡ tôi trong suốt quá trình nghiên cứu và thực hiện luận án. Tôi xin trân trọng cảm ơn Thủ trưởng Viện Khoa học và Công nghệ quân sự, Phòng Đào tạo/ Viện Khoa học và Công nghệ quân sự, đã tạo điều kiện hướng dẫn, giúp đỡ tôi trong quá trình nghiên cứu và thực hiện luận án. Tôi xin trân trọng cảm ơn Thủ trưởng Viện Công nghệ thông tin, các phòng, ban của Viện Công nghệ thông tin đã quan tâm, giúp đỡ, tạo điều kiện thuận lợi cho tôi hoàn thành bản luận án. Cuối cùng, tôi xin bày tỏ sự biết ơn đến gia đình, người thân, đồng nghiệp cùng bạn bè, đặc biệt là PGS.TS. Nguyễn Long, đã luôn quan tâm, cổ vũ, động viên, góp ý và tạo điều kiện thuận lợi cho tôi thực hiện luận án này.
iii MỤC LỤC Trang DANH MỤC CÁC KÝ HIỆU ..................................................................................v DANH MỤC CÁC CHỮ VIẾT TẮT ................................................................... vii DANH MỤC CÁC BẢNG .......................................................................................x DANH MỤC CÁC HÌNH VẼ .................................................................................xi MỞ ĐẦU ....................................................................................................................1 Chương 1. TỔNG QUAN GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU SỬ DỤNG MÔ HÌNH ĐẠI DIỆN CHO BÀI TOÁN CHI PHÍ LỚN .........................8 1.1. Tổng quan bài toán chi phí lớn .............................................................. 8 1.1.1. Các khái niệm.................................................................................. 8 1.1.2. Bài toán chi phí lớn ....................................................................... 11 1.2. Kỹ thuật chỉ dẫn cho giải thuật tiến hóa đa mục tiêu ........................... 12 1.2.1. Giải thuật tiến hóa đa mục tiêu ..................................................... 12 1.2.2. Một số kỹ thuật chỉ dẫn cho giải thuật tiến hóa đa mục tiêu ........ 16 1.3. Giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện .................. 19 1.3.1. Mô hình đại diện ........................................................................... 19 1.3.2. Sơ đồ giải thuật SAEA .................................................................. 21 1.3.3. Các giải thuật SAEA điển hình ..................................................... 23 1.4. Một số vấn đề tồn tại ............................................................................ 36 1.4.1. Một số vấn đề tồn tại của giải thuật SAEA................................... 36 1.4.2. Nội dung dự kiến nghiên cứu của luận án .................................... 38 1.5. Kết luận Chương 1 ............................................................................... 39 Chương 2. ĐỀ XUẤT KỸ THUẬT CHỈ DẪN CHO GIẢI THUẬT K-RVEA ..40 2.1. Giải thuật M-K-RVEA chỉ dẫn tự động ............................................... 40 2.1.1. Xác định tương quan giữa thông tin tham chiếu và thông tin điều khiển ........................................................................................................ 40 2.1.2. Giải thuật M-K-RVEA .................................................................. 44 2.2. Giải thuật iK-RVEA chỉ dẫn tương tác ................................................ 49 2.2.1. Xác định thông tin tham chiếu ...................................................... 49 2.2.2. Giải thuật iK-RVEA ..................................................................... 51 2.3. Thử nghiệm và đánh giá ....................................................................... 55
iv 2.3.1. Kịch bản thử nghiệm ..................................................................... 55 2.3.2. Kết quả thử nghiệm ....................................................................... 59 2.3.3. So sánh với một số giải thuật khác ............................................... 71 2.3.4. Đánh giá chung ............................................................................. 73 2.4. Kết luận Chương 2 ............................................................................... 75 Chương 3. ĐỀ XUẤT KỸ THUẬT CHỈ DẪN CHO GIẢI THUẬT CSEA ......76 3.1. Giải thuật M-CSEA chỉ dẫn tự động .................................................... 76 3.2. Giải thuật iCSEA chỉ dẫn tương tác ..................................................... 81 3.3. Thử nghiệm và đánh giá ....................................................................... 85 3.3.1. Kịch bản thử nghiệm ..................................................................... 85 3.3.2. Kết quả thử nghiệm ....................................................................... 87 3.3.3. So sánh với một số giải thuật khác ............................................... 98 3.3.4. Đánh giá chung ........................................................................... 100 3.4. Kết luận Chương 3 ............................................................................. 102 Chương 4. ỨNG DỤNG CHO BÀI TOÁN LẬP KẾ HOẠCH TÁC CHIẾN .. 103 4.1. Bài toán lập kế hoạch tác chiến cho lực lượng tác chiến điện tử ....... 103 4.1.1. Đặt vấn đề ................................................................................... 103 4.1.2. Mô tả bài toán ............................................................................. 106 4.1.3. Mô hình hóa bài toán .................................................................. 108 4.2. Ứng dụng giải thuật sử dụng kỹ thuật chỉ dẫn để giải bài toán ......... 112 4.2.1. Thiết lập thông số thử nghiệm .................................................... 112 4.2.2. Kết quả thử nghiệm ..................................................................... 116 4.3. Nhận xét, đánh giá.............................................................................. 120 4.4. Kết luận Chương 4 ............................................................................. 121 KẾT LUẬN ........................................................................................................... 122 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ .................. 124 TÀI LIỆU THAM KHẢO.................................................................................... 125 PHỤ LỤC .............................................................................................................. 134
v DANH MỤC CÁC KÝ HIỆU MT Ma trận chuyển vị của ma trận M x Véc-tơ biến quyết định f Véc-tơ hàm mục tiêu z Véc-tơ mục tiêu n Số biến (số chiều của không gian quyết định) k Số mục tiêu (số chiều của không gian mục tiêu) S Không gian quyết định Z Không gian mục tiêu P Quần thể chính Q Quần thể con cái L Quần thể ghép A, A1, A2 Tập lưu trữ ngoài NP Kích thước quần thể chính NPOF Kích thước của lớp tối ưu Pareto ngen Số thế hệ đã trải qua Ngen Tổng số thế hệ nnon Số giải pháp không bị trội Pareto Cprb Mức độ phức tạp của bài toán Qt Tham số tiến trình thời gian pt Tham số điều khiển p0 Điểm gieo pstart Cận dưới của tham số điều khiển pend Cận trên của tham số điều khiển FE Số lần đánh giá độ thích nghi (trong trường hợp cụ thể giải thuật K-RVEA và CSEA thì FE là số lần tính toán hàm gốc) FEmax Số lần đánh giá độ thích nghi tối đa (trong trường hợp cụ thể giải thuật K-RVEA và CSEA thì FEmax là số lần tính toán hàm gốc tối đa) wmax Số thế hệ sử dụng mô hình Kriging wtmax Số thế hệ sử dụng mô hình Kriging ở bước t (được điều chỉnh tự động) wndmax Số thế hệ sử dụng mô hình Kriging (do người quyết định tự xác định) m Số véc-tơ tham chiếu
vi u Số cá thể được chọn để huấn luyện mô hình Kriging NI Số cá thể tối đa được duy trì trong A1  Tham số quyết định sử dụng APD hay sử dụng thông tin không chắc chắn từ Kriging Vt Tập véc-tơ tham chiếu tại thế hệ t Va Tập véc-tơ tham chiếu thích ứng Vaa Tập véc-tơ tham chiếu thích ứng hoạt động Vaia Tập véc-tơ tham chiếu thích ứng không hoạt động Vf Tập véc-tơ tham chiếu cố định Vfa Tập véc-tơ tham chiếu cố định hoạt động Vfia Tập véc-tơ tham chiếu cố định không hoạt động K Số giải pháp tham chiếu xác định biên phân lớp Kt Số giải pháp tham chiếu xác định biên phân lớp (được điều chỉnh tự động) Knd Số giải pháp tham chiếu xác định biên phân lớp (do người quyết định tự xác định) gmax Số thế hệ sử dụng mạng FNN H Số nơ-ron lớp ẩn của mạng FNN PR Tập giải pháp tham chiếu để làm biên phân lớp Dtrain Tập giải pháp để huấn luyện mạng FNN Dtest Tập giải pháp để kiểm tra mạng FNN ND Kích thước tập Dtrain NT Kích thước tập Dtest O Độ phức tạp tính toán của giải thuật Cf Độ phức tạp tính toán cực đại của các hàm gốc CK Độ phức tạp tính toán mô hình
vii DANH MỤC CÁC CHỮ VIẾT TẮT MOP Bài toán tối ưu đa mục tiêu Multi-Objective Problem MOEA Giải thuật tiến hóa đa mục Multi-Objective Evolutionary tiêu Algorithm POF Lớp tối ưu Pareto Pareto Optimal Front GD Khoảng cách thế hệ Generational Distance IGD Khoảng cách thế hệ ngược Inverse Generational Distance HV Siêu thể tích Hypervolume DTLZ Lớp bài toán do K. Deb, L. Deb-Thiele-Laumanns-Zitzler Thiele, M. Laumanns, E. Problems Zitzler đề xuất LHS Lấy mẫu siêu khối Latinh Latin Hypercube Sampling DMEA Giải thuật tiến hóa đa mục Direction-based Multi-Objective tiêu dựa trên hướng Evolutionary Algorithm DMEA-II Giải thuật tiến hóa đa mục Direction-based Multi- tiêu dựa trên hướng II (cải Objective Evolutionary tiến của DMEA) Algorithm II Giải thuật di truyền đa mục Multi-Objective Genetic MOGA tiêu Algorithm MOEA/D Giải thuật tiến hóa đa mục Multi-Objective Evolutionary tiêu dựa trên phân rã Algorithm-based on Decomposition NPGA Giải thuật di truyền sử dụng Niched-Pareto Genetic kỹ thuật nich trên Pareto Algorithm NSGA Giải thuật di truyền sắp xếp Non-dominated Sorting Genetic không trội Algorithm NSGA-II Giải thuật di truyền sắp xếp Non-dominated Sorting Genetic không trội II Algorithm II PAES Giải thuật tiến hóa sử dụng Pareto Archived Evolutionary lưu trữ ngoài Pareto Strategy SPEA Giải thuật tiến hóa Pareto Strength Pareto Evolutionary cường độ Algorithm SPEA2 Giải thuật tiến hóa Pareto Strength Pareto Evolutionary cường độ 2 (cải tiến của SPEA) Algorithm 2
viii SAEA Giải thuật tiến hóa sử dụng Surrogate-Assisted mô hình đại diện Evolutionary Algorithm PRS Bề mặt đáp ứng đa thức Polynomial Response Surface RBF Hàm cơ sở bán kính Radial Basis Function SVM Máy véc-tơ tựa Support Vector Machine ANN Mạng nơ-ron nhân tạo Artificial Neural Network HO- Giải thuật memetic tìm Hypervolume-based Local MOMA kiếm cục bộ dựa trên độ đo Search Multi-Objective siêu thể tích sử dụng SVM Memetic Algorithm with SVM MOPSA- Giải thuật tiến hóa sử dụng Multi-Objective Parallel EA mô hình đại diện song song Surrogate-Assisted đa mục tiêu Evolutionary Algorithms MOEA/D- Giải thuật tiến hóa đa mục Multi-objective Evolutionary EGO tiêu dựa trên phân rã với Algorithm-based on quá trình Gauss Decomposition with the Gaussian Process Model MOEA/D- Giải thuật tiến hóa đa mục Multi-objective Evolutionary RBF tiêu dựa trên phân rã sử Algorithm-based on dụng RBF Decomposition-assisted by RBF ParEGO Giải thuật tối ưu toàn cục Pareto Efficient Global hiệu quả Pareto Optimization SMS- Giải thuật tối ưu toàn cục S-metric Selection-based EGO hiệu quả dựa trên chọn lọc Efficient Global Optimization độ đo S SS- Giải thuật memetic tìm Surrogate-assisted Local Search MOMA kiếm cục bộ sử dụng mô Multi-Objective Memetic hình đại diện Algorithm Classification and Pareto Giải thuật tiến hóa đa mục CPS- Domination-based Multi- tiêu dựa trên quan hệ trội MOEA Objective Evolutionary Pareto và phân lớp Algorithm RVEA Giải thuật tiến hóa sử dụng Reference Vector-guided véc-tơ tham chiếu Evolutionary Algorithm APD Khoảng cách góc phạt Angle Penalized Distance K-RVEA Giải thuật tiến hóa sử dụng Kriging-assisted Reference mô hình Kriging cùng với Vector-guided Evolutionary véc-tơ tham chiếu Algorithm
ix M-K-RVEA Giải thuật tiến hóa sử dụng Modified Kriging-assisted mô hình Kriging cùng với Reference Vector-guided véc-tơ tham chiếu được chỉ Evolutionary Algorithm dẫn tự động iK-RVEA Giải thuật tiến hóa sử dụng Interactive Kriging-assisted mô hình Kriging cùng với Reference Vector-guided véc-tơ tham chiếu được chỉ Evolutionary Algorithm dẫn tương tác CSEA Giải thuật tiến hóa sử dụng Classification-based Surrogate- mô hình đại diện phân lớp assisted Evolutionary Algorithm FNN Mạng nơ-ron truyền thẳng Feedforward Neural Network M-CSEA Giải thuật tiến hóa sử dụng Modified Classification-based mô hình đại diện phân lớp Surrogate-assisted Evolutionary được chỉ dẫn tự động Algorithm iCSEA Giải thuật tiến hóa sử dụng Interactive Classification-based mô hình đại diện phân lớp Surrogate-assisted Evolutionary được chỉ dẫn tương tác Algorithm TCĐT Tác chiến điện tử Electronic Warfare
x DANH MỤC CÁC BẢNG Trang Bảng 2.1. Các bài toán mẫu DTLZ sử dụng trong thử nghiệm ...................... 55 Bảng 2.2. Kết quả thử nghiệm của K-RVEA và M-K-RVEA trên độ đo GD ... 59 Bảng 2.3. Kết quả thử nghiệm của K-RVEA và M-K-RVEA trên độ đo IGD .. 60 Bảng 2.4. Thời gian chạy của K-RVEA và M-K-RVEA................................ 63 Bảng 2.5. Quá trình điều chỉnh giá trị wtmax trong M-K-RVEA ..................... 63 Bảng 2.6. Kết quả thử nghiệm của K-RVEA và iK-RVEA trên độ đo GD ... 66 Bảng 2.7. Kết quả thử nghiệm của K-RVEA và iK-RVEA trên độ đo IGD .. 67 Bảng 2.8. Thời gian chạy của K-RVEA và iK-RVEA ................................... 69 Bảng 2.9. Quá trình điều chỉnh giá trị wndmax trong iK-RVEA ....................... 70 Bảng 2.10. Kết quả thử nghiệm của M-K-RVEA, iK-RVEA so với giải thuật SAEA khác trên độ đo GD ............................................................. 72 Bảng 2.11. Kết quả thử nghiệm của M-K-RVEA, iK-RVEA so với giải thuật SAEA khác trên độ đo IGD ........................................................... 73 Bảng 3.1. Kết quả thử nghiệm của CSEA và M-CSEA trên độ đo GD ......... 87 Bảng 3.2. Kết quả thử nghiệm của CSEA và M-CSEA trên độ đo IGD ........ 88 Bảng 3.3. Thời gian chạy của CSEA và M-CSEA ......................................... 91 Bảng 3.4. Quá trình điều chỉnh giá trị Kt trong M-CSEA ............................... 91 Bảng 3.5. Kết quả thử nghiệm của CSEA và iCSEA trên độ đo GD ............. 93 Bảng 3.6. Kết quả thử nghiệm của CSEA và iCSEA trên độ đo IGD ............ 94 Bảng 3.7. Thời gian chạy của CSEA và iCSEA ............................................. 97 Bảng 3.8. Quá trình điều chỉnh giá trị Knd trong iCSEA................................. 97 Bảng 3.9. Kết quả thử nghiệm của M-CSEA, iCSEA so với giải thuật SAEA khác trên độ đo GD ...................................................................... 99 Bảng 3.10. Kết quả thử nghiệm của M-CSEA, iCSEA so với giải thuật SAEA khác trên độ đo IGD .................................................................... 99 Bảng 4.1. Ví dụ về bảng giá trị các thuộc tính của các nhiệm vụ ................. 111 Bảng 4.2. Dữ liệu thử nghiệm của kế hoạch gồm 12 nhiệm vụ .................... 114 Bảng 4.3. Dữ liệu thử nghiệm của kế hoạch gồm 30 nhiệm vụ .................... 115 Bảng 4.4. Kết quả thử nghiệm cho bài toán lập kế hoạch tác chiến sử dụng các giải thuật M-K-RVEA, M-CSEA trên độ đo HV ........................... 119
xi DANH MỤC CÁC HÌNH VẼ Trang Hình 1.1. Minh họa lớp tối ưu Pareto trong không gian mục tiêu .................. 10 Hình 1.2. Sơ đồ giải thuật tiến hóa đa mục tiêu .............................................. 13 Hình 1.3. Minh họa hội tụ và đa dạng trong không gian mục tiêu ................. 15 Hình 1.4. Sơ đồ giải thuật tiến hóa sử dụng mô hình đại diện ........................ 22 Hình 2.1. Minh họa các độ đo GD, IGD ......................................................... 57 Hình 2.2. Quá trình tối ưu của K-RVEA, M-K-RVEA với bài toán DTLZ1 ... 62 Hình 2.3. Quá trình tối ưu của K-RVEA, M-K-RVEA với bài toán DTLZ3 ... 62 Hình 2.4. Quá trình tối ưu của K-RVEA, M-K-RVEA với bài toán DTLZ5 ... 62 Hình 2.5. Quá trình tối ưu của K-RVEA, M-K-RVEA với bài toán DTLZ9 ... 63 Hình 2.6. Quá trình tối ưu của K-RVEA, iK-RVEA với bài toán DTLZ1 ..... 68 Hình 2.7. Quá trình tối ưu của K-RVEA, iK-RVEA với bài toán DTLZ4 ..... 68 Hình 2.8. Quá trình tối ưu của K-RVEA, iK-RVEA với bài toán DTLZ5 ..... 69 Hình 2.9. Quá trình tối ưu của K-RVEA, iK-RVEA với bài toán DTLZ8 ..... 69 Hình 3.1. Quá trình tối ưu của CSEA, M-CSEA với bài toán DTLZ3 ........... 89 Hình 3.2. Quá trình tối ưu của CSEA, M-CSEA với bài toán DTLZ4 ........... 90 Hình 3.3. Quá trình tối ưu của CSEA, M-CSEA với bài toán DTLZ5 ........... 90 Hình 3.4. Quá trình tối ưu của CSEA, M-CSEA với bài toán DTLZ8 ........... 90 Hình 3.5. Quá trình tối ưu của CSEA, iCSEA với bài toán DTLZ1 .............. 95 Hình 3.6. Quá trình tối ưu của CSEA, iCSEA với bài toán DTLZ3 .............. 96 Hình 3.7. Quá trình tối ưu của CSEA, iCSEA với bài toán DTLZ7 .............. 96 Hình 3.8. Quá trình tối ưu của CSEA, iCSEA với bài toán DTLZ8 .............. 96 Hình 4.1. Ví dụ biểu diễn kế hoạch tác chiến dưới dạng đồ thị .................... 107 Hình 4.2. Ví dụ biểu diễn kế hoạch trên biểu đồ Gantt ................................ 112 Hình 4.3. Tập giải pháp đạt được với giải thuật K-RVEA, M-K-RVEA trên bộ dữ liệu 12 nhiệm vụ.......................................................................... 116 Hình 4.4. Tập giải pháp đạt được với giải thuật K-RVEA, M-K-RVEA trên bộ dữ liệu 30 nhiệm vụ.......................................................................... 116 Hình 4.5. Tập giải pháp đạt được với giải thuật CSEA, M-CSEA trên bộ dữ liệu 12 nhiệm vụ .................................................................................... 117 Hình 4.6. Tập giải pháp đạt được với giải thuật CSEA, M-CSEA trên bộ dữ liệu 30 nhiệm vụ .................................................................................... 117
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Thế giới ngày nay đang sống trong kỷ nguyên kỹ thuật số với sự tác động mạnh mẽ của cuộc cách mạng công nghiệp lần thứ tư. Đây là cuộc cách mạng sản xuất mới gắn liền với các đột phá về kỹ thuật số, được đánh dấu bởi các công nghệ số tiêu biểu như: trí tuệ nhân tạo; xử lý dữ liệu lớn; Internet vạn vật; điện toán đám mây; công nghệ in 3D; công nghệ cảm biến; mô phỏng thực tại ảo, thực tại tăng cường; robot tự động… Bản chất của cuộc cách mạng này là dựa trên nền tảng kỹ thuật số, tích hợp các công nghệ thông minh để tối ưu hóa quy trình, phương thức sản xuất. Chính vì vậy, yêu cầu phát triển ứng dụng và công nghệ đã góp phần thúc đẩy việc nghiên cứu các giải thuật tối ưu giải các lớp bài toán khác nhau. Trong lĩnh vực thiết kế, tính toán và mô phỏng, nhu cầu về giải quyết các lớp bài toán tối ưu là rất lớn. Đặc biệt trong quân sự, có nhiều bài toán tối ưu cần giải quyết, bao gồm bài toán lập kế hoạch tác chiến cho lực lượng tác chiến trực tiếp hoặc các đơn vị chiến đấu, các đơn vị bảo đảm. Các bài toán thường có nhiều mục tiêu tối ưu và xung đột với nhau, các bài toán đó gọi là bài toán tối ưu đa mục tiêu. Trong thực tế, có rất nhiều bài toán tối ưu đa mục tiêu có chi phí tính toán lớn với các đặc điểm như: số mục tiêu lớn, không gian tìm kiếm rộng, hàm mục tiêu có độ phức tạp tính toán lớn, thậm chí không khả vi hoặc không được cho, mô tả, biểu diễn dưới dạng giải tích. Vì thế, để tìm được giải pháp tối ưu cho bài toán này, đòi hỏi chi phí lớn về thời gian và tài nguyên. Các bài toán đó hình thành lớp bài toán đa mục tiêu chi phí lớn [19], [21]. Trong phạm vi luận án, để thuận tiện cho việc trình bày, nói đến bài toán chi phí lớn tức là nói đến bài toán tối ưu đa mục tiêu chi phí lớn. Để giải quyết hiệu quả các bài toán chi phí lớn, đòi hỏi sự đầu tư nghiên
2 cứu chuyên sâu với nhiều kỹ thuật đặc trưng. Hiện nay, có một số phương pháp phổ biến để giải, đó là: phương pháp mô phỏng, phương pháp phân rã, phương pháp xấp xỉ. Xu thế hiện nay để giải các bài toán chi phí lớn là sử dụng phương pháp tối ưu xấp xỉ thông qua các giải thuật sử dụng nguyên lý phỏng sinh học. Nguyên lý phỏng sinh học được chia làm hai loại: nguyên lý tiến hóa phỏng theo sự phát triển tự nhiên và nguyên lý bầy đàn phỏng theo hành vi sinh học. Các giải thuật tối ưu đa mục tiêu sử dụng nguyên lý tiến hóa với cơ chế ngẫu nhiên, làm việc trên quần thể, có tính tương tác, phù hợp trong việc tìm kiếm một tập giải pháp xấp xỉ lời giải cho các bài toán tối ưu đa mục tiêu, bài toán chi phí lớn. Các giải thuật này hình thành lớp giải thuật tiến hóa đa mục tiêu [57]. Giải thuật tiến hóa đa mục tiêu sử dụng hai cơ chế: cơ chế tái tạo không tinh tú, điển hình như các giải thuật NPGA [40], NSGA [45], MOGA[71] và cơ chế tái tạo tinh tú, điển hình như các giải thuật DMEA [16], NSGA-II [25], PAES [41], DMEA-II [63], MOEA/D [86], SPEA2 [90]. Để đánh giá chất lượng, hiệu quả của giải thuật, thông thường cần quan tâm 5 yếu tố: (i) độ hội tụ; (ii) độ đa dạng; (iii) số giải pháp tốt; (iv) độ phức tạp tính toán; (v) tính bền vững. Các nghiên cứu gần đây, nhằm cải thiện chất lượng, hiệu quả của giải thuật tiến hóa đa mục tiêu, việc nghiên cứu, sử dụng kỹ thuật chỉ dẫn là một chủ đề được quan tâm và áp dụng hiệu quả trong thực tế. Kỹ thuật chỉ dẫn được phân thành hai loại cơ bản là chỉ dẫn tự động và chỉ dẫn tương tác. Kỹ thuật chỉ dẫn sử dụng phân tích thông tin tham chiếu để điều chỉnh quá trình tiến hóa, hướng tới sự cải thiện một số yếu tố nào đó về chất lượng, hiệu quả của giải thuật. Trường hợp có tương tác, sẽ sử dụng trực tiếp thông tin ưu tiên của người quyết định để điều chỉnh quá trình tiến hóa hướng tới khu vực mục tiêu mong muốn. Việc điều chỉnh được thực hiện thông qua các tham số điều khiển, cải tiến cơ chế tìm kiếm giải pháp, chọn lọc
3 các cá thể, ưu tiên thông tin chỉ dẫn. Đã có nhiều công trình công bố các kỹ thuật chỉ dẫn tự động như: chỉ dẫn sử dụng hướng đạo hàm âm [5], [9], [12], hướng vi phân [3], [58], hướng cải thiện [14], [49], [60], [61]. Với kỹ thuật chỉ dẫn tương tác, cũng có nhiều đề xuất được công bố như: tương tác sử dụng véc-tơ tham chiếu [30], [31], tương tác đa điểm [59], sử dụng hướng tham chiếu [75], [80]. Đặc biệt, gần đây các giải thuật tiến hóa sử dụng mô hình đại diện (mô hình xấp xỉ) đã giải quyết bài toán chi phí lớn một cách hiệu quả hơn. Mô hình đại diện được sử dụng để xấp xỉ hàm mục tiêu hoặc phân lớp giải pháp thay vì phải dùng hàm mục tiêu gốc. Mô hình đại diện có độ phức tạp tính toán thấp hơn hàm mục tiêu gốc nhiều nên giảm được chi phí tính toán chung của giải thuật [21]. Giải thuật này vừa kế thừa được các ưu điểm của nguyên lý tiến hóa, vừa tận dụng được hiệu quả tính toán của mô hình đại diện. Có nhiều giải thuật sử dụng các mô hình đại diện Kriging, RBF, PRS, SVM, ANN đã được công bố và được phân làm hai loại: các giải thuật sử dụng mô hình để xấp xỉ hàm gốc, tiêu biểu là K-RVEA [20], MOEA/D-RBF, ParEGO, SMS-EGO, MOEAD/D-EGO, HO-MOMA, SS-MOMA [21]; các giải thuật sử dụng mô hình để phân lớp giải pháp, tiêu biểu như CPS-MOEA [28], CSEA, [65]. Khi sử dụng mô hình đại diện, một số vấn đề đặt ra như: chọn mô hình đại diện, sử dụng mô hình đại diện, xác định thời điểm huấn luyện mô hình, lựa chọn mẫu để huấn luyện mô hình, sử dụng tham số điều khiển như thế nào để vừa đạt hiệu quả tính toán, vừa nâng cao độ hội tụ, độ đa dạng và tính bền vững của giải thuật [21]. Cho đến nay, các kỹ thuật chỉ dẫn đã được sử dụng khá rộng rãi trong giải thuật tiến hóa đa mục tiêu, nhưng hầu như chưa được áp dụng cho các giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện. Nguyên lý của các giải thuật sử dụng mô hình đại diện nhằm giảm chi phí tính toán thông qua
4 việc thay thế, giảm bớt số lượng tính toán giá trị hàm mục tiêu gốc bằng việc sử dụng các hàm đại diện để xấp xỉ hàm gốc hoặc phân lớp giải pháp. Đây là một kỹ thuật rất hiệu quả với các bài toán chi phí lớn. Tuy vậy, việc sử dụng các mô hình đại diện cũng có thể làm cho giải thuật suy giảm tốc độ hội tụ, phạm vi tìm kiếm toàn cục, ảnh hưởng trực tiếp đến độ hội tụ, độ đa dạng, tính bền vững của tập giải pháp tìm được qua mỗi thế hệ trong suốt quá trình tìm kiếm tối ưu. Để giải quyết vấn đề đó, cần phải có chiến lược để đảm bảo cho giải thuật duy trì được sự cân bằng giữa khả năng khai thác và thăm dò của quá trình tìm kiếm, qua đó giúp giải thuật luôn đạt được chất lượng tốt nhất về độ hội tụ, độ đa dạng và tính bền vững. Khi đó, kỹ thuật chỉ dẫn, với đặc điểm phân tích các thông tin tham chiếu để chỉ dẫn giải thuật là một cách tiếp cận để thực hiện chiến lược này một cách hiệu quả, tinh tế. Đây là vấn đề nghiên cứu có tính khoa học, cần thiết hiện nay và là định hướng cho đề tài của luận án. 2. Mục tiêu nghiên cứu Mục tiêu nghiên cứu của luận án là: nghiên cứu, phát triển một số kỹ thuật chỉ dẫn cho giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện để nâng cao chất lượng, hiệu quả của giải thuật cho bài toán chi phí lớn, tập trung vào độ hội tụ và độ đa dạng. Từ đó, luận án đề xuất cải tiến hai giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện tiêu biểu gần đây, là K- RVEA và CSEA với các kỹ thuật chỉ dẫn. 3. Đối tƣợng và phạm vi nghiên cứu Đối tượng nghiên cứu: Giải thuật tiến hóa đa mục tiêu, giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện, kỹ thuật chỉ dẫn, bài toán đa mục tiêu, bài toán chi phí lớn, bài toán mẫu, bài toán thực tế, độ đo. Phạm vi nghiên cứu: Tối ưu đa mục tiêu, nguyên lý tiến hóa, mô hình đại
5 diện, kỹ thuật chỉ dẫn, bài toán chi phí lớn, các bài toán mẫu DTLZ. 4. Nội dung nghiên cứu (i) Nghiên cứu tổng quan bài toán chi phí lớn, giải thuật tiến hóa đa mục tiêu cùng với các kỹ thuật chỉ dẫn; nghiên cứu, phân tích các đặc trưng của giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện để giải bài toán chi phí lớn, tập trung vào hai giải thuật tiêu biểu K-RVEA và CSEA; (ii) Đề xuất phát triển giải thuật K-RVEA sử dụng các kỹ thuật chỉ dẫn để nâng cao chất lượng, hiệu quả của giải thuật cho bài toán chi phí lớn, tập trung vào độ hội tụ và độ đa dạng; thực nghiệm và đánh giá hiệu quả của các giải thuật cải tiến trên các bài toán mẫu; (iii) Đề xuất phát triển giải thuật CSEA sử dụng các kỹ thuật chỉ dẫn để nâng cao chất lượng, hiệu quả của giải thuật cho bài toán chi phí lớn, tập trung vào độ hội tụ và độ đa dạng; thực nghiệm và đánh giá hiệu quả của giải thuật trên các bài toán mẫu; (iv) Nghiên cứu, mô hình hóa bài toán lập kế hoạch tác chiến trong quân sự và ứng dụng các giải thuật cải tiến để giải quyết. 5. Phƣơng pháp nghiên cứu Nghiên cứu lý thuyết: Phân tích, tổng hợp các kết quả nghiên cứu liên quan và cơ sở lý thuyết về toán học của bài toán đa mục tiêu, bài toán chi phí lớn, giải thuật tiến hóa đa mục tiêu, giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện, chất lượng hiệu quả của giải thuật. Từ đó, đề xuất các kỹ thuật chỉ dẫn (chỉ dẫn tự động và chỉ dẫn tương tác) cho giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện để giải bài toán chi phí lớn. Trên cơ sở đó, đề xuất áp dụng kỹ thuật chỉ dẫn nhằm nâng cao chất lượng, hiệu quả cho một số giải thuật tiêu biểu.
6 Thực nghiệm: Lập trình giải thuật cải tiến trên phần mềm Matlab phiên bản 2020b, công cụ PlatEMO [78], sử dụng bài toán mẫu, bài toán thực tế, độ đo phổ biến để thực nghiệm, so sánh và đánh giá các giải thuật. 6. Ý nghĩa khoa học và thực tiễn của luận án Ý nghĩa khoa học: Giúp đánh giá các vấn đề đặc trưng, đưa ra các vấn đề tồn tại của giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện cho bài toán chi phí lớn. Dựa trên các nhận xét, đánh giá, luận án đề xuất các kỹ thuật chỉ dẫn nhằm nâng cao chất lượng, hiệu quả của các giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện cho bài toán chi phí lớn. Trên cơ sở các kỹ thuật chỉ dẫn, luận án đề xuất các cải tiến của hai giải thuật K-RVEA và CSEA, cho kết quả tốt hơn. Ý nghĩa thực tiễn: Luận án đề xuất các giải thuật cải tiến ứng dụng giải quyết bài toán chi phí lớn trong lĩnh vực quân sự. 7. Bố cục của luận án Nội dung của luận án được kết cấu gồm: phần mở đầu, 4 chương, phần kết luận, danh mục các công trình khoa học đã công bố, tài liệu tham khảo và phụ lục. Cụ thể như sau: Mở đầu: Trình bày về tính cấp thiết, mục tiêu, đối tượng, phạm vi, nội dung, phương pháp nghiên cứu, ý nghĩa khoa học và thực tiễn của luận án. Chƣơng 1. Tổng quan giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện cho bài toán chi phí lớn: Trình bày tổng quan về bài toán tối ưu đa mục tiêu, bài toán chi phí lớn; kỹ thuật chỉ dẫn cho giải thuật tiến hóa đa mục tiêu; giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện. Phân tích hai giải thuật tiêu biểu là K-RVEA (sử dụng mô hình Kriging để xấp xỉ hàm mục tiêu gốc) và CSEA (sử dụng mạng nơ-ron lan truyền thẳng làm mô
7 hình đại diện để phân lớp); từ đó đánh giá các vấn đề tồn tại và xác định bài toán cần giải quyết. Chƣơng 2. Đề xuất kỹ thuật chỉ dẫn cho giải thuật K-RVEA: Trình bày về đề xuất giải thuật M-K-RVEA chỉ dẫn tự động và giải thuật iK-RVEA chỉ dẫn tương tác nhằm nâng cao chất lượng, hiệu quả của giải thuật. Chương 2 cũng trình bày các kết quả thực nghiệm và so sánh, đánh giá các giải thuật cải tiến cùng với giải thuật gốc K-RVEA. Chƣơng 3. Đề xuất kỹ thuật chỉ dẫn cho giải thuật CSEA: Đề xuất giải thuật M-CSEA chỉ dẫn tự động và giải thuật iCSEA chỉ dẫn tương tác. Chương 3 cũng tiến hành thực nghiệm và so sánh, đánh giá các giải thuật cải tiến cùng với giải thuật gốc CSEA. Chƣơng 4. Ứng dụng cho bài toán lập kế hoạch tác chiến: Phát biểu và mô hình hóa bài toán lập kế hoạch tác chiến cho lực lượng tác chiến điện tử; Ứng dụng giải thuật đề xuất M-K-RVEA, M-CSEA để giải bài toán và nhận xét. Kết luận: Tóm lược kết quả nghiên cứu, các đóng góp mới và hướng phát triển của đề tài luận án. Danh mục các công trình khoa học đã công bố: Nội dung chính của luận án đã được công bố trong 4 bài báo hội thảo quốc tế và 2 bài báo trên tạp chí chuyên ngành trong nước. Tài liệu tham khảo: Gồm danh mục tài liệu tham khảo tiếng Việt và tài liệu tham khảo tiếng Anh. Phụ lục: Mô tả bài toán mẫu DTLZ được sử dụng trong thực nghiệm.