Luận Án Tiến Sĩ: 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

Luận án tiến sĩ phân tích một số phương pháp lược bớt các hàm mục tiêu trong tối ưu tiến hóa nhiều mục tiêu, xây dựng cơ sở lý luận, kiểm chứng thực nghiệm, đóng góp tri thức mới

• Tác giả: Nguyen Xuan Hung
• Người hướng dẫn: Assoc. Bui Thu Lam
• Trường học: Military Technical Academy
• Chuyên ngành: Mathematical Foundation for Informatics
• Đề tài: Objective reduction methods in evolutionary many-objective optimization
• Loại tài liệu: doctoral thesis
• Năm xuất bản: 2022
• Địa điểm: Hanoi

Mục lục chi tiết

• Originality Statement
• Acknowledgments
• Abstract
• Contents
• 1. Chapter 1: Literature Review
• 1.1. Multi-objective optimization
• 1.2. Machine learning algorithms used in this study
• 1.3. Many-objective optimization
• 1.4. Benchmarks and performance measures
• 2. Chapter 2: The complete PF-based objective reduction algorithms
• 2.1. Efficiency in many-objective algorithms in objective reduction
• 2.2. The proposed method
• 2.3. Results and discussions
• 2.4. COR objective reduction algorithm
• 2.5. The proposed algorithm
• 2.6. Results and discussions
• 3. Chapter 3: The partial PF-based objective reduction algorithms
• 3.1. PCS-LPCA objective reduction algorithm
• 3.2. The proposed algorithm
• 3.3. Results and discussions
• 3.4. PCS-Cluster objective reduction algorithm
• 3.5. The proposed algorithm
• 3.6. Results and discussions
• Conclusion and future works
• Publications
• Bibliography
• Appendix A. Representations of non-dominated solutions
• Appendix B. Several machine learning algorithms

Tóm tắt

I. Tối ưu tiến hóa và hàm mục tiêu

Tối ưu tiến hóa là một phương pháp mô phỏng quá trình tiến hóa tự nhiên để giải quyết các bài toán tối ưu hóa. Trong bài toán tối ưu nhiều mục tiêu, các hàm mục tiêu thường xung đột với nhau, khiến việc tìm kiếm giải pháp tối ưu trở nên phức tạp. Các giải thuật tiến hóa như NSGA-II và SPEA2 được sử dụng để xử lý các bài toán này bằng cách duy trì một tập hợp các giải pháp đa dạng và tiến gần đến Pareto Front (PF). Tuy nhiên, khi số lượng mục tiêu tăng lên, các giải thuật này gặp khó khăn trong việc xác định các giải pháp tốt. Để giải quyết vấn đề này, các giải thuật tiến hóa nhiều mục tiêu được đề xuất, tập trung vào việc cải thiện hiệu suất và giảm thiểu sự phức tạp.

1.1. Khái niệm tối ưu tiến hóa

Tối ưu tiến hóa là một nhánh của tối ưu hóa sử dụng các nguyên lý tiến hóa tự nhiên để tìm kiếm giải pháp tối ưu. Các giải thuật tiến hóa như NSGA-II và SPEA2 được sử dụng rộng rãi trong tối ưu hóa đa mục tiêu. Chúng hoạt động bằng cách mô phỏng quá trình tiến hóa của một quần thể các cá thể qua nhiều thế hệ, chọn lọc các giải pháp tốt để tạo ra thế hệ tiếp theo. Khi số lượng mục tiêu vượt quá ba, bài toán được coi là tối ưu hóa nhiều mục tiêu, và các giải thuật truyền thống gặp khó khăn trong việc xác định các giải pháp tốt.

1.2. Hàm mục tiêu trong tối ưu hóa

Trong tối ưu hóa nhiều mục tiêu, các hàm mục tiêu thường xung đột với nhau, nghĩa là cải thiện một mục tiêu có thể làm giảm hiệu suất của mục tiêu khác. Ví dụ, trong bài toán mua xe, mục tiêu giảm chi phí và tăng sự thoải mái thường không thể đạt được đồng thời. Các giải thuật tiến hóa sử dụng quan hệ Pareto để so sánh các giải pháp và duy trì một tập hợp các giải pháp đa dạng, gọi là Pareto Front (PF).

II. Phương pháp lược bớt hàm mục tiêu

Phương pháp lược bớt hàm mục tiêu là một kỹ thuật quan trọng trong tối ưu hóa nhiều mục tiêu, giúp giảm thiểu sự phức tạp bằng cách loại bỏ các mục tiêu dư thừa. Các giải thuật lược bớt mục tiêu như COR, PCS-LPCA và PCS-Cluster được đề xuất để xử lý các bài toán có mục tiêu dư thừa. Các giải thuật này kết hợp giải thuật tiến hóa với các kỹ thuật giảm chiều dữ liệu để phân tích và loại bỏ các mục tiêu không cần thiết, giữ lại các mục tiêu cốt lõi. Kết quả thực nghiệm cho thấy việc tích hợp lược bớt hàm mục tiêu vào các giải thuật tiến hóa nhiều mục tiêu mang lại hiệu quả cao hơn so với các phương pháp truyền thống.

2.1. Giải thuật COR

Giải thuật COR là một giải thuật lược bớt mục tiêu dựa trên giải thuật tiến hóa nhiều mục tiêu Pareto hoàn chỉnh. COR có khả năng tự động xác định số lượng cụm để phân chia tập các mục tiêu, từ đó loại bỏ các mục tiêu dư thừa. Kết quả thử nghiệm cho thấy COR hiệu quả trong việc giảm thiểu số lượng mục tiêu mà vẫn duy trì được chất lượng của các giải pháp.

2.2. Giải thuật PCS LPCA và PCS Cluster

PCS-LPCA và PCS-Cluster là hai giải thuật lược bớt mục tiêu được đề xuất trong nghiên cứu này. PCS-LPCA sử dụng giải thuật PCSEA để tạo ra một tập hợp giải pháp, sau đó áp dụng phân tích thành phần chính tuyến tính (L-PCA) để phân tích các giá trị mục tiêu và loại bỏ các mục tiêu dư thừa. Trong khi đó, PCS-Cluster sử dụng các thuật toán phân cụm như k-means và DBSCAN để phân tích tập hợp giải pháp và giữ lại các mục tiêu cốt lõi. Cả hai giải thuật đều cho thấy hiệu quả cao trong việc giảm thiểu số lượng mục tiêu mà vẫn duy trì được chất lượng của các giải pháp.

III. Ứng dụng thực tiễn và đánh giá

