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 cấp
Viện, họp tại Viện Khoa học Công nghệ quân sự vào hồi …..
ngày ….. tháng ….. năm 2024
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 chất lượng của tập giải pháp hiệu quả m kiếm
của giải thuật. Duy tcân bằng giữa khả năng thăm khai thác ảnh
hưởng lớn đến hiệu quả tìm kiếm của giải thuật 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ì 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ậy,
việc nghiên cứu, sử dụng phù hợp các thông tin nêu trong 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
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 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 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đa dạng của tập giải pháp á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ể á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 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 giải thuật cải tiến 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ẽ đồ 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 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) 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 phương pháp dựa trên nguyên tiến
hóa, trong đó giải thuật tiến hóa tối ưu đa mục tiêu (MOEA) 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 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
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 lai ghép. Lược đồ hoạt động 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 tính tiêu biểu để khái quát hóa 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 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 g chất ng hiệu qucủ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ụ đa dạng 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 đề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 GD, IGD HV. Các bộ dữ liệu thử nghiệm trong lĩnh vực
nghiên cứu các lớp bài toán mẫu với một số lớp thường được sử dụng
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 chất lượng tốt về hội tụ
đ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 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 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 chất lượng hội tụ kém, giá trị hàm mục tiêu 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 sự tương đồng khá cao về giá trị trên các mục tiêu nhưng thể
bỏ qua những lựa chọn tối ưu toàn cục. Theo nguyên 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 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ị