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

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

Thêm vào BST

Báo xấu

36
lượt xem 4
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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ình đại diện Mô hình đại diện sử dụng phương pháp xấp xỉ để giảm chi phí tính toán cho các bài toán đa mục tiêu khó và được mô tả như sau: Nếu gọi f ( x) là hàm hàm mục tiêu (hàm thích nghi) gốc, thì khi đó chúng ta có f '( x) là một hàm đại diện được xác định theo công thức (2) [24]: f '( x) = f ( x) + e( x) (2) Hàm e( x ) là sai số của xấp xỉ. Trong trường hợp này, hàm thích nghi f ( x) không được biết và chúng ta chỉ quan tâm đến giá trị đầu vào hoặc đầu ra. Dựa trên những phản hồi của bộ mô phỏng từ tập dữ liệu lựa chọn huấn luyện, xây dựng lên một hàm đại diện, khi đó mô hình dễ dàng sinh ra các đại diện mô tả mối quan hệ giữa thông tin tham chiếu của đầu vào và đầu ra. Có nhiều cách tiếp cận cho mô hình đại diện và sau đây là một số phương pháp tiếp cận tiêu biểu. 2.1.1. Hàm cơ sở bán kính (The radial basis function - RBF) Trong công trình [5], tác giả đề xuất một phương pháp để xây dựng phương trình cho mặt địa hình cùng các bề mặt bất thường khác, đó là phương pháp phân tích đa phân (multi-quadric analysis). Phương pháp này sử dụng khái niệm hàm cơ sở bán kính (RBF), là hàm có giá trị thực xác định khoảng cách từ tâm của mạng nơ-ron tới điểm đầu 4 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ vào (input point) và được tính theo công thức (3): ( )  x =  ( x) (3) Mô hình RBF thường bao gồm ba lớp: - Lớp đầu vào (Input layer): Làm việc trên một hàm xác định; - Lớp ẩn (Hidden layer): Làm việc trên một hàm kích hoạt RBF phi tuyến; - Lớp đầu ra (Output layer): Làm việc trên hàm  dưới đây:  : Rn → R :  ( x) = i =1 wi i N ( x−c ) i (4) Trong phương pháp này, một vài tham số được sử dụng như: véc-tơ tâm ci , trọng số wi và khoảng cách RBF i. Quá trình tối ưu chính là quá trình tinh chỉnh các tham số này. Dựa trên mô hình, có một số đề xuất gần đây như [3, 8, 13, 21]. 2.1.2. Bề mặt đáp ứng đa thức (The polynomial response surface - PRS) Các tác giả trong [15] đã đề xuất khái niệm tĩnh (static) để phân tích hồi quy nhằm tìm ra phương sai đáp ứng cực tiểu (miminum responsive variance) và được gọi là phương pháp bề mặt đáp ứng (The response surface methodology - RSM). Phương pháp bề mặt đáp ứng đa thức là sự kết hợp giữa RSM với đa thức, được mô tả như sau: ( p) p y = T x (5) Trong đó, tập dữ liệu kích thước n được biểu diễn là x1 , x2 ,..., xn ,  là véc-tơ hệ số p được ước lượng, x là véc-tơ tương ứng để tạo thành cặp x1(p) và x2(p). Có hai cách để ước lượng các hệ số không xác định là phương pháp đạo hàm và phương pháp bình phương tối thiểu. Ở đây, số hệ số chính là số mẫu dữ liệu cần có. Phương pháp bề mặt đáp ứng đa thức thường gồm các bước sau: - Bước 1: Khởi tạo mô hình; - Bước 2: Thực hiện vòng lặp, mô hình sẽ liên tục được thêm hoặc loại bỏ các biến dự báo theo một tiêu chí đặc biệt; - Bước 3: Dừng tìm kiếm khi vòng lặp kết thúc. Dựa trên kỹ thuật này, có một số đề xuất gần đây như [2, 4, 9, 14, 16]. 2.1.3. Máy véc-tơ hỗ trợ (The support vector machine - SVM) Trong công trình [16], dựa trên lý thuyết học máy thống kê, tác giả đề xuất phương pháp sử dụng máy véc-tơ hỗ trợ bao gồm một số phương pháp học có giám sát. Ở đây, tập dữ liệu được phân tích để nhận dạng mẫu. Phương pháp này sử dụng các siêu bề mặt (hyperlanes) trong không gian nhiều chiều để phân lớp, hồi quy và phân tích dữ liệu. Tập đầu vào ánh xạ tới không gian rộng hơn và khi đó chi phí tính toán sẽ giảm đi đáng kể so với việc tính toán tích véc-tơ của các biến trong không gian ban đầu. Khái niệm hàm nhân (kernel function) K(x, y) được sử dụng để giải bài toán hồi quy, là tích véc-tơ có hướng trong không gian rộng hơn. Hàm mất mát (loss function) cũng được dùng đến, là giá trị đo khoảng cách. Bài toán xấp xỉ tập dữ liệu được biểu diễn như sau: f ( x ) = g ( w, x ) + b (6) Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 5
Công nghệ thông tin Và cực tiểu của hàm (7) được gọi là hàm hồi quy tối ưu, trong đó: C là một giá trị xác định,  − và  + là các biến không chặt thể hiện ràng buộc trên và dưới của tập kết quả. w + C  (i− + i+ ) n 1 2  ( w,  ) = (7) 2 i =1 Có một số đề xuất theo phương pháp SVM được công bố ở [10, 15, 16]. 2.1.4. Kriging (KRG) Trong đề xuất [11], tác giả giới thiệu phương pháp Kriging, là một phương pháp bề mặt đáp ứng dựa trên kỹ thuật dự báo không gian. Phương pháp này cực tiểu hóa sai số bình phương trung bình để xây dựng mối tương quan không gian theo các giá trị của một thuộc tính. Trong công trình [18], tác giả phát triển một mô hình hồi quy tham số, được gọi là DACE. Mô hình này là sự mở rộng của phương pháp Kriging đối với bài toán có tối thiểu ba mục tiêu. Mô hình kết hợp giữa hàm đã biết f(x) và hàm ngẫu nhiên Gauss f’(x) được giả định có giá trị trung bình bằng không và hiệp phương sai là: (i ) ( j) (i ) ( j) (i ) ( j) E ( f '( x ), f '( x )) = Cov( f '( x ), f '( x )) =  2 R( , x , x ) (8) ( j) Trong đó, x là hàm tương quan với tham số θ, σ là phương sai quá trình của đáp (i ) ( j) ứng và R( , x , x ) . Dựa trên phương pháp Kriging, có một số công bố gần đây như [1, 2, 5, 7, 20]. Trong phần tiếp theo của bài báo, chúng ta sẽ tìm hiểu và phân tích hiệu quả của kỹ thuật Kriging, kỹ thuật hay được chọn để giải bài toán đa mục tiêu khó, thông qua một số giải thuật tiêu biểu. 2.2. Một số giải thuật tiêu biểu Bài báo lựa chọn hai giải thuật gần đây sử dụng mô hình đại diện dựa trên kỹ thuật Kriging giải bài toán đa mục tiêu khó được xem là hiệu quả để phân tích, đánh giá những vấn đề về cải thiện, nâng cao chất lượng giải thuật. Hai giải thuật đó là K-RVEA (Kriging-assisted reference vector guided evolutionary algorithm) và CSEA (Classification based surrogate-assisted evolutionary algorithm). 2.2.1. Giải thuật K-RVEA Giải thuật K-RVEA được xây dựng dựa trên giải thuật RVEA [21], một giải thuật tiến hóa đa mục tiêu sử dụng véc-tơ tham chiếu. Trong giải thuật RVEA, quá trình tìm kiếm được chỉ dẫn bởi một tập véc-tơ tham chiếu được sinh ra từ các véc-tơ hướng. Các véc-tơ tham chiếu chia không gian mục tiêu thành các không gian con. Sau đó, thực hiện chiến lược lựa chọn giải pháp tinh tú trong mỗi không gian con, sử dụng giá trị khoảng cách góc phạt (angle-penalized distance - APD) để đo khoảng cách giải pháp tới điểm lý tưởng và mức độ gần của giải pháp với véc-tơ tham chiếu. Ví dụ minh họa cho giải thuật RVEA được thể hiện hình 1. Ở ví dụ này, f’ là véc-tơ mục tiêu chuyển đổi, v1 và v2 là hai véc-tơ tham chiếu đơn vị, 1 và 2 là góc giữa f’ với v1, f’ với v2. Nếu 2 < 1 thì giải pháp biểu diễn bởi f’ sẽ được gán với v2. Giải thuật K-RVEA gồm ba bước cơ bản là: khởi tạo, sử dụng và cập nhật mô hình đại diện. 6 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ - Khởi tạo: Giải thuật khởi tạo quần thể bằng phương pháp lấy mẫu LHS (Latin hypercube sampling). Tạo hai tập A1 và A2 để lưu trữ các cá thể được đánh giá bởi hàm mục tiêu gốc. Mô hình Kriging cho mỗi hàm mục tiêu sẽ được xây dựng bởi các cá thể của tập A1. - Sử dụng mô hình đại diện: Giải thuật sử dụng mô hình Kriging thay cho hàm mục tiêu gốc để tính giá trị thích nghi. Mô hình này được sử dụng để đánh giá thích nghi cho một số cố định thế hệ mà không cần cập nhật mô hình. - Cập nhật mô hình đại diện: Sau khi quá trình tiến hóa sử dụng mô hình đại diện trải qua một số thế hệ, mô hình Kriging sẽ được cập nhật. Việc lựa chọn cá thể để đánh giá lại bởi hàm gốc để cập nhật mô hình là có ý nghĩa rất lớn đối với hiệu quả giải thuật. Các thông tin từ mô hình Kriging được sử dụng để lựa chọn các cá thể cho việc huấn luyện lại mô hình. Hình 1. Ví dụ biểu diễn cách gán một giải pháp với một véc-tơ tham chiếu. Hình 2. Phân cụm các véc-tơ tham chiếu thích ứng tích cực Va. Các cá thể này sẽ được đánh giá lại bởi hàm mục tiêu gốc và các dữ liệu mẫu này sẽ được thêm vào cả tập A1 và A2. Tác giả cũng sử dụng kỹ thuật lựa chọn dựa trên véc-tơ tham chiếu để đảm bảo tập A1 chỉ lưu trữ một số lượng cá thể nhất định, nghĩa là sẽ phải loại bỏ cá thể dư thừa. Kỹ thuật này được thực hiện bằng cách phân cụm các véc-tơ tham chiếu rồi lựa chọn ngẫu nhiên một điểm dữ liệu được giữ lại từ mỗi cụm và phần dữ liệu còn lại sẽ bị loại bỏ. Điều này giúp giải thuật duy trì được một số lượng cố định dữ liệu huấn luyện có tính đa dạng trong tập A1. 2.2.2. Giải thuật CSEA Các tác giả trong [20] đã đề xuất CSEA, một giải thuật tiến hóa đa mục tiêu dựa vào Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 7
Công nghệ thông tin kỹ thuật phân lớp sử dụng mô hình đại diện để giải các bài toán đa mục tiêu khó. Với CSEA, các giải pháp sẽ được phân thành hai nhóm khác nhau, sau đó sử dụng một mô hình đại diện để huấn luyện tiêu chí phân lớp nhằm dự báo các giải pháp ứng viên sẽ vào nhóm nào và sử dụng chiến lược lựa chọn để tìm các giải pháp có chất lượng hội tụ tốt cho việc đánh giá. Đặc điểm chính của CSEA là tiêu chí phân lớp và chiến lược quản lý mô hình đại diện. - Tiêu chí phân lớp: Cách phân lớp phụ thuộc rất lớn vào tiêu chí phân lớp. Dựa trên cơ sở các bài toán đa mục tiêu chỉ có hai loại giải pháp là trội và không trội, nên cần có một tập giải pháp tham chiếu làm biên trội Pareto để chia tất cả các giải pháp vào hai nhóm khác nhau. Để chọn tập giải pháp tham chiếu này, các tác giả đã sử dụng chiến lược lựa chọn dựa trên kỹ thuật phân chia không gian hướng tia, tức là chọn các giải pháp được đánh giá bởi hàm mục tiêu mà chiếu đầu tiên vào trong không gian hướng tia 2 chiều. Lớp đầu vào Lớp ẩn Lớp đầu ra b1 x1 y1 .. .. . . b2 w1j xi .. w2j yj v1h . whj .. vih wqj .. . vdh . bh xd .. yl . d q bh = K hidden ( h ),  h =  vih xi y j = K output (  j ),  j =  w hj bh i =1 bq h =1 Hình 3. Minh họa cấu trúc 3 lớp mạng nơ-ron truyền thẳng sử dụng trong CSEA. - Để quản lý mô hình đại diện, CSEA chia thành bốn bước cơ bản: + Khởi tạo: Khởi tạo các tham số (K: Số giải pháp tham chiếu, gmax: số giải pháp được đánh giá bởi mô hình) và cấu trúc của mạng nơ-ron truyền thẳng (Feedforward neural networks - FNNs) như trong hình 3. Mạng nơ-ron này có kết nối giữa các nơ-ron không tạo thành một vòng khép kín. Ba thành phần chính của mạng nơ-ron cần phải khởi tạo là: cấu trúc mạng, trọng số và hàm kích hoạt; + Cập nhật: Cập nhật trọng số cho mạng nơ-ron với tập dữ liệu huấn luyện. Phương pháp lan truyền ngược Lenvenberg-Marquardt được sử dụng để cập nhật trọng số cho mạng; + Kiểm tra hợp lệ: Sử dụng sai số trên tập dữ liệu kiểm tra để ước lượng khả năng dự báo không chắc chắn của mạng nơ-ron. Các sai số được tính toán bằng kiểm tra hợp lệ chéo; + Lựa chọn sử dụng mô hình đại diện: Trong bước này, các giải pháp tiềm năng được chọn để đánh giá thích nghi. Việc lựa chọn dựa vào khả năng dự báo cũng như độ tin cậy. Sử dụng các sai số trên tập dữ liệu kiểm tra để ước lượng độ tin cậy trong dự báo của mạng nơ-ron. Một cặp sai số (cho hai nhóm giải pháp) tạo ra một điểm đặt trong vùng cấu hình tin cậy, tính không chắc chắn của mạng. Không gian ở đây sử dụng để biểu diễn quan hệ giữa độ không chắc chắn và sai số kiểm tra của mạng. Trong giải thuật CSEA, có hai vòng lặp: vòng lặp chính biểu diễn quá trình tiến hóa 8 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ sử dụng hàm mục tiêu gốc; và tại vòng lặp thứ hai, các giải pháp được chọn thông qua việc phân lớp của mô hình đại diện, minh họa thể hiện trong hình 4. Khởi tạo Lựa chọn cá Cập nhật và kiểm Đánh giá lại thể tham chiếu tra mô hình Kết thúc Cá thể cha mẹ Cập nhật mô hình và cấu hình độ tin cậy Các toán tử tiến hóa Lựa chọn mô hình đại diện Kết hợp cá thể cha mẹ và cá thể con Cá thểLẶP VÒNG con Cá thể tốt CHÍNH Cá thể con VÒNG LẶP PHỤ Kết thúc Lựa chọn môi trường Đánh giá lại Kết hợp giải pháp Toán tử tiến tốt và tham chiếu hóa Hình 4. Minh họa vòng lặp chính đánh giá bằng hàm mục tiêu gốc và vòng lặp phụ chọn các giải pháp từ mô hình đại diện. 2.3. Tiêu chí đánh giá chất lượng, hiệu quả giải thuật Để có cơ sở đánh giá chất lượng, hiệu quả của giải thuật tiến hóa đa mục tiêu, chúng ta quan tâm đến những tiêu chí sau: - Thứ nhất, cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa: Bài toán đa mục tiêu là bài toán tối ưu toàn cục. Do đó, giải thuật hiệu quả cần phải định hướng tìm kiếm theo chiều sâu để nhanh chóng tìm ra giải pháp khả thi, hay nói cách khác quá trình tiến hóa cần phải có khả năng khai thác (exploitation). Đồng thời, giải thuật cũng cần phải tìm kiếm theo chiều rộng để tìm đa dạng lời giải, tránh các điểm tối ưu cục bộ, nghĩa là quá trình tiến hóa cần phải có khả năng thăm dò (exploration). Do vậy, để tìm kiếm hiệu quả các giải pháp tối ưu, cần duy trì sự cân bằng giữa khả năng thăm dò và khả năng khai thác trong suốt quá trình tiến hóa. - Thứ hai, chất lượng hội tụ và đa dạng của quần thể giải pháp: Với bài toán đa mục tiêu, lời giải của giải thuật là tập các giải pháp không trội lẫn nhau và thường được tìm kiếm theo nguyên lý Pareto. Do vậy, để giúp người dùng có cơ sở lựa chọn lời giải tốt nhất, tập giải pháp tìm kiếm phải tiệm cận đến tập giải pháp lý tưởng hay lớp tối ưu Pareto (Pareto optimal front - POF). Mặt khác, để có nhiều chọn lựa, các giải pháp đạt được phải đa dạng trên không gian tìm kiếm. Vì vậy, để có quần thể giải pháp tốt, giải thuật cần tìm kiếm tập giải pháp vừa có tính hội tụ, vừa có tính đa dạng. Nói cách khác, về mặt trực quan, giải thuật cần định hướng tìm kiếm tập giải pháp vừa tiếp cận, vừa trải đều trên mặt lớp tối ưu Pareto trong không gian mục tiêu. Sự cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa có tác động trực tiếp để đạt được tập giải pháp vừa có chất lượng hội tụ tốt, vừa đa dạng. Từ phân tích nêu trên cho thấy, sự cân bằng giữa khả năng thăm dò và khai thác cùng với việc hướng tới tập giải pháp có chất lượng hội tụ tốt và đa dạng là các tiêu chí chính để đánh giá chất lượng, hiệu quả của giải thuật, là cơ sở để phát triển các giải thuật tốt. Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 9
Công nghệ thông tin 2.4. Đánh giá các yếu tố ảnh hưởng đến chất lượng, hiệu quả của giải thuật sử dụng mô hình đại diện Từ nghiên cứu cơ chế hoạt động của các giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện có thể nhận thấy một số yếu tố có tác động quan trọng đến quá trình tìm kiếm, đó là: - Thứ nhất, việc cập nhật mô hình (updating model): Cập nhật mô hình là bước quan trọng, dựa trên việc huấn luyện tập dữ liệu mẫu là tập giải pháp có được trong quá trình tìm kiếm. Đây là yếu tố ảnh hưởng đến khả năng tìm kiếm theo hướng khai thác, hướng tập giải pháp hội tụ đến lớp tối ưu Pareto. Việc lựa chọn thời điểm để cập nhật mô hình rất quan trọng, mang tính chiến lược, có tác động điều chỉnh quá trình tiến hóa cho phù hợp. - Thứ hai, lựa chọn dữ liệu mẫu (sample data) để huấn luyện mô hình: Việc lựa chọn số lượng, chất lượng dữ liệu mẫu là yếu tố tác động trực tiếp đến quá trình học máy để huấn luyện mô hình, có ảnh hưởng đến khả năng tìm kiếm theo hướng thăm dò, tạo ra tính đa dạng cho quần thể giải pháp. Hai yếu tố trên được tham số hóa cho các giải thuật, giúp người dùng có nhiều lựa chọn trong quá trình thiết lập môi trường. Tuy vậy, các tham số này thường được thiết lập cố định từ đầu, không thay đổi, không điều chỉnh trong suốt quá trình tìm kiếm. Qua phân tích quá trình tìm kiếm, có thể thấy rằng một số điều kiện có tác động trực tiếp đến hai yếu tố trên như sau: Về thời điểm của quá trình tiến hóa, ở những thế hệ đầu, xuất phát từ quần thể khởi tạo, khi dữ liệu cho huấn luyện còn ít, cần ưu tiên tìm kiếm chiều sâu (hướng khai thác) để tìm các giải pháp có xu hướng hội tụ. Ở những thế hệ giai đoạn giữa của quá trình, cần phải duy trì tìm kiếm theo cả hướng thăm dò và khai thác để đạt được tập giải pháp tốt cả về chất lượng hội tụ và đa dạng. Ngược lại, ở những thế hệ cuối, khi các giải pháp đã đủ tốt về chất lượng hội tụ, ít có cải thiện qua các thế hệ thì lúc này cần ưu tiên tìm kiếm theo hướng thăm dò để đạt được tính đa dạng của quần thể giải pháp. Một trong các điều kiện tác động đến việc cần điều chỉnh các tham số để hướng đến sự cân bằng thăm dò và khai thác, cải thiện tính hội tụ và đa dạng, đó chính là chất lượng của quần thể tại thời điểm đánh giá, trong đó số giải pháp không bị trội (non- dominated) là thể hiện cơ bản về chất lượng quần thể. Một yếu tố hết sức quan trọng nữa đó là độ phức tạp của hàm mục tiêu gốc. Do giải thuật sử dụng mô hình đại diện vẫn sử dụng hàm gốc để tạo ra tập dữ liệu dùng cho huấn luyện, vì thế đánh giá sự phức tạp của hàm mục tiêu gốc cũng là yếu tố để điều chỉnh các tham số cho phù hợp. Với những phân tích ở trên thấy rằng, việc thiết lập các tham số cố định, không tính đến các điều kiện trong quá trình tìm kiếm có thể tạo ra cơ chế mang tính cứng, làm giảm sự linh hoạt và khả năng điều chỉnh quá trình tiến hóa. Vấn đề đặt ra là chúng ta có thể đánh giá, quan sát các điều kiện liên quan ở trên để chỉ dẫn cho giải thuật hướng tới duy trì tốt sự cân bằng thăm dò và khai thác của quá trình tiến hóa, cải thiện chất lượng hội tụ và đa dạng của quần thể giải pháp, thông qua việc điều chỉnh các tham số tại một số thời điểm cụ thể. Bằng các lập luận ở trên, khi phân tích cơ chế hoạt động của các giải thuật sử dụng mô hình đại diện tiêu biểu là K-RVEA và CSEA, có thể thấy một số vấn đề như sau: - Với K-RVEA, giải thuật đã sử dụng các tham số cố định (được thiết lập giá trị từ đầu) 10 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ cho việc cập nhật mô hình đại diện. Điều này làm cho giải thuật thiếu tính linh hoạt, gây ra sự mất cân bằng giữa khả năng thăm dò và khai thác. Qua thử nghiệm giải thuật K- RVEA với lớp bài toán DTLZs cùng với các tham số khác nhau, đó là sử dụng tham số wmax (số thế hệ sử dụng mô hình đại diện trước khi cập nhật mô hình Kriging) với các giá trị 10, 20, 30, 50, 70 cho các bài toán DTLZ1 đến DTLZ9 và tham số FEmax là 20.000 lần đánh giá, kết quả thể hiện qua hai độ đo GD và IGD như sau: Tại mỗi thời điểm, phụ thuộc vào quá trình tiến hóa, giá trị wmax có ảnh hưởng đến khả năng thăm dò và khai thác hay nói cách khác là chất lượng hội tụ và đa dạng của quần thể. Đặc biệt, ở các thế hệ đầu, việc cập nhật nhanh mô hình cho kết quả tốt hơn khi wmax có giá trị nhỏ với các bài toán DTLZ1, DTLZ2, DTLZ4, DTLZ5. Ở các thế hệ tiếp theo, có sự thay đổi là kết quả tốt hơn với các bài toán DTLZ1, DTLZ2, DTLZ6, DTLZ7 khi tăng giá trị wmax, nhất là với bài toán DTLZ9. Như vậy, khi tham số wmax với giá trị được thiết lập cố định thì chưa thực sự đạt hiệu quả giải thuật, giảm chất lượng hội tụ và đa dạng. Việc áp dụng số thế hệ sử dụng các hàm mục tiêu gốc trước khi sử dụng hàm đại diện theo mô hình Kriging có liên hệ với chất lượng của quần thể tại thời điểm xét. Khi số giải pháp không bị trội trong quần thể là nhỏ và còn xa lớp tối ưu Pareto, sẽ rất thích hợp nếu tham số này đặt ở mức phù hợp (mức giá trị 30 hoặc 50). Nếu tỉ lệ này cao, chất lượng phụ thuộc rất lớn vào việc sử dụng hàm mục tiêu gốc và hiệu quả của việc sử dụng hàm đại diện không đáng kể. Nếu tỉ lệ này thấp, số cá thể nhiều, việc cập nhật mô hình đại diện sẽ không có nhiều tác động đến chất lượng. Khi số giải pháp không bị trội trong quần thể đủ lớn nhưng vẫn chưa gần lớp tối ưu Pareto, sẽ cần phải tăng số lần đánh giá sử dụng hàm đại diện và tăng tần suất cập nhật mô hình Kriging (phụ thuộc vào chất lượng quần thể, giá trị của wmax có thể là 20 hoặc 30). Khi số giải pháp không bị trội trong quần thể tiệm cận lớp tối ưu Pareto thì tần suất sử dụng hàm đại diện và tần suất cập nhật mô hình cần lớn hơn, lúc này giá trị wmax có thể là 10. Nhìn chung, việc tăng hay giảm giá trị wmax phụ thuộc vào các yếu tố chính là: thời gian tiến hóa, chất lượng hội tụ của quần thể và độ phức tạp tính toán của mỗi bài toán. - Với CSEA, chiến lược để lựa chọn các giải pháp tham chiếu là một yếu tố quan trọng đối với hiệu quả giải thuật. Tham số chính của giải thuật CSEA là K, tức là số giải pháp tham chiếu được lựa chọn. Tham số K có tác động khá lớn tới sự hội tụ đến lớp tối ưu Pareto cũng như khả năng mở rộng tìm kiếm giải pháp ở các khu vực lân cận. Nói cách khác, từ các giải pháp tham chiếu được chọn, sẽ có chiến lược thăm dò hoặc khai thác ở mức độ khác nhau trong quá trình tiến hóa. Việc chọn nhiều giải pháp tham chiếu có thể tăng cường khả năng khai thác, hướng đến các giải pháp tốt một cách nhanh nhất, nhưng có thể làm hạn chế khu vực tìm kiếm giải pháp, hay khả năng thăm dò giảm đi. Những xu hướng khác nhau đó sẽ tạo ra sự khác nhau về chất lượng hội tụ và đa dạng. Thực vậy, khi thử nghiệm với các giá trị K khác nhau, chúng tôi nhận thấy rằng: khi giá trị K lớn, tiến trình hướng đến lớp tối ưu Pareto khá nhanh (thể hiện qua giá trị độ đo GD), có nghĩa là chất lượng hội tụ của tập giải pháp khá tốt, nhưng không gian tìm kiếm lại hướng đến khu vực tương đối cục bộ, thậm chí có thể bị “tắc” ở một khu vực cục bộ, làm giảm tính chất toàn cục của bài toán, đồng thời tính đa dạng của tập giải pháp không được tốt. Ngược lại, khi giá trị K nhỏ, khả năng thăm dò của quá trình tiến hóa và tính đa dạng của quần thể là tốt, nhưng khả năng khai thác lại kém đi, thể hiện qua tính hội tụ của quần thể không tốt. Vấn đề đặt ra là làm thế nào có thể tùy biến giá trị K một cách thích hợp để nâng cao Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 11
Công nghệ thông tin hiệu quả của giả thuật thông qua việc duy trì tính cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa, đồng thời, duy trì quần thể đạt chất lượng cao nhất cả về tính hội tụ và đa dạng. Trong công bố về CSEA, các tác giả cũng đã đánh giá được mức độ ảnh hưởng quan trọng của tham số K, tuy nhiên, các tác giả chỉ phân tích về mối quan hệ giữa K và số mục tiêu để chọn một giá trị K thực nghiệm và giá trị đó luôn là 6. Tuy nhiên, vì giá trị của K được thiết lập cố định từ đầu nên CSEA thiếu đi sự thích ứng linh hoạt, có thể làm mất sự cân bằng giữa khả năng thăm dò và khai thác của giải thuật. Từ phân tích về các đặc điểm của các giải thuật tiến hóa đa mục tiêu nói chung và giải thuật sử dụng mô hình đại diện nói riêng, chúng tôi giả thuyết rằng để đánh giá đầy đủ hiệu quả của giải thuật, cần phải tính đến các yếu tố tác động khác để có chiến lược xác định số giải pháp tham chiếu phù hợp hơn. Qua đó, có thể sử dụng kỹ thuật chỉ dẫn để tăng cường chất lượng của giải thuật, nâng cao khả năng giải quyết các bài toán khó trong thực tế. 3. KỸ THUẬT CHỈ DẪN Chỉ dẫn (guidance technique) là một kỹ thuật nhận được nhiều sự quan tâm, nghiên cứu và đã có nhiều kết quả được công bố. Kỹ thuật chỉ dẫn là từ việc phân tích thông tin tham chiếu từ các nguồn như: quá trình tiến hóa; thông tin trích rút từ quần thể giải pháp, tập lưu trữ ngoài, giá trị độ đo, dự báo; thông tin người dùng,… để điều chỉnh quá trình tiến hóa hướng đến sự cải thiện nào đó. Kỹ thuật chỉ dẫn được phân làm hai loại chính là: Chỉ dẫn tự động và chỉ dẫn thông qua tương tác. Với phương pháp chỉ dẫn tự động, quá trình điều chỉnh tham số được tiến hành liên tục, đều đặn qua mỗi thế hệ hoặc tại một thời điểm xác định nào đó. Ưu điểm của phương pháp này là quá trình điều chỉnh linh hoạt hơn, kịp thời hơn. Tuy nhiên, việc đánh giá trước khi quyết định điều chỉnh tại mỗi thời điểm lại khó khăn hơn, cần phải có cơ chế để giới hạn biên cho các điều chỉnh từ các phép tính tự động giá trị tham số. Với phương pháp chỉ dẫn thông qua tương tác, các thông tin tham chiếu được biểu diễn, mô phỏng, cung cấp cho người dùng một cách trực quan và người dùng với kỹ năng, kinh nghiệm sẽ điều chỉnh các tham số theo việc phân tích các điều kiện tác động tại thời điểm cụ thể. Phương pháp này dễ tiến hành nhưng lại đòi hỏi người ra quyết định phải có kiến thức và phải có chiến lược lựa chọn thời điểm tương tác phù hợp. 4. 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 Trên cơ sở phân tích các yếu tố ảnh hưởng đến việc tăng cường duy trì sự cân bằng giữa khả năng thăm dò và khai thác, đặc điểm của giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện, chúng tôi giả thuyết rằng: Việc cập nhật mô hình đại diện, lựa chọn dữ liệu mẫu để huấn luyện,… là những yếu tố quan trọng để đảm bảo sự cân bằng giữa thăm dò và khai thác của quá trình tiến hóa, cải thiện chất lượng hội tụ và đa dạng của quần thể giải pháp. Việc cố định thời điểm cập nhật mô hình, số lượng, chất lượng dữ liệu mẫu trong suốt quá trình tìm kiếm, khiến cho giải thuật thiếu tính linh hoạt, ảnh hưởng đến chất lượng của giải thuật. Mặt khác, kỹ thuật chỉ dẫn sẽ định hướng quá trình tìm kiếm để duy trì cân bằng giữa thăm dò và khai thác, cải thiện chất lượng hội tụ và đa dạng. Chúng tôi đề xuất sử dụng kỹ thuật chỉ dẫn phân tích các điều kiện tác động, làm 12 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ cơ sở điều chỉnh các tham số cho giải thuật, giúp giải thuật thích ứng tốt hơn. Các tham số điều kiện được đưa vào đánh giá là: Tiến trình thời gian: Là tỷ lệ giữa số thế hệ đã trải qua với tổng số thế hệ sử dụng (hoặc là số lần đánh giá trên tổng số lần đánh giá của quá trình tiến hóa) nhân với tỷ lệ giữa số giải pháp không bị trội với kích thước quần thể và độ phức tạp của hàm mục tiêu gốc. Về mặt toán học, chúng ta xem xét giá trị đánh giá sau: t n n n Qt =  non  k hoặc Qt = cal  non  k (9) ngen size( P) max cal size( P) Trong đó: t là số thế hệ đã trải qua; ngen là tổng số thế hệ; nnon là số giải pháp không bị trội; size(P) là kích thước quần thể; k là độ phức tạp của hàm mục tiêu gốc, k  [0.8, 1]. Chúng ta hãy xem xét tác động của tham số Qt với các yếu tố ảnh hưởng chất lượng giải thuật: Khi Qt nhỏ, ở các thế hệ đầu, chất lượng quần thể thấp, do vậy cần phải tăng cường tìm kiếm chiều sâu (hướng khai thác) để cải thiện chất lượng hội tụ của quần thể. Ngược lại khi Qt lớn (t và nnon tăng lên), cần tăng cường khả năng thăm dò để cải thiện sự đa dạng của quần thể. Trên cơ sở chọn hai giải thuật sử dụng mô hình đại diện để thử nghiệm là K-RVEA và CSEA, chúng ta có thể thấy: Với giải thuật K-RVEA, wmax là tham số xác định thời điểm cập nhật mô hình đại diện, khi cần tăng cường khả năng khai thác thì giảm giá trị wmax xuống (cập nhật mô hình nhanh hơn). Và ngược lại, khi cần tăng cường khả năng thăm dò thì tăng giá trị wmax lên (cập nhật mô hình chậm lại). Với giải thuật CSEA, khi cần tăng cường khả năng khai thác thì giảm số lượng cụm xuống (K giảm) và ngược lại, khi cần tăng cường khả năng thăm dò thì tăng số lượng cụm lên (K tăng). Do vậy, chúng tôi đề xuất cách tính wmax và K như sau: wmax = Normalize(Qt  60) (10) K = Normalize(Qt  6) (11) Giá trị 60 trong công thức (10) là điểm gieo, hàm Normalize sẽ đảm bảo giá trị wmax  [10, 50]. Giá trị 6 trong công thức (11) cũng là điểm gieo, hàm Normalize sẽ đảm bảo giá trị K  [3, 9]. Kỹ thuật chỉ dẫn được sử dụng theo hai cách: - Cách 1: Tự động điều chỉnh tham số, tức là Qt sẽ được tính toán ở mỗi thế hệ và các tham số wmax, K được tính lại sau mỗi thế hệ; - Cách 2: Điều chỉnh tham số thông qua tương tác với người dùng, tức là người dùng sẽ lựa chọn thời điểm bất kỳ để đánh giá giá trị, sự biến đổi Qt để điều chỉnh tham số wmax, K và điều chỉnh tăng giảm theo ý muốn. 5. THỬ NGHIỆM VÀ ĐÁNH GIÁ 5.1. Giải thuật được lựa chọn để thử nghiệm Bài báo lựa chọn các giải thuật tiêu biểu để thử nghiệm là: Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 13
Công nghệ thông tin - Giải thuật K-RVEA gốc và giải thuật K-RVEA sử dụng kỹ thuật chỉ dẫn, tự động điều chỉnh tham số wmax, xác định thời điểm cập nhật mô hình (đặt tên phiên bản giải thuật là M-K-RVEA); - Giải thuật CSEA gốc và giải thuật CSEA sử dụng kỹ thuật chỉ dẫn, tự động điều chỉnh tham số K, số lượng cụm để chọn mẫu (đặt tên phiên bản giải thuật là M-CSEA). 5.2. Bài toán thử nghiệm Chúng tôi chọn lớp bài toán mẫu phổ biến DTLZs [23], là các bài toán khó với các đặc điểm khác nhau, cho phép tùy biến mở rộng không gian quyết định và không gian mục tiêu để thử nghiệm đánh giá hiệu quả thực thi của các giải thuật. Lớp bài toán DTLZs bao gồm 9 bài toán, từ DTLZ1 đến DTLZ9. 5.3. Độ đo Để so sánh kết quả thử nghiệm giữa giải thuật gốc và giải thuật đề xuất sử dụng kỹ thuật chỉ dẫn, với tiêu chí đánh giá chất lượng hội tụ và đa dạng, chúng tôi sử dụng hai độ đo phổ biến là: khoảng cách thế hệ (Generational distance - GD) [19] và khoảng cách thế hệ nghịch đảo (Inverse generational distance - IGD) [19]. Độ đo GD được định nghĩa là khoảng cách trung bình từ một tập giải pháp tìm được, ký hiệu là P, đến lớp tối ưu Pareto. Công thức tính như sau [19]:  n di GD = i =1 (12) n Trong đó: di là khoảng cách Euclide (trong không gian mục tiêu) từ giải pháp i thuộc P đến điểm gần nhất thuộc lớp tối ưu Pareto và n là kích thước của P. Độ đo này để đánh giá về tính hội tụ. Một ví dụ về độ đo GD được minh họa trong hình 3. Với mỗi giải pháp thuộc P, xác định khoảng cách đến điểm gần nhất trong lớp tối ưu Parto và khi đó trung bình của các khoảng cách này sẽ là giá trị của độ đo GD. Độ đo IGD là độ đo có tính đến cả sự hội tụ và lan truyền đến tất cả các phần của lớp tối ưu Pareto. Công thức tính IGD như sau [19]:  n j =1 dj IGD = (13) n Trong đó: d j là khoảng cách từ điểm j thuộc lớp tối ưu Pareto đến giải pháp gần nhất thuộc P và n là kích thước của lớp tối ưu Pareto. f2 GD f2 IGD f1 f1 Các lời giải thuộc lớp tối ưu Pareto Các lời giải thuộc P Hình 5. Minh họa các độ đo GD và IGD. 14 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ 5.4. Kết quả, so sánh và đánh giá Các giải thuật được thử nghiệm với các tham số có giá trị khác nhau để so sánh, đánh giá. Kết quả thử nghiệm trong quá trình tiến hóa là giá trị của độ đo GD và IGD được ghi lại, của từng cặp giải thuật với từng bài toán DTLZ. Các bảng 1, 2 trình bày kết quả thử nghiệm cho từng cặp giải thuật K-RVEA và M-K- RVEA, CSEA và M-CSEA trên độ đo GD. Trong bảng, ADC là giá trị của tham số wmax được tự động điều chỉnh, Evals là số lần đánh giá (evaluations). Bảng 1. Kết quả thử nghiệm của K-RVEA với tham số cố định và M-K-RVEA sử dụng kỹ thuật chỉ dẫn, tự động điều chỉnh tham số trên độ đo GD. Evals 2.000 4.000 6.000 8.000 10.000 12.000 14.000 16.000 18.000 20.000 wmax DTLZ1 10 50,7441 7,4836 5,6692 4,1103 3,2282 2,7263 2,5096 2,4711 2,4463 2,3877 20 41,9546 10,0818 10,9039 3,7888 3,7041 3,7041 4,0672 4,0672 4,0097 4,0097 30 39,0192 9,4198 7,2260 5,4170 3,9909 3,9062 3,9777 4,0149 3,9320 3,7725 50 42,5498 10,4695 6,7609 5,9252 5,5349 4,6894 4,7492 4,3930 4,1622 4,0916 70 43,5096 12,6410 8,0107 6,6715 7,1815 6,2105 5,7701 5,2643 5,0035 4,7697 ADC 46,6079 4,7267 3,3725 3,3725 3,3725 3,3725 3,3725 3,3725 3,3725 3,3725 DTLZ2 10 0,1032 0,0023 0,0014 0,0011 0,0009 0,0008 0,0008 0,0007 0,0007 0,0006 20 0,1151 0,0014 0,0009 0,0007 0,0006 0,0005 0,0005 0,0005 0,0004 0,0004 30 0,0999 0,0015 0,0010 0,0008 0,0006 0,0005 0,0005 0,0004 0,0004 0,0004 50 0,1076 0,0015 0,0009 0,0006 0,0005 0,0005 0,0004 0,0004 0,0004 0,0004 70 0,1165 0,0014 0,0010 0,0007 0,0006 0,0005 0,0005 0,0004 0,0004 0,0004 ADC 0,1227 0,0019 0,0011 0,0008 0,0007 0,0006 0,0006 0,0005 0,0005 0,0004 DTLZ3 10 183,1624 43,1944 36,1737 33,9130 30,8676 29,8677 28,4940 30,4472 29,3890 30,4415 20 171,6720 65,1569 57,1465 47,8764 47,3865 42,2447 40,1520 38,8519 36,7741 36,5496 30 220,4797 74,7820 56,8731 52,7536 52,7041 48,8366 44,5964 42,4959 41,5517 40,6848 50 194,0912 85,5257 83,2413 70,2972 59,2193 50,7384 50,3928 49,8387 48,0394 44,5380 70 151,5813 77,2795 68,4175 59,9071 51,6176 47,8923 49,5671 51,3997 48,6738 48,7996 ADC 183,1624 69,5647 54,4809 48,0276 47,8869 43,2640 42,0306 40,3582 39,2478 42,3035 DTLZ4 10 0,1739 0,0148 0,0093 0,0063 0,0051 0,0043 0,0038 0,0034 0,0031 0,0029 20 0,1613 0,0113 0,0072 0,0054 0,0044 0,0039 0,0035 0,0033 0,0031 0,0029 30 0,1634 0,0108 0,0077 0,0060 0,0051 0,0044 0,0038 0,0035 0,0033 0,0031 Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 15
Công nghệ thông tin Evals 2.000 4.000 6.000 8.000 10.000 12.000 14.000 16.000 18.000 20.000 wmax 50 0,1841 0,0115 0,0074 0,0057 0,0048 0,0042 0,0038 0,0034 0,0031 0,0028 70 0,1564 0,0129 0,0085 0,0073 0,0063 0,0055 0,0050 0,0047 0,0045 0,0042 ADC 0,2219 0,0084 0,0055 0,0040 0,0033 0,0030 0,0027 0,0024 0,0022 0,0020 DTLZ5 10 0,1407 0,0068 0,0057 0,0054 0,0050 0,0046 0,0042 0,0042 0,0042 0,0041 20 0,1571 0,0096 0,0069 0,0063 0,0056 0,0053 0,0052 0,0050 0,0049 0,0048 30 0,1207 0,0111 0,0082 0,0068 0,0063 0,0058 0,0056 0,0054 0,0051 0,0051 50 0,1584 0,0052 0,0046 0,0042 0,0041 0,0041 0,0040 0,0040 0,0039 0,0038 70 0,1368 0,0101 0,0072 0,0065 0,0062 0,0056 0,0055 0,0052 0,0050 0,0049 ADC 0,1286 0,0071 0,0055 0,0048 0,0045 0,0042 0,0039 0,0039 0,0037 0,0037 DTLZ6 10 0,9746 0,4591 0,4409 0,3822 0,3919 0,3913 0,3306 0,3261 0,3428 0,3140 20 0,9513 0,4647 0,4897 0,4926 0,4734 0,4403 0,4151 0,3610 0,3625 0,3456 30 0,9965 0,4503 0,3943 0,4227 0,3993 0,3845 0,3798 0,3657 0,3867 0,3529 50 0,9480 0,5927 0,5124 0,4898 0,4478 0,4311 0,4444 0,4308 0,4108 0,3957 70 0,9599 0,5421 0,4830 0,4446 0,4565 0,4716 0,4370 0,4339 0,4248 0,4184 ADC 1,0474 0,4951 0,5234 0,5070 0,4695 0,4490 0,4279 0,4099 0,3823 0,3597 DTLZ7 10 2,0241 0,0026 0,0012 0,0008 0,0006 0,0005 0,0005 0,0004 0,0004 0,0003 20 2,6543 0,0012 0,0007 0,0005 0,0004 0,0003 0,0003 0,0003 0,0002 0,0002 30 2,6896 0,0009 0,0005 0,0004 0,0003 0,0003 0,0003 0,0002 0,0002 0,0002 50 2,3290 0,0010 0,0007 0,0005 0,0004 0,0004 0,0003 0,0003 0,0002 0,0002 70 2,0943 0,0007 0,0005 0,0005 0,0004 0,0003 0,0003 0,0003 0,0002 0,0002 ADC 2,0241 0,0009 0,0007 0,0004 0,0004 0,0003 0,0003 0,0003 0,0002 0,0002 DTLZ8 10 0,0548 0,0322 0,0322 0,0322 0,0322 0,0322 0,0322 0,0322 0,0322 0,0322 20 0,0587 0,0327 0,0327 0,0327 0,0327 0,0327 0,0327 0,0327 0,0327 0,0327 30 0,0706 0,0358 0,0358 0,0358 0,0358 0,0358 0,0358 0,0358 0,0358 0,0358 50 0,0728 0,0303 0,0303 0,0303 0,0303 0,0303 0,0303 0,0303 0,0303 0,0303 70 0,0635 0,0357 0,0357 0,0357 0,0357 0,0357 0,0357 0,0357 0,0357 0,0357 ADC 0,0635 0,0310 0,0310 0,0310 0,0310 0,0310 0,0310 0,0310 0,0310 0,0310 DTLZ9 10 3,4231 2,2998 1,5890 1,3484 1,4657 2,2714 1,4092 1,2228 1,1880 1,1553 16 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ Evals 2.000 4.000 6.000 8.000 10.000 12.000 14.000 16.000 18.000 20.000 wmax 20 6,3959 2,5242 2,3244 2,1598 1,9384 1,9384 2,3200 1,5506 1,6016 2,1090 30 4,2762 2,1689 1,9599 1,7168 1,6040 1,4022 1,5312 1,4316 1,3738 1,2709 50 3,9907 1,5387 1,1807 0,9758 2,3940 2,1892 1,8939 1,8939 1,8430 1,7425 70 4,5920 2,5457 1,9841 2,2016 2,0792 2,0511 1,9588 1,8728 1,9472 1,7881 ADC 3,7733 2,5289 2,2851 2,1059 2,0260 2,0260 1,8907 1,8280 1,2761 1,1746 Bảng 2. Kết quả thử nghiệm của CSEA và M-CSEA sử dụng kỹ thuật chỉ dẫn, tự động điều chỉnh tham số trên độ đo GD. Evals 1.000 2.000 3.000 4.000 5.000 6.000 7.000 8.000 9.000 10.000 MOEAs DTLZ1 M-CSEA 34,5520 7,2937 1,6599 0,5930 0,2533 0,0940 0,0497 0,0457 0,0074 0,0044 CSEA 38,3042 0,2495 0,0935 0,0675 0,0498 0,0390 0,0373 0,0367 0,0385 0,0237 DTLZ2 M-CSEA 0,1095 0,0033 0,0012 0,0008 0,0006 0,0004 0,0003 0,0003 0,0003 0,0002 CSEA 0,1119 0,0031 0,0017 0,0011 0,0007 0,0005 0,0004 0,0004 0,0003 0,0003 DTLZ3 M-CSEA 189,4952 47,6430 25,8744 9,1384 6,4038 3,3551 3,0307 1,6288 0,7489 0,5760 CSEA 183,1624 55,9032 19,8560 14,2806 11,1903 8,8064 6,5278 5,1156 3,5796 2,0172 DTLZ4 M-CSEA 0,1462 0,0079 0,0022 0,0013 0,0009 0,0007 0,0006 0,0005 0,0004 0,0004 CSEA 0,1601 0,0093 0,0016 0,0009 0,0006 0,0005 0,0004 0,0004 0,0003 0,0003 DTLZ5 M-CSEA 0,1295 0,0055 0,0026 0,0017 0,0010 0,0004 0,0003 0,0003 0,0003 0,0001 CSEA 0,1430 0,0091 0,0029 0,0017 0,0007 0,0004 0,0003 0,0003 0,0002 0,0002 DTLZ6 M-CSEA 0,9824 0,3928 0,1033 0,0017 0,0003 0,0001 0,0000 0,0000 0,0000 0,0000 CSEA 0,9374 0,4903 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 DTLZ7 M-CSEA 2,6315 0,0513 0,0082 0,0031 0,0012 0,0008 0,0005 0,0004 0,0003 0,0003 CSEA 2,1157 0,0376 0,0026 0,0015 0,0010 0,0007 0,0005 0,0004 0,0004 0,0003 DTLZ8 M-CSEA 0,0527 0,0153 0,0153 0,0153 0,0153 0,0153 0,0153 0,0153 0,0153 0,0153 CSEA 0,0586 0,0173 0,0173 0,0173 0,0173 0,0173 0,0173 0,0173 0,0173 0,0173 Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 17
Công nghệ thông tin Các hình 6, 7 biểu diễn quá trình tìm kiếm giải pháp của các giải thuật đề xuất so sánh với các giải thuật gốc. - So sánh quá trình tối ưu của giải thuật đề xuất M-K-RVEA và giải thuật gốc K- RVEA thể hiện tại hình 6. Hình 6. Quá trình tối ưu của M-K-RVEA và K-RVEA với bài toán DTLZ1. - So sánh quá trình tối ưu của giải thuật đề xuất M-CSEA và giải thuật gốc CSEA thể hiện tại hình 7. Hình 7. Quá trình tối ưu của M-CSEA và CSEA với bài toán DTLZ8. Qua các kết quả thử nghiệm, chúng tôi có nhận xét như sau: Với giải thuật M-K-RVEA, so sánh kết quả thử nghiệm với giải thuật gốc K-RVEA thấy rằng M-K-RVEA sử dụng kỹ thuật chỉ dẫn, tự động điều chỉnh tham số đã duy trì được sự cân bằng tốt hơn giữa tính hội tụ và đa dạng của quần thể giải pháp. Cụ thể là ở những thế hệ đầu, kết quả tốt hơn với các bài toán DTLZ1, DTLZ3, DTLZ4, DTLZ5, DTLZ8 trên GD và DTLZ1, DTLZ3, DTLZ4, DTLZ5, DTLZ7, DTLZ9 trên IGD. Ở các thế hệ liền sau đó, M-K-RVEA tốt hơn với các bài toán DTLZ1, DTLZ3, DTLZ4, DTLZ5, DTLZ8, và có kết quả tương tự K-RVEA với bài toán DTLZ2 trên GD. Trên IGD, giải thuật M-K-RVEA cũng đạt kết quả tốt hơn với các bài toán DTLZ1, DTLZ3, DTLZ4, DTLZ5, DTLZ6, DTLZ8, DTLZ9. Ở các thế hệ cuối, M-K-RVEA đạt kết quả tốt hơn với các bài toán DTLZ1, DTLZ3, DTLZ4, DTLZ5, DTLZ6, DTLZ8, DTLZ9 18 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ trên GD và DTLZ1, DTLZ4, DTLZ5, DTLZ8, DTLZ9 trên IGD. Trong một số ít trường hợp khác, M-K-RVEA có kết quả tương tự hoặc kém không đáng kể so với K-RVEA. Nói chung, thông qua kết quả thử nghiệm cho thấy, việc đề xuất kỹ thuật chỉ dẫn gắn với tự động điều chỉnh tham số đã nâng cao hiệu quả của các giải thuật tiến hóa đa mục tiêu sử dụng hàm đại diện nói chung và sử dụng mô hình Kriging nói riêng. Kết quả sử dụng cơ chế tự động điều chỉnh tham số đã minh chứng cho giả thuyết về ảnh hưởng của các yếu tố tiến trình thời gian, chất lượng hội tụ hiện tại của quần thể và đặc điểm của bài toán đối với việc đảm bảo cả chất lượng hội tụ và đa dạng của quần thể, thông qua việc duy trì cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa. Hiệu quả của kỹ thuật chỉ dẫn tự động tại các giai đoạn tiến hóa còn phụ thuộc vào chất lượng và hiệu quả ở giai đoạn trước, điều đó chứng tỏ rằng cần có sự điều chỉnh kịp thời để duy trì sự cân bằng giữa thăm dò và khai thác. Tuy vậy, một số ít trường hợp kết quả của K- RVEA tốt hơn M-K-RVEA (dù chỉ tốt hơn một chút) cũng đặt ra cho chúng ta một vài vấn đề như sự ổn định, tính ngẫu nhiên. Với giải thuật M-CSEA, so sánh kết quả thử nghiệm với giải thuật gốc CSEA thấy rằng, M-CSEA sử dụng kỹ thuật chỉ dẫn với chiến lược lựa chọn số lượng cụm linh hoạt khi lấy dữ liệu mẫu để huấn luyện, giải thuật đã tạo nên sự cân bằng tốt hơn giữa chất lượng hội tụ và đa dạng. Cụ thể, ở những thế hệ đầu, giải thuật đạt kết quả tốt hơn với các bài toán DTLZ1, DTLZ2, DTLZ3, DTLZ6, DTLZ8 trên GD và DTLZ1, DTLZ3, DTLZ4, DTLZ6, DTLZ7, DTLZ8 trên IGD. Ở các thế hệ liền sau đó, M-CSEA đạt kết quả tốt hơn với các bài toán DTLZ2, DTLZ3, DTLZ6, DTLZ7, DTLZ8 trên GD. Trên IGD, giải thuật cũng tốt hơn với các bài toán DTLZ1, DTLZ3, DTLZ4, DTLZ6, DTLZ7, DTLZ8. Ở các thế hệ cuối, M-CSEA đạt kết quả tốt hơn với các bài toán DTLZ1, DTLZ2, DTLZ3, DTLZ5, DTLZ6, DTLZ7, DTLZ8 trên GD và DTLZ1, DTLZ2, DTLZ3, DTLZ6, DTLZ7, DTLZ8 trên IGD. Qua kết quả thử nghiệm cho thấy, việc đề xuất sử dụng kỹ thuật chỉ dẫn tự động với chiến lược lựa chọn từ số cụm dữ liệu linh hoạt đã giúp nâng cao hiệu quả của giải thuật tiến hóa đa mục tiêu sử dụng mô hình Kriging. Tương tự như M-K-RVEA, kết quả thử nghiệm của M-CSEA đã minh chứng cho giả thuyết về tác động của tiến trình thời gian, chất lượng hội tụ hiện tại của quần thể và đặc điểm của bài toán tới việc duy trì cân bằng giữa khả năng thăm dò và khai thác để đảm bảo quần thể vừa có tính hội tụ, vừa đa dạng. Và cũng cần phải điều chỉnh kịp thời tại các giai đoạn tiến hóa để duy trì sự cân bằng giữa thăm dò và khai thác. Đối với các giải thuật sử dụng kỹ thuật chỉ dẫn điều chỉnh tham số thông qua tương tác, đặt tên là iK-RVEA và iCSEA tương ứng với các giải thuật gốc K-RVEA và CSEA, sẽ có một bước tương tác với người dùng được thêm vào vòng lặp qua các thế hệ. Ở bước tương tác này, giao diện hiển thị các thông tin tham chiếu như: giá trị hiện tại của các tham số chung (số thế hệ, số lần đánh giá), tham số wmax, K (tương ứng của K-RVEA và CSEA), biểu đồ thay đổi các độ đo GD, IGD từ thế hệ đầu đến hiện tại. Giao diện tương tác cho phép người dùng nhập các giá trị mới của các tham số. Người dùng không nhất thiết phải tương tác tại mỗi thế hệ mà chỉ tương tác khi muốn kiểm tra và xem xét để điều chỉnh tham số. Trong các thử nghiệm, chúng tôi tiến hành tương tác 5 lần với mỗi giải thuật và quan sát sự thay đổi của các độ đo GD, IGD cùng với các giai đoạn của quá trình tiến hóa. Bằng kiến thức chuyên gia để điều chỉnh giá trị các tham số trong các giải thuật Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 19
Công nghệ thông tin iK-RVEA và iCSEA, quá trình tiến hóa đã có những biến đổi tích cực, bổ sung đầy đủ hơn cho kỹ thuật chỉ dẫn nhằm nâng cao hiệu quả giải thuật. Thật vậy, thông qua tương tác, việc điều chỉnh các tham số quan trọng như thời điểm cập nhật mô hình, số lượng mẫu các cụm dùng để phân lớp,… giúp cho các giải thuật có chất lượng tốt hơn. Kết quả của sự tương tác với người dùng chính là các yếu tố ảnh hưởng đến chất lượng của giải thuật (số thế hệ đã trải qua, số lần đánh giá, tính hội tụ và đa dạng của quần thể hiện tại, đặc điểm của các bài toán). Các kết quả của sự tương tác cùng với sự điều chỉnh tự động tham số đã tạo nên kỹ thuật chỉ dẫn hiệu quả cho các giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện có ý nghĩa quan trọng đối với việc giải quyết các bài toán thực tế. 6. KẾT LUẬN Giải các bài toán khó bằng giải thuật tiến hóa đa mục tiêu sử dụng mô hình đại diện là lựa chọn hiệu quả, được các nhà nghiên cứu quan tâm. Đã có nhiều công bố giải quyết hiệu quả các bài toán khó. Tuy nhiên, các chiến lược cập nhật mô hình đại diện, lựa chọn dữ liệu mẫu để huấn luyện mô hình,… vẫn còn chưa được đánh giá kỹ, nhất là sự ảnh hưởng đến việc duy trì cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa, cải thiện chất lượng hội tụ và đa dạng của quần thể, là hai yếu tố quan trọng quyết định chất lượng của giải thuật. Trên cơ sở phân tích các điều kiện trong quá trình tiến hóa, chúng tôi đã đề xuất kỹ thuật chỉ dẫn để có chiến lược cập nhật mô hình và lựa chọn dữ liệu mẫu linh hoạt, hiệu quả hơn. Kết quả thử nghiệm đã minh chứng cho giả thuyết và khẳng định tính hiệu quả của kỹ thuật chỉ dẫn, nhất là sự kết hợp phương pháp tự động điều chỉnh tham số với điều chỉnh tham số thông qua tương tác người dùng trong quá trình tiến hóa. Bài báo cũng đưa ra khuyến nghị sử dụng để bảo đảm tính bền vững, kết quả hội tụ và đa dạng trong giải quyết các bài toán đa mục tiêu khó trong thực tế. TÀI LIỆU THAM KHẢO [1]. Seongim Choi, Juan J Alonso, and Hyoung S Chung, "Design of a low-boom supersonic business jet using evolutionary algorithms and an adaptive unstructured mesh method", AIAA paper, 1758:2004, 2004. [2]. Michael TM Emmerich, Kyriakos C Giannakoglou, Boris Naujoks, "Single-and multiobjective evolutionary optimization assisted by Gaussian random field metamodels", IEEE Transactions on Evolutionary Computation, 10(4):421-439, 2006. [3]. Chariklia A Georgopoulou and Kyriakos C Giannakoglou, "Multi-objective metamodel- assisted memetic algorithms", In Multi-Objective Memetic Algorithms, pages 153-181. Springer, 2009. [4]. Tushar Goel, Rajkumar Vaidyanathan, Raphael T Haftka, Wei Shyy, Nestor V Queipo, and Kevin Tucker, "Response surface approximation of Pareto optimal front in multi- objective optimization", Computer methods in applied mechanics and engineering, 196(4- 6):879-893, 2007. [5]. Rolland L Hardy, "Multi-quadric equations of topography and other irregular surfaces", Journal of geophysical research, 76(8):1905-1915, 1971. [6]. Afzal Husain and Kwang-Yong Kim, "Enhanced multi-objective optimization of a micro- channel heat sink through evolutionary algorithm coupled with multiple surrogate models", Applied Thermal Engineering, 30(13):1683-1691, 2010. [7]. Amitay Isaacs, Tapabrata Ray, and Warren Smith, "An evolutionary algorithm with spatially distributed surrogates for multi-objective optimization", In Australian Conference 20 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”
Nghiên cứu khoa học công nghệ on Artificial Life, pages 257-268. Springer, 2007. [8]. Xingtao Liao, Qing Li, Xujing Yang, Weigang Zhang, and Wei Li, "Multi-objective optimization for crash safety design of vehicles using stepwise regression model", Structural and multidisciplinary optimization, 35(6):561-569, 2008. [9]. Saul Zapotecas Martinez and C. A Coello Coello, "A memetic algorithm with non gradient- based local search assisted by a meta-model", In International Conference on Parallel Problem, Solving from Nature, pages 576-585. Springer, 2010. [10]. K. Miettinen, "Nonlinear multi-objective optimization", Kluwer Academic Publishers, Boston, USA, 1999. [11]. Alfredo Arias Montano, Carlos A Coello Coello, and Efren Mezura-Montes, "MODE- LD+SS: A novel differential evolution algorithm incorporating local dominance and scalar selection mechanisms for multi-objective optimization", In Evolutionary Computation (CEC), 2010 IEEE Congress on, pages 1-8. IEEE, 2010. [12]. Martin Pilát and Roman Neruda, "Lamm-mma: Multi-objective memetic algorithm with local aggregate meta-model", In Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, pages 79-80. ACM, 2011. [13]. Martin Pilat and Roman Neruda, "An evolutionary strategy for surrogate-based multiobjective optimization", In Evolutionary Computation (CEC), 2012 IEEE Congress on, pages 1-7. IEEE, 2012. [14]. Martin Piláat and Roman Neruda, "Aggregate meta-models for evolutionary multi-objective and many-objective optimization", Neurocomputing, 116:392-402, 2013. [15]. D. C. Montgomery R. H. Myers and C. M. Anderson-Cook, "Response surface methodology: Process and product optimization using designed experiments", Wiley New York, 2009. [16]. Vladimir Vapnik, "Statistical learning theory. 1998, volume 3", Wiley, New York, 1998. [17]. Ivan Voutchkov and AJ Keane, "Multi-objective optimization using surrogates", 2006. [18]. Saul Zapotecas Martinez and Carlos A Coello Coello, "MOEA/D assisted by RBF networks for expensive multi-objective optimization problems", In Proceedings of the 15th annual conference on Genetic and evolutionary computation, pages 1405-1412. ACM, 2013. [19]. D.A.V. Veldhuizen, "Multi-objective evolutionary algorithms: Classifications, analyses, and new innovation", PhD thesis, Department of Electrical Engineering and Computer Engineering, Airforce Institue of Technology, Ohio, 1999. [20]. Linqiang Pan, Cheng He, Ye Tian, Handing Wang, Xingyi Zhang, and Yaochu Jin, "A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization", IEEE Transactions on Evolutionary Computation, 23(1):74-88, 2018. [21]. Ran Cheng, Yaochu Jin, Markus Olhofer, and Bernhard Sendhoff, "A reference vector guided evolutionary algorithm for many-objective optimization", 20(5):773-791, 2016. [22]. T Chugh, Y Jin, K Miettinen, J Hakanen, and K Sindhya, "K-RVEA: A Kriging-assisted evolutionary algorithm for many-objective optimization", Scientific Computing no.B, 2, 2016. [23]. Kalyanmoy Deb, Lothar Thiele, Macro Laumanns, Eckart Zitzler, "Scalable test problems for evolutionary multi-objective optimization", In: Evolutionary multiobjective optimization, Springer, London, 2005. p. 105-145. [24]. A. Diaz-Manriquez, G. Toscano, J. Barron-Zambrano, E. Tello-Leal, "A review of surrogate assisted multi-objective evolutionary algorithms", Computational Intelligence and Neuroscience Volume 2016, Hindawi. [25]. I. Voutchkov, A. Keane, "Multi-objective optimization using surrogates", Computational Intelligence in Optimization, ALO 7, pp. 155-175, 2010. [26]. Hussein, Rayan, and Kalyanmoy Deb, "A generative kriging surrogate model for constrained and unconstrained multi-objective optimization", Proceedings of the Genetic Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 21
Công nghệ thông tin and Evolutionary Computation Conference 2016. [27]. Dammak, Khalil, and Abdelkhalak El Hami. "Multi-objective reliability based design optimization using Kriging surrogate model for cementless hip prosthesis", Computer Methods in Biomechanics and Biomedical Engineering (2020): 1-14. ABSTRACT GUIDANCE TECHNIQUES FOR SURROGATE ASSISTED MULTI-OBJECTIVE EVOLUTIONARY ALGORITHMS Solving difficult and high cost problems (expensive problems) by using surrogate model in multi-objective evolutionary algorithm is an effective choice and is interested by many researchers. Algorithms have been published that effectively solve expensive problems. However, the strategy in updating the surrogate model, selecting sample data to train the model, etc. has not been thoroughly evaluated, especially affecting the ability to keep the balance of exploration and exploitation. Quality of convergence and diversity, they are important factors determine the quality of a multi-objective optimization algorithm. On the basis of analyzing the conditions in the search process, the guidance technique based on the assessed value at different times to have a strategy for updating the model and selecting sample data more flexible and efficient has been proposed. Through the test results, the comparation, it has demonstrated the explanation and affirmed the effectiveness of guidance techniques, especially combining automatic guide and user interaction in the search process. The publication also recommends using to create sustainability, convergence and diversity results in solving expensive problems in the real world. Keywords: Guidance technique; Surrogate model; Kriging; MOEAs. Nhận bài ngày 30 tháng 09 năm 2020 Hoàn thiện ngày 10 tháng 12 năm 2020 Chấp nhận đăng ngày 15 tháng 12 năm 2020 Địa chỉ: 1Viện Công nghệ thông tin/Viện KH-CN quân sự; 2 Khoa Chỉ huy tham mưu/Học viện Quốc phòng. *Email: nddinh76@gmail.com. 22 N. Đ. Định, N. Long, T. T. Kiên, “Kỹ thuật chỉ dẫn cho giải thuật … mô hình đại diện.”