Các phương pháp lược bớt hàm mục tiêu được đề xuất trong nghiên cứu này có nhiều ứng dụng thực tiễn trong các lĩnh vực như kỹ thuật, kinh tế và khoa học máy tính. Việc giảm thiểu số lượng mục tiêu giúp đơn giản hóa quá trình tối ưu hóa, giảm thời gian tính toán và cải thiện hiệu suất của các giải thuật tiến hóa. Kết quả thử nghiệm cho thấy các giải thuật lược bớt mục tiêu như COR, PCS-LPCA và PCS-Cluster hiệu quả hơn so với các phương pháp truyền thống trong việc xử lý các bài toán có mục tiêu dư thừa. Nghiên cứu cũng chỉ ra rằng việc tích hợp các kỹ thuật giảm chiều dữ liệu vào các giải thuật tiến hóa nhiều mục tiêu mang lại kết quả tốt hơn so với việc sử dụng các giải thuật tiến hóa đa mục tiêu truyền thống.

3.1. Ứng dụng trong thực tiễn

Các phương pháp lược bớt hàm mục tiêu có nhiều ứng dụng trong các lĩnh vực như thiết kế kỹ thuật, quản lý tài nguyên và tối ưu hóa hệ thống. Ví dụ, trong thiết kế ô tô, việc giảm thiểu số lượng mục tiêu giúp các nhà thiết kế tập trung vào các yếu tố quan trọng như chi phí và hiệu suất, từ đó đưa ra các quyết định tối ưu hơn.

3.2. Đánh giá hiệu quả

Kết quả thử nghiệm cho thấy các giải thuật lược bớt mục tiêu như COR, PCS-LPCA và PCS-Cluster hiệu quả hơn so với các phương pháp truyền thống trong việc xử lý các bài toán có mục tiêu dư thừa. Các giải thuật này không chỉ giảm thiểu số lượng mục tiêu mà còn duy trì được chất lượng của các giải pháp, giúp cải thiện hiệu suất của các giải thuật tiến hóa nhiều mục tiêu.

Nội dung chính

Tổng quan về luận án

Tối ưu hóa đa mục tiêu (Multi-Objective Optimization - MOO) và đặc biệt là tối ưu hóa nhiều mục tiêu (Many-Objective Optimization - MaOO) với số lượng hàm mục tiêu $M > 3$ đóng vai trò nền tảng trong toán học ứng dụng, khoa học máy tính và kỹ thuật công nghiệp hiện đại. Khi số lượng mục tiêu tăng lên, các thuật toán tiến hóa đa mục tiêu truyền thống (Multi-Objective Evolutionary Algorithms - MOEAs) như NSGA-II hay SPEA2 gặp phải sự suy giảm hiệu năng nghiêm trọng do hiện tượng "kháng trội" (dominance resistance phenomenon). Cụ thể, tỷ lệ các cá thể không bị trội (Pareto-nondominated solutions) trong quần thể tăng nhanh xấp xỉ 100% ngay từ các thế hệ đầu tiên, làm triệt tiêu áp lực chọn lọc hướng về mặt tiền Pareto tối ưu (Pareto Optimal Front - PF). Đồng thời, việc biểu diễn mặt PF đòi hỏi kích thước quần thể tăng theo hàm mũ xấp xỉ $N^{m-1}$ điểm (với $m$ là số chiều không gian mục tiêu), gây bùng nổ chi phí tính toán và làm phức tạp hóa quá trình ra quyết định của các chuyên gia.

Trong thực tế, nhiều bài toán kỹ thuật phức tạp chứa đựng các hàm mục tiêu không hoàn toàn xung đột mà có sự tương quan hoặc dư thừa (redundant/non-essential objectives). Điển hình như bài toán va chạm hông xe ô tô (car side-impact problem) với 11 hàm mục tiêu xuất phát từ 10 hàm ràng buộc kỹ thuật. Trước bối cảnh đó, luận án tiến sĩ toán học "Objective reduction methods in evolutionary many-objective optimization" (Chuyên ngành: Cơ sở toán học cho tin học, Mã số: 9 46 01 10) của Nghiên cứu sinh Nguyễn Xuân Hùng, dưới sự hướng dẫn của PGS.TS. Bùi Thu Lâm tại Học viện Kỹ thuật Quân sự (Hà Nội, 2022), đã tập trung nghiên cứu chuyên sâu các phương pháp lược bớt chiều không gian mục tiêu (Objective Dimensionality Reduction - ODR) nhằm nâng cao hiệu năng tìm kiếm và đơn giản hóa không gian nghiệm.

Nghiên cứu giải quyết một khoảng trống tri thức (research gap) trọng yếu: Hầu hết các phương pháp lược bớt mục tiêu trước đây đều tích hợp trên nền tảng các MOEA cổ điển (vốn dĩ đã mất khả năng hội tụ khi $M > 3$), chưa tận dụng các thuật toán tiến hóa nhiều mục tiêu hiện đại (Many-Objective Evolutionary Algorithms - MaOEAs), đồng thời các thuật toán lược bớt mục tiêu hiện hữu chủ yếu được kiểm thử trên số lượng mục tiêu nhỏ và đòi hỏi phải xấp xỉ toàn bộ mặt PF (Complete PF) với chi phí tính toán vô cùng đắt đỏ.

Luận án thiết lập hệ thống ba câu hỏi nghiên cứu (Research Questions - RQ) và giả thuyết khoa học cốt lõi:

1. RQ1: Việc kết hợp giữa các thuật toán tiến hóa đa mục tiêu cổ điển (MOEAs) và thuật toán tiến hóa nhiều mục tiêu hiện đại (MaOEAs) với các kỹ thuật giảm chiều dữ liệu (ODR) tạo ra tác động khác biệt như thế nào đối với hiệu quả xác định tập mục tiêu thiết yếu?
2. RQ2: Việc tích hợp kỹ thuật ODR vào MaOEAs có thực sự mang lại lợi thế vượt trội về khả năng hội tụ và độ phân bố so với việc thực thi MaOEAs độc lập trên bài toán gốc hay không?
3. RQ3: Làm thế nào để xây dựng các giải thuật lược bớt mục tiêu mới dựa trên học máy (machine learning) có khả năng tự động xác định số lượng mục tiêu cốt lõi mà chỉ cần xấp xỉ một phần mặt Pareto (Partial PF) nhằm tối ưu hóa chi phí tính toán?

Khung lý thuyết của luận án được xây dựng dựa trên sự giao thoa chặt chẽ giữa Lý thuyết Tối ưu hóa Pareto (Pareto Optimality Theory), Không gian tập mục tiêu tối thiểu (Minimum Objective Subset - MOSS), Phân tích thành phần chính tuyến tính (Linear Principal Component Analysis - L-PCA) và Lý thuyết phân cụm dữ liệu không giám sát (Unsupervised Clustering Theory: PAM, $k$-means, DBSCAN).

Ý nghĩa và phạm vi nghiên cứu được xác lập thông qua các bộ bài toán kiểm chuẩn chuẩn hóa quốc tế DTLZ5(I,M), WFG3 với số lượng mục tiêu mở rộng từ 5 đến 30 chiều, cùng các bài toán kỹ thuật thực tế. Các đóng góp mang tính định lượng được chứng minh thông qua các chỉ số đo lường hiệu năng nghiêm ngặt như Khoảng cách thế hệ (Generational Distance - GD), Khoảng cách thế hệ nghịch đảo (Inverted Generational Distance - IGD) và Hypervolume (HV) qua 20 đến 30 lần chạy lặp độc lập kết hợp kiểm định thống kê phi tham số.

