Luận án Tiến sĩ Toán học: Nghiên cứu, phát triển một số kỹ thuật điều khiển thích ứng nhằm cải thiện chất lượng giải thuật tiến hóa tối ưu đa mục tiêu

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

Thêm vào BST

Báo xấu

2
lượt xem 1
download

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

Luận án Tiến sĩ Toán học "Nghiên cứu, phát triển một số kỹ thuật điều khiển thích ứng nhằm cải thiện chất lượng giải thuật tiến hóa tối ưu đa mục tiêu" trình bày các nội dung chính sau: Tổng quan giải thuật tiến hóa tối ưu đa mục tiêu; Nghiên cứu, phát triển kỹ thuật điều khiển thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp; Nghiên cứu, phát triển kỹ thuật điều khiển thích ứng dựa trên phân bố của quần thể.

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: Nghiên cứu, phát triển một số kỹ thuật điều khiển thích ứng nhằm cải thiện chất lượng giải thuật tiến hóa tối ưu đa mục tiêu

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Ự TRẦN BÌNH MINH NGHIÊN CỨU, PHÁT TRIỂN MỘT SỐ KỸ THUẬT ĐIỀU KHIỂN THÍCH ỨNG NHẰM CẢI THIỆN CHẤT LƢỢNG GIẢI THUẬT TIẾN HÓA TỐI ƢU ĐA MỤC TIÊU LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2024
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Ự TRẦN BÌNH MINH NGHIÊN CỨU, PHÁT TRIỂN MỘT SỐ KỸ THUẬT ĐIỀU KHIỂN THÍCH ỨNG NHẰM CẢI THIỆN CHẤT LƢỢNG GIẢI THUẬT TIẾN HÓA TỐI ƢU ĐA MỤC TIÊU Ngành: Cơ sở toán học cho tin học Mã số: 9460110 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC: 1. PGS.TS Nguyễn Long 2. TS Thái Trung Kiên Hà Nội - 2024
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 2024 Tác giả luận án Trần Bình Minh
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 Long 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/Viện Khoa học và Công nghệ quân sự, các Phòng, Ban trong Viện đã 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. Tôi xin trân trọng cảm ơn TS Nguyễn Đức Định đã giúp đỡ tôi trong quá trình công bố các kết quả nghiên cứu và hoàn thiệ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è đã 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. Tác giả luận án Trần Bình Minh
iii MỤC LỤC Trang DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ........................................ vi DANH MỤC CÁC BẢNG ............................................................................. ix DANH MỤC CÁC HÌNH VẼ......................................................................... x MỞ ĐẦU .......................................................................................................... 1 Chƣơng 1 TỔNG QUAN GIẢI THUẬT TIẾN HÓA TỐI ƢU ĐA MỤC TIÊU ................................................................................................................. 9 1.1. Bài toán tối ưu đa mục tiêu .................................................................... 9 1.1.1. Phát biểu bài toán ............................................................................ 9 1.1.2. Một số khái niệm cơ bản ............................................................... 10 1.1.3. Người quyết định .......................................................................... 12 1.1.4. Ứng dụng của bài toán tối ưu đa mục tiêu trong thực tế .............. 13 1.1.5. Phương pháp giải bài toán tối ưu đa mục tiêu .............................. 13 1.2. Giải thuật tiến hóa tối ưu đa mục tiêu .................................................. 16 1.2.1. Tổng quan về giải thuật................................................................. 16 1.2.2. Một số giải thuật điển hình ........................................................... 21 1.3. Đánh giá chất lượng và hiệu quả của giải thuật tiến hóa tối ưu đa mục tiêu ....................................................................................................... 27 1.3.1. Đánh giá chất lượng của tập giải pháp .......................................... 28 1.3.2. Đánh giá hiệu quả tìm kiếm của giải thuật ................................... 31 1.3.3. Đánh giá trên một số tiêu chí khác ............................................... 31 1.4. Một số vấn đề trong đánh giá chất lượng và hiệu quả của giải thuật tiến hóa tối ưu đa mục tiêu .......................................................................... 32 1.4.1. Cân bằng giữa hội tụ và đa dạng của tập giải pháp ...................... 32 1.4.2. Cân bằng giữa khả năng thăm dò và khai thác của giải thuật ....... 34 1.4.3. Kỹ thuật điều khiển thích ứng nhằm duy trì cân bằng khả năng thăm dò và khai thác của giải thuật ......................................................... 36 1.5. Đề xuất nội dung nghiên cứu của luận án ............................................ 41 1.5.1. Một số vấn đề tồn tại trong lĩnh vực nghiên cứu .......................... 41 1.5.2. Giả thuyết nghiên cứu ................................................................... 45 1.5.3. Nội dung nghiên cứu của luận án ................................................. 46 1.6. Kết luận Chương 1 ............................................................................... 47
iv Chƣơng 2 NGHIÊN CỨU, PHÁT TRIỂN KỸ THUẬT ĐIỀU KHIỂN THÍCH ỨNG DỰA TRÊN XU HƢỚNG BIẾN ĐỔI ĐỘ ĐO VỀ HỘI TỤ VÀ ĐA DẠNG CỦA TẬP GIẢI PHÁP ................................................ 48 2.1. Kỹ thuật điều khiển thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp ............................................................. 49 2.1.1. Mối quan hệ giữa xu hướng biến đổi độ đo chất lượng của tập giải pháp và xu thế tìm kiếm của giải thuật ............................................ 49 2.1.2. Đề xuất kỹ thuật điều khiển thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp .................................... 50 2.1.3. Áp dụng vào cải tiến giải thuật tiến hóa tối ưu đa mục tiêu ......... 57 2.2. Đề xuất cải thiện một số giải thuật điển hình ...................................... 59 2.2.1. Giải thuật DMEA-II++ ................................................................. 59 2.2.2. Giải thuật MOEA/D+ .................................................................... 62 2.2.3. Giải thuật MOEA/D-DE+ ............................................................. 67 2.2.4. Giải thuật NSGAII-DE+ ............................................................... 70 2.3. Thử nghiệm và đánh giá....................................................................... 74 2.3.1. Kịch bản thử nghiệm ..................................................................... 74 2.3.2. Kết quả thử nghiệm ....................................................................... 77 2.3.3. Đánh giá chung về kỹ thuật .......................................................... 89 2.4. Kết luận Chương 2 ............................................................................... 91 Chƣơng 3 NGHIÊN CỨU, PHÁT TRIỂN KỸ THUẬT ĐIỀU KHIỂN THÍCH ỨNG DỰA TRÊN PHÂN BỐ CỦA QUẦN THỂ ........................ 92 3.1. Kỹ thuật điều khiển thích ứng dựa trên phân bố của quần thể ............ 92 3.1.1. Mối quan hệ giữa phân bố quần thể và khả năng thăm dò, khai thác của giải thuật ................................................................................... 92 3.1.2. Đề xuất kỹ thuật điều khiển thích ứng dựa trên phân bố của quần thể ................................................................................................... 95 3.1.3. Áp dụng vào cải tiến giải thuật tiến hóa tối ưu đa mục tiêu ...... 101 3.2. Đề xuất cải thiện một số giải thuật điển hình .................................... 102 3.2.1. Giải thuật DMEA-II+ .................................................................. 103 3.2.2. Giải thuật MOEA/D++ ............................................................... 107 3.3. Thử nghiệm và đánh giá..................................................................... 113 3.3.1. Kịch bản thử nghiệm ................................................................... 113 3.3.2. Kết quả thử nghiệm ..................................................................... 116
v 3.3.3. Đánh giá chung về kỹ thuật ........................................................ 130 3.4. Một số đánh giá giữa các kỹ thuật được phát triển trong luận án ...... 133 3.5. Kết luận Chương 3 ............................................................................. 135 KẾT LUẬN .................................................................................................. 136 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ......... 138 TÀI LIỆU THAM KHẢO .......................................................................... 139 PHỤ LỤC ........................................................................................................ p1
vi DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT Số chiều của véc-tơ biến quyết định (hoặc số chiều của D không gian biến quyết định) f Véc-tơ hàm mục tiêu Gc Số thế hệ trong một phân đoạn thời gian điều chỉnh Ge Số thế hệ trong quá trình điều chỉnh Gmax Số thế hệ tối đa trong quá trình tiến hóa Số mục tiêu của bài toán (hoặc số chiều của không gian M mục tiêu) N Kích thước quần thể Nnon(A) Số giải pháp không bị trội trong tập giải pháp A Non(A) Các giải pháp không bị trội trong tập giải pháp A NPF Kích thước của lớp tối ưu Pareto O Độ phức tạp tính toán của giải thuật P Quần thể cha mẹ Q Quần thể con cái RD Không gian biến quyết định RM Không gian mục tiêu T Số bài toán lân cận của một bài toán con Z Vùng khả thi trong không gian mục tiêu Ω Vùng khả thi trong không gian biến quyết định Kỹ thuật điều khiển thích ứng (Adaptive Control ACT Technique) DE Tiến hóa vi phân (Differential Evolution) DM Người quyết định (Decision Maker) Giải thuật tiến hóa tối ưu đa mục tiêu dựa trên hướng cải DMEA thiện (Direction-based Multi-Objective Evolutionary Algorithm)
vii Giải thuật tiến hóa tối ưu đa mục tiêu dựa trên hướng cải DMEA-II thiện phiên bản II (Direction-based Multi-Objective Evolutionary Algorithm II) Giải thuật cải tiến DMEA-II bằng kỹ thuật điều khiển DMEA-II++ thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp GD Khoảng cách thế hệ (Generational Distance) HV Siêu thể tích (Hypervolume) Khoảng cách thế hệ ngược (Inverted Generational IGD Distance) Giải thuật tiến hóa tối ưu đa mục tiêu (Multi-Objective MOEA Evolutionary Algorithm) Giải thuật tiến hóa tối ưu đa mục tiêu dựa trên phân hoạch MOEA/D (Multi-Objective Evolutionary Algorithm-based on Decomposition) Giải thuật cải tiến MOEA/D bằng kỹ thuật điều khiển MOEA/D+ thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp Giải thuật cải tiến MOEA/D bằng kỹ thuật điều khiển MOEA/D++ thích ứng dựa trên phân bố của quần thể Giải thuật tiến hóa tối ưu đa mục tiêu dựa trên phân hoạch và tiến hóa vi phân (Multi-Objective Evolutionary MOEA/D-DE Algorithm-based on Decomposition and Differential Evolution) Giải thuật cải tiến MOEA/D-DE bằng kỹ thuật điều khiển MOEA/D-DE+ thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp Bài toán tối ưu nhiều mục tiêu (Many-Objective MaOP Optimization Problem) Bài toán tối ưu đa mục tiêu (Multi-Objective Optimization MOP Problem) Giải thuật di truyền sắp xếp không trội II dựa trên tiến hóa NSGAII-DE vi phân (Non-dominated Sorting Genetic Algorithm II and Differential Evolution)
viii Giải thuật cải tiến NSGAII-DE bằng kỹ thuật điều khiển NSGAII-DE+ thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp Lớp tối ưu Pareto trong không gian mục tiêu (Pareto PF Optimal Front) Tập tối ưu Pareto trong không gian biến quyết định PS (Pareto Optimal Set) QI Chỉ số đánh giá chất lượng (Quality Indicator) RD Mật độ dựa trên tia (Ray based Density) Bài toán tối ưu đơn mục tiêu (Single-Objective SOP Optimization Problem) Phương pháp phân hoạch Tchebycheff (Tchebycheff TCH Decomposition) Lớp bài toán mẫu do Q. Zhang, A. Zhou, S. Zhao, P. N. UF Suganthan, W. Liu, S. Tiwari đề xuất (UF benchmark set) Lớp bài toán mẫu do E. Zitzler, K. Deb, L. Thiele đề xuất ZDT (ZDT benchmark set)
ix DANH MỤC CÁC BẢNG Trang Bảng 2.1 Mối quan hệ giữa xu thế tìm kiếm của giải thuật và giá trị của Δ .. 55 Bảng 2.2 Bài toán mẫu trong lớp ZDT sử dụng trong thử nghiệm ................. 75 Bảng 2.3 Bài toán mẫu trong lớp UF sử dụng trong thử nghiệm ................... 75 Bảng 2.4 Thông số thử nghiệm các giải thuật cải tiến bằng kỹ thuật điều khiển thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp ..................................................................................... 77 Bảng 2.5 Kết quả thử nghiệm của DMEA-II và DMEA-II++ ........................ 78 Bảng 2.6 Kết quả thử nghiệm của MOEA/D và MOEA/D+ .......................... 80 Bảng 2.7 Kết quả thử nghiệm của MOEA/D-DE và MOEA/D-DE+ ............. 82 Bảng 2.8 Kết quả thử nghiệm của NSGAII-DE và NSGAII-DE+ ................. 85 Bảng 2.9 Thời gian thực thi của DMEA-II và DMEA-II++ (1.000 thế hệ); MOEA/D và MOEA/D+ (2.000 thế hệ) ......................................... 88 Bảng 2.10 Thời gian thực thi của MOEA/D-DE và MOEA/D-DE+; NSGAII-DE và NSGAII-DE+ (2.000 thế hệ) ................................ 88 Bảng 3.1 Thông số thử nghiệm các giải thuật cải tiến bằng kỹ thuật điều khiển thích ứng dựa trên phân bố của quần thể ............................ 116 Bảng 3.2 Kết quả thử nghiệm của DMEA-II và DMEA-II+ (độ đo GD) .... 117 Bảng 3.3 Kết quả thử nghiệm của DMEA-II và DMEA-II+ (độ đo IGD) ... 118 Bảng 3.4 Thời gian thực thi của DMEA-II và DMEA-II+ (1.000 thế hệ).... 120 Bảng 3.5 Kết quả thử nghiệm của MOEA/D và MOEA/D++ (độ đo GD) .. 123 Bảng 3.6 Kết quả thử nghiệm của MOEA/D và MOEA/D++ (độ đo IGD) . 124 Bảng 3.7 Thời gian thực thi của MOEA/D và MOEA/D++ (1.000 thế hệ) . 126
x DANH MỤC CÁC HÌNH VẼ Trang Hình 1.1 Minh họa các khái niệm trong bài toán tối ưu đa mục tiêu ............. 12 Hình 1.2 Lược đồ cơ bản của giải thuật tiến hóa tối ưu đa mục tiêu .............. 20 Hình 1.3 Minh họa tính hội tụ, tính đa dạng của tập giải pháp....................... 29 Hình 1.4 Minh họa trường hợp mất cân bằng giữa hội tụ và đa dạng ............ 33 Hình 1.5 Minh họa trường hợp chưa đảm bảo đa dạng của tập giải pháp ...... 33 Hình 1.6 Hướng thăm dò và khai thác của giải thuật ..................................... 35 Hình 2.1 Lược đồ cơ bản của kỹ thuật điều khiển thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp ........ 52 Hình 2.2 Minh họa tính toán biến đổi độ đo GD theo chu kỳ ........................ 54 Hình 2.3 Minh họa tập véc-tơ trọng số và lân cận trong MOEA/D................ 63 Hình 2.4 Minh họa toán tử vi phân và tham số chiều dài bước nhảy ꞵ .......... 67 Hình 2.5 So sánh giá trị Δ khi cải tiến DMEA-II với ZDT1 .......................... 78 Hình 2.6 So sánh giá trị Δ khi cải tiến DMEA-II với ZDT2 .......................... 79 Hình 2.7 So sánh giá trị Δ khi cải tiến DMEA-II với UF4 ............................. 79 Hình 2.8 So sánh giá trị Δ khi cải tiến MOEA/D với ZDT1 .......................... 81 Hình 2.9 So sánh giá trị Δ khi cải tiến MOEA/D với ZDT4 .......................... 81 Hình 2.10 So sánh giá trị Δ khi cải tiến MOEA/D với UF1 ........................... 81 Hình 2.11 So sánh giá trị Δ khi cải tiến MOEA/D-DE với ZDT1 .................. 83 Hình 2.12 So sánh giá trị Δ khi cải tiến MOEA/D-DE với ZDT4 .................. 83 Hình 2.13 So sánh giá trị Δ khi cải tiến MOEA/D-DE với UF3 .................... 84 Hình 2.14 So sánh giá trị Δ khi cải tiến NSGAII-DE với ZDT1 .................... 86 Hình 2.15 So sánh giá trị Δ khi cải tiến NSGAII-DE với ZDT3 .................... 86 Hình 2.16 So sánh giá trị Δ khi cải tiến NSGAII-DE với UF1....................... 86 Hình 3.1 Minh họa vùng trống trong không gian mục tiêu ............................ 93 Hình 3.2 Lược đồ cơ bản của kỹ thuật điều khiển thích ứng dựa trên phân bố của quần thể ............................................................................... 98 Hình 3.3 Minh họa hệ thống tia đồng gốc trong giải thuật DMEA-II .......... 103 Hình 3.4 Minh họa hệ thống tia song song trong giải thuật DMEA-II ......... 104 Hình 3.5 Minh họa tâm các vùng trống trong không gian mục tiêu ............. 104
xi Hình 3.6 Minh họa tia tham chiếu tăng cường .............................................. 105 Hình 3.7 Minh họa về vai trò của điểm tham chiếu trong giải thuật MOEA/D (điểm tham chiếu nằm ở xa lớp tối ưu Pareto) .............. 108 Hình 3.8 Minh họa về vai trò của điểm tham chiếu trong giải thuật MOEA/D (điểm tham chiếu nằm ở gần lớp tối ưu Pareto) ............ 109 Hình 3.9 Minh họa tâm của vùng bao của các vùng trống quan tâm............ 109 Hình 3.10 Minh họa điểm tham chiếu mới trong giải thuật MOEA/D++ .... 110 Hình 3.11 Minh họa sự thay đổi của vùng không gian được chiếu bởi tập véc-tơ trọng số khi cải thiện giải thuật MOEA/D ......................... 111 Hình 3.12 So sánh GD giữa DMEA-II+ và DMEA-II với ZDT1 ................ 120 Hình 3.13 So sánh IGD giữa DMEA-II+ và DMEA-II với ZDT1 ............... 121 Hình 3.14 So sánh GD giữa DMEA-II+ và DMEA-II với UF1 ................... 121 Hình 3.15 So sánh IGD giữa DMEA-II+ và DMEA-II với UF1 .................. 121 Hình 3.16 So sánh GD giữa MOEA/D++ và MOEA/D với ZDT1 .............. 127 Hình 3.17 So sánh IGD giữa MOEA/D++ và MOEA/D với ZDT1 ............. 127 Hình 3.18 So sánh GD giữa MOEA/D++ và MOEA/D với ZDT3 .............. 127 Hình 3.19 So sánh IGD giữa MOEA/D++ và MOEA/D với ZDT3 ............. 128 Hình 3.20 Lớp tối ưu Pareto của bài toán mẫu ZDT3 .................................. 129 Hình 3.21 Lớp tối ưu Pareto của bài toán mẫu UF5 ..................................... 130
MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Trong nhiều lĩnh vực như thiết kế, lập kế hoạch, ra quyết định…, nhu cầu giải quyết các bài toán tối ưu là rất lớn. Bài toán tối ưu gồm nhiều mục tiêu có xung đột với nhau và các mục tiêu cần tối ưu đồng thời được gọi là bài toán tối ưu đa mục tiêu [63]. Sự xung đột giữa các mục tiêu dẫn đến lời giải của bài toán tối ưu đa mục tiêu không phải là một giải pháp tối ưu toàn cục duy nhất mà là một tập giải pháp có tính chất thỏa hiệp giữa các mục tiêu [17]. Bài toán tối ưu đa mục tiêu là lớp bài toán khó, yêu cầu phương pháp giải đặc thù với những kỹ thuật chuyên sâu nên là vấn đề thách thức trong lĩnh vực nghiên cứu trong một thời gian dài [11]. Do những hạn chế của phương pháp giải truyền thống trong giải các bài toán tối ưu đa mục tiêu phức tạp [3] nên xu hướng hiện nay là sử dụng phương pháp dựa trên nguyên lý tiến hóa, trong đó giải thuật tiến hóa tối ưu đa mục tiêu là phương pháp hiệu quả do dựa trên cơ chế ngẫu nhiên và xấp xỉ, làm việc trên quần thể nên phù hợp để tìm kiếm tập giải pháp có tính chất thỏa hiệp giữa các mục tiêu [64]. Trải qua quá trình gần 40 năm phát triển, nhiều giải thuật tiến hóa tối ưu đa mục tiêu với những kỹ thuật đặc trưng như dựa trên quan hệ trội, dựa trên phân hoạch, dựa trên hướng, dựa trên độ đo, kỹ thuật lai ghép [87] đã được đề xuất và góp phần giải quyết nhiều bài toán tối ưu đa mục tiêu trong thực tế. Tuy vậy, trong lĩnh vực nghiên cứu vẫn còn một số vấn đề và hướng mở cần được tiếp tục giải quyết như [12], [75], [78], [87]: Giải quyết trường hợp hàm mục tiêu thay đổi trong quá trình tiến hóa; đề xuất các toán tử lai ghép, đột biến mới; duy trì cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa; lai ghép các kỹ thuật nhằm giải các bài toán tối ưu đa mục tiêu có hàm mục tiêu phức tạp và chi phí tính toán lớn; đề xuất cấu trúc dữ liệu hiệu quả hơn để biểu diễn dữ liệu cho bài toán; nghiên cứu giảm thời gian thực thi bằng
2 phương pháp tính toán xấp xỉ hàm mục tiêu, tính toán song song cho các bài toán khó, chi phí lớn; ứng dụng học máy để cải thiện chất lượng của giải thuật; cải thiện tính bền vững của giải thuật trước tác động của nhiễu. Trong các vấn đề kể trên, duy trì cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa là hướng nghiên cứu được quan tâm vì vai trò quyết định của nó đối với chất lượng, hiệu quả của giải thuật tiến hóa tối ưu đa mục tiêu [61]. Cụ thể, khi đánh giá chất lượng, hiệu quả của giải thuật, hai khía cạnh chính được quan tâm là chất lượng của tập giải pháp và hiệu quả tìm kiếm của giải thuật. Với chất lượng của tập giải pháp, người ta quan tâm đồng thời đến chất lượng hội tụ và chất lượng đa dạng còn với hiệu quả tìm kiếm của giải thuật, người ta quan tâm đồng thời đến khả năng thăm dò và khả năng khai thác trong quá trình tiến hóa [10]. Khả năng thăm dò và khai thác của giải thuật có ảnh hưởng lớn đến cân bằng giữa khả năng tìm kiếm toàn cục và cục bộ của giải thuật, từ đó quyết định chất lượng hội tụ và đa dạng của tập giải pháp thu được qua các thế hệ tiến hóa. Theo cơ chế chọn lọc của nguyên lý tiến hóa, chất lượng của tập giải pháp ở thế hệ trước sẽ ảnh hưởng trực tiếp đến chất lượng của tập giải pháp ở các thế hệ sau, do đó cần duy trì cân bằng giữa khả năng thăm dò và khai thác của giải thuật tiến hóa tối ưu đa mục tiêu ngay từ giai đoạn đầu của quá trình tiến hóa để đảm bảo tập giải pháp thu được đồng thời có chất lượng hội tụ và đa dạng tốt trong toàn bộ quá trình tiến hóa. Ngoài ra, đối với các bài toán trong thực tế, duy trì cân bằng giữa khả năng thăm dò và khai thác của giải thuật ngay từ giai đoạn đầu của quá trình tiến hóa cũng giúp sẵn sàng cung cấp cho người quyết định một tập giải pháp có mức độ cân bằng nhất định giữa chất lượng hội tụ và đa dạng trong một khoảng thời gian ngắn phục vụ đưa ra quyết định kịp thời để đáp ứng sự thay đổi liên tục của môi trường. Tuy nhiên, duy trì cân bằng giữa khả năng thăm dò và khai thác là một vấn đề thách thức trong lĩnh vực nghiên cứu vì bản thân nó cũng là một bài toán tối ưu đa mục tiêu [3].
3 Khảo sát cơ chế duy trì cân bằng giữa khả năng thăm dò và khai thác của các giải thuật tiến hóa tối ưu đa mục tiêu điển hình, có thể đánh giá là các giải thuật khi thiết kế đã áp dụng một số kỹ thuật chung để đảm bảo cân bằng giữa khả năng thăm dò và khai thác. Tuy nhiên, các kỹ thuật chung thường thiết lập các tham số với giá trị được cài đặt cố định ngay từ đầu, thông tin tham chiếu được xác định từ giai đoạn khởi tạo hoặc không sử dụng thông tin tham chiếu được trích rút từ phân tích quá trình tiến hóa của giải thuật. Điều này dẫn đến giảm tính linh hoạt của cơ chế duy trì cân bằng và chưa tận dụng được thông tin lịch sử của quá trình tiến hóa. Do đó, cần đề xuất thêm những kỹ thuật chuyên sâu để tăng cường thêm cho các kỹ thuật chung đã được sử dụng. Các công trình nghiên cứu theo hướng duy trì cân bằng giữa khả năng thăm dò và khai thác của giải thuật thường sử dụng kỹ thuật điều khiển thích ứng vì tính linh hoạt và mức độ thích hợp với các bài toán trong thực tế. Một số nhóm kỹ thuật điều khiển thích ứng điển hình gồm kỹ thuật dựa trên phân vùng không gian (sử dụng số lượng phân vùng không gian thích ứng theo quá trình tiến hóa), kỹ thuật dựa trên độ đo (điều khiển quá trình tiến hóa theo hướng cải thiện giá trị độ đo) và kỹ thuật dựa trên tham số của giải thuật (thay đổi giá trị tham số điều khiển để tăng cường khả năng thăm dò/khai thác phù hợp với từng giai đoạn của quá trình tiến hóa). Một số loại thông tin tham chiếu chính được sử dụng trong các kỹ thuật kể trên gồm giai đoạn tiến hóa, giá trị độ đo và phân bố của quần thể. Dựa trên khảo sát, luận án nhận thấy: (i) với thông tin tham chiếu là giai đoạn tiến hóa, việc phân chia giai đoạn thường được xác định ngay từ đầu và không thích ứng theo quá trình tiến hóa; (ii) với thông tin tham chiếu là giá trị độ đo, thường chỉ sử dụng giá trị độ đo tại thế hệ hiện tại (thời điểm), thông tin về xu thế tìm kiếm của giải thuật được xác định dựa trên biến đổi độ đo chất lượng hội tụ và đa dạng của tập giải pháp theo phân đoạn thời gian (quá trình) chưa được chú trọng sử dụng; (iii) với thông tin tham chiếu là phân bố của quần thể, thông tin về vùng chưa có giải pháp được chọn trong phân bố quần thể (vùng trống) vẫn chưa được chú trọng sử dụng.
4 Trên cơ sở đánh giá về những kỹ thuật chung đã được sử dụng trong các giải thuật và phân tích về thông tin tham chiếu được sử dụng trong cơ chế điều khiển cân bằng giữa khả năng thăm dò và khai thác, luận án nhận thấy còn một số vấn đề tồn tại như sau: (i) xu thế tìm kiếm của giải thuật trong một phân đoạn thời gian cho biết giải thuật đang ưu tiên thăm dò hay khai thác, từ đó xác định được giải thuật có đang mất cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa hay không. Vì độ đo chất lượng hội tụ và đa dạng của tập giải pháp phản ánh khả năng khai thác và thăm dò của giải thuật nên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp trong một phân đoạn thời gian là cơ sở định lượng để đánh giá xu thế tìm kiếm của giải thuật và có thể sử dụng để điều khiển cân bằng giữa khả năng thăm dò và khai thác của giải thuật. Tuy nhiên, thông tin về xu hướng biến đổi của các độ đo về hội tụ và đa dạng của tập giải pháp theo phân đoạn thời gian chưa được chú trọng sử dụng làm thông tin tham chiếu trong cơ chế điều khiển thích ứng nhằm cân bằng giữa khả năng thăm dò và khai thác của các giải thuật; (ii) thông tin về phân bố của quần thể cho biết các khu vực bị bỏ qua hoặc chưa được ưu tiên trong không gian tìm kiếm (còn gọi là vùng trống trong luận án). Sự xuất hiện của các vùng trống này chỉ ra rằng tập giải pháp phân bố chưa đều nên chất lượng đa dạng chưa được đảm bảo và giải thuật đang tập trung vào khai thác nên chưa cân bằng được khả năng thăm dò và khai thác trong quá trình tiến hóa. Tuy nhiên, thông tin về các vùng trống chưa được quan tâm sử dụng làm thông tin tham chiếu trong cơ chế điều khiển thích ứng nhằm cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của các giải thuật. Những tồn tại nêu trên chính là động lực nghiên cứu để định hướng cho đề tài luận án và cơ sở để đặt ra giả thuyết về việc sử dụng thông tin đánh giá về xu thế tìm kiếm của giải thuật được xác định dựa trên biến đổi của các độ đo chất lượng hội tụ và đa dạng của tập giải pháp theo phân đoạn thời gian và thông tin về các vùng trống xuất hiện trong phân bố của quần thể làm thông tin tham chiếu cho cơ chế điều khiển thích ứng sẽ giúp duy trì cân bằng giữa khả
5 năng thăm dò và khai thác trong quá trình tiến hóa, góp phần cải thiện chất lượng của giải thuật tiến hóa tối ưu đa mục tiêu. 2. Mục tiêu nghiên cứu Phát triển một số kỹ thuật điều khiển thích ứng nhằm duy trì cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật tiến hóa tối ưu đa mục tiêu. Từ đó, đề xuất áp dụng để cải tiến một số giải thuật tiến hóa tối ưu đa mục tiêu điển hình nhằm minh chứng hiệu quả và tính phổ dụng của những kỹ thuật đã phát triển. 3. Đối tƣợng và phạm vi nghiên cứu Đối tượng nghiên cứu: Kỹ thuật điều khiển thích ứng nhằm cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật tiến hóa tối ưu đa mục tiêu. Phạm vi nghiên cứu: Áp dụng cho một số giải thuật tiến hóa tối ưu đa mục tiêu điển hình thuộc các nhóm dựa trên phân hoạch, dựa trên hướng và dựa trên quan hệ trội trong điều kiện lớp tối ưu Pareto của bài toán tối ưu đa mục tiêu là liên tục. 4. Nội dung nghiên cứu (i) Nghiên cứu tổng quan về giải thuật tiến hóa tối ưu đa mục tiêu, vấn đề đánh giá chất lượng, hiệu quả của giải thuật và tầm quan trọng của việc duy trì cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật. (ii) Nghiên cứu, phát triển kỹ thuật điều khiển thích ứng dựa trên xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp nhằm duy trì cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật. Đề xuất áp dụng phù hợp với đặc điểm riêng để cải tiến các giải thuật DMEA-II, MOEA/D, MOEA/D-DE, NSGAII-DE và thực nghiệm, đánh giá hiệu quả của các giải thuật cải tiến trên một số lớp bài toán mẫu.
6 (iii) Nghiên cứu, phát triển kỹ thuật điều khiển thích ứng dựa trên phân bố của quần thể nhằm duy trì cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật. Đề xuất áp dụng phù hợp với đặc điểm riêng để cải tiến các giải thuật DMEA-II, MOEA/D và thực nghiệm, đánh giá hiệu quả của các giải thuật cải tiến trên một số lớp bài toán mẫu. 5. Phƣơng pháp nghiên cứu Các phương pháp nghiên cứu sử dụng trong luận án gồm: - Sử dụng phương pháp phân tích - tổng hợp: Phân tích cơ sở lý thuyết nhằm hiểu bản chất toán học, cơ chế tiến hóa, phương pháp điều khiển quá trình tiến hóa của giải thuật tiến hóa tối ưu đa mục tiêu để từ đó tổng hợp, phân loại các kỹ thuật điều khiển thích ứng nhằm cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật; - Sử dụng phương pháp quy nạp - diễn dịch: Nghiên cứu các kết quả đã được công bố để xác định xu hướng, phân tích các tồn tại, xác định động cơ nghiên cứu để từ đó đề xuất một số kỹ thuật điều khiển thích ứng mới nhằm cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật tiến hóa tối ưu đa mục tiêu; - Sử dụng phương pháp thực nghiệm: Dùng phần mềm mô phỏng (Matlab phiên bản R2020b, công cụ PlatEMO [82]) để khảo sát cơ chế hoạt động của các giải thuật tiến hóa tối ưu đa mục tiêu gốc; kiểm tra, đánh giá chất lượng, hiệu quả của các giải thuật cải tiến; - Sử dụng phương pháp phân tích - tổng kết: So sánh kết quả thực nghiệm các giải thuật cải tiến với các giải thuật gốc nhằm minh chứng về tính đúng đắn của mô hình toán học, đưa ra các đánh giá về ưu nhược điểm theo các khía cạnh khác nhau, rút ra các kết luận và đề xuất hướng phát triển.
7 6. Ý nghĩa khoa học và thực tiễn của luận án Về ý nghĩa khoa học: Luận án đóng góp thêm vào lĩnh vực nghiên cứu hai kỹ thuật điều khiển thích ứng mới nhằm cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật tiến hóa tối ưu đa mục tiêu. Đồng thời, luận án cũng đề xuất cải tiến được một số giải thuật điển hình thuộc các nhóm giải thuật tiêu biểu (DMEA-II, MOEA/D, MOEA/D-DE, NSGAII-DE), những giải thuật cải tiến được minh chứng tốt hơn các giải thuật gốc thông qua các kết quả thử nghiệm. Về ý nghĩa thực tiễn: Những kỹ thuật điều khiển thích ứng được đề xuất trong luận án giúp cung cấp cho người quyết định tập giải pháp cân bằng giữa chất lượng hội tụ và đa dạng ngay từ giai đoạn đầu của quá trình tiến hóa. Điều này cần thiết để luôn sẵn sàng có một tập giải pháp với chất lượng ở mức độ khả thi nhất định trong thời gian ngắn phục vụ đưa ra quyết định kịp thời để đáp ứng sự thay đổi liên tục của môi trường đối với các bài toán trong thực tế. Đồng thời, các giải thuật cải tiến có thể sử dụng để giải các bài toán tối ưu đa mục tiêu trong thực tế trong nhiều lĩnh vực khác nhau (ví dụ các bài toán trong lĩnh vực quân sự như lập kế hoạch tác chiến, đánh giá phương án tác chiến, tính toán hiệu quả chiến đấu…). 7. Bố cục của luận án Ngoài các phần mở đầu, 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, nội dung chính của luận án được trình bày trong 03 chương như sau: Chƣơng 1. Tổng quan giải thuật tiến hóa tối ƣu đa mục tiêu: Tổng quan một số kiến thức cơ bản, trọng tâm là phân tích tầm quan trọng của vấn đề duy trì cân bằng giữa khả năng thăm dò và khai thác trong quá trình tiến hóa của giải thuật, đánh giá những tồn tại, xác định động lực nghiên cứu, đặt ra giả thuyết và xác định những nội dung cần tập trung nghiên cứu.