Xem mẫu
- 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.”
nguon tai.lieu . vn