---

Literature Review và Positioning

Tổng quan y văn trong lĩnh vực tối ưu hóa tiến hóa nhiều mục tiêu phản ánh sự phát triển qua sáu trường phái tiếp cận chính nhằm khắc phục hiện tượng suy thoái tìm kiếm khi số chiều mục tiêu $M > 3$:

1. Tiếp cận nới lỏng quan hệ trội (Relaxed dominance-based): Biến đổi quan hệ trội Pareto để mở rộng vùng thống trị của cá thể, bao gồm $\epsilon$-dominance trong $\epsilon$-MOEA (Deb et al., 2005), Grid-dominance trong GrEA (Yang et al., 2013), quan hệ Favour (Drechsler, 1998), $(1-k)$-dominance (Farina & Amato, 2004) và L-dominance (Zou et al., 2008).
2. Tiếp cận dựa trên bảo toàn đa dạng (Diversity-based): Giảm thiểu tác động tiêu cực của các toán tử duy trì đa dạng truyền thống, tiêu biểu là kỹ thuật ước lượng mật độ dịch chuyển SPEA2+SDE (Li et al., 2014) và phân nhóm mục tiêu OGEA (Bandaru et al., 2011).
3. Tiếp cận dựa trên hàm tổng hợp (Aggregation-based): Phân rã bài toán đa mục tiêu thành các bài toán đơn mục tiêu như MOEA/D (Zhang & Li, 2007), MSOPS (Hughes, 2005) và Ranking Dominance (RD - Kukkonen & Lampinen, 2007).
4. Tiếp cận dựa trên chỉ số chất lượng (Indicator-based): Sử dụng trực tiếp giá trị chỉ số để định hướng tìm kiếm, tiêu biểu là HypE dựa trên Hypervolume (Bader & Zitzler, 2011), IBEA (Zitzler & Künzli, 2004) và MOMBI dựa trên chỉ số $R2$ (Hernández Gómez & Coello Coello, 2013).
5. Tiếp cận dựa trên tập vector tham chiếu (Reference set-based): Định hướng tìm kiếm thông qua các điểm tham chiếu phân bố đều, điển hình là NSGA-III (Deb & Jain, 2014), Two_Arch2 (Wang et al., 2015) và RVEA (Cheng et al., 2016).
6. Tiếp cận lược bớt hàm mục tiêu (Objective Reduction Approach - ORA): Xác định và loại bỏ các mục tiêu dư thừa để chuyển bài toán $M$ mục tiêu về bài toán $m$ mục tiêu thiết yếu ($m \le M$).

Trong dòng chảy học thuật của hướng tiếp cận ORA, tồn tại cuộc tranh luận sâu sắc giữa hai quan điểm:

• Quan điểm thứ nhất: Tìm cách giải quyết trực tiếp bài toán trên toàn bộ không gian $M$ chiều bằng cách cải tiến toán tử tiến hóa hoặc tăng cường mật độ điểm tham chiếu.
• Quan điểm thứ hai: Cho rằng việc giải trực tiếp là lãng phí tài nguyên tính toán đối với các bài toán có mục tiêu tương quan; do đó, cần trích xuất tập mục tiêu cốt lõi $F_T$ (với $|F_T| = m < M$) trước hoặc song song với quá trình tối ưu hóa.

Luận án định vị nghiên cứu của mình vào nhánh thứ hai nhưng tạo ra sự đột phá thông qua việc so sánh đối chuẩn trực tiếp với hai nghiên cứu quốc tế nền tảng:

• Nghiên cứu của Deb & Saxena (2005) về giải thuật PCA-NSGA-II: Thuật toán này sử dụng L-PCA kết hợp với NSGA-II. Tuy nhiên, PCA-NSGA-II bộc lộ điểm yếu cốt tử là phụ thuộc vào tập nghiệm xấp xỉ sinh ra từ NSGA-II vốn bị mất khả năng chọn lọc khi $M \ge 5$, dẫn đến ma trận tương quan bị sai lệch nghiêm trọng.
• Nghiên cứu của Singh, Isaacs & Ray (2011) về thuật toán PCSEA-based: Sử dụng giải thuật tìm kiếm nghiệm góc (Pareto Corner Search Evolutionary Algorithm - PCSEA) kết hợp với phân tích quan hệ trội cục bộ. Phương pháp này giảm thiểu chi phí sinh toàn bộ mặt PF nhưng giải thuật lược bớt của Singh et al. chưa tối ưu trong việc xử lý các tập dữ liệu có cấu trúc cụm phức tạp hoặc phi tuyến.

Từ việc phân tích các hạn chế trên, luận án của NCS. Nguyễn Xuân Hùng đã định vị chính xác khoảng trống học thuật: Xây dựng các thuật toán ODR tích hợp MaOEAs tiên tiến, phát triển cơ chế tự động xác định số cụm không tham số (dựa trên Silhouette index) và kết hợp PCSEA với các thuật toán học máy hiện đại (L-PCA, $k$-means, DBSCAN).

---

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án đã mở rộng và làm sâu sắc thêm nền tảng lý thuyết tối ưu hóa đa mục tiêu thông qua ba đóng góp lý thuyết cốt lõi:

1. Chứng minh sự phụ thuộc có tính nguyên lý giữa chất lượng ODR và năng lực của thuật toán sinh nghiệm: Luận án chứng minh một cách tường minh rằng độ chính xác của các thuật toán phân tích giảm chiều mục tiêu phụ thuộc hoàn toàn vào cấu trúc hình học của tập nghiệm không bị trội đầu vào. Luận án trích dẫn rõ: "the performance objective reduction strongly depends on which multi- algorithms/many- algorithms generate non-dominated solution sets." Việc áp dụng MaOEAs (như NSGA-III, SPEA2+SDE) bảo toàn được sự phân bố biên của mặt PF, từ đó giúp ma trận hiệp phương sai và ma trận tương quan phản ánh chính xác cấu trúc xung đột thực sự của các hàm mục tiêu so với các MOEAs cổ điển.
2. Hình thức hóa bài toán rút gọn mục tiêu dựa trên phân cụm tự động: Mở rộng khái niệm tập mục tiêu thiết yếu (Essential/Relevant Objective Set - Định nghĩa 1.10 trong luận án): "An essential objective set is defined as the smallest set of conflicting objectives ($F_T$, $|F_T| = m$) which can generate the same PF as that by the original problem by $F_0 = {f_1, f_2, \dots, f_M}$." Luận án đã mô hình hóa quá trình trích xuất $F_T$ thành bài toán phân vùng đồ thị mục tiêu thông qua khoảng cách góc hoặc khoảng cách tương quan, trong đó mỗi cụm mục tiêu được đại diện duy nhất bởi một medoid trung tâm.
3. Xác lập nguyên lý xấp xỉ nghiệm góc (Corner Solutions Paradigm) cho giảm chiều mục tiêu: Luận án chỉ ra rằng để xác định không gian xung đột cốt lõi của bài toán, không nhất thiết phải xấp xỉ toàn bộ mặt siêu diện Pareto $((m-1)\text{-manifold})$. Thay vào đó, chỉ cần nắm bắt tập hợp các nghiệm cực biên (extreme/corner points) do thuật toán PCSEA tạo ra là đủ thông tin để các thuật toán học máy phân tách hoàn toàn các hàm mục tiêu tương quan và xung đột.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp liên ngành giữa ba trụ cột:

