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

uyê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 : Rn → R là hàm mục tiêu (i =1, 2,, k). 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ó). Công nghệ thông tin 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.” 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 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 5 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: ( )1: : ( ) Nn i i ii R R x w x c   = → = − (4) Trong phương pháp này, một vài tham số được sử dụng như: véc-tơ tâm ic , 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 Ty x= (5) Trong đó, tập dữ liệu kích thước n được biểu diễn là 1 2, ,..., ,nx x x  là véc-tơ hệ số được ước lượng, p 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: ( ) ( ) , wf x g x b= + (6) Công nghệ thông tin 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.” 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ả. ( )2 1 1 ( , ) 2 n i i i w w C   − + = = + + (7) 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à: ( ) ( ) ( ) ( ) ( ) ( ) 2( '( ), '( )) ( '( ), '( )) ( , , ) i j i j i j E f x f x Cov f x f x R x x = = (8) Trong đó, ( )j x là hàm tương quan với tham số θ, σ là phương sai quá trình của đáp ứng và ( ) ( ) ( , , ) i j 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. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 7 - 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 Công nghệ thông tin 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.” 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. xd xi x1 b1 b2 bh bq y1 yj yl ... ... ... ... ... ... Lớp đầu vào Lớp ẩn Lớp đầu ra v1h vih vdh w1j w2j whj wqj ( ),h hidden hb K = 1 d h ih i i v x = = ( ),j output jy K = 1 w q j hj h h b = = 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 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 9 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. Cá thể con Cập nhật và kiểm tra mô hình Lựa chọn cá thể tham chiếu Toán tử tiến hóa Kết hợp giải pháp tốt và tham chiếu Kết hợp cá thể cha mẹ và cá thể con Lựa chọn môi trường VÒNG LẶP CHÍNH Kết thúc Các toán tử tiến hóa Cá thể con Kết thúc Cá thể tốt Lựa chọn mô hình đại diện Cá thể cha mẹ Đánh giá lại Khởi tạo Cập nhật mô hình và cấu hình độ tin cậy VÒNG LẶP PHỤ Đánh giá lại 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. Công nghệ thông tin 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.” 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) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 11 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 Công nghệ thông tin 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.” 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