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 .