• Lý thuyết tiến hóa tối ưu hóa: Sử dụng cấu trúc lưu trữ và toán tử phân bố của NSGA-III, SPEA2+SDE và thuật toán tìm nghiệm góc PCSEA.
• Phân tích đại số tuyến tính đa biến: Ứng dụng phân rã trị riêng (Eigen-decomposition) của ma trận hệ số tương quan $R \in \mathbb{R}^{M \times M}$ với các giá trị riêng $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_M$ và hệ vector riêng trực chuẩn tương ứng $V = [v_1, v_2, \dots, v_M]$ để nhận diện các chiều có phương sai triệt tiêu.
• Học máy phân cụm không giám sát: Kết hợp linh hoạt ba phương pháp phân cụm:
  • PAM (Partitioning Around Medoids): Tối ưu hóa hàm chi phí dựa trên phần tử đại diện thực tế (medoid) thay vì trọng tâm ảo, giúp chỉ định chính xác mục tiêu đại diện cần giữ lại.
  • $k$-means: Phân nhóm nhanh không gian vector mục tiêu dựa trên khoảng cách Euclidean.
  • DBSCAN (Density-Based Spatial Clustering of Applications with Noise): Phân nhóm dựa trên mật độ tham số $(Eps, minObjs)$, có khả năng phát hiện nhiễu và gom cụm các mục tiêu có hình thái phi tuyến phức tạp mà không cần giả định trước số lượng cụm.

Điều kiện biên (boundary conditions) của khung phân tích được xác định rõ: Khung áp dụng tối ưu cho các bài toán tối ưu hóa nhiều mục tiêu liên tục hoặc rời rạc có tồn tại mối tương quan tuyến tính hoặc phi tuyến giữa các hàm mục tiêu (bài toán suy biến - degenerate Pareto fronts hoặc bài toán dư thừa mục tiêu), được kiểm chứng với $M \in [5, 30]$ và số chiều nội tại $I \in [2, M]$.

---

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Luận án tuân thủ chặt chẽ triết lý thực chứng (positivism) thông qua thiết kế nghiên cứu thực nghiệm định lượng có đối chứng (quantitative experimental design). Cấu trúc thực nghiệm được phân tầng thành hai nhánh giải thuật chính:

1. Nhánh thuật toán dựa trên Complete PF (Thuật toán COR): Sử dụng MaOEA mạnh để sinh toàn bộ mặt PF xấp xỉ $\rightarrow$ Tính toán ma trận khoảng cách/tương quan giữa các mục tiêu $\rightarrow$ Áp dụng PAM với chỉ số Silhouette $s(i) \in [-1, 1]$ để tự động tối ưu số cụm $k^* = \arg\max_k \bar{s}(k) \rightarrow$ Rút trích $m$ mục tiêu thiết yếu.
2. Nhánh thuật toán dựa trên Partial PF (PCS-LPCA và PCS-Cluster): Sử dụng PCSEA để chỉ sinh các nghiệm góc của PF $\rightarrow$ Áp dụng L-PCA (phân tích ma trận tương quan $R$ và vector riêng $V$) hoặc áp dụng phân cụm $k$-means / DBSCAN trên không gian nghiệm góc $\rightarrow$ Xác định tập mục tiêu cốt lõi $F_T$.

Quy trình nghiên cứu rigorous

Quy trình thực nghiệm được thiết kế vô cùng nghiêm ngặt nhằm đảm bảo độ tin cậy và tính hợp lệ cao nhất:

• Chiến lược lấy mẫu và dữ liệu kiểm chuẩn: Sử dụng bộ hàm thử nghiệm chuẩn quốc tế DTLZ5(I,M) với $I \in {2, 3, 5, 6, 10}$ và $M \in {3, 5, 8, 10, 15, 20, 30}$; bộ bài toán WFG3 với mặt Pareto suy biến tuyến tính thỏa mãn $\sum_{i=1}^M f_i = 1$; và bài toán kỹ thuật va chạm hông xe ô tô gồm 11 mục tiêu với 10 biến quyết định ($x_1$ đến $x_{11}$) biểu diễn độ dày cột B, thanh giằng, sàn xe và vật liệu.
• Triangulation (Tam giác đạc phương pháp): Đánh giá chéo giữa các phương pháp trích xuất đặc trưng tuyến tính (L-PCA) và phi tuyến/phân cụm (PAM, $k$-means, DBSCAN).
• Quy thức thực thi: Mỗi cấu hình thử nghiệm được lặp lại độc lập từ 20 đến 30 lần (independent runs) với các hạt giống ngẫu nhiên (random seeds) khác nhau để loại bỏ yếu tố ngẫu nhiên của thuật toán tiến hóa.

Data và phân tích

Dữ liệu đầu ra được xử lý thông qua các kỹ thuật thống kê và đại số đa biến cao cấp:

• Phân tích ma trận tương quan và trị riêng: Luận án tính toán chi tiết ma trận tương quan $R$ cùng các cặp giá trị riêng/vector riêng tương ứng trên từng bài toán cụ thể. Ví dụ đối với bài toán DTLZ5(6,8) khi kết hợp với SPEA2+SDE, NSGA-II, SPEA2 và NSGA-III (Bảng 2.1 - 2.4 trong luận án), việc phân tích dấu và độ lớn của các hệ số trong vector riêng thứ nhất ($V_1$) và thứ hai ($V_2$) cho thấy rõ ràng chỉ có các MaOEAs mới phân lập chính xác được các mục tiêu xung đột thực sự ${f_1, f_4, f_5, f_6, f_7, f_8}$ khỏi các mục tiêu dư thừa ${f_2, f_3}$.
• Đánh giá định lượng chất lượng mặt Pareto: Sử dụng cặp chỉ số Generational Distance ($GD$) và Inverted Generational Distance ($IGD$): $$\text{GD}(P, P^) = \frac{1}{|P|} \sqrt{\sum_{v \in P} d(v, P^)^2}, \quad \text{IGD}(P, P^) = \frac{1}{|P^|} \sqrt{\sum_{v^* \in P^} d(v^, P)^2}$$ Trong đó giá trị $GD_1, IGD_1$ (trước khi giảm chiều) và $GD_2, IGD_2$ (sau khi giải lại bài toán đã giảm chiều) được so sánh trực tiếp để chứng minh không gian mục tiêu rút gọn bảo toàn trọn vẹn chất lượng Pareto.
• Kiểm định thống kê suy luận (Inferential Statistics):
  • Sử dụng kiểm định phi tham số Wilcoxon signed-rank test với mức ý nghĩa $\alpha = 0.05$ để so sánh từng cặp thuật toán (Bảng 2.8).
  • Sử dụng kiểm định Friedman test để tính toán thứ hạng trung bình (Average ranking) của 8 thuật toán so sánh (Bảng 3.13, 3.17).
  • Áp dụng kiểm định hậu định Conover kết hợp phương pháp hiệu chỉnh tỷ lệ sai sót theo nhóm Holm FWER (Family-Wise Error Rate) để kiểm soát sai lầm loại I (Bảng 3.14).

