Tổng quan luận án
Luận án tiến sĩ toán học với tiêu đề "Objective reduction methods in evolutionary many-objective optimization" (Phương pháp lược bớt hàm mục tiêu trong tối ưu tiến hóa nhiều mục tiêu) do nghiên cứu sinh Nguyễn Xuân Hùng thực hiện dưới sự hướng dẫn khoa học của PGS. Bùi Thu Lâm tại Học viện Kỹ thuật Quân sự (Bộ Giáo dục và Đào tạo – Bộ Quốc phòng), thuộc chuyên ngành Cơ sở toán học cho tin học (Mã số: 9 46 01 10), bảo vệ năm 2022.
Tính cấp thiết và khoảng trống nghiên cứu
Trong thực tế, các bài toán tối ưu hóa thường liên quan đến nhiều mục tiêu cần tối ưu hóa đồng thời. Khi số lượng mục tiêu lớn hơn 3, bài toán được gọi là bài toán tối ưu nhiều mục tiêu (many-objective optimization problem - many-problem). Khi giải quyết các bài toán này, các thuật toán tiến hóa đa mục tiêu truyền thống (multi-objective evolutionary algorithms - multi-algorithms) như NSGA-II hay SPEA2 gặp phải nhiều trở ngại nghiêm trọng:
- Sự suy giảm khả năng tìm kiếm (Deterioration of search ability): Phần lớn quần thể trở thành không bị trội lẫn nhau ngay từ các thế hệ đầu tiên, làm mất đi áp lực chọn lọc hướng về phía mặt Pareto tối ưu (Pareto optimal front - PF).
- Sự bùng nổ số chiều (Dimensionality): Kích thước quần thể cần thiết để biểu diễn một tập PF đầy đủ tăng theo hàm mũ ($N^{m-1}$ điểm đối với bài toán $m$ mục tiêu).
- Khó khăn trong trực quan hóa (Visualization): Khó biểu diễn tập nghiệm trong không gian lớn hơn 3 chiều để người ra quyết định lựa chọn nghiệm cuối cùng.
- Đánh giá hiệu năng phức tạp (Performance evaluations): Các độ đo khoảng cách như Generational Distance (GD) và Inverted Generational Distance (IGD) đòi hỏi tập tham chiếu chuẩn rất lớn, trong khi độ đo Hypervolume (HV) có độ phức tạp tính toán rất cao khi số chiều tăng.
Để giải quyết các khó khăn trên, hai hướng tiếp cận chính đã được phát triển: (1) Cải tiến quan hệ so sánh Pareto hoặc cơ chế chọn lọc trong thuật toán tiến hóa nhiều mục tiêu (many-algorithms); (2) Sử dụng các kỹ thuật lược bớt hàm mục tiêu (objective reduction) nhằm loại bỏ các mục tiêu dư thừa (không xung đột hoặc tương quan) trước và trong khi tối ưu.
Khoảng trống nghiên cứu được tác giả chỉ ra bao gồm:
- Hầu hết các phương pháp lược bớt mục tiêu trước đây tích hợp kỹ thuật giảm số chiều vào các thuật toán đa mục tiêu (multi-algorithms) thay vì các thuật toán nhiều mục tiêu tiên tiến (many-algorithms).
- Nhiều thuật toán tối ưu nhiều mục tiêu chưa xem xét việc lược bớt mục tiêu hoặc chưa được kiểm thử trên các bài toán có mục tiêu dư thừa.
- Các phương pháp lược bớt mục tiêu hiện hữu thường chỉ được kiểm nghiệm trên các bài toán có số lượng mục tiêu nhỏ.
Mục tiêu nghiên cứu
Mục tiêu tổng quát của luận án là tìm hiểu và cải thiện hiệu năng của các thuật toán tiến hóa nhiều mục tiêu thông qua kỹ thuật lược bớt số chiều mục tiêu (objective dimensionality reduction - ODR).
Các mục tiêu cụ thể được xác định bao gồm:
- Mục tiêu 1: Khảo sát hiệu quả của việc kết hợp các thuật toán tiến hóa nhiều mục tiêu (many-algorithms) với kỹ thuật giảm số chiều mục tiêu (ODR), cụ thể là phân tích thành phần chính tuyến tính (Linear Principal Component Analysis - L-PCA). So sánh hiệu năng giữa việc tích hợp ODR vào multi-algorithms với many-algorithms, cũng như so sánh many-algorithms khi có và không có ODR.
- Mục tiêu 2: Đề xuất các phương pháp loại bỏ mục tiêu dư thừa sử dụng thuật toán học máy:
- Phương pháp dựa trên PF toàn phần: Đề xuất thuật toán COR sử dụng thuật toán phân cụm Partitioning Around Medoids (PAM) kết hợp chỉ số Silhouette để tự động xác định số cụm và giữ lại mục tiêu cốt lõi.
- Phương pháp dựa trên PF cục bộ: Tận dụng thuật toán tiến hóa tìm kiếm góc Pareto (Pareto Corner Search Evolutionary Algorithm - PCSEA) để chỉ tạo ra một phần PF (nghiệm góc), sau đó áp dụng L-PCA (thuật toán PCS-LPCA) hoặc các thuật toán phân cụm như $k$-means và DBSCAN (thuật toán PCS-Cluster) để loại bỏ mục tiêu dư thừa.
Câu hỏi nghiên cứu
Luận án giải quyết 3 câu hỏi nghiên cứu:
- Tác động của việc sử dụng multi-algorithms và many-algorithms khi kết hợp với ODR để giải quyết many-problems là gì?
- Mức độ hiệu quả của việc kết hợp many-algorithms với ODR trong việc giải quyết many-problems như thế nào?
- Các đề xuất nào có thể nâng cao hiệu năng của many-algorithms xét theo khía cạnh lược bớt số chiều mục tiêu?
Đối tượng và phạm vi nghiên cứu
- Đối tượng nghiên cứu: Các phương pháp và thuật toán lược bớt hàm mục tiêu trong tối ưu hóa tiến hóa nhiều mục tiêu; các thuật toán học máy giảm chiều và phân cụm dữ liệu (L-PCA, PAM, $k$-means, DBSCAN); các thuật toán tiến hóa đa mục tiêu và nhiều mục tiêu (NSGA-II, SPEA2, SPEA2+SDE, NSGA-III, PCSEA).
- Phạm vi nghiên cứu: Bài toán tối ưu hóa nhiều mục tiêu liên tục có chứa mục tiêu dư thừa (redundant/correlated objectives). Các bộ bài toán chuẩn được sử dụng gồm DTLZ5(I,M), WFG3, và bài toán kỹ thuật thực tế về va chạm hông xe ô tô (car side-impact problem) với số lượng mục tiêu lên đến 10 và 11 chiều.
Tổng quan tài liệu và vị trí của luận án
Các hướng tiếp cận trong tối ưu hóa nhiều mục tiêu
Luận án tổng hợp và phân loại các phương pháp giải quyết bài toán tối ưu nhiều mục tiêu (many-problems) thành 6 nhóm tiếp cận chính:
| Nhóm tiếp cận |
Nguyên lý hoạt động |
Thuật toán / Công trình tiêu biểu |
| Dựa trên nới lỏng quan hệ trội (Relaxed dominance based) |
Sửa đổi quan hệ Pareto bằng cách thay đổi giá trị mục tiêu (value-based) hoặc đếm số lượng mục tiêu vượt trội (number-based) để tăng áp lực chọn lọc. |
$\epsilon$-MOEA (Deb et al., 2003), GrEA (Yang et al., 2013), Favour relation (Drechsler, 1998), $(1-k)$-dominance (Farina & Amato, 2004), L-dominance (Zou et al., 2008). |
| Dựa trên đa dạng quần thể (Diversity based) |
Giảm thiểu tác động tiêu cực của việc duy trì tính đa dạng trong không gian nhiều chiều. |
Grid-based criteria (Yang et al., 2013), Shift-based Density Estimation - SDE (Li et al., 2014), OGEA (Bandaru et al., 2011). |
| Dựa trên hàm tổng hợp (Aggregation based) |
Chuyển đổi bài toán nhiều mục tiêu thành các bài toán con đơn mục tiêu hoặc so sánh từng cặp nghiệm. |
MOEA/D (Zhang & Li, 2007), MSOPS (Hughes, 2005), Ranking Dominance - RD (Kukkonen & Lampinen, 2007), Global Detriment (Garza-Fabre et al., 2009). |
| Dựa trên chỉ số chất lượng (Indicator based) |
Sử dụng giá trị của các chỉ số hiệu năng trực tiếp để định hướng quá trình tìm kiếm. |
HypE (Bader & Zitzler, 2011), IBEA (Zitzler & Künzli, 2004), AGE (Bringmann et al., 2011), MOMBI (Hernández Gómez & Coello Coello, 2013). |
| Dựa trên tập tham chiếu (Reference set based) |
Sử dụng tập các điểm hoặc vector tham chiếu phân bố đều để dẫn dắt quá trình tiến hóa. |
Two_Arch2 (Wang et al., 2015), NSGA-III (Deb & Jain, 2014), SDIEA (Yuan et al., 2016). |
| Dựa trên lược bớt mục tiêu (Objective reduction) |
Xác định và loại bỏ các mục tiêu dư thừa/không xung đột nhằm đưa bài toán về không gian mục tiêu cốt lõi có số chiều nhỏ hơn. |
PCA-NSGA-II (Deb & Saxena, 2005), PCSEA-based (Singh et al., 2011), MICA-NORMOEA, OC-ORA. |
Phân loại các thuật toán lược bớt hàm mục tiêu (ORA)
Theo tổng quan của luận án, các thuật toán lược bớt mục tiêu có thể được phân loại theo nhiều góc độ:
- Lựa chọn đặc trưng (feature selection) hoặc trích xuất đặc trưng (feature extraction).
- Trực tuyến (online - thực hiện trong quá trình tiến hóa) hoặc ngoại tuyến (offline - thực hiện sau khi tạo tập nghiệm).
- Dựa trên quan hệ trội Pareto (Pareto dominance based) hoặc dựa trên hệ số tương quan (correlation based).
- Cho phép sai số (allowing error) hoặc không có sai số (without error).
- Phân loại của luận án: Luận án chia các phương pháp lược bớt mục tiêu thành 2 nhóm cấu trúc:
- Dựa trên PF toàn phần (Complete PF-based): Cần thuật toán tối ưu sinh ra toàn bộ bề mặt Pareto gần đúng trước khi phân tích số chiều.
- Dựa trên PF cục bộ (Partial PF-based): Chỉ sinh ra một tập nghiệm đặc trưng cục bộ (như các nghiệm góc Pareto - corner solutions) để phân tích lược bớt mục tiêu.
Khoảng trống nghiên cứu được lựa chọn giải quyết
Luận án định vị trọng tâm vào việc khắc phục hạn chế về chi phí tính toán khi phải tạo toàn bộ PF trong không gian nhiều chiều, đồng thời nâng cao độ chính xác trong việc nhận diện tập mục tiêu cốt lõi thông qua việc kết hợp các thuật toán học máy phân cụm và trích xuất đặc trưng với các bộ sinh nghiệm tiến hóa chuyên biệt.
Cơ sở lý thuyết và phương pháp nghiên cứu
Khung khái niệm và định nghĩa toán học
-
Bài toán tối ưu hóa đa mục tiêu (Multi-objective Optimization Problem):
$$\min f(x) = [f_1(x), f_2(x), \dots, f_M(x)]^T \quad \text{với } x \in \Omega \subset \mathbb{R}^n$$
Trong đó $x = [x_1, x_2, \dots, x_n]^T$ là vector biến quyết định; $\Omega$ là không gian khả thi; $f_i(x): \mathbb{R}^n \rightarrow \mathbb{R}$ là các hàm mục tiêu thành phần ($M \ge 2$).
-
Quan hệ trội Pareto (Pareto dominance):
Nghiệm $x_1$ được gọi là trội nghiệm $x_2$ ($x_1 \prec x_2$) khi và chỉ khi:
$$\forall i \in {1, \dots, M}: f_i(x_1) \le f_i(x_2) \quad \text{và} \quad \exists j \in {1, \dots, M}: f_j(x_1) < f_j(x_2)$$
-
Tập nghiệm Pareto tối ưu (Pareto Optimal Set - PS) và Mặt Pareto (Pareto Optimal Front - PF):
Nghiệm $x^* \in \Omega$ là tối ưu Pareto nếu không tồn tại $x \in \Omega$ nào trội $x^*$. Tập hợp tất cả các nghiệm tối ưu Pareto trong không gian quyết định tạo thành $PS$, và ảnh của $PS$ trong không gian mục tiêu tạo thành $PF$.
-
Tập mục tiêu cốt lõi (Essential / Relevant objective set - $F_T$):
Tập mục tiêu cốt lõi $F_T \subseteq F_0 = {f_1, \dots, f_M}$ ($|F_T| = m \le M$) là tập nhỏ nhất các mục tiêu xung đột lẫn nhau có khả năng duy trì cùng một trật tự Pareto và tập nghiệm tối ưu như tập mục tiêu ban đầu $F_0$.
-
Mục tiêu dư thừa (Redundant / Nonessential objective):
Một mục tiêu được coi là dư thừa nếu nó không xung đột (hoặc có tương quan đồng biến mạnh) với các mục tiêu khác trong bài toán, việc loại bỏ nó không làm thay đổi cấu trúc của tập nghiệm Pareto tối ưu.
Cấu trúc khung của một quy trình lược bớt mục tiêu
Quy trình ORA tổng quát bao gồm hai khối chức năng chính:
- Khối sinh nghiệm (Generator module): Sử dụng thuật toán tiến hóa (multi-algorithm hoặc many-algorithm) để tạo ra tập nghiệm không bị trội xấp xỉ PF ($PF_{know}$).
- Khối giảm số chiều (Reduction module - ODR): Áp dụng thuật toán học máy để phân tích ma trận giá trị mục tiêu của tập nghiệm thu được, phát hiện tương quan và loại bỏ mục tiêu dư thừa, giữ lại tập $F_T$.
Các thuật toán học máy sử dụng trong luận án
- Linear Principal Component Analysis (L-PCA): Tính toán ma trận tương quan $R$ từ tập nghiệm không bị trội, tìm các trị riêng (eigenvalues) và vector riêng (eigenvectors) tương ứng để xác định mức độ đóng góp và sự tương quan giữa các mục tiêu.
- Partitioning Around Medoids (PAM): Thuật toán phân cụm chia $M$ mục tiêu thành $k$ cụm dựa trên ma trận khoảng cách; mỗi cụm được đại diện bởi một medoid (đối tượng có tổng độ khác biệt nhỏ nhất với các đối tượng khác trong cùng cụm). Số cụm $k$ được xác định tự động thông qua chỉ số Silhouette.
- $k$-means: Thuật toán phân cụm phân hoạch dựa trên trọng tâm (center of gravity) của các cụm mục tiêu.
- Density-Based Spatial Clustering of Applications with Noise (DBSCAN): Thuật toán phân cụm dựa trên mật độ với hai tham số cơ bản là bán kính lân cận ($Eps$) và số lượng điểm tối thiểu ($minObjs$). Các mục tiêu nằm trong vùng mật độ cao được nhóm thành cụm tương quan.
Bộ bài toán chuẩn và thước đo đánh giá
- Bộ bài toán kiểm thử:
- DTLZ5(I,M): Bài toán suy biến với $M$ mục tiêu, trong đó số chiều thực sự của PF là $I$ ($2 \le I \le M$). Trong bài toán này, $M - I + 1$ mục tiêu đầu tiên có tương quan với nhau, trong khi các mục tiêu còn lại xung đột trực tiếp với nhau. Bề mặt Pareto tuân theo phương trình $\sum_{i=1}^M (f_i)^2 = 1$.
- WFG3(M): Bài toán kiểm thử có PF suy biến thành siêu phẳng tuyến tính thỏa mãn $\sum_{i=1}^M f_i = 1$, trong đó $M-1$ mục tiêu đầu tiên tương quan hoàn toàn với nhau, mục tiêu thứ $M$ xung đột với tất cả các mục tiêu trước đó.
- Car side-impact problem: Bài toán tối ưu va chạm hông xe ô tô thực tế gồm 11 mục tiêu/ràng buộc được chuyển đổi từ bài toán đơn mục tiêu có 10 ràng buộc thiết kế kỹ thuật ($x_1, \dots, x_{11}$).
- Thước đo hiệu năng:
- Generational Distance (GD): Đo khoảng cách trung bình từ tập nghiệm tìm được $PF_{know}$ đến mặt Pareto thực $PF_{true}$ (đánh giá độ hội tụ):
$$GD = \frac{\sqrt{\sum_{i=1}^M d_i^2}}{M}$$
- Inverted Generational Distance (IGD): Đo khoảng cách trung bình từ $PF_{true}$ đến điểm gần nhất trong $PF_{know}$ (đánh giá đồng thời cả độ hội tụ và độ phân bố):
$$IGD = \frac{\sum_{j=1}^n d_j}{n}$$
- Số lần thành công (Success rate): Số lần thuật toán xác định chính xác tập mục tiêu cốt lõi $F_T$ trong 20 hoặc 30 lần chạy độc lập.
- Kiểm định thống kê: Kiểm định Wilcoxon signed-rank test, kiểm định thứ hạng Friedman, và kiểm định hậu nghiệm Conover điều chỉnh theo phương pháp Holm FWER để khẳng định ý nghĩa thống kê ở mức ý nghĩa tiêu chuẩn.
Nội dung chính theo từng chương
Chapter 1: Literature Review (Tổng quan tài liệu)
Chương 1 hệ thống hóa toàn diện các lý thuyết nền tảng và các công trình liên quan trực tiếp đến đề tài:
- Trình bày định nghĩa toán học của bài toán tối ưu hóa tổng quát, bài toán đơn mục tiêu, đa mục tiêu và các đặc tính không gian tìm kiếm (liên tục/rời rạc, lồi/không lồi, có/không ràng buộc).
- Phân tích nguyên lý của thuật toán tiến hóa (EC/EA), các toán tử tái tổ hợp (recombination), đột biến (mutation), chọn lọc (selection) và ưu thế xử lý quần thể song song.
- Làm rõ bản chất của bài toán tối ưu nhiều mục tiêu ($M > 3$) và phân tích sâu 4 thách thức cốt lõi (suy giảm áp lực chọn lọc Pareto, bùng nổ số chiều biểu diễn PF, hạn chế trực quan hóa và chi phí đánh giá hiệu năng).
- Phân loại chi tiết 6 hướng tiếp cận đương đại xử lý bài toán many-problems.
- Tổng hợp cơ chế của các thuật toán học máy giảm chiều (PCA) và phân cụm (PAM, $k$-means, DBSCAN).
- Giới thiệu các phương thức trực quan hóa không gian nhiều chiều (tọa độ sao - star coordinates, ma trận biểu đồ phân tán - scatter-plot matrix, hệ tọa độ song song - parallel coordinates) cùng công thức toán học của các hàm thử nghiệm DTLZ, WFG và bài toán va chạm ô tô.
Chapter 2: The complete PF-based objective reduction algorithms (Các thuật toán lược bớt hàm mục tiêu dựa trên PF toàn phần)
Chương 2 tập trung nghiên cứu hiệu quả của việc kết hợp các thuật toán tiến hóa nhiều mục tiêu với kỹ thuật giảm số chiều, đồng thời đề xuất thuật toán COR:
1. Đánh giá tương tác giữa many-algorithms và ODR (L-PCA)
- Tác giả thực hiện các phân tích thực nghiệm so sánh việc tích hợp L-PCA vào các thuật toán đa mục tiêu cổ điển (NSGA-II, SPEA2) với các thuật toán nhiều mục tiêu (SPEA2+SDE, NSGA-III) trên bài toán DTLZ5(6,8).
- Kết quả ma trận tương quan $R$, các trị riêng và vector riêng được phân tích chi tiết:
| Thuật toán kết hợp L-PCA |
Số mục tiêu giữ lại trung bình ($\pm$ Độ lệch chuẩn) |
GD trước ODR ($GD_1$) |
GD sau ODR ($GD_2$) |
IGD trước ODR ($IGD_1$) |
IGD sau ODR ($IGD_2$) |
Số lần tìm đúng tập mục tiêu cốt lõi (/20 lần) |
| SPEA2 + L-PCA |
Không ổn định |
Cao |
Không cải thiện |
Cao |
Không cải thiện |
Thấp |
| NSGA-II + L-PCA |
Không ổn định |
Cao |
Không cải thiện |
Cao |
Không cải thiện |
Thấp |
| SPEA2+SDE + L-PCA |
Tiệm cận số chiều $I=6$ |
Nhỏ |
Duy trì tốt |
Nhỏ |
Duy trì tốt |
Cao |
| NSGA-III + L-PCA |
Chính xác $I=6$ |
Nhỏ |
Cải thiện rõ |
Nhỏ |
Cải thiện rõ |
Vượt trội |
- Kiểm định Wilcoxon signed-rank test (Bảng 2.8) chứng minh có ý nghĩa thống kê ($p < 0.05$) rằng việc sử dụng many-algorithms làm khối sinh nghiệm giúp L-PCA nhận diện mục tiêu chính xác hơn rõ rệt so với multi-algorithms. Đồng thời, many-algorithms khi được tích hợp ODR đạt hiệu quả tìm kiếm vượt trội so với khi chạy đơn lẻ.
2. Thuật toán lược bớt mục tiêu COR (Clustering Objective Reduction)
- Cơ chế đề xuất: COR sử dụng một thuật toán many-algorithm để sinh tập nghiệm xấp xỉ PF đầy đủ. Sau đó, coi $M$ hàm mục tiêu như $M$ đối tượng dữ liệu trong không gian nghiệm.
- Tự động xác định số cụm: Thay vì yêu cầu người dùng chỉ định trước số cụm $k$, COR áp dụng chỉ số Silhouette để đánh giá chất lượng phân cụm và tự động chọn giá trị $k$ tối ưu.
- Lược bớt: Thuật toán PAM được sử dụng để gom cụm các mục tiêu có tính chất tương đồng; từ mỗi cụm, thuật toán chỉ giữ lại một mục tiêu đại diện (medoid) và loại bỏ tất cả các mục tiêu còn lại trong cụm.
- Kết quả thực nghiệm trên DTLZ5(I,M) khẳng định COR xác định chính xác số lượng và thành phần của tập mục tiêu cốt lõi $F_T$ mà không cần can thiệp tham số số cụm từ người dùng.
Chapter 3: The partial PF-based objective reduction algorithms (Các thuật toán lược bớt hàm mục tiêu dựa trên PF cục bộ)
Nhận thấy việc tạo toàn bộ bề mặt PF trong không gian nhiều chiều tiêu tốn tài nguyên tính toán rất lớn và có thể bất khả thi khi số mục tiêu rất cao, Chương 3 đề xuất hướng tiếp cận mới: chỉ sinh tập nghiệm cục bộ tại các vị trí góc (corner solutions) thông qua thuật toán PCSEA.
[PCSEA] -> Sinh tập nghiệm góc (Partial PF) -> [Thuật toán Học máy] -> Xác định tập mục tiêu cốt lõi FT
[PCS-LPCA] [PCS-Cluster]
(Linear PCA) (k-means hoặc DBSCAN)
1. Thuật toán PCS-LPCA
- Tích hợp PCSEA với phân tích thành phần chính tuyến tính L-PCA.
- PCSEA nhanh chóng tìm kiếm các nghiệm tối ưu đơn lẻ cho từng mục tiêu riêng biệt (nghiệm cực biên/nghiệm góc của PF).
- L-PCA phân tích ma trận tương quan tạo bởi các nghiệm góc này để trích xuất các mục tiêu xung đột chính.
- Bảng 3.4 so sánh số lần thành công trên 30 lần chạy độc lập giữa PCS-LPCA, PCSEA-based thuần túy và mô hình kết hợp many-algorithms + L-PCA. PCS-LPCA đạt tỷ lệ thành công vượt trội trên các bài toán DTLZ5 có số chiều lớn, giảm thiểu đáng kể số lần đánh giá hàm mục tiêu.
2. Thuật toán PCS-Cluster
- Tích hợp PCSEA với các thuật toán phân cụm học máy: $k$-means (Bảng 3.10) và DBSCAN (Bảng 3.11).
- Tính toán ma trận khoảng cách giữa các vector mục tiêu của tập nghiệm góc:
- Với $k$-means: Phân chia các mục tiêu thành các nhóm tương quan dựa trên khoảng cách hình học của các giá trị tại điểm góc.
- Với DBSCAN: Tự động gom cụm các mục tiêu nằm trong vùng mật độ lân cận bán kính $Eps$ với ngưỡng $minObjs$, xác định các mục tiêu cốt lõi độc lập mà không bị phụ thuộc vào hình dạng phân bố cụm.
- Đánh giá thống kê tổng hợp (Bảng 3.12, 3.13, 3.14):
- Kiểm định Friedman xếp hạng 8 thuật toán cho thấy PCS-Cluster (đặc biệt là biến thể sử dụng DBSCAN) và PCS-LPCA đạt thứ hạng trung bình cao nhất về độ chính xác nhận diện mục tiêu.
- Kiểm định hậu nghiệm Conover điều chỉnh bằng Holm FWER xác nhận sự khác biệt vượt trội về mặt thống kê của các thuật toán đề xuất so với các phương pháp đối chứng.
- So sánh GD và IGD (Bảng 3.15) trước và sau khi giảm chiều khẳng định việc loại bỏ mục tiêu dư thừa không làm suy giảm chất lượng biểu diễn mặt Pareto thực.
Kết quả và những đóng góp mới
Luận án đã đạt được các đóng góp khoa học chính sau đây:
-
Làm sáng tỏ vai trò của thuật toán sinh nghiệm đối với hiệu năng ODR:
- Chứng minh bằng thực nghiệm và kiểm định thống kê rằng độ chính xác của kỹ thuật giảm số chiều mục tiêu phụ thuộc chặt chẽ vào chất lượng của tập nghiệm không bị trội đầu vào. Các many-algorithms (như NSGA-III, SPEA2+SDE) khi đóng vai trò khối sinh nghiệm cho kết quả vượt trội so với multi-algorithms truyền thống (NSGA-II, SPEA2).
- Chứng minh việc tích hợp ODR giúp nâng cao rõ rệt hiệu năng hội tụ và phân bố của chính các many-algorithms khi xử lý bài toán có chứa mục tiêu dư thừa.
-
Đề xuất thuật toán COR dựa trên PF toàn phần:
- Xây dựng thành công thuật toán COR kết hợp many-algorithms với thuật toán phân cụm PAM.
- Giải quyết bài toán tự động xác định số lượng cụm mục tiêu tối ưu thông qua chỉ số Silhouette, loại bỏ việc phải thiết lập tham số số chiều $k$ một cách thủ công.
-
Đề xuất hai thuật toán lược bớt mục tiêu dựa trên PF cục bộ (PCS-LPCA và PCS-Cluster):
- Đề xuất khung phương pháp mới chỉ sử dụng tập nghiệm góc do PCSEA sinh ra (thay vì toàn bộ PF) để phân tích lược bớt mục tiêu.
- Phát triển thuật toán PCS-LPCA kết hợp PCSEA và L-PCA.
- Phát triển thuật toán PCS-Cluster kết hợp PCSEA với các thuật toán phân cụm $k$-means và DBSCAN.
- Giảm chi phí tính toán tạo quần thể mẫu theo hàm mũ, đồng thời duy trì độ chính xác cao trong việc tìm kiếm tập mục tiêu cốt lõi $F_T$ trên các không gian mục tiêu quy mô lớn (đã kiểm nghiệm trên các bộ bài toán DTLZ5, WFG3 và bài toán thực tế va chạm hông xe ô tô 11 mục tiêu).
Hạn chế và hướng nghiên cứu tiếp
Căn cứ theo nội dung và phạm vi nghiên cứu được trình bày trong luận án:
- Hạn chế về chi phí tính toán của phương pháp toàn phần: Các thuật toán dựa trên PF toàn phần (như COR) vẫn đòi hỏi khối sinh nghiệm phải vận hành đủ số thế hệ để xấp xỉ toàn bộ mặt Pareto trước khi tiến hành gom cụm, dẫn đến chi phí tính toán lớn khi số chiều mục tiêu ban đầu quá cao.
- Sự phụ thuộc vào chất lượng nghiệm góc trong phương pháp cục bộ: Hiệu năng của PCS-LPCA và PCS-Cluster phụ thuộc trực tiếp vào khả năng tìm chính xác các nghiệm biên/nghiệm góc của thuật toán PCSEA. Nếu bài toán có không gian mục tiêu phức tạp, đa đỉnh hoặc nghiệm góc khó tiếp cận, độ chính xác phân cụm mục tiêu có thể bị ảnh hưởng.
- Hướng phát triển: Mở rộng nghiên cứu áp dụng các kỹ thuật học máy phi tuyến tính, mở rộng kiểm thử trên các bài toán thực tế có ràng buộc phức tạp hơn, và phát triển các cơ chế lược bớt mục tiêu trực tuyến (online reduction) thích nghi động trong quá trình tiến hóa.
Giá trị tham khảo
Luận án là tài liệu chuyên khảo có giá trị cao đối với:
- Nghiên cứu sinh và học viên cao học: Chuyên ngành Cơ sở toán học cho tin học, Khoa học máy tính, Toán ứng dụng và Trí tuệ nhân tạo; đặc biệt là những người nghiên cứu sâu về tính toán tiến hóa (Evolutionary Computation) và tối ưu hóa đa mục tiêu/nhiều mục tiêu (MOO/MaOO).
- Giảng viên và nhà nghiên cứu: Cung cấp tổng quan hệ thống về 6 trường phái tối ưu hóa nhiều mục tiêu đương đại, cùng hệ thống kiểm thử toán học chuẩn (DTLZ5(I,M), WFG3) và các kỹ thuật thống kê đối sánh (Wilcoxon, Friedman, Conover-Holm).
- Kỹ sư và chuyên gia tối ưu hóa kỹ thuật: Cung cấp giải pháp thực tế để xử lý các bài toán thiết kế kỹ thuật công nghiệp có số chiều lớn nhưng tồn tại tương quan mục tiêu (như bài toán thiết kế cấu trúc an toàn va chạm ô tô).
Câu hỏi thường gặp
1. Tại sao các thuật toán đa mục tiêu truyền thống như NSGA-II lại suy giảm hiệu năng nghiêm trọng khi số mục tiêu lớn hơn 3?
Khi số lượng mục tiêu $M > 3$, hiện tượng kháng trội (dominance resistance) xuất hiện: hầu hết các cá thể trong quần thể đều trở thành không bị trội lẫn nhau. Do đó, quan hệ trội Pareto mất đi khả năng phân loại chất lượng nghiệm để tạo áp lực chọn lọc hướng về phía mặt Pareto tối ưu ($PF$). Đồng thời, số lượng nghiệm cần thiết để bao phủ $PF$ tăng theo cấp số nhân ($N^{m-1}$), khiến thuật toán không thể duy trì độ hội tụ và phân bố đồng đều.
2. Sự khác biệt cốt lõi giữa hai thuật toán đề xuất COR và PCS-Cluster là gì?
- COR (Chương 2): Thuộc nhóm tiếp cận dựa trên PF toàn phần (complete PF-based). Thuật toán cần một many-algorithm tạo ra toàn bộ mặt Pareto xấp xỉ, sau đó dùng chỉ số Silhouette để tự động tìm số cụm và dùng thuật toán PAM để gom cụm mục tiêu.
- PCS-Cluster (Chương 3): Thuộc nhóm tiếp cận dựa trên PF cục bộ (partial PF-based). Thuật toán chỉ sử dụng PCSEA để tìm các nghiệm góc (corner solutions) của PF, sau đó áp dụng $k$-means hoặc DBSCAN trên ma trận khoảng cách của các nghiệm góc này để xác định mục tiêu cốt lõi, giúp tiết kiệm đáng kể chi phí tính toán.
3. Thuật toán COR giải quyết bài toán xác định số cụm mục tiêu như thế nào mà không cần người dùng nhập trước?
Thuật toán COR tích hợp chỉ số chất lượng phân cụm Silhouette index ($s(i)$). Trong quá trình phân cụm các hàm mục tiêu bằng thuật toán PAM, COR quét qua các giá trị $k$ khả dĩ, tính toán giá trị Silhouette trung bình cho từng cấu hình phân hoạch, và tự động chọn giá trị $k$ có chỉ số Silhouette cao nhất làm số lượng mục tiêu cốt lõi cần giữ lại.
4. Thuật toán DBSCAN được cấu hình và hoạt động ra sao trong phương pháp PCS-Cluster?
DBSCAN hoạt động dựa trên hai tham số là bán kính vùng lân cận ($Eps$) và số lượng đối tượng tối thiểu ($minObjs$). Trong PCS-Cluster, các hàm mục tiêu được ánh xạ thành các điểm dữ liệu dựa trên giá trị tại các nghiệm góc. DBSCAN nhận diện các vùng mật độ cao để nhóm các mục tiêu có tính chất tương quan mạnh vào cùng một cụm và tách biệt các mục tiêu độc lập/xung đột.
5. Kết quả kiểm định thống kê nào khẳng định tính ưu việt của các thuật toán đề xuất trong luận án?
Luận án sử dụng kiểm định Wilcoxon signed-rank test ở Chương 2 để chứng minh sự vượt trội có ý nghĩa thống kê ($p < 0.05$) khi kết hợp many-algorithms với L-PCA. Tại Chương 3, kiểm định thứ hạng Friedman và kiểm định hậu nghiệm Conover điều chỉnh theo phương pháp Holm FWER (Bảng 3.13, 3.14, 3.17) khẳng định PCS-LPCA và PCS-Cluster đạt thứ hạng vượt trội so với các thuật toán ORA đối chứng trên tổng số 30 lần chạy thử nghiệm độc lập.
Kết luận
Luận án của tác giả Nguyễn Xuân Hùng đã giải quyết bài toán giảm chiều không gian mục tiêu trong tối ưu hóa tiến hóa nhiều mục tiêu thông qua việc kết hợp chặt chẽ giữa giải thuật tiến hóa và các kỹ thuật học máy. Bằng việc phân tích sâu sắc tương tác giữa khối sinh nghiệm và khối giảm chiều, luận án đã chứng minh tính hiệu quả vượt trội của many-algorithms so với multi-algorithms trong quy trình ODR. Các đóng góp mang tính thực tiễn và học thuật cao gồm thuật toán COR tự động xác định số cụm dựa trên PF toàn phần, cùng hai thuật toán PCS-LPCA và PCS-Cluster dựa trên nghiệm góc cục bộ giúp giảm thiểu chi phí tính toán trên các bài toán quy mô lớn. Toàn bộ các đề xuất đều được kiểm chứng nghiêm ngặt qua các bộ bài toán chuẩn DTLZ5, WFG3, bài toán va chạm ô tô thực tế và các phép kiểm định thống kê toán học chuẩn tắc.
