Tóm tắt Luận án Tiến sĩ Toán học: Nghiên cứu, phát triển một số kỹ thuật 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:27

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 đủ

Tóm tắt Luận án Tiến sĩ Toán học "Nghiên cứu, phát triển một số kỹ thuật 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" được nghiên cứu với mục tiê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.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Toán học: Nghiên cứu, phát triển một số kỹ thuật 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Ự/BTTM TRẦN BÌNH MINH NGHIÊN CỨU, PHÁT TRIỂN MỘT SỐ KỸ THUẬT 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 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2024
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ/BTTM Người hướng dẫn khoa học: 1. PGS.TS Nguyễn Long 2. TS Thái Trung Kiên Phản biện 1: GS.TS Nguyễn Hiếu Minh Học viện Kỹ thuật Mật mã Phản biện 2: PGS.TS Nguyễn Quang Uy Học viện Kỹ thuật quân sự Phản biện 3: TS Đỗ Việt Bình Viện Khoa học và Công nghệ quân sự Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Viện, họp tại Viện Khoa học và Công nghệ quân sự vào hồi ….. ngày ….. tháng ….. năm 2024 Có thể tìm hiểu luận án tại thư viện: - Thư viện Viện Khoa học và Công nghệ quân sự - Thư viện Quốc gia Việt Nam
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án 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 được đánh giá trên hai khía cạnh 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. Duy trì cân bằng giữa khả năng thăm dò và khai thác có ảnh hưởng lớn đến hiệu quả tìm kiếm của giải thuật và chất lượng của tập giải pháp thu được. Thông tin tham chiếu được sử dụng để duy trì cân bằng trong các giải thuật hiện nay thường được cài đặt ngay từ đầu, độc lập với quá trình tiến hóa. Một số thông tin quan trọng được trích rút trong quá trình tiến hóa như xu hướng biến đổi độ đ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 hay các vùng trống xuất hiện trong phân bố của quần thể chưa được sử dụng hoặc sử dụng chưa đầy đủ làm thông tin tham chiếu. Vì vậy, việc nghiên cứu, sử dụng phù hợp các thông tin nê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 giải thuật là cần thiết, có ý nghĩa khoa học và thực tiễn cao. 2. Mục tiêu của luận án 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 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 - Tổng quan giải thuật tiến hóa tối ưu đa mục tiêu, vấn đề đánh giá chất lượng của giải thuật và duy trì cân bằng giữa khả năng thăm dò và khai thác. - 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 và áp dụng để cải tiến các giải thuật DMEA-II, MOEA/D, MOEA/D-DE, NSGAII-DE. - 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ể và áp dụng để cải tiến các giải thuật DMEA-II, MOEA/D. 5. Phương pháp nghiên cứu Phương pháp phân tích - tổng hợp để hiểu cơ chế của giải thuật, từ đó tổng hợp và phân loại các kỹ thuật điều khiển thích ứng. Phương pháp quy nạp - diễn dịch để phân tích tồn tại, từ đó đề xuất một số kỹ thuật điều khiển thích
2 ứng mới. Phương pháp thực nghiệm để kiểm tra, đánh giá chất lượng, hiệu quả của các giải thuật cải tiến. Phương pháp phân tích - tổng kết để đánh giá về ưu nhược điểm, rút ra các kết luận và hướng phát triển. 6. Ý nghĩa khoa học và thực tiễn Ý 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 của giải thuật tiến hóa tối ưu đa mục tiêu và một số giải thuật cải tiến dựa trên các kỹ thuật đã phát triển. Ý nghĩa thực tiễn: Các kỹ thuật phát triển và giải thuật cải tiến có thể ứng dụng giải quyết tốt các bài toán tối ưu đa mục tiêu trong thực tế. 7. Bố cục của luận án Nội dung chính của luận án được trình bày trong 03 chương, với 43 hình vẽ và đồ thị minh họa, 17 bảng biểu, sử dụng 104 đầu tài liệu tham khảo trên hai thứ tiếng (Việt, Anh). Luận án có kết cấu gồm: Mở đầu, 03 chương, kết luận, tài liệu tham khảo và phụ lục. Chương 1. TỔNG QUAN GIẢI THUẬT TIẾN HÓA TỐI ƯU ĐA MỤC TIÊU 1.1. Bài toán tối ưu đa mục tiêu 1.1.1. Phát biểu bài toán Bài toán tối ưu đa mục tiêu (MOP) là bài toán gồm nhiều hơn một mục tiêu, các mục tiêu có sự xung đột và cần được tối ưu đồng thời. 1.1.2. Một số khái niệm cơ bản Những khái niệm cơ bản trong tối ưu đa mục tiêu gồm quan hệ trội Pareto, tối ưu Pareto, tập tối ưu Pareto và lớp tối ưu Pareto. 1.1.3. Người quyết định Là người đưa ra quyết định cuối cùng về giải pháp của MOP. 1.1.4. Ứng dụng của bài toán tối ưu đa mục tiêu trong thực tế MOP được ứng dụng rộng rãi trong nhiều lực vực khác nhau từ kinh tế - xã hội, khoa học kỹ thuật đến an ninh - quốc phòng. 1.1.5. Phương pháp giải bài toán tối ưu đa mục tiêu Gồm phương pháp truyền thống và 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 (MOEA) là phương pháp dựa trên nguyên lý tiến hóa hiệu quả để giải MOP. 1.2. Giải thuật tiến hóa tối ưu đa mục tiêu 1.2.1. Tổng quan về giải thuật MOEA sử dụng nguyên lý tiến hóa để tìm các giải pháp tối ưu toàn cục cho MOP. MOEA đã trải qua bốn giai đoạn phát triển, được chia thành các nhóm 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 và lai ghép. Lược đồ hoạt động cơ bản của MOEA bao gồm ba giai đoạn
3 chính là khởi tạo, vòng lặp tiến hóa và kết thúc. 1.2.2. Một số giải thuật điển hình Một số giải thuật có tính tiêu biểu để khái quát hóa và hướng đến việc áp dụng các kỹ thuật điều khiển thích ứng được đề xuất trong luận án là DMEA- II dựa trên hướng, MOEA/D dựa trên phân hoạch, MOEA/D-DE dựa trên phân hoạch và vi phân, NSGAII-DE dựa trên quan hệ trội và vi phân. 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 1.3.1. Đánh giá chất lượng của tập giải pháp Hội tụ và đa dạng là hai yếu tố cốt lõi trong đánh giá chất lượng của MOEA. Hội tụ thể hiện ở các giải pháp tiệm cận đến lớp tối ưu Pareto (PF) còn đa dạng thể hiện ở các giải pháp phân bố rộng và đều theo lớp PF. Chất lượng của tập giải pháp được đánh giá định lượng bằng độ đo với một số độ đo phổ biến là GD, IGD và HV. Các bộ dữ liệu thử nghiệm trong lĩnh vực nghiên cứu là các lớp bài toán mẫu với một số lớp thường được sử dụng là ZDT, UF, DTLZ, WFG. 1.3.2. Đánh giá hiệu quả tìm kiếm của giải thuật Hướng đến mục tiêu đạt được tập giải pháp có chất lượng tốt về hội tụ và đa dạng, cần nhanh chóng tìm kiếm theo hướng cục bộ để thu được tập giải pháp tiệm cận đến lớp PF nhưng đồng thời cũng phải tìm kiếm rộng khắp trong không gian tìm kiếm để đảm bảo tính tối ưu toàn cục. Do đó, MOEA cần có khả năng để khai thác tại khu vực lân cận của các giải pháp đã thu được và khả năng thăm dò những khu vực mới trong không gian mục tiêu. 1.3.3. Đánh giá trên một số tiêu chí khác Gồm tính bền vững và độ phức tạp tính toán của giải thuật. 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 1.4.1. Cân bằng giữa hội tụ và đa dạng của tập giải pháp Nếu tập giải pháp có chất lượng hội tụ kém, giá trị hàm mục tiêu là tương đối kém ở ít nhất một mục tiêu. Ngược lại, khi chất lượng đa dạng kém, tập giải pháp có sự tương đồng khá cao về giá trị trên các mục tiêu nhưng có thể bỏ qua những lựa chọn tối ưu toàn cục. Theo 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 thế hệ sau, do đó cần phải đạt được đồng thời chất lượng hội tụ và đa dạng ở các thế hệ trước. 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 Nếu MOEA thiên về thăm dò, việc tìm kiếm sẽ được thực hiện rộng trong không gian tìm kiếm dẫn đến đảm bảo tính chất toàn cục và cải thiện chất lượng đa dạng, tuy nhiên tốc độ thu nhận các giải pháp tiệm cận đến lớp PF chậm và chưa cải thiện chất lượng hội tụ. Ngược lại, khi MOEA thiên về khai thác, việc tìm kiếm được thực hiện quanh các khu vực đã thăm dò dẫn đến cải thiện chất lượng hội tụ, tuy nhiên khả năng mở rộng không gian tìm kiếm bị
4 hạn chế và chưa cải thiện được chất lượng đa dạng. Sự mất cân bằng giữa khả năng thăm dò và khai thác ở giai đoạn trước ảnh hưởng lớn đến quá trình tìm kiếm ở giai đoạn sau, do đó cần duy trì cân bằng ngay giai đoạn đầu nhằm đảm bảo hiệu quả tìm kiếm của giải thuật trong toàn bộ quá trình tiến hóa. 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 Một số nhóm kỹ thuật điều khiển thích ứng điển hình nhằm duy trì cân bằng giữa khả năng thăm dò và khai thác gồm nhóm dựa trên phân vùng không gian, nhóm dựa trên độ đo và nhóm dựa trên tham số của giải thuật. 1.5. Đề xuất nội dung nghiên cứu của luận án 1.5.1. Một số vấn đề tồn tại trong lĩnh vực nghiên cứu - Việc sử dụng thông tin về xu hướng biến đổi độ đo về hội tụ và đa dạng của tập giải pháp theo các phân đoạn thời gian như một cơ sở định lượng để đánh giá về xu thế tìm kiếm của giải thuật và sử dụng thông tin tương quan biến đổi giữa các độ đo làm thông tin tham chiếu để điều chỉnh quá trình tìm kiếm nhằm duy trì cân bằng giữa khả năng thăm dò và khai thác trong các thế hệ tiếp theo vẫn chưa được chú trọng. - Nếu định nghĩa vùng trống là các vùng trong không gian mục tiêu nằm giữa các giải pháp được chọn thì thông tin về các vùng trống trong phân bố của quần thể chưa được chú trọng sử dụng làm thông tin tham chiếu trong 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 của giải thuật trong quá trình tiến hóa. 1.5.2. Giả thuyết nghiên cứu - Nếu sử dụng 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 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 tương quan biến đổi giữa các độ đo làm thông tin tham chiếu để điều khiển thích ứng theo hướng tăng cường khả năng chưa được ưu tiên sẽ giúp duy trì tốt hơn sự cân bằng giữa khả 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. - Nếu sử dụng thông tin về các vùng trống trong phân bố của quần thể làm thông tin tham chiếu để tăng cường tìm kiếm trong các khu vực này sẽ giúp mở rộng khu vực tìm kiếm, tránh bỏ qua các giải pháp tốt, từ đó giúp duy trì tốt hơn sự cân bằng giữa khả 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. 1.5.3. Nội dung nghiên cứu của luận án - 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 và đề xuất cải tiến các giải thuật DMEA-II, MOEA/D, MOEA/D-DE, NSGAII-DE. - 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ố
5 của quần thể và đề xuất cải tiến các giải thuật DMEA-II, MOEA/D. 1.6. Kết luận Chương 1 Chương 1 trình bày kiến thức cơ sở, tập trung vào vai trò việc duy trì cân bằng giữa khả năng thăm dò và khai thác. Một số tồn tại được xác định làm cơ sở đặt ra giả thuyết và xác định các nội dung cần nghiên cứu trong luận án. 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 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 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 Độ đo hội tụ phản ánh khả năng khai thác của giải thuật, độ đo đa đạng phản ánh khả năng thăm dò của giải thuật. Vì thế, xu hướng 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 theo hướng cải thiện trong một phân đoạn thời gian thể hiện xu thế tìm kiếm của giải thuật, thông tin tương quan biến đổi các độ đo chất lượng của tập giải pháp có thể sử dụng làm thông tin tham chiếu để điều khiển thích ứng nhằm duy trì sự cân bằng giữa khả năng thăm dò và khai thác của giải thuật. 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 Phân tích xu hướng biến đổi chất lượng của tập giải pháp về hội tụ và đa dạng theo phân đoạn thời gian để xác định xu thế tìm kiếm của giải thuật, sử dụng tương quan biến đổi giữa các độ đo làm thông tin tham chiếu để điều khiển thích ứng quá trình tiến hóa. Các độ đo được lựa chọn sử dụng là GD và IGD. Các bước cơ bản của kỹ thuật khi nhúng trong lược đồ cơ bản của MOEA được trình bày trong Hình 2.1: (1) Khởi tạo: Cài đặt các tham số của giải thuật, kỹ thuật và khởi tạo quần thể ban đầu P0; tính giá trị GD và IGD của quần thể P0; khởi tạo giá trị maxGD và maxGD làm tham chiếu khi so sánh tương quan biến đổi: maxGD  GD( P0 ); maxIGD  IGD( P0 ) (2.1) (2) Vòng lặp tiến hóa: - Tính giá trị độ đo GDcGen và IGDcGen của quần thể hiện tại; cập nhật maxGD, maxIGD dựa trên giá trị GD và IGD lớn nhất tính đến thế hệ cGen. - Nếu cGen là thế hệ cuối của một chu kỳ điều chỉnh: + Tính toán biến đổi của GD và IGD trong chu kỳ:  GD   GD cGen  Gc   GDcGen / maxGD (2.2)
6  IGD   IGD cGen  Gc  IGDcGen / maxIGD  (2.3) + Tính toán tương quan biến đổi của GD và IGD trong chu kỳ:   GD   IGD (2.4) + Điều chỉnh giá trị tham số điều khiển của giải thuật theo Δ. - Tiếp tục thực hiện theo lược đồ của giải thuật gốc, tham số điều khiển với giá trị thay đổi theo Δ sẽ điều khiển thích ứng quá trình tiến hóa trong phân đoạn thời gian tiếp theo. (3) Kết thúc: Tập giải pháp cung cấp cho người quyết định. Bắt đầu 1. Khởi tạo: Khởi tạo quần thể ban đầu và các tham số 2. Vòng lặp tiến hóa Thỏa mãn Đúng điều kiện dừng? Sai Kết thúc quá trình Đúng điều chỉnh? Các bước trong kỹ Sai thuật điều khiển thích 2.1. Tính toán giá trị GD, IGD ứng dựa trên xu hướng 2.2. Tính toán giá trị GD, IGD lớn biến đổi độ nhất cho đến vòng lặp hiện tại đo về hội tụ và đa dạng của tập giải 2.3. Kết thúc chu kỳ Sai pháp điều chỉnh? Đúng 2.3.1. Tính toán biến đổi của GD và IGD trong chu kỳ 2.3.2. Tính toán tương quan giữa biến đổi của GD và IGD 2.3.3. Điều chỉnh giá trị tham số điều khiển của giải thuật theo giá trị tỷ lệ tương quan 2.4. Tiếp tục theo lược đồ của giải thuật gốc 3. Kết thúc: Chọn các giải pháp tốt để cung cấp cho người quyết định Kết thúc 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
7 Giải thuật 2.1. CalculateCorrelation Đầu vào: cGen: thế hệ hiện tại; P: quần thể của thế hệ cGen; Ge: số thế hệ trong quá trình điều chỉnh; Gc: số thế hệ trong một chu kỳ điều chỉnh; GDe, IGDe: tập lưu trữ giá trị GD, IGD trong quá trình tiến hóa; maxGD, maxIGD: giá trị GD, IGD lớn nhất tính đến trước thế hệ cGen; dtold: giá trị delta của chu kỳ trước đó. Đầu ra: giá trị tương quan biến đổi giữa các độ đo dt. 1: if (cGen ≤ Ge) then 2: gd  GD(P). 3: igd  IGD(P). 4: GDe(cGen)  gd; IGDe(cGen)  igd. 5: if (maxGD < gd) then maxGD  gd end if. 6: if (maxIGD < igd) then maxIGD  igd end if. 7: dt  dtold. 8: if (cGen mod Gc) = 0 then 9: dtGD  (GDe(cGen-Gc) - gd)/maxGD. 10: dtIGD  (IGDe(cGen-Gc) - igd)/maxIGD. 11: dt  dtGD - dtIGD. 12: end if 13: end if 14: return dt. 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 Quy trình áp dụng phải phù hợp với đặc điểm và dựa trên khảo sát tham số điều khiển ảnh hưởng đến khả năng thăm dò/khai thác của MOEA. 2.2. Đề xuất cải thiện một số giải thuật điển hình 2.2.1. Giải thuật DMEA-II++ Giải thuật gốc DMEA-II chọn số giải pháp con theo hướng hội tụ và hướng tản mát dựa trên tỷ lệ giải pháp không bị trội trong tập giải pháp, tuy nhiên, số giải pháp không bị trội trong tập giải pháp lớn không đồng nghĩa với tập giải pháp có tính đa dạng kém và ngược lại, nên không thể hiện được xu thế tìm kiếm của giải thuật. Luận án đề xuất phương án sử dụng tỷ lệ hướng linh hoạt dựa trên tương quan biến đổi giữa các độ đo với số giải pháp sinh theo các hướng được chọn như sau: nCD  Normalize(0, 5  ) x N ; nSD  N  nCD (2.6) Trong đó: nCD và nSD là số giải pháp chọn theo hướng hội tụ và đa dạng; Normalize() để đảm bảo nCD thuộc khoảng từ 10% đến 90% số giải pháp của tập giải pháp nhằm tránh ưu tiên quá mức vào một hướng.
8 Khi giá trị Δ > 0 (giải thuật đang ưu tiên khả năng khai thác), số giải pháp con được sinh theo hướng hội tụ nCD nhỏ hơn số giải pháp con sinh theo hướng tản mát nSD, thể hiện rằng điều chỉnh theo hướng tăng cường thăm dò. Ngược lại với trường hợp Δ < 0. Trường hợp Δ = 0, số giải pháp con theo hai hướng mát cân bằng nhau. Giải thuật 2.2. DMEA-II++ [CT2] Đầu vào: MOP với M là số mục tiêu; điều kiện dừng; N: kích thước quần thể; Ge: số thế hệ trong quá trình điều chỉnh; Gc: số thế hệ trong một chu kỳ điều chỉnh. Đầu ra: quần thể P chứa các giải pháp của bài toán. 1: Khởi tạo quần thể P; C  ∅; CD  ∅; SD  ∅; 2: GDe(0) = GD(P); IGDe(0) = IGD(P). 3: maxGD  GDe(0); maxIGD  IGDe(0); dtold  0. 4: while (điều kiện dừng chưa thỏa mãn) do 5: Fitness(P); A  Non(P); B  ∅; 6: dt  CalculateCorrelation(); dtold  dt. 7: nCD  Normalize(0,5 - dt) x N; nSD  N - nCD. 8: while (|B| < N) do 9: Par  RandParent(P). 10: if (|CD| < nCD) then 11: CDnew  NewRay(); CD  CD  {CDnew}; S1  NewSolution(Par,CDnew); B  B  {S1}. 12: elseif (|SD| < nSD) then 13: SDnew  NewRay(); SD  SD  {SDnew}; S2  NewSolution(Par,SDnew); B  B  {S2}. 14: end if 15: end while 16: PMutation(B); Fitness(B); C  A  B. 17: for i = 1 to N 18: Smin  GetSolution(C,R(i)); A  A  {Smin}. 19: end for 20: if (Nnon(C) < N/2) then P  Non(C). 21: else 22: Niching(C); Sort(C, niching); P  GetNiching(C,N/2). 24: end if 25: FillSolution(P, C, N). 26: end while 27: return P.
9 2.2.2. Giải thuật MOEA/D+ Giải thuật 2.3. MOEA/D+ [CT3] Đầu vào: MOP với M là số mục tiêu; điều kiện dừng; N: số lượng bài toán con; tập véc-tơ trọng số λ = (λ1,…,λN); T: kích cỡ tập lân cận; Ge: số thế hệ điều chỉnh; Gc: số thế hệ trong một chu kỳ điều chỉnh; ε: ngưỡng thay đổi. Đầu ra: quần thể EP chứa các giải pháp của bài toán. 1: EP  ∅; 2: B  FindNeighbor(T). 3: Khởi tạo quần thể P =(x1, x2,…,xN). 4: FVi  f(xi) với i = (1,…,N). 5: z  (z1,z2,…,zM): zk = min(fk(x1), fk(x2),…, fk(xN)). 6: GDe(0) = GD(P); IGDe(0) = IGD(P); niche  0. 7: maxGD  GDe(0); maxIGD  IGDe(0); dtold  0. 8: while (điều kiện dừng chưa thỏa mãn) do 9: for i = 1 to N 10: y  Reproduction(B(i)); y’  Enhance(y). 11: for j = 1 to M /* Cập nhật điểm tham chiếu */ 12: if zj > fj(y’) then zj  fj(y’) end if 13: end for 14: dt  CalculateCorrelation(); Tnew  T; dtold  dt. 15: niche  AdjustNiche(Δ); 16: Tnew  Tnew + Normalize(niche). 17: B  FindNeighbor(Tnew). 18: for each j ∈ B(i) 19: if ( | ( | then 20: x  y’; FV  f(y’). j j 21: end if 22: end for 23: UpdateEP(y’). 24: end for 25: end while 26: return EP. Trong giải thuật gốc MOEA/D, nếu số lượng véc-tơ lân cận của một véc-tơ trọng số (T) lớn sẽ dẫn đến các giải pháp cha mẹ được chọn để đưa vào bể phối xa nhau, từ đó giải pháp con có thể rất xa với giải pháp cha mẹ, dẫn đến
10 tăng tính đa dạng. Ngược lại, đối với trường hợp T có giá trị nhỏ. Như vậy, nếu điều chỉnh giá trị tham số T trong một khoảng phù hợp có thể định hướng tăng cường khả năng thăm dò hoặc khai thác. Tham số T trong giải thuật gốc MOEA/D được đặt cố định tại bước khởi tạo, độc lập với quá trình tiến hóa, chưa có cơ chế sử dụng tham số linh hoạt dựa vào xu thế tìm kiếm của giải thuật. Luận án đề xuất phương án sử dụng tham số số lượng véc-tơ lân cận động dựa trên tương quan biến đổi giữa các độ đo trong quá trình tiến hóa như sau: niche  1 nÕu  >  niche   niche  1 nÕu  < -  (2.7) Tnew T  Normalize(niche) Trong đó: niche là số lượng véc-tơ tăng hoặc giảm so với số lượng véc-tơ lân cận được cài đặt từ ban đầu; ε = 2 là tham số thực nghiệm để xác định ngưỡng thay đổi; Normalize() để đảm bảo niche nằm trong khoảng [-T/2; T/2] nhằm tránh ưu tiên quá mức vào một hướng; Tnew là số lượng véc-tơ lân cận mới, được khởi tạo lại về giá trị ban đầu mỗi khi kết thúc chu kỳ điều chỉnh trước khi thay đổi phụ thuộc vào giá trị Δ ở cuối chu kỳ. Khi Δ vượt ngưỡng trên (giải thuật đang ưu tiên khả năng khai thác), giá trị niche sẽ tăng dẫn đến số lượng véc-tơ lân cận tăng để thể hiện hướng điều chỉnh là tăng cường thăm dò. Ngược lại với trường hợp Δ vượt ngưỡng dưới. Trường hợp Δ nằm trong ngưỡng thì số lượng véc-tơ lân cận không thay đổi. 2.2.3. Giải thuật MOEA/D-DE+ Trong giải thuật gốc MOEA/D-DE, tham số chiều dài bước nhảy của biến thiên vi phân trong chiến lược đột biến “DE/rand/1” có ảnh hưởng đến chất lượng hội tụ và đa dạng của tập giải pháp. Khi ꞵ nhỏ thì mức độ khuếch đại thấp dẫn đến giảm đa dạng và ngược lại. Giải thuật gốc MOEA/D-DE sử dụng giá trị ꞵ cố định (bằng 0,5), cài đặt từ giai đoạn khởi tạo, độc lập với quá trình tiến hóa. Luận án đề xuất phương án sử dụng tham số bước nhảy linh hoạt của biến thiên vi phân được tính toán dựa trên tương quan biến đổi giữa các độ đo. Công thức tính tham số bước nhảy linh hoạt của biến thiên vi phân:   Normalize(0, 5   x  ) (2.9) Trong đó: ω là tham số bước để điều chỉnh giá trị của ꞵ, giá trị thực nghiệm là 20; Normalize() để đảm bảo ꞵ thuộc khoảng [0,1; 0,9] nhằm tránh ưu tiên quá mức vào một hướng. Khi Δ > 0 (giải thuật đang ưu tiên khả năng khai thác), mức độ khuếch đại cao để định hướng tăng cường khả năng thăm dò. Ngược lại với trường hợp Δ < 0. Trường hợp Δ = 0 thì ꞵ = 0,5 như giải thuật gốc.
11 Giải thuật 2.4. MOEA/D-DE+ [CT5] Đầu vào: MOP với M là số mục tiêu; điều kiện dừng; N: số lượng bài toán con; tập véc-tơ trọng số λ = (λ1,…,λN); T: kích cỡ tập lân cận; δ: xác suất cha mẹ được chọn từ lân cận; nr: số lượng tối đa giải pháp cha mẹ bị thay thế bởi giải pháp con; Ge: số thế hệ trong quá trình điều chỉnh; Gc: số thế hệ trong một chu kỳ điều chỉnh; ω: tham số bước. Đầu ra: tập xấp xỉ lớp Pareto FV = {f(x1),...,f(xN)}. 1: B  FindNeighbor(T). 2: Khởi tạo quần thể P = (x1, x2,…,xN). 3: FVi  f(xi) với i = (1,…,N). /* f là hàm mục tiêu */ 4: z  (z1,z2,…,zM): zk = min(fk(x1), fk(x2),…, fk(xN)). 5: GDe(0) = GD(P); IGDe(0) = IGD(P). 6: maxGD  GDe(0); maxIGD  IGDe(0); dtold  0. 7: while (điều kiện dừng chưa thỏa mãn) do 8: for i = 1 to N 9: Tạo ngẫu nhiên một số rand ∈ [0, 1].  B (i ) rand   10: PN   {1,...,N} rand   11: dt  CalculateCorrelation();dtold  dt. 12: ꞵ  Normalize(0,5 + dt x ω). 13: y  Reproduction(B(i)); y’  Enhance(y). 14: for j = 1 to M /* Cập nhật điểm tham chiếu */ 15: if zj > fj(y’) then zj  fj(y’) end if 16: end for 17: c  0. 18: while (c < nr) and (PN ≠ ∅) do 19: Lấy ngẫu nhiên một chỉ số j từ PN 20: if ( | ( | then 21: xj  y’; FVj  f(y). 22: end if 23: c  c + 1. 24: Loại bỏ j khỏi PN. 25: end while 26: end for 27: end while 28: return FV
12 2.2.4. Giải thuật NSGAII-DE+ Giải thuật 2.5. NSGAII-DE+ [CT6] Đầu vào: MOP với M là số mục tiêu; điều kiện dừng; N: kích thước quần thể; Ge: số thế hệ trong quá trình điều chỉnh; Gc: số thế hệ trong một chu kỳ điều chỉnh. Đầu ra: quần thể chứa các giải pháp của bài toán. 1: t = 0; Khởi tạo quần thể Pt; 2: GDe(0) = GD(Pt); IGDe(0) = IGD(Pt). 3: maxGD  GDe(0); maxIGD  IGDe(0); dtold  0. 4: while (điều kiện dừng chưa thỏa mãn) do 5: dt  CalculateCorrelation();dtold  dt. 6: if (dt 0) bR  Normalize(dt) else bR  0,3. 7: Qt  MakeNewPop(Pt, bR). 8: Rt  Pt  Qt. 9: F  FastNonSort(Rt). 10: Pt+1  ∅. 11: i  1. 12: while (|Pt+1| + |Fi|)  N do 13: CrowdingDistance(Fi). 14: Pt+1  Pt  Fi. 15: i  i + 1. 16: end while 17: SortCrowding(Fi). 18: Pt+1  Pt+1  Fi[1:(N – |Pt+1|)]. 19: t  t + 1. 20: end while 21: return Pt. Trong giải thuật gốc NSGAII-DE, tỷ lệ phần trăm để chọn giải pháp ứng viên cho theo chiến lược chiến lược đột biến “DE/best/1” có ảnh hưởng đến chất lượng hội tụ và đa dạng của tập giải pháp. Cụ thể với các tham số khác cố định thì: - Khi tỷ lệ phần trăm nhỏ, số giải pháp được chọn làm ứng viên cho xG ít rBest nên xác suất để xG là giải pháp không bị trội cao. Do đó, giải pháp sinh bởi rBest toán tử tiến hóa vi phân sẽ có tỷ lệ không bị trội cao, dẫn đến góp phần làm tăng hội tụ của tập giải pháp; - Ngược lại, khi tỷ lệ phần trăm lớn, số giải pháp được chọn làm ứng viên
13 cho xG lớn nên xác suất để xG nằm rộng trong các phân vùng con của rBest rBest không gian tìm kiếm cao hơn. Vì vậy, giải pháp sinh bởi toán tử tiến hóa vi phân sẽ nằm rộng trong không gian tìm kiếm, dẫn đến góp phần làm tăng đa dạng của tập giải pháp. Giải thuật gốc NSGAII-DE sử dụng tỷ lệ cố định khi chọn cá thể tốt nhất cho toán tử vi phân (bằng 30%), cài đặt từ giai đoạn khởi tạo, độc lập với quá trình tiến hóa. Luận án đề xuất phương án sử dụng tỷ lệ linh hoạt được tính toán dựa trên tương quan biến đổi giữa các độ đo theo công thức sau: bR  Normalize( ) (2.11) Trong đó: bR tỷ lệ phần trăm để chọn giải pháp ứng viên cho xG ; rBest Normalize() để đảm bảo bR thuộc khoảng [0,2; 0,8]. Khi Δ > 0 (giải thuật đang ưu tiên khả năng khai thác), bR sẽ lớn, do đó tỷ lệ để chọn giải pháp ứng viên cho xG lớn dẫn đến định hướng tăng cường rBest khả năng thăm dò nhằm tăng tính đa dạng. Ngược lại với trường hợp Δ < 0. Trường hợp Δ = 0 thì bR = 0,3 như giải thuật gốc. 2.3. Thử nghiệm và đánh giá 2.3.1. Kịch bản thử nghiệm Lựa chọn 10 bài toán mẫu thuộc các lớp bài toán mẫu ZDT và UF để thử nghiệm. Thiết lập thông số cho bài toán, giải thuật, kỹ thuật. 2.3.2. Kết quả thử nghiệm a) Với giải thuật DMEA-II++ Bảng 2.5 Kết quả thử nghiệm của DMEA-II và DMEA-II++ Giải thuật DMEA-II DMEA-II++ Bài toán Trung bình Độ lệch chuẩn Trung bình Độ lệch chuẩn ZDT1 -0,2762 0,0652 -0,1428 0,0682 ZDT2 -0,1699 0,0381 -0,1358 0,0811 ZDT3 -0,2234 0,0958 -0,1686 0,0478 ZDT4 -0,0548 0,1493 -0,0777 0,1928 ZDT6 -0,3454 0,1209 -0,0432 0,1195 UF1 -0,4700 0,2020 -0,2847 0,1593 UF2 -0,5573 0,2261 -0,4710 0,2265 UF3 -0,4711 0,0037 -0,1714 0,0669 UF4 -0,4374 0,2373 -0,4933 0,2417 UF5 -0,2785 0,1991 -0,2056 0,1381 +/-/= 8/2/0 Tương quan biến đổi độ đo trong quá trình tiến hóa của DMEA-II++ tốt hơn rõ trên 4 bài toán và tốt hơn trên 4 bài toán. Kết quả với bài toán ZDT4 và UF4 chưa tốt vì lớp PF gồm nhiều điểm tối ưu cục bộ (ZDT4) hoặc không lồi (UF4) nên cần ưu tiên nhiều hơn khả năng thăm dò để tránh bẫy tối ưu cục bộ.
14 Kết quả thử nghiệm cho thấy việc cải tiến giải thuật DMEA-II bằng kỹ thuật điều khiển thích ứng đề xuất cho kết quả tốt. b) Với giải thuật MOEA/D+ Bảng 2.6 Kết quả thử nghiệm của MOEA/D và MOEA/D+ Giải thuật MOEA/D MOEA/D+ Bài toán Trung bình Độ lệch chuẩn Trung bình Độ lệch chuẩn ZDT1 -0,6532 2,0747 -0,2755 1,2456 ZDT2 -1,1863 4,1209 -0,5399 2,1085 ZDT3 -0,1108 1,1237 -0,0619 0,5708 ZDT4 -0,4122 2,0665 -0,1774 1,3261 ZDT6 -3,4848 8,0759 -1,6774 4,0383 UF1 -0,0032 0,1692 -0,0022 0,0187 UF2 0,0520 0,6186 0,0310 0,3678 UF3 -0,0340 0,4286 0,0096 0,5830 UF4 0,0382 0,1905 0,0339 0,3042 UF5 0,0070 0,1760 0,0010 0,0964 +/-/= 10/0/0 Tương quan biến đổi độ đo trong quá trình tiến hóa của MOEA/D+ tốt hơn rõ trên 4 bài toán và tốt hơn trên các bài toán còn lại. Kết quả thử nghiệm cho thấy việc cải tiến giải thuật MOEA/D bằng kỹ thuật điều khiển thích ứng đề xuất cho kết quả tốt. c) Với giải thuật MOEA/D-DE+ Bảng 2.7 Kết quả thử nghiệm của MOEA/D-DE và MOEA/D-DE+ Giải thuật MOEA/D-DE MOEA/D-DE+ Bài toán Trung bình Độ lệch chuẩn Trung bình Độ lệch chuẩn ZDT1 0,0025 0,0121 0,0015 0,0074 ZDT2 0,0021 0,0078 0,0018 0,0048 ZDT3 0,0051 0,0200 0,0038 0,0095 ZDT4 -0,0013 0,0133 -0,0017 0,0134 ZDT6 0,0007 0,0026 0,0004 0,0018 UF1 0,0048 0,0048 0,0014 0,0117 UF2 -0,0106 0,0746 -0,0007 0,0098 UF3 0,0013 0,0161 -0,0002 0,0064 UF4 0,0059 0,0411 0,0056 0,0231 UF5 -0,0026 0,0524 -0,0015 0,0375 +/-/= 9/1/0 Tương quan biến đổi độ đo trong quá trình tiến hóa của MOEA/D-DE+ tốt hơn rõ trên 3 bài toán và tốt hơn trên 6 bài toán. Kết quả với bài toán ZDT4 chưa tốt vì lớp PF gồm nhiều điểm tối ưu cục bộ, cần ưu tiên khả năng thăm dò để tránh bẫy tối ưu cục bộ. Kết quả thử nghiệm cho thấy việc cải tiến giải thuật MOEA/D-DE bằng kỹ thuật điều khiển thích ứng đề xuất cho kết quả tốt.
15 d) Với giải thuật NSGAII-DE+ Bảng 2.8 Kết quả thử nghiệm của NSGAII-DE và NSGAII-DE+ Giải thuật NSGAII-DE NSGAII-DE+ Bài toán Trung bình Độ lệch chuẩn Trung bình Độ lệch chuẩn ZDT1 0,0671 0,1392 0,0388 0,0802 ZDT2 0,0422 0,0803 0,0319 0,0571 ZDT3 0,0852 0,1591 0,0976 0,1622 ZDT4 0,0465 0,0765 0,0207 0,0548 ZDT6 0,0282 0,0517 0,0087 0,0198 UF1 0,1934 0,3261 0,1009 0,1700 UF2 0,1506 0,3147 0,0197 0,1352 UF3 0,1426 0,1831 0,1074 0,1412 UF4 0,1368 0,2353 0,1066 0,2051 UF5 0,0665 0,0905 0,0329 0,0549 +/-/= 9/1/0 Tương quan biến đổi độ đo trong quá trình tiến hóa của NSGAII-DE+ tốt hơn rõ trên 4 bài toán và tốt hơn trên 5 bài toán. Kết quả với bài toán ZDT3 chưa tốt vì lớp PF của bài toán không liên tục, gồm một số phần rời rạc, cần ưu tiên khả năng khai thác tại các vùng này. Kết quả thử nghiệm cho thấy việc cải tiến giải thuật NSGAII-DE bằng kỹ thuật điều khiển thích ứng đề xuất cho kết quả tốt. 2.3.3. Đánh giá chung về kỹ thuật Trong đa số trường hợp, các giải thuật cải tiến đảm bảo cân bằng tốt hơn giữa khả năng thăm dò và khai thác trong quá trình tiến hóa, trong một số trường hợp do PF của các bài toán có các đặc điểm riêng, cần ưu tiên khả năng thăm dò/khai thác nhiều hơn khả năng còn lại nên kỹ thuật chưa phát huy tác dụng. Các giải thuật cải tiến DMEA-II++ và NSGAII-DE+ có độ phức tạp tương đương các giải thuật gốc, các giải thuật cải tiến MOEA/D+ và MOEA/D-DE+ có độ phức tạp lớn hơn các giải thuật gốc. Kỹ thuật hữu ích ngay từ giai đoạn đầu của quá trình tiến hóa vì sự mất cân bằng giữa khả năng thăm dò và khai thác trong giai đoạn này thường xảy ra rõ rệt hơn. Kỹ thuật có tính phổ dụng cao, có khả năng áp dụng để cải tiến nhiều nhóm giải thuật khác nhau. Lớp bài toán phù hợp áp dụng kỹ thuật là lớp bài toán có lớp tối ưu Pareto gồm ít điểm tối ưu cục bộ. Khi giải các bài toán trong thực tế, các giải thuật cải tiến cần thêm bước xác định “lớp tối ưu Pareto thực nghiệm”. 2.4. Kết luận Chương 2 Chương 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 và áp dụng để cải tiến các giải thuật DMEA-II, MOEA/D, MOEA/D-DE, NSGAII-DE. Kết quả thử nghiệm đã minh chứng hiệu quả của kỹ thuật cũng như các giải thuật cải tiến. Các kết quả chính được công bố trong các công trình [CT2], [CT3], [CT5] và [CT6].
16 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Ể 3.1. Kỹ thuật điều khiển thích ứng dựa trên phân bố của quần thể 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 Phân bố của quần thể trong không gian mục tiêu giúp xác định mức độ cân bằng giữa hội tụ và đa dạng của tập giải pháp cũng như xu thế tìm kiếm của giải thuật. Sự xuất hiện các vùng trống lớn trong phân bố của quần thể thể hiện rằng: Giải pháp chưa phân bố đều theo lớp PF dẫn đến tính đa dạng chưa cao, chưa cân bằng giữa chất lượng hội tụ và đa dạng; giải thuật đang tăng cường tìm kiếm theo chiều sâu để khai thác một số khu vực nhất định, chưa tìm kiếm rộng khắp trong toàn bộ không gian tìm kiếm, có thể làm cho quá trình tìm kiếm mất đi tính chất toàn cục và chưa cân bằng giữa khả năng thăm dò và khai thác của giải thuật. f2 Vùng trống trong V1 không gian mục tiêu V2 V3 V4 Lớp tối ưu V5 Pareto Giải pháp xấp xỉ f1 Hình 3.1 Minh họa vùng trống trong không gian mục tiêu Vùng trống trong phân bố quần thể cung cấp thông tin quan trọng, tuy nhiên 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 trong quá trình tiến hóa của giải thuật. 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ể Phân tích đặc điểm phân bố của quần thể để xác định các vùng trống trong không gian mục tiêu và sử dụng làm thông tin tham chiếu cho cơ chế điều khiển thích ứng nhằm định hướng tăng cường tìm kiếm tại các vùng này giúp duy trì tính toàn cục của quá trình tìm kiếm và từ đó đảm bảo cân bằng giữa khả năng thăm dò và khai thác, góp phần nâng cao chất lượng, hiệu quả của giải thuật. Các bước cơ bản của kỹ thuật khi nhúng trong lược đồ cơ bản của MOEA được trình bày trong Hình 3.2: (1) Khởi tạo: Cài đặt tham số của kỹ thuật, giải thuật và khởi tạo quần thể.
17 (2) Vòng lặp tiến hóa: Khởi tạo biến đếm số vùng trống; sắp xếp các cá thể theo giá trị mục tiêu để tạo dãy các điểm liền kề trong không gian mục tiêu; tính diện tích của các hình chữ nhật tạo bởi 2 điểm liền kề trong dãy (số mục tiêu của MOP bằng 3 thì tính thể tích hình hộp); xác định các vùng thỏa mãn điều kiện là vùng trống lớn theo tham số kích thước tối thiểu và lấy các vùng trống dựa trên ưu tiên diện tích/thể tích giảm dần cho đủ số vùng quan tâm; điều chỉnh giá trị tham số điều khiển của giải thuật theo thông tin tham chiếu từ các vùng trống; thực hiện theo lược đồ của giải thuật gốc, tham số với giá trị thay đổi sẽ điều khiển quá trình tiến hóa theo hướng mong muốn. (3) Kết thúc: Tập giải pháp cung cấp cho người quyết định lựa chọn. Bắt đầu 1. Khởi tạo: Khởi tạo quần thể ban đầu và các tham số 2. Vòng lặp tiến hóa Thỏa mãn Đúng điều kiện dừng? Sai Kết thúc quá trình Đúng điều chỉnh? Sai Các bước trong kỹ 2.1. Đặt số lượng vùng trống = 0 thuật điều khiển thích ứng dựa 2.2. Sắp xếp quần thể theo giá trị trên phân hàm mục tiêu bố của quần thể 2.3. Tính toán diện tích các hình chữ nhật tạo bởi 2 điểm liền kề trong dãy sắp xếp 2.4. Xác định các vùng trống thỏa mãn điều kiện Số lượng vùng trống > 0? Sai Đúng 2.5. Điều chỉnh tham số điều khiển giải thuật theo thông tin trích rút từ các vùng trống 2.6. Tiếp tục theo lược đồ của giải thuật gốc 3. Kết thúc: Chọn các giải pháp tốt để cung cấp cho người quyết định Kết thúc 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ể
18 Giải thuật 3.1. FindEmptyRegion Đầu vào: cGen: thế hệ hiện tại; quần thể P với kích thước N; M: số mục tiêu; f: hàm mục tiêu; Ge: số thế hệ trong quá trình điều chỉnh; r: kích thước tối thiểu; nEpt: số lượng vùng trống quan tâm. Đầu ra: tập A lưu thông tin về các vùng trống lớn được quan tâm trong phân bố của quần thể tại thế hệ cGen. 1: if (cGen ≤ Ge) then 2: P’ Sort(P) /* Sắp xếp theo giá trị mục tiêu */ 3: A  ∅; B  ∅. 4: for i = 2 to N 5: isEmptyRegion  1; V  1; 6: for j = 1 to M 7: d[j] = |P’[i].fj–P’[i-1].fj|. /* Cạnh thứ j */ 8: if d[j] < r then isEmptyRegion  0; break. 9: else V = V * d[j] end if 10: end for 11: if (isEmptyRegion = 1) then 12: B[|B| + 1]  {P’[i-1], P’[i], V}. 13: end if 14: end for 15: if B ∅ then 16: A  Sort(B,V) /* Sắp xếp theo diện tích giảm */ 17: if |A| > nEpt then 18: for i = |A| downto nEpt + 1 19: Remove(A[i]). /* Chỉ lấy đủ nEpt vùng lớn nhất */ 20: end for 21: end if 22: end if 23: end if 24: return A. 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 Quy trình áp dụng phải phù hợp với đặc điểm và dựa trên khảo sát tham số ảnh hưởng đến khả năng thăm dò/khai thác của MOEA. 2.2. Đề xuất cải thiện một số giải thuật điển hình 3.2.1. Giải thuật DMEA-II+ Giải thuật gốc DMEA-II chưa có cơ chế tăng cường tìm kiếm vào một khu nhất định trong không gian mục tiêu. Luận án đề xuất phương án sử dụng tia tham chiếu tăng cường qua các vùng trống bằng cách bổ sung vào hệ thống tia của giải thuật gốc các tia tăng cường đi qua tâm các vùng trống. Các tia bổ sung giúp tăng cường tìm kiếm các giải pháp ở khu vực lân cận các vùng trống để tránh bỏ qua giải pháp tốt có tính chất tối ưu toàn cục, góp phần tăng cường tính đa dạng của tập giải pháp.