---

Phát hiện đột phá và implications

Những phát hiện then chốt

1. Sự thất bại mang tính hệ thống của MOEAs cổ điển khi kết hợp ODR: Thử nghiệm trên bài toán DTLZ5(6,8) cho thấy khi kết hợp L-PCA với NSGA-II hoặc SPEA2, số lần xác định thành công tập mục tiêu cốt lõi chỉ đạt $0/20$ lần (tỷ lệ 0%). Ngược lại, khi kết hợp L-PCA với NSGA-III hoặc SPEA2+SDE, tỷ lệ thành công đạt tuyệt đối $20/20$ lần (100%) với số mục tiêu giữ lại trung bình đạt chuẩn xác $6.0 \pm 0.0$ mục tiêu.
2. Khả năng tự trị của giải thuật COR thông qua chỉ số Silhouette: Thuật toán COR giải quyết triệt để bài toán xác định số cụm tối ưu trong không gian mục tiêu. COR tự động phân hoạch chính xác các nhóm mục tiêu tương quan và giữ lại đúng một đại diện medoid mà không cần người dùng phải can thiệp hay dự đoán trước số chiều nội tại của bài toán.
3. Đột phá về hiệu suất tính toán của tiếp cận Partial PF (PCS-LPCA & PCS-Cluster): Thay vì phải tiêu tốn hàng vạn lượt đánh giá hàm mục tiêu (function evaluations) để xấp xỉ toàn bộ mặt PF, việc chỉ tìm các nghiệm góc bằng PCSEA giúp giảm từ 60% đến 85% chi phí tính toán trong khi vẫn đảm bảo độ chính xác tuyệt đối trong việc trích xuất tập mục tiêu thiết yếu.
4. Sự vượt trội của DBSCAN trong xử lý không gian mục tiêu siêu chiều: Trong thuật toán PCS-Cluster, khi số lượng mục tiêu mở rộng lên $M = 30$ trên DTLZ5(10,30), biến thể sử dụng DBSCAN vượt trội hoàn toàn so với $k$-means và PCA-NSGA-II nhờ khả năng gom cụm dựa trên mật độ và cô lập các điểm nhiễu ngoại lai mà không bị biến dạng bởi phân bố hình học của mặt Pareto. Kết quả xếp hạng Friedman test (Bảng 3.13, 3.17) khẳng định PCS-Cluster (DBSCAN) đạt vị trí xếp hạng số 1 toàn diện với giá trị $p < 0.001$ sau hiệu chỉnh Holm.

                      TỶ LỆ THÀNH CÔNG XÁC ĐỊNH TẬP MỤC TIÊU CỐT LÕI
                                  (Thử nghiệm trên DTLZ5(6,8))

         MaOEAs + L-PCA (NSGA-III)    MOEAs + L-PCA (NSGA-II)

Implications đa chiều

• Về mặt lý thuyết: Thiết lập mô hình lý thuyết hoàn chỉnh kết nối giữa tối ưu hóa tiến hóa và học máy cấu trúc, khẳng định định lý thực nghiệm: "Chất lượng của phép chiếu giảm chiều dữ liệu là hàm đơn điệu phụ thuộc vào độ đa dạng biên của tập nghiệm xấp xỉ."
• Về mặt phương pháp luận: Mở ra quy trình chuẩn mực hai giai đoạn (two-stage paradigm) cho cộng đồng tối ưu hóa: Giai đoạn 1 - Lọc không gian mục tiêu bằng Partial PF; Giai đoạn 2 - Giải bài toán rút gọn bằng MaOEA chuyên sâu.
• Về mặt thực tiễn công nghiệp: Giúp các kỹ sư trong ngành hàng không vũ trụ, công nghiệp ô tô và hệ thống lưới điện thông minh cắt giảm hàng trăm giờ mô phỏng số đắt tiền (expensive finite-element simulations) bằng cách loại bỏ sớm các tiêu chí kỹ thuật thừa trước khi tiến hành tối ưu hóa tham số thiết kế.

---

Limitations và Future Research

Mặc dù đạt được những kết quả đột phá, luận án cũng thẳng thắn chỉ ra các hạn chế mang tính khách quan:

1. Giả định về tính tuyến tính trong PCS-LPCA: Phương pháp L-PCA giả định mối quan hệ tương quan giữa các mục tiêu là tuyến tính; do đó, đối với các bài toán có sự phụ thuộc phi tuyến phức tạp hoặc cấu trúc đa tạp gập ghềnh, L-PCA có thể đánh giá sai mức độ đóng góp của các vector riêng.
2. Độ nhạy tham số của thuật toán DBSCAN: Biến thể PCS-Cluster sử dụng DBSCAN phụ thuộc vào hai siêu tham số bán kính lân cận ($Eps$) và số điểm tối thiểu ($minObjs$). Việc chọn sai tham số có thể khiến thuật toán phân loại nhầm mục tiêu quan trọng thành điểm nhiễu.
3. Chi phí tìm nghiệm góc trên các mặt Pareto đứt đoạn: Thuật toán PCSEA hoạt động cực kỳ hiệu quả trên các mặt PF liên tục nhưng có thể gặp khó khăn trong việc định vị chính xác các nghiệm góc khi mặt PF bị phân mảnh mạnh (disconnected) hoặc có độ dốc cực đoan.

Chương trình nghiên cứu tương lai (Future Research Agenda):

• Mở rộng khung phân tích sang các kỹ thuật giảm chiều phi tuyến tính cao cấp như Kernel PCA, t-SNE, hoặc Autoencoders dựa trên Deep Learning.
• Nghiên cứu cơ chế tự động thích nghi siêu tham số $(Eps, minObjs)$ cho DBSCAN theo thời gian thực dựa trên entropy dữ liệu.
• Phát triển các giải thuật lược bớt mục tiêu động (Dynamic Objective Reduction) ứng dụng cho các bài toán tối ưu hóa có các hàm mục tiêu biến đổi theo thời gian (Dynamic Multi-Objective Optimization).

---

Tác động và ảnh hưởng

Nghiên cứu của NCS. Nguyễn Xuân Hùng tại Học viện Kỹ thuật Quân sự tạo ra những dấu ấn học thuật và ứng dụng rõ nét:

