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

Bài viết tập trung đánh giá một số yếu tố tác động đến chất lượng, hiệu quả của giải thuật, đồng thời phân tích kỹ thuật chỉ dẫn, tác động của các tham số điều khiển quá trình tiến hóa. Từ đó, đề xuất các kỹ thuật chỉ dẫn để nâng cao chất lượng giải thuật thông qua các cơ chế thích ứng, quá trình tiến hóa tự điều chỉnh.
Nội dung trích xuất từ tài liệu:
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 Nghiên cứu khoa học công nghệ 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 Nguyễn Đức Định1*, Nguyễn Long2, Thái Trung Kiên1 Tóm tắt: Trong thực tế, có nhiều bài toán đa mục tiêu (Multi-objective problems - MOPs) khó, nếu giải bằng phương pháp thông thường, kể cả sử dụng giải thuật tiến hóa, vẫn gặp phải nhiều thách thức như: hàm mục tiêu khó mô hình hóa, chi phí tính toán lớn, tài nguyên tính toán có hạn,… Ý tưởng chung để giải quyết các bài toán khó này là làm đơn giản hóa, tách ra thành các bài toán con. Có hai phương pháp phổ biến để thực hiện ý tưởng đó là mô phỏng và sử dụng mô hình xấp xỉ. Trong đó, mô hình xấp xỉ, còn gọi là mô hình đại diện (surrogate model), sử dụng hàm đại diện thay thế cho hàm mục tiêu gốc tỏ ra khá hiệu quả, dễ thực hiện, phù hợp với các bài toán thực tế. Giải thuật tiến hóa đa mục tiêu (Multi-objective evolutionary algorithms - MOEAs) sử dụng mô hình đại diện đang được nhiều nhà nghiên cứu quan tâm. Việc duy trì sự cân bằng giữa khả năng thăm dò (exploration) và khai thác (exploitation) trong quá trình tiến hóa cũng như cân bằng giữa chất lượng hội tụ (convergence) và đa dạng (diversity) của quần thể giải pháp là vấn đề nghiên cứu hết sức cần thiết nhằm nâng cao chất lượng, duy trì tính bền vững của giải thuật. Bài báo tập trung đánh giá một số yếu tố tác động đến chất lượng, hiệu quả của giải thuật, đồng thời phân tích kỹ thuật chỉ dẫn, tác động của các tham số điều khiển quá trình tiến hóa. Từ đó, đề xuất các kỹ thuật chỉ dẫn để nâng cao chất lượng giải thuật thông qua các cơ chế thích ứng, quá trình tiến hóa tự điều chỉnh. Thông qua thử nghiệm với các bài toán mẫu tiêu biểu, sử dụng các độ đo phổ biến, kết quả đã chứng minh tính hiệu quả của các kỹ thuật chỉ dẫn, góp phần tạo ra những phiên bản giải thuật mới giải quyết tốt hơn các bài toán khó. Từ khóa: Kỹ thuật chỉ dẫn; Mô hình đại diện; Kriging; Giải thuật tiến hóa đa mục tiêu. 1. ĐẶT VẤN ĐỀ Các bài toán tối ưu trong thực tế thường có nhiều mục tiêu xung đột với nhau. Bài toán đòi hỏi tìm kiếm các giải pháp tối ưu cho các mục tiêu một cách đồng thời. Bài toán đó được định nghĩa là bài toán tối ưu đa mục tiêu hay bài toán đa mục tiêu và được biểu diễn như sau [10]: minimize {f1(x), f2(x),…, fk(x)} x  S (1) Trong đó: k (≥ 2) là số mục tiêu, fi : R → R là hàm mục tiêu (i =1, 2,…, k). n Véc-tơ các hàm mục tiêu được ký hiệu là f(x) = (f1(x), f2(x),…, fk(x))T. Véc-tơ biến hay véc-tơ quyết định được ký hiệu là x = (x1, x2,…, xn)T thuộc vùng (tập hợp) khả thi S, là không gian con của không gian biến Rn (không gian quyết định). Thuật ngữ “minimize” có nghĩa là tất cả các hàm mục tiêu được cực tiểu hóa đồng thời. Nếu không có sự xung đột giữa các hàm mục tiêu, thì một giải pháp có thể tìm được thỏa mãn mọi hàm mục tiêu là tối ưu. Trong trường hợp này, không cần đến một phương pháp đặc biệt nào để giải quyết. Để tránh trường hợp tầm thường này, giả sử rằng, không tồn tại một giải pháp tối ưu cho tất cả các mục tiêu, có nghĩa là các hàm mục tiêu ít nhất xung đột nhau một phần. Bài toán đa mục tiêu thường có hai hoặc ba mục tiêu, nhưng trong thực tế có nhiều bài toán phức tạp với các đặc điểm như: nhiều mục tiêu, không gian tìm kiếm lớn, hàm mục tiêu khó, do đó, độ phức tạp tính toán lớn, thậm chí là “hộp đen” không mô hình hóa được về toán học. Các bài toán mang đặc điểm đó được xếp vào lớp bài toán đa mục tiêu khó, chi phí lớn (bài toán đa mục tiêu khó). Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 3 Công nghệ thông tin Với bài toán đa mục tiêu thông thường, giải thuật tiến hóa khá phù hợp, hiệu quả và được gọi là giải thuật tiến hóa đa mục tiêu. Giải thuật có nhiều ưu điểm như: Làm việc trên quần thể, sử dụng cơ chế tiến hóa, làm việc theo cơ chế ngẫu nhiên, xấp xỉ, nên có thể giải được hầu hết các bài toán, kể cả bài toán không khả vi. Tuy vậy, với lớp bài toán đa mục tiêu khó, giải thuật gặp nhiều khó khăn. Để giải các bài toán đa mục tiêu khó, chúng ta có thể sử dụng một số phương pháp phổ biến như: mô phỏng, phân hoạch, sử dụng mô hình xấp xỉ. Trong phương pháp mô phỏng, với các kỹ thuật máy tính, không gian tìm kiếm được biểu diễn trực quan và người dùng sẽ quan sát, lựa chọn một hoặc nhiều giải pháp tối ưu. Phương pháp này có ưu điểm là trực quan và vai trò của người dùng rất quan trọng, có tính quyết định. Tuy vậy, để sử dụng phương pháp này đòi hỏi nhiều chi phí và kiến thức chuyên gia của người dùng. Trong phương pháp phân hoạch, bài toán được phân chia thành các bài toán con, đơn giản hơn. Các bài toán con được giải đồng thời để tạo ra tập giải pháp tối ưu. Phương pháp này tương đối hiệu quả, nhưng có nhiều bài toán, việc phân hoạch thành các bài toán con là rất khó, thậm chí không thể phân hoạch. Còn phương pháp sử dụng mô hình xấp xỉ (mô hình đại diện) với các kỹ thuật như bề mặt đáp ứng đa thức (PRS), hàm cơ sở bán kính (RBF), Kriging, máy véc-tơ hỗ trợ (SVM),… kết hợp học máy để xây dựng các hàm đại diện (huấn luyện mô hình) nhằm đơn giản hóa, giảm chi phí tính toán là lựa chọn hiệu quả cho các bài toán đa mục tiêu khó trong thời gian gần đây. Bài báo khảo sát phương pháp sử dụng mô hình đại diện để giải bài toán đa mục tiêu khó, đồng thời đánh giá các yếu tố tác động trong quá trình tiến hóa và cơ chế của mô hình đại diện tới hiệu quả thực thi, chất lượng quần thể giải pháp. Qua đó, đề xuất kỹ thuật chỉ dẫn nhằm cải thiện, nâng cao chất lượng giải thuật. 2. PHƯƠNG PHÁP GIẢI BÀI TOÁN BẰNG MÔ HÌNH ĐẠI DIỆN 2.1. Các kỹ thuật sử dụng mô hìn ...