TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI LUẬN VĂN THẠC SĨ Tối ưu đa mục tiêu ngẫu nhiên ĐÀO MINH HỒNG hoang.dm202895m@sis.hust.edu.vn Ngành Tốn Tin Giảng viên hướng dẫn: TS Nguyễn Cảnh Nam Viện: Toán ứng dụng Tin học HÀ NỘI, 4/2022 Chữ kí GVHD ĐỀ TÀI LUẬN VĂN Tên học viên: Đào Minh Hoàng Mã số học viên: CB20895 Tên đề tài: Tối ưu đa mục tiêu ngẫu nhiên Mã đề tài: 2020BTOANTIN-KH10 Hệ : Thạc sĩ khoa học Ngành: Toán Tin Cán hướng dẫn: TS Nguyễn Cảnh Nam Đơn vị: Viện Toán ứng dụng Tin học, Trường Đại học Bách Khoa Hà Nội Chữ kí GVHD Lời cảm ơn Đầu tiên quan trọng nhất, em xin gửi lời cảm ơn chân thành đến thầy Nguyễn Cảnh Nam thầy Trần Ngọc Thăng - người thầy hướng dẫn tận tình để em hồn thành tốt luận văn Em xin gửi lời cảm ơn chân thành đến thầy Viện Tốn ứng dụng Tin học, trường Đại học Bách Khoa Hà Nội, người tận tâm truyền đạt kiến thức quý giá cho em suốt trình học tập Tiếp theo, em muốn gửi lời cảm ơn đến người bạn xung quanh, đồng nghiệp nhóm AI cơng ty Smartlog bên cạnh động viên, lắng nghe đưa lời khuyên giúp em giải vấn đề luận văn Cuối cùng, em xin gửi lời cảm ơn đến tất thành viên gia đình em, người ln quan tâm tạo động lực để em hồn thành luận văn Hà Nội, ngày tháng năm 2022 Học viên thực Đào Minh Hồng Tóm tắt nội dung luận văn Bản chất hành động loài người việc làm dựa định tối ưu theo Có thể thấy tối ưu yếu tố giúp loài người phát triển, đặc biệt trình sản xuất xã hội đại Vì thế, ngành Tối ưu hoá trở thành lĩnh vực quan tâm, phát triển thiếu Toán học ứng dụng Rất nhiều lớp toán tối ưu khác nghiên cứu để áp dụng giải vấn đề thực tế Tuy nhiên, toán thực tế ngày phức tạp khả đo đạc giá trị ảnh hưởng đến việc mơ hình tốn trở nên khó khăn để xác định xác, việc sử dụng phương pháp mơ hình tối ưu truyền thống với tham số cố định biểu diễn hết yếu tố không chắn từ thực tế Các yếu tố đến từ sai số thiết bị đo, ý kiến chủ quan chun gia, việc khơng đủ khả nhìn hết tầm ảnh hưởng yếu tố, hay đơn giản số lượng mẫu thống kê chưa đủ nhiều để mơ hình xác Chính thế, luận văn tập trung vào việc trình bày số dạng toán tối ưu đa mục tiêu có yếu tố ngẫu nhiên mờ nhằm tăng khả biểu đạt yếu tố không chắn thực tế Sau đó, mơ hình đưa mơ hình định tính tương đương giải phương pháp toán học truyền thống sau đưa dạng toán lồi phương pháp tối ưu ngẫu nhiên dựa thuật tốn tiến hố đa mục tiêu Một số ví dụ đưa để người đọc có nhìn tổng quan kết thử nghiệm tốn thực tế Từ khóa: tối ưu đa mục tiêu, tối ưu ngẫu nhiên mờ, hàm tựa lồi nửa chặt, phương pháp xấp xỉ ngồi, giải thuật tiến hố đa mục tiêu Mục lục PHẦN MỞ ĐẦU Cơ sở lý thuyết 11 1.1 Các khái niệm 11 1.1.1 Hàm tựa lồi hàm tựa lõm 11 1.1.2 Hàm tựa lồi nửa chặt hàm phân thức 12 1.1.3 Tập chuẩn đa hộp 16 1.2 Bài toán quy hoạch đa mục tiêu tựa lồi nửa chặt 20 1.2.1 Phát biểu toán 20 1.2.2 Phương pháp giải dựa tối ưu đơn điệu 21 1.2.3 Phương pháp giải dựa giải thuật tiến hoá 27 1.2.4 Các độ đo đánh giá kết 30 Bài toán quy hoạch đa mục tiêu tuyến tính với yếu tố bất định 33 2.1 Quy hoạch đa mục tiêu tuyến tính ngẫu nhiên 33 2.1.1 E-model 36 2.1.2 V-model 36 2.1.3 P-model 37 2.1.4 F-model 38 Tối ưu đa mục tiêu ngẫu nhiên 2.1.5 Bài toán tương đương 2.2 Quy hoạch đa mục tiêu tuyến tính ngẫu nhiên mờ 40 46 2.2.1 FE-model 47 2.2.2 FV-model 48 2.2.3 FEV-model 49 2.2.4 Bài toán tương đương 49 Một số ứng dụng quy hoạch đa mục tiêu tuyến tính ngẫu nhiên mờ 52 3.1 Bài toán tối ưu danh mục đầu tư 52 3.1.1 Phát biểu toán 53 3.1.2 Dạng quy hoạch đa mục tiêu tuyến tính ngẫu nhiên 53 3.1.3 Tối ưu tập nghiệm hữu hiệu 55 3.1.4 Kết thử nghiệm 55 3.2 Bài toán tối ưu canh tác 3.2.1 Phát biểu toán 59 59 3.2.2 Dạng quy hoạch đa mục tiêu tuyến tính ngẫu nhiên mờ 60 3.2.3 Kết thử nghiệm KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 61 68 4.1 Kết luận 68 4.2 Hướng phát triển 69 TÀI LIỆU THAM KHẢO 70 Danh sách hình vẽ 1.1 Đồ thị hàm số h(x) = |x| tập số thực R 12 1.2 Đồ thị hàm số h(x) = min{|x|, 1} đoạn [−2, 2] 14 1.3 Quan hệ bao hàm tính chất lồi, tựa lồi nửa chặt tựa lồi 14 1.4 Một tập chuẩn trường hợp hai chiều (được minh họa phần màu xám) 16 1.5 Minh họa tập chuẩn đảo đa hộp đảo 18 1.6 Minh họa cho Mệnh đề 1.8 trường hợp p = 19 1.7 Non-dominated sorting genetic algorithm II 28 1.8 Non-dominated sorting genetic algorithm III 29 1.9 Shift-based Density Estimation 30 1.10 Độ đo Hypervolume 31 1.11 Độ đo GD 32 1.12 Độ đo IGD 32 3.1 Các quần thể NSGA-III toán tối ưu danh mục đầu tư 56 3.2 Phương pháp xấp xỉ ngồi cho tốn tối ưu danh mục đầu tư 57 3.3 Tập nghiệm không gian ảnh hai thuật toán 58 3.4 Các quần thể NSGA-II toán tối ưu canh tác 64 3.5 Tập nghiệm phương pháp xấp xỉ ngồi với thuật tốn tiến hố 66 Danh sách bảng 3.1 Kết tối ưu tập nghiệm hữu hiệu 3.2 Giới hạn sản lượng yêu cầu loại hình canh tác 58 61 3.3 Tham số hàm mục tiêu 62 3.4 Tham số hàm đích mờ 63 3.5 Độ đo hypervolume số quần thể 63 3.6 Tham số khởi tạo thuật toán tiến hoá 64 3.7 Các giá trị Mean, Std, Median, IQR HV, GD, IGD 65 3.8 Mean, Std HV 66 PHẦN MỞ ĐẦU Vận trù học nói chung hay Tối ưu hố nói riêng ngành ứng dụng toán học vào đời sống thực tiễn quan trọng Ngày có nhiều nghiên cứu việc phát triển lớp toán, phương pháp giải ứng dụng vào lĩnh vực Hướng mơ hình tốn tối ưu sử dụng yếu tố ngẫu nhiên tính mờ cách tiếp cận cho việc biểu diễn thông tin không chắn từ thực tế Trong vấn đề nghiên cứu dạng hàm tốn tối ưu, hàm dạng tuyến tính hay lồi quan tâm tính chất đẹp Cụ thể, tính chất nghiệm cực trị địa phương có phải nghiệm cực trị tồn cục hay khơng câu hỏi quan trọng sau câu hỏi có tồn nghiệm cực trị tốn Ngồi ra, ngành nghiên cứu thuật toán tiến hoá giải toán tối ưu đa mục tiêu phát triển có tính ứng dụng cao thực tế với khả giải đa số lớp toán khác với tốc độ tốt khả song song hoá Luận văn “Tối ưu đa mục tiêu ngẫu nhiên” tập trung vào mục tiêu sau: • Nghiên cứu phương pháp mơ hình hóa tốn quy hoạch đa mục tiêu có yếu tố bất định bao gồm ngẫu nhiên mờ • Chuyển toán ngẫu nhiên, mờ toán tất định tương đương Ở đây, tác giả chứng minh tất toán tương đương xét có dạng tốn quy hoạch tựa lồi nửa chặt • Dựa vào tính chất đẹp đẽ lớp toán tựa lồi nửa chặt để đề xuất phương pháp giải hiệu • Ứng dụng kết lý thuyết vào toán nảy sinh thực tế so Tối ưu đa mục tiêu ngẫu nhiên sánh với giải thuật tiến hoá Bố cục luận văn trình bày sau: • Chương 1: giới thiệu, trình bày sở lý thuyết vài thuật ngữ toán tối ưu nghiên cứu luận văn • Chương 2: trình bày cách mơ hình hố tốn tối ưu tuyến tính với yếu tố ngẫu nhiên, mờ kết hợp 2, vài mô hình tất định để định lượng yếu tố • Chương 3: Một số ví dụ thực tế toán tối ưu thêm yếu tố ngẫu nhiên mờ kết thực nghiệm 10