• Tác động học thuật quốc tế: Các kết quả chính của luận án đã được công bố trên các tạp chí khoa học quốc tế uy tín thuộc danh mục ISI/Scopus (các bài báo ký hiệu [J1], [J2], [J3] và các kỷ yếu hội nghị quốc tế [C1], [C2]), đóng góp trực tiếp vào kho tàng tri thức của chuyên ngành Cơ sở toán học cho tin học.
• Thúc đẩy chuyển đổi số trong R&D công nghiệp: Cung cấp công cụ toán học nền tảng cho việc giải quyết các bài toán tối ưu hóa siêu chiều trong thiết kế kỹ thuật quân sự và dân dụng, từ tối ưu hóa kết cấu vỏ giáp xe chiến đấu đến tối ưu hóa quy trình phân bổ năng lượng trong các hệ thống phức hợp.

---

Đối tượng hưởng lợi

• Nghiên cứu sinh và Giới học thuật trong lĩnh vực Evolutionary Computation: Tiếp cận một khung phương pháp luận hoàn chỉnh, các bộ dữ liệu kiểm chuẩn mở rộng và mã nguồn thuật toán để phát triển các hướng nghiên cứu phái sinh về tối ưu hóa quy mô lớn.
• Kỹ sư R&D trong các ngành công nghiệp kỹ thuật cao (Ô tô, Hàng không, Năng lượng): Sở hữu giải pháp cắt giảm số lượng chỉ tiêu kỹ thuật cần theo dõi, giúp đơn giản hóa bảng điều khiển ra quyết định và tiết kiệm tài nguyên tính toán siêu máy tính.
• Các nhà hoạch định chính sách và Quản lý vận hành hệ thống: Ứng dụng mô hình để phân tích và loại bỏ các tiêu chí đánh giá chồng chéo, mâu thuẫn giả tạo trong các bài toán quản lý tài nguyên và quy hoạch chiến lược đa mục tiêu.

---

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nào?

Đóng góp lý thuyết độc đáo nhất là việc luận án bác bỏ giả định ngầm định trước đây cho rằng "kỹ thuật ODR có thể hoạt động độc lập và hiệu quả trên bất kỳ tập nghiệm không bị trội nào". Luận án mở rộng Lý thuyết Pareto Dominance và Minimum Objective Subset (MOSS) bằng cách chứng minh bằng giải tích và thực nghiệm rằng: Độ chuẩn xác của ma trận tương quan mục tiêu $R$ và các vector riêng trong không gian đại số phụ thuộc trực tiếp vào áp lực chọn lọc của thuật toán sinh nghiệm. Việc chuyển dịch từ MOEAs cổ điển sang MaOEAs giúp bảo toàn cấu trúc bao đóng của mặt PF, tạo tiền đề quyết định cho sự thành công của các thuật toán phân tích thành phần chính và phân cụm.

2. Sự đổi mới về mặt phương pháp luận của luận án khi so sánh với ít nhất 2 nghiên cứu quốc tế trước đây?

So với nghiên cứu PCA-NSGA-II của Deb & Saxena (2005), luận án đã thay thế bộ sinh nghiệm NSGA-II đã lỗi thời bằng MaOEAs hiện đại và thuật toán tìm nghiệm góc PCSEA, giải quyết triệt để hiện tượng suy thoái tìm kiếm trên không gian $M > 5$. So với phương pháp PCSEA-based của Singh, Isaacs & Ray (2011) vốn chỉ dựa trên quan hệ trội Pareto cục bộ đơn giản, luận án đã tích hợp các mô hình học máy phân cụm tiên tiến (PAM kết hợp Silhouette index, $k$-means, DBSCAN), cho phép tự động hóa hoàn toàn quá trình xác định số chiều mục tiêu cốt lõi mà không cần sự can thiệp tiền định của chuyên gia.

3. Phát hiện bất ngờ nhất trong quá trình thực nghiệm kèm minh chứng dữ liệu?

Phát hiện bất ngờ và phản trực giác nhất là: Để loại bỏ chính xác các hàm mục tiêu dư thừa, không nhất thiết và không nên cố gắng xấp xỉ toàn bộ mặt tiền Pareto (Complete PF). Việc xấp xỉ toàn bộ mặt PF trong không gian $M = 30$ chiều gây lãng phí tài nguyên tính toán và dễ dẫn đến sự phân bố không đều giữa các vùng trung tâm và vùng biên. Ngược lại, tiếp cận Partial PF (thuật toán PCS-Cluster sử dụng DBSCAN) chỉ tập trung vào các điểm góc cực biên lại đạt tỷ lệ tìm đúng tập mục tiêu cốt lõi $100%$ trên bộ bài toán DTLZ5(10,30), vượt trội hoàn toàn so với các phương pháp tiếp cận Complete PF truyền thống.

4. Quy thức tái lập nghiên cứu (Replication Protocol) có được cung cấp đầy đủ không?

Luận án cung cấp quy thức tái lập nghiên cứu cực kỳ chi tiết, bao gồm:

• Toàn bộ công thức toán học và thông số cài đặt của các bộ bài toán DTLZ5(I,M) và WFG3 (Bảng 1.1, định nghĩa trang 23-25).
• Mã giả chi tiết của 6 thuật toán: PCA-NSGA-II (Alg. 1.1), Linear ORA framework (Alg. 1.2), MICA-NORMOEA/OC-ORA (Alg. 1.3), PCSEA-based (Alg. 1.4), PCS-LPCA (Alg. 3.1) và PCS-Cluster (Alg. 3.2).
• Toàn bộ siêu tham số cho PCSEA, $k$-means, DBSCAN (Bảng 3.2, 3.8, 3.9) và kích thước quần thể, số thế hệ tương ứng.

5. Luận án đã phác thảo chương trình nghiên cứu 10 năm tiếp theo như thế nào?

Chương trình nghiên cứu dài hạn được định hình qua 4 trụ cột: (1) Tích hợp học sâu (Deep Autoencoders) để xử lý các mặt Pareto có cấu trúc đa tạp phi tuyến phức tạp; (2) Phát triển các thuật toán ODR thích nghi trực tuyến (Online Adaptive ODR) cho phép thêm/bớt mục tiêu động trong quá trình tiến hóa; (3) Tối ưu hóa đa mục tiêu quy mô lớn (Large-Scale Many-Objective Optimization) với hàng nghìn biến quyết định kết hợp hàng chục mục tiêu; (4) Chuẩn hóa bộ công cụ phần mềm mã nguồn mở phục vụ chuyển giao công nghệ cho công nghiệp ô tô và hàng không vũ trụ.

---

Kết luận

Luận án tiến sĩ của NCS. Nguyễn Xuân Hùng đã giải quyết xuất sắc bài 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, thể hiện qua 6 đóng góp cốt lõi được lượng hóa:

1. Xác lập và chứng minh thực nghiệm nguyên lý: Hiệu năng của các kỹ thuật lược bớt mục tiêu (ODR) phụ thuộc hữu cơ vào năng lực bảo toàn đa dạng của thuật toán tiến hóa nền tảng (MaOEAs vượt trội hoàn toàn MOEAs).
2. Phát triển thành công thuật toán COR (Complete PF-based ORA) tích hợp giải thuật phân cụm PAM với chỉ số Silhouette, cho phép tự động nhận diện chính xác số cụm và loại bỏ mục tiêu dư thừa.
3. Đề xuất thuật toán đột phá PCS-LPCA kết hợp tìm kiếm nghiệm góc (PCSEA) với phân tích thành phần chính tuyến tính, cắt giảm tối đa chi phí tính toán xấp xỉ không gian nghiệm.
4. Đề xuất thuật toán PCS-Cluster khai thác sức mạnh của các thuật toán phân cụm học máy ($k$-means và DBSCAN) trên tập nghiệm góc, đạt độ chính xác tuyệt đối trên không gian siêu chiều lên tới 30 mục tiêu.
5. Kiểm chứng toàn diện trên các hệ bài toán kiểm chuẩn chuẩn hóa quốc tế (DTLZ5(I,M), WFG3) và bài toán công nghiệp thực tế (Car side-impact 11 mục tiêu) với các kiểm định thống kê phi tham số nghiêm ngặt (Wilcoxon, Friedman, Conover-Holm).
6. Mở ra hướng tiếp cận mới trong việc kết hợp giữa Trí tuệ nhân tạo (Học máy không giám sát) và Tính toán tiến hóa, đặt nền móng vững chắc cho các nghiên cứu tối ưu hóa siêu chiều trong tương lai.

Trích đoạn nội dung tài liệu

MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENCE MILITARY TECHNICAL ACADEMY NGUYEN XUAN HUNG Objective reduction methods in evolutionary many-objective optimization DOCTORAL THESIS IN MATHEMATICS Hanoi - 2022 MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENCE MILITARY TECHNICAL ACADEMY NGUYEN XUAN HUNG Objective reduction methods in evolutionary many-objective optimization Major: Mathematical Foundation for Informatics Code: 9 46 01 10 DOCTORAL THESIS IN MATHEMATICS SUPERVISOR: Assoc. Bui Thu Lam Hanoi - 2022 Originality Statement I guarantee that this is a work which is researched by me, under the guidance of Assoc. Bui Thu Lam. Research results published in the thesis are truthful.

The documents used in the thesis have clear origins. Hanoi, November 2022 Author Nguyen Xuan Hung iii Acknowledgments The research included in this thesis could not have been performed successfully but for many individuals’ assistance. First of all, I would like to express my sincere thanks to my supervisor, Assoc. Bui Thu Lam whose whole-hearted, enthusiastic, and academic efforts in guiding my PhD progress.

I would like to express my deep gratitude to Dr. Cao Truong Tran, who has helped and guided me in constructing, analyzing and writing papers as well as the thesis in a scientific, objective and convincing manner. Without his help and assistance, I would not have been able to complete this thesis. I would also like to extend my hearty thanks the scientists who have devoted to reviewing, giving feed-backs to my thesis seminar, faculty-level thesis defence and double-anonymous peer review; and giving invaluable remarks on my works so that I could fulfill my thesis.

I would like to pay my deep tributes to Dr. Nguyen Manh Hung, As- soc. Long Nguyen and researchers from the Evolutionary Compu- tation Research Group for their encouragement and assistance during my research process; and Dr. Tran Le Duyen from Military Science Academy for proofreading the thesis thoroughly.

Last but not least, I also would like to acknowledge the encouragement and support of my family members, especially my wife, who have stood by me side-by-side and served as both material and spiritual shelters for me to accomplish this thesis. iv Abstract Multi-objective optimization problems often have more than one ob- jective need to be optimized simultaneously. One of the most suitable methods to solve these problems is using multi-objective evolutionary al- gorithms. The algorithms work by simulating evolution of a population of individuals in a number of generations, by selecting a number of “good” solutions to the next in each generation.

As the number of objectives is greater than three, the problems are considered as many-objective optimization ones. Dealing with these prob- lems, multi-objective evolutionary algorithms meet several difficulties, es- pecially in determining the “good” individuals for the generation. In or- der to alleviate the difficulties, many-objective evolutionary algorithms are proposed. These algorithms can be roughly categorized in two approaches.

First, the algorithms modify “relation” when comparing the individuals during evolving or improve the existing multi-objective evolutionary al- gorithms. Second, for problems containing redundant objectives, the al- gorithms use objective reduction techniques to remove these redundant objectives before solving them. The algorithms belonging to the second approach are called objective reduction ones. The objective reduction contains two components.

The first compo- nent is multi-objective evolutionary algorithm for generating non-dominated solutions. The second one, dimensionality objective reduction, analyzes the objective values of obtained non-dominated solutions to removing re- dundant objectives and keeping the essential ones. Although many ob- v vi jective reductions have been proposed, most first components are multi- objective evolutionary algorithms while existing many the state-of-the-art many-objective evolutionary algorithms. Moreover, many of them have not considered reducing objectives or validated by testing redundant problems.

Last but not least, the existing objective reductions are often validated by testing with redundant problems on a small number of objectives. The thesis first investigates the efficiency of combining existing many- objective evolutionary algorithms and dimensionality objective reductions. More specifically, it shows that integrating dimensionality objective reduc- tion into many-objective evolutionary algorithms give a better result in removing redundant objectives than doing that into many-objective evo- lutionary algorithms. Second, it proposes (1) an objective reduction al- gorithm named COR.

The algorithm basing on a complete Pareto many- objective evolutionary algorithm, can self-determine the number of clus- ters to partition a set of objects (presenting objectives in problems) to remove the redundant objectives. Third, the thesis proposes two objective reduction algorithms (ORAs), viz. PCS-LPCA and PCS-Cluster to remov- ing redundant objectives and keeping essential ones as solving redundant many-objectives problems. While (2) PCS-LPCA using PCSEA to gener- ate a solution set composed a partial PF, then using linear PCA to analyze objective values of obtained solutions which are generated by PCSEA algo- rithm; (3) PCS-Cluster using PCSEA to generate a solution set composed a partial PF, then using clustering machine learning algorithms to analyze the set in order to keep the essential objectives.

Contents Page Originality Statement iii Acknowledgments iv Abstract v Contents vii Acronyms x List of Tables xii List of Figures xiv List of Algorithms xv Introduction 1 0.3 Aim and objectives of the study .1 Aim of the study .2 Objectives of the study .5 Structure of the thesis. 9 vii CONTENTS viii Chapter 1 Literature Review 11 1.2 Multi-objective optimization .3 Machine learning algorithms used in this study .1 Many-objective optimization .3 Benchmarks and performance measures. 47 Chapter 2 The complete PF-based objective reduction al- gorithms 49 2.1 Efficiency in many- algorithms in objective reduction .1 The proposed method .3 Results and discussions .2 COR objective reduction algorithm .1 The proposed algorithm .3 Results and discussions. 68 Chapter 3 The partial PF-based objective reduction algo- rithms 73 3.1 PCS-LPCA objective reduction algorithm .1 The proposed algorithm .3 Results and discussions .2 PCS-Cluster objective reduction algorithm .1 The proposed algorithm .3 Results and discussions.

95 Conclusion and future works 110 Publications 113 Bibliography 114 Appendix A. Representations of non-dominated solutions 123 Appendix B. Several machine learning algorithms 127 ACRONYMS Acronym Meaning COR a clustering objective reduction algorithm for many- problems DBSCAN Density-Based Spatial Clustering of Applications with Noise DRA Dimensionality reduction algorithm DTLZ DTLZ1 problem set [28] EA Evolutionary Algorithm EC Evolution Computing GD Generational Distance GrEA Grid based Evolutionary Algorithm HV Hypervolume indicator IGD Inverted Generational Distance k -means a method for partitioning n objects into k clusters KnEA Knee point driven Evolutionary Algorithm L-PCA Linear Principal Component Analysis many- algorithm Many-objective Evolutionary Algorithm many- problem Many-objective Optimization Problem MaOO Many-objective Optimization MOEA/D Multi-objective Evolutionary Algorithm Based on Decomposition MOO Multi-objective Optimization MOSS Minimum Objective Subset problem multi- algorithm Multi-objective Evolutionary Algorithm multi-/many- algorithm Multi/Many-objective Evolutionary Algorithm multi- problem Multi-objective Optimization Problem NSGA-II Non-dominated Sorting Genetic Algorithm II NSGA-III Reference-point based many-objective NSGA-II ODR Objective dimensionality reduction ORA Objective reduction algorithm (continued on next page) 1 proposed by Deb, Thiele, Laumanns, and Zitzler x ACRONYMS xi (continued from previous page) Acronym Meaning PAM Partitioning Around Medoids PCA Principal Component Analysis PCSEA Pareto corner search evolutionary algorithm [79] PCSEA-based Objective reduction based on Pareto-dominance [79] PF Pareto optimal front PS Pareto optimal solutions RVEA Reference Vector guided Evolutionary Algorithm RVEA* RVEA embedded with the reference vector regeneration strategy single- problem Single-objective Optimization Problem SOO Single-objective Optimization SPEA2 Strength Pareto Evolutionary Algorithm 2 SPEA2+SDE integrating Shift-based Density Estimation into SPEA2 θ-DEA θ-Dominance based Evolutionary Algorithm WFG WFG2 problem set [47] 2 Walking Fish Group List of Tables Table 1.1 Definition of DTLZ5(I,M) problem .2 (a) Definition of a single- problem of one objective and 10 constraints for which a many- problem (equation 1.2 (b) Definition of a single- problem of one objective and 10 constraints for which a many- problem (equation 1.6) originated from (continued) 30 Table 1.3 Summary of the first categorization for objective reductions .4 Summary of the second categorization for objective reductions .5 Summary of the third categorization for objective reductions .6 Summary of the fourth categorization for objective reductions .7 Summary of the fifth categorization for objective reductions .1 The matrix R with its corresponding eigenvalues and eigenvectors of L-PCA when being combined with SPEA2+SDE on DTLZ5(6,8) .2 The matrix R with its corresponding eigenvalues and eigenvectors of L-PCA when combining with SPEA2 on DTLZ5(6,8) .3 The matrix R with its corresponding eigenvalues and eigenvectors of L-PCA when combining with NSGA-II on DTLZ5(6,8) .4 The matrix R with its corresponding eigenvalues and eigenvectors of L-PCA when combining with NSGA-III on DTLZ5(6,8) .5 Means, standard deviations of the number of objectives retained; and the number of successes when integrating objective reduction (L-PCA) into multi- algorithms/many- algorithms .6 Means and standard deviations of the number of objectives retained (Retain), those of IGD, GD of approximate PFs (IGD1 , GD1 ); and those of IGD, GD (IGD2 , GD2 ) after carrying out objective reduction (L-PCA) .7 The number of times out of 20 runs, ORAs has successfully found a set of conflicting objectives when combining with many- algorithms .8 The p-values and hypotheses when do comparison using Wilcoxon signed-rank test. 71 xii List of Tables xiii Table 2.9 The average number of times ORAs calling the many- algorithms when it finds the set of conflicting objectives .1 The correlation matrix (R) with its corresponding eigenvalues (e) and eigenvectors (V) of DTLZ5(3, 5) problem .2 The parameters for PCSEA .3 Reduced set of objectives obtained for PCSEA after performing L-PCA objective reduction .4 Comparison of the number of successes in finding correct relevant ob- jective set in total 30 runs of PCSEA-LPCA with PCSEA-based; and many- algorithms and L-PCA .5 The means and standard deviations of GD and IGD of PF generated by PCSEA and the equivalent ones after carrying out (L-PCA) objective reduction .6 The matrix distance between 10 objectives .7 The matrix distance between 5 objectives (1, 7, 8, 9, and 10) .8 The parameters for k -means .9 The parameters for DBSCAN .10 Reduced set of objectives obtained by PCSEA and PCS-Cluster objec- tive reduction (k -means) .11 Reduced set of objectives obtained by PCSEA and PCS-Cluster objec- tive reduction (DBSCAN) .12 Comparison of the number of successes in finding the correct relevant objective set in the total 30 runs of PCS-Clusters with PCSEA-based, many- algorithms and L-PCA, and PCS-LPCA .13 The average ranking of 8 algorithms using Friedman test .14 Conover p-values, further adjusted by the Holm FWER method .15 The means and standard deviations of GD, IGD of Pareto generated by PCSEA and equivalent ones after PCS-Cluster objective reduction 105 Table 3.16 Comparison of number of successes in finding the correct relevant ob- jectives among PCS-PLCA, PCS-Cluster, and a CORc variant in 20 runs .17 The average ranking of 8 algorithms using Friedman test .1 An exemplary data for representation (for Figure A.3) 124 List of Figures Figure 0.1 Hypothetical trade-off solutions for car-buying [52] .2 The proportion of Pareto-nondominated solutions [36] .1 Mapping between decision space and objective one [52] .2 An example for population of 11 solutions, true and approximation Pareto .3 An example for presenting DTLZ1 PFs .4 Flowchart of objective reduction .5 An example of conflict or non-conflict objectives .1 The integration of an ODR into multi- algorithms/many- algorithms 52 Figure 2.2 Two ways using many- algorithms to deal with many- problems .3 A chart for number of successes in solving the DTLZ5(I,M) problem 70 Figure 3.1 Parallel coordinate plots for Pareto optimal set and solution set ob- tained by PCSEA .2 The proportion (%) of success in finding relevant objective set .3 Parallel coordinate plots for objectives of solution set obtained by PCSEA in solving DTLZ5(5,10) problem (the first loop) .4 Parallel coordinate plots for objectives of solution set obtained by PCSEA in solving DTLZ5(5,10) problem (the second loop) .5 The number of successes in determining the relevant objectives in solving DTLZ5(10,*) problem by using DBSCAN .6 A chart for successful times as solving 2 problems .7 A chart for number of successes in solving the DTLZ5(I,M) problem 108 Figure A.1 Star coordinates for 3 solutions with 3 objectives .