Luận án Objective reduction methods in evolutionary many-objective optimization

e 8 cases of results in Table 3.12, the Friedman test is utilized to detect statistical differences among the results and Holm post-hoc analysis is also applied, to find out which algorithms are distinc- tive among the comparisons performed. The null hypothesis is that the performances of all algorithms are similar to the significant level at 0.05, and the alternative hypothesis is that the performance of at least two of them are not the same. Friedman chi-squared statistics is 160.263, with 7 degrees of freedom at the significant level 0.05, the p-value for Fried- man is 2.824E-31. This p-value is for rejection of null hypothesis, when all algorithms are from the same distribution, i.e., there is no difference in algorithms. The alternate hypothesis is that one or more of the algo- rithms is different. Besides, Table 3.13 uncaps the average ranking of 8 algorithms. Generally, the smaller the rank is, the better the performance 3.2. PCS-Cluster objective reduction algorithm 103 of the algorithm does. Table 3.13: The average ranking of 8 algorithms using Friedman test Algorithm Average rank 1 PCS-Cluster(DBSCAN) 2.4022 2 PCS-LPCA 2.7283 3 PCS-Cluster(k -means) 3.3587 4 θ-DEA /L-PCA 3.8370 5 PCSEA-based 5.1196 6 RVEA* /L-PCA 5.3913 7 NSGA-III /L-PCA 6.1087 8 GrEA /L-PCA 7.0543 The p-value is at or below the respectable critical threshold of 0.05, hence post-hoc pairwise multiple comparison test is conducted to discern which of the pairs have significant differences. The thesis uses Conover method, and the p-value is adjusted according to the family-wide error rate (FWER) procedure of Holm. Table 3.14 releases post-hoc p-values of all possible pairs of algorithms. The table is compactly represented as a lower triangular matrix. Each numerical entry is the p-value of row/column pair, i.e., the null hypotheses that the algorithm represented by a particular column name is different from that of a particular row name. 3.2. PCS-Cluster objective reduction algorithm 104 Table 3.14: Conover p-values, further adjusted by the Holm FWER method P C S E A -b as ed G rE A /L -P C A N SG A -I II /L -P C A R V E A */ L -P C A θ- D E A /L -P C A P C S -L P C A P C S- C lu st er (k -m ea ns ) GrEA/L-PCA 4.37E-28 NSGA-III/L-PCA 5.28E-09 1.94E-08 RVEA*/L-PCA 8.10E-02 6.23E-22 2.78E-05 θ-DEA/L-PCA 3.99E-14 1.92E-59 3.90E-36 1.35E-19 PCS-LPCA 4.73E-39 1.36E-85 2.04E-63 9.01E-46 5.73E-11 PCS-Cluster(k-means) 4.29E-24 5.34E-71 6.80E-48 2.25E-30 6.73E-03 2.46E-04 PCS-Cluster(DBSCAN) 4.20E-47 8.38E-93 3.06E-71 8.03E-54 4.05E-17 7.29E-02 1.53E-08 From the Table 3.14, if the p-value is at or below the critical threshold of 0.05, two algorithms, which create the cell containing that p-value, have significant differences. Otherwise, there is no discrepancy between the results of those two algorithms. It indicates that most of the pairs of the algorithms are significantly different in statistical sense except for the two pairs of algorithms; namely, the pair of PCSEA-based and RVEA*/L-PCA and the pair of PCSEA-Cluster(DBSCAN) and PCS-LPCA. According to Table 3.14 and Table 3.13, it can be concluded that the results of the two algorithms PCS-Cluster(DBSCAN) and PCS-LPCA are the best with no significant difference between them in statistical sense. Besides considering the reduced objective set as in Table 3.12, Ta- ble 3.15 examines the quality of solution set obtained by PCSEA and its re- duction by using PCS-Cluster objective reduction. The 4th and 7th columns depict the GD and IGD values of solution set generated by PCSEA. The objectives of this set are then reduced by using PCS-Cluster objective re- duction. Its GD values are shown in 5th and 6th columns of the table for two kinds of clustering algorithms, namely k -means and DBSCAN. Sim- 3.2. PCS-Cluster objective reduction algorithm 105 Table 3.15: The means and standard deviations of GD, IGD of Pareto generated by PCSEA and equivalent ones after PCS-Cluster objective reduction Problems I M GD GD Reduction (k-means) GD Reduction (DBSCAN) IGD IGD Reduction (k-means) IGD Reduction (DBSCAN) DTLZ5 5 10 1.8560E-02 ±5.414E-04 1.9590E-04 ±8.091E-08 1.9590E-04 ±8.091E-08 5.3196E-01 ±6.930E-04 9.6453E-02 ±4.950E-04 9.6453E-02 ±4.950E-04 DTLZ5 5 20 1.3141E-02 ±2.424E-04 2.0358E-06 ±1.294E-11 2.0358E-06 ±1.294E-11 5.3473E-01 ±2.338E-04 3.1976E-03 ±3.491E-07 3.1976E-03 ±3.491E-07 DTLZ5 5 30 1.9509E-02 ±3.738E-04 3.3553E-07 ±3.514E-14 3.3553E-07 ±3.514E-14 5.0159E-01 ±3.723E-04 7.7209E-05 ±4.191E-10 7.7209E-05 ±4.191E-10 DTLZ5 5 40 1.9132E-02 ±2.489E-04 1.4233E-08 ±4.416E-17 1.4233E-08 ±4.416E-17 4.9583E-01 ±4.937E-04 2.1558E-06 ±3.851E-13 2.1558E-06 ±3.851E-13 DTLZ5 5 50 1.3947E-02 ±3.850E-04 3.5209E-10 ±5.611E-20 3.5209E-10 ±5.611E-20 4.9528E-01 ±4.338E-04 7.0147E-08 ±5.430E-16 7.0147E-08 ±5.430E-16 DTLZ5 5 60 1.5540E-02 ±2.306E-04 1.3535E-11 ±3.279E-23 1.3535E-11 ±3.279E-23 4.9105E-01 ±2.394E-04 2.2627E-09 ±2.981E-19 2.2627E-09 ±2.981E-19 DTLZ5 5 70 1.5987E+00 ±2.229E+01 4.4342E-13 ±6.708E-26 4.4342E-13 ±6.708E-26 4.9150E-01 ±4.274E-04 6.7522E-11 ±3.462E-22 6.7522E-11 ±3.462E-22 DTLZ5 5 80 2.5527E+00 ±3.225E+01 1.1147E-14 ±6.174E-29 1.1147E-14 ±6.174E-29 5.0591E-01 ±1.126E-03 2.3682E-12 ±4.213E-25 2.3682E-12 ±4.213E-25 DTLZ5 5 90 4.6240E+00 ±4.968E+01 2.7229E-16 ±8.073E-32 2.7229E-16 ±8.073E-32 5.1762E-01 ±1.074E-03 7.6175E-14 ±4.243E-28 7.6175E-14 ±4.243E-28 DTLZ5 5 100 6.1788E+00 ±5.693E+01 1.2722E-17 ±7.631E-35 1.2722E-17 ±7.631E-35 5.0527E-01 ±8.938E-04 2.2514E-15 ±4.108E-31 2.2514E-15 ±4.108E-31 DTLZ5 10 20 1.9168E-01 ±7.352E-03 2.7268E-04 ±3.253E-07 2.7264E-04 ±3.253E-07 6.8101E-01 ±6.181E-04 6.0656E-02 ±9.914E-05 6.0056E-02 ±1.086E-04 DTLZ5 10 30 1.6408E-01 ±4.987E-03 1.2123E-05 ±1.246E-10 1.1963E-05 ±1.261E-10 6.6672E-01 ±5.726E-04 1.4205E-03 ±2.638E-07 1.3809E-03 ±2.333E-07 DTLZ5 10 40 1.8570E-01 ±6.262E-03 4.8331E-07 ±2.396E-13 4.8331E-07 ±2.396E-13 6.6427E-01 ±2.607E-04 4.5941E-05 ±1.432E-10 4.5941E-05 ±1.432E-10 DTLZ5 10 50 2.3348E-01 ±1.137E-02 1.2627E-08 ±1.132E-16 1.2627E-08 ±1.132E-16 6.6860E-01 ±8.880E-04 1.4863E-06 ±4.831E-13 1.4863E-06 ±4.831E-13 DTLZ5 10 60 2.0770E-01 ±1.709E-02 7.0177E-10 ±3.543E-19 7.0038E-10 ±3.559E-19 6.6548E-01 ±6.293E-04 4.5127E-08 ±1.444E-16 4.4404E-08 ±1.177E-16 DTLZ5 10 70 2.5145E-01 ±1.060E-01 1.8807E-11 ±4.219E-22 1.8765E-11 ±4.232E-22 6.6408E-01 ±3.107E-04 1.3262E-09 ±3.754E-19 1.2937E-09 ±2.758E-19 DTLZ5 10 80 2.7152E-01 ±5.467E-02 4.5692E-13 ±1.642E-25 4.4614E-13 ±1.670E-25 6.7308E-01 ±1.656E-03 4.2779E-11 ±3.692E-22 4.0647E-11 ±3.440E-22 DTLZ5 10 90 4.9918E-01 ±3.815E-01 1.3169E-14 ±1.215E-28 1.3169E-14 ±1.215E-28 6.6170E-01 ±6.496E-04 1.3318E-12 ±2.954E-25 1.2968E-12 ±1.729E-25 DTLZ5 10 100 6.2946E-01 ±5.507E-01 4.6572E-16 ±1.720E-31 4.6572E-16 ±1.720E-31 6.6624E-01 ±7.366E-04 3.9188E-14 ±2.059E-28 3.9188E-14 ±2.059E-28 DTLZ5 15 20 3.0474E-01 ±1.814E-02 1.3061E-02 ±6.330E-05 1.1716E-02 ±6.859E-05 7.0498E-01 ±1.160E-02 4.4658E-01 ±3.940E-03 4.1599E-01 ±6.379E-03 DTLZ5 15 30 3.0351E-01 ±2.677E-02 7.6061E-04 ±7.907E-07 7.3230E-04 ±7.611E-07 6.8628E-01 ±7.850E-03 1.9488E-02 ±1.221E-04 1.7017E-02 ±8.957E-05 DTLZ5 15 40 3.1979E-01 ±3.836E-02 2.3313E-05 ±6.840E-10 2.3081E-05 ±6.921E-10 7.1221E-01 ±1.100E-02 5.6781E-04 ±1.083E-07 4.5852E-04 ±4.803E-08 DTLZ5 15 50 3.6863E-01 ±8.192E-02 6.6962E-07 ±4.528E-13 6.4758E-07 ±4.183E-13 6.9280E-01 ±4.974E-03 2.0521E-05 ±2.176E-10 1.6630E-05 ±1.061E-10 (continued on next page) 3.2. PCS-Cluster objective reduction algorithm 106 Table 3.15 continued Problems I M GD GD Reduction (k-means) GD Reduction (DBSCAN) IGD IGD Reduction (k-means) IGD Reduction (DBSCAN) DTLZ5 15 60 3.8035E-01 ±7.028E-02 2.7480E-08 ±7.332E-16 2.7405E-08 ±7.371E-16 6.8637E-01 ±7.483E-03 4.9298E-07 ±1.244E-13 3.8773E-07 ±5.642E-14 DTLZ5 15 70 3.8602E-01 ±9.214E-02 6.8363E-10 ±9.642E-19 6.1341E-10 ±7.724E-19 7.0413E-01 ±8.577E-03 2.1164E-08 ±1.580E-16 1.7155E-08 ±1.390E-16 DTLZ5 15 80 3.8357E-01 ±3.383E-02 2.3026E-11 ±6.567E-22 1.9643E-11 ±3.490E-22 6.8140E-01 ±7.344E-03 5.7157E-10 ±1.141E-19 4.6463E-10 ±6.351E-20 DTLZ5 15 90 4.4234E-01 ±7.329E-02 6.2786E-13 ±5.627E-25 5.6396E-13 ±4.451E-25 6.9026E-01 ±5.404E-03 1.9831E-11 ±1.903E-22 1.4949E-11 ±1.008E-22 DTLZ5 15 100 4.5147E-01 ±2.550E-01 2.8299E-14 ±8.292E-28 2.8088E-14 ±8.381E-28 6.8443E-01 ±6.677E-03 5.0601E-13 ±9.285E-26 3.8647E-13 ±3.361E-26 DTLZ5 20 30 4.0598E-01 ±6.228E-02 9.7725E-03 ±7.203E-05 8.9001E-03 ±6.733E-05 4.7263E-01 ±7.223E-02 2.0646E-01 ±7.837E-03 1.4625E-01 ±7.430E-03 DTLZ5 20 40 4.6156E-01 ±7.747E-02 1.1518E-03 ±3.320E-06 1.1467E-03 ±3.331E-06 5.6108E-01 ±7.733E-02 1.0899E-02 ±6.310E-05 7.2010E-03 ±5.381E-05 DTLZ5 20 50 5.6642E-01 ±2.163E-01 4.0280E-05 ±3.006E-09 3.7731E-05 ±2.896E-09 5.4540E-01 ±8.315E-02 3.4577E-04 ±7.824E-08 2.3787E-04 ±6.111E-08 DTLZ5 20 60 4.9068E-01 ±5.375E-02 1.5426E-06 ±4.039E-12 1.5378E-06 ±4.050E-12 5.2834E-01 ±9.083E-02 1.0227E-05 ±3.109E-11 6.8761E-06 ±3.190E-11 DTLZ5 20 70 5.2761E-01 ±9.245E-02 3.6772E-08 ±3.066E-15 3.4499E-08 ±2.869E-15 5.7402E-01 ±8.121E-02 2.8977E-07 ±4.492E-14 1.6719E-07 ±2.739E-14 DTLZ5 20 80 5.9250E-01 ±2.089E-01 7.7056E-10 ±1.909E-18 7.3865E-10 ±1.882E-18 5.9229E-01 ±7.070E-02 1.1079E-08 ±3.904E-17 5.4477E-09 ±2.220E-17 DTLZ5 20 90 6.5945E-01 ±2.253E-01 3.2079E-11 ±2.768E-21 3.1249E-11 ±2.510E-21 5.8227E-01 ±8.707E-02 2.5150E-10 ±5.363E-20 1.5113E-10 ±3.055E-20 DTLZ5 20 100 7.0824E-01 ±3.785E-01 9.2522E-13 ±2.230E-24 8.9737E-13 ±2.187E-24 5.9934E-01 ±8.518E-02 8.3435E-12 ±3.335E-23 4.9960E-12 ±2.672E-23 WFG3 10 1.7677E-01 ±7.350E-06 8.0472E-02 ±1.278E-05 5.8913E-02 ±2.989E-13 4.9527E+00 ±6.114E-07 1.2160E+00 ±5.717E-03 8.4134E-01 ±1.233E-32 WFG3 20 2.5165E-01 ±1.299E-04 8.6127E-02 ±7.604E-05 6.3277E-02 ±6.418E-06 9.7664E+00 ±6.215E-02 1.2180E+00 ±1.522E-02 8.9487E-01 ±1.283E-03 WFG3 30 2.8616E-01 ±1.317E-04 8.5221E-02 ±9.367E-05 6.3929E-02 ±1.858E-11 1.9350E+01 ±2.554E-02 1.2052E+00 ±1.874E-02 9.0407E-01 ±3.081E-31 WFG3 40 3.1979E-01 ±1.185E-04 8.9377E-02 ±6.560E-05 6.4543E-02 ±4.982E-12 3.0224E+01 ±1.393E-02 1.2639E+00 ±1.312E-02 9.1276E-01 ±1.109E-31 WFG3 50 3.5109E-01 ±8.657E-05 9.0248E-02 ±7.652E-05 6.4931E-02 ±2.557E-12 4.1343E+01 ±1.236E-02 1.2763E+00 ±1.531E-02 9.1826E-01 ±0.000E+00 WFG3 60 3.8134E-01 ±1.007E-04 8.7662E-02 ±1.088E-04 6.5199E-02 ±8.456E-13 5.2644E+01 ±5.298E-03 1.2397E+00 ±2.176E-02 9.2205E-01 ±1.109E-31 WFG3 70 4.1060E-01 ±8.103E-05 8.9494E-02 ±4.507E-05 6.5395E-02 ±5.389E-13 6.4041E+01 ±5.572E-03 1.2656E+00 ±9.011E-03 9.2483E-01 ±0.000E+00 WFG3 80 4.3720E-01 ±3.834E-05 8.7889E-02 ±8.030E-05 6.5545E-02 ±6.222E-14 7.5479E+01 ±3.424E-03 1.2429E+00 ±1.605E-02 9.2695E-01 ±1.972E-31 WFG3 90 4.6301E-01 ±4.399E-05 9.0591E-02 ±5.729E-05 6.5663E-02 ±1.712E-12 8.6934E+01 ±2.572E-03 1.2812E+00 ±1.146E-02 9.2862E-01 ±1.109E-31 WFG3 100 4.8584E-01 ±3.658E-05 8.9111E-02 ±5.903E-05 6.5759E-02 ±4.267E-13 9.8421E+01 ±1.603E-03 1.2602E+00 ±1.181E-02 9.2997E-01 ±4.437E-31 3.2. PCS-Cluster objective reduction algorithm 107 ilarly, columns 8th and 9th show IGD of solution set after applying the algorithms. The table unveils that the GD and IGD of reduced solution set obtained by objective reduction are better than (smaller than) those of it without objective reduction in all of 46 cases for both DTLZ5(I,M), and WFG3(M) problems in both kinds of clustering algorithms, namely k -means and DBSCAN. 3.2.3.4 Comparison the partial objective reduction algorithms with COR algorithm This sub-section compares the performance of three proposed algo- rithms. They are a complete PF-based objective algorithm, COR algo- rithm; and two partial PF-based ones, namely PCS-LPCA and PCS-Cluster. The experiment are performed on 4 instances of DTLZ5(I,M) prob- lem [26]. The thesis uses CORc, a variant of COR algorithm to compare. Five many- algorithms, which are GrEA, KnEA, NSGA-III, RVEA*, and θ-DEA; are utilized to generate non-dominated set for CORc. Parameters are set as in section 2.2.2, section 3.1.2, and section 3.2.2 for COR, PCS-LPCA, and PCS-Cluster, respectively. Other parameters for many- algorithm are set as all many- algorithms are implemented by PlatEMO platform [83]. The population size is set to 200, and the number of generations is set to 2000. The probability of crossover and mutation is set to 0.9 and 0.1, respectively. The distribution index for crossover is set to 5, and the distribution index for mutation is set to 20. The result of experiment is shown in Table 3.16 and is drawn in Fig- ure 3.7. According to the table, PCS-LPCA and PCS-Cluster(DBSCAN) give the best results with 100 times of successful finding the correct set in the total of 100 runs, while CORc variant (integrated with GrEA) gives the worst with 81 times of success. In general, the results decrease when the number of objectives (value of M) is 20. Table 3.17 shows the average of the rank of the algorithms for each instance, in which, PCS-Cluster(DBSCAN) 3.2. PCS-Cluster objective reduction algorithm 108 Table 3.16: Comparison of number of successes in finding the correct relevant objec- tives among PCS-PLCA, PCS-Cluster, and a CORc variant in 20 runs DTLZ5 GrEA KnEA NSGA-III RVEA* θ-DEA PCS-LPCA PCS-Cluster (k -means) PCS-Cluster (DBSCAN)I M COR COR COR COR COR 3 5 20 20 20 20 20 20 20 20 5 10 20 20 20 20 20 20 20 20 7 10 20 20 20 20 20 20 20 20 5 20 1 11 14 13 17 20 6 20 + 81 91 94 93 97 100 86 100 and PCS-LPCA stand on two top rows of the table, while CORc (inte- grated with GrEA) stands on the bottom of the table. 1 C O R c( G rE A ) C O R c( K nE A ) C O R c( N S G A -I II ) C O R c( R V E A *) C O R c( θ- D E A ) P C S -L P C A P C S -C lu st er (k -m ea ns ) P C S -C lu st er (D B S C A N ) 0 20 40 60 80 100 N u m b er of su cc es se s Figure 3.7: A chart for number of successes in solving the DTLZ5(I,M) problem 3.2. PCS-Cluster objective reduction algorithm 109 Table 3.17: The average ranking of 8 algorithms using Friedman test Algorithm Average rank 1 PCS-Cluster(DBSCAN) 3.90 2 PCS-LPCA 3.90 3 CORc(θ-DEA ) 4.20 4 CORc(NSGA-III) 4.40 5 CORc(RVEA*) 4.60 6 CORc(KnEA) 4.80 7 PCS-Cluster(k -means) 5.00 8 CORc(GrEA) 5.20 Summary This chapter has proposed two objective reduction algorithms. They are PCS-LPCA and PCS-Cluster. In the first step, they use PCSEA for generating non-dominated solutions set located only in the “corner” of PF. In the second step, while PCS-LPCA uses L-PCA for reduction, PCS- Cluster uses clustering algorithm: k -means and DBSCAN, for clustering objectives of the non-dominated solution set. Two steps are repeated until the algorithms cannot reduce any more objectives. Experiments pinpoint that the PCS-LPCA algorithm and PCS-Cluster (using DBSCAN) give better results than others. Conclusion and future works Conclusion In this thesis, many- problems which have redundant objectives have been settled. To do that; approaches to solving many- problems have been investigated and analyzed; the impacts of multi-/many- algorithms on objective reduction have also been pinpointed and then three ORAs have been proposed. The thesis has given an overview of multi- problems together with common approaches to solving them, and focused on multi- algorithms. It has also mentioned many- problems and the difficulties the multi- al- gorithms had to face. Numerous many- algorithms have appeared in the hope of eliminating or reducing the difficulties. However, in several many- problems, it still remains unknown if all objectives are essential or not. An approach to eliminating the difficulties has been proposed to determine which objectives in problems are redun- dant, then the redundant objectives have been discarded. This approach is called objective reduction. This thesis has investigated the interaction between objective dimen- sionality reduction (ODR) and many- algorithms. The experiments were designed to evaluate the impacts of many- algorithms on the performance of an ODR. Then, the thesis examined the benefits which many- algo- rithms can achieve when being combined with an ODR to remove redun- dant objectives. The results have unveiled that the performance of an 110 Conclusion and future works 111 ODR strongly depends on multi-/many- algorithms which generate non- dominated set. By combining with many- algorithms, can an objective reduction successfully remove redundant objectives even when the num- ber of original objectives is getting larger. The results also demonstrate that being combined with an ODR to remove redundant objectives, it can significantly improve the performance of many- algorithms. This thesis focused on L-PCA for performing objective reduction. Three ORAs have been proposed to deal with redundant many- prob- lems. Those algorithms use multi-/many- algorithms to generate PFs then use machine learning algorithm to perform objective reduction. (1) COR algorithm utilizes multi-/many- algorithms to generate com- plete PF then uses PAM algorithm to determine redundant objectives and essential ones. Furthermore, it considers objectives as objects (or points) in space, then partitions them into clusters. The number of clusters is determined by using the silhouette index. It kept one objective in each cluster and discards other ones. The proposed algorithm has been com- pared with two other existing ones in different instances of DTLZ5(I,M) problem. The result unseals that the proposed algorithm is not only equiv- alent to or more efficient than existing ones. (2) PCS-LPCA algorithm, which uses PCSEA to generate a partial PF then utilizes the L-PCA for identifying the relevant and redundant objectives. It proves that the proposed algorithm is better than the original ones. It also examines the effects of threshold values for PCSEA-based objective reduction. It indicates that PCSEA-based objective reduction is very efficient in solving redundant problems with a small number of relevant objectives. It also suggests that PCSEA-based objective reduction becomes inefficient for the larger number. (3) PCS-Cluster algorithm uses PCSEA to generate a partial PF and clustering algorithms for identifying the relevant and redundant objec- Conclusion and future works 112 tives. It takes advantage of PCSEA and the simple of clustering algo- rithms: k -means and DBSCAN. Experiments with wider range instances of DTLZ5(I,M) problem have been designed and 30 times have been run independently. The results prove that the proposed algorithm is better than the original ones. Future works Currently, ORAs use a linear or monotonic measure of dependence, namely, Pearson’s rho, to estimate the conflict among objectives. However, other linear measures like Spearman’s rank or Kendall’s tau, and non- linear measure like the Hilbert-Schmidt independence criterion have not been experimented. There may be other methods which are able to automatically deter- mine the number of clusters; hence, future works may investigate these methods for the proposed methods. The results will further strengthen the links between evolutionary computation and machine learning in applications. As the result of PCSEA-based ORA is not entirely independent of the order in which the objective is re- moved; therefore, future works can investigate the order of objective being examined for retaining or discarding. Further work will be studied for solving many- problems which con- tains functions being a combination of other ones. Publications Journal articles [J1] HX Nguyen, LT Bui, and CT Tran. “Improving many objective optimisation algorithms using objective dimensionality reduction”. In: Evolutionary Intelligence ISSN 1864-5909. Springer, 2020, 13.3, pp. 365–380. [J2] HX Nguyen, LT Bui, and CT Tran. “An improvement of clustering-based ob- jective reduction method for many-objective optimization problems”. In: Journal of Science and Technique - Le Quy Don Technical University ISSN-1859-0209 No. 202 (10-2019)-Section on Information and Communication Technology (ICT)- No. 14. 2019. [J3] HX Nguyen, CT Tran, and LT Bui. “Improve performance of pareto corner search-based objective reduction in many-objective optimization”. In: Evolutionary Intelligence ISSN 1864-5909. Springer, 2022 Oct (accepted). doi: 10.1007/s12065- 022-00787-y. Conference papers [C1] HX Nguyen, LT Bui, and CT Tran. “A Pareto Corner Search Evolutionary Algo- rithm and Principal Component Analysis for Objective Dimensionality Reduction”. In: 2019 11th International Conference on Knowledge and Systems Engineering (KSE’19) (IEEE). Da Nang, Vietnam, Oct. 2019. [C2] HX Nguyen, LT Bui, and CT Tran. “Clustering Method Using Pareto Corner Search Evolutionary Algorithm for Objective Reduction in Many-Objective Opti- mization Problems”. In: Proceedings of the Tenth International Symposium on In- formation and Communication Technology. SoICT 2019. Hanoi, Ha Long Bay, Viet Nam: ACM, 2019, pp. 78–84. isbn: 978-1-4503-7245-9. 113 Bibliography [1] A Abraham, N Nedjah, and L de Macedo Mourelle. “Evolutionary computation: from genetic algorithms to genetic programming”. In: Genetic systems program- ming. Springer, 2006, pp. 1–20. [2] SF Adra and PJ Fleming. “Diversity management in evolutionary many-objective optimization”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2011, 15.2, pp. 183–195. [3] J Bader and E Zitzler. “HypE: An algorithm for fast hypervolume-based many- objective optimization”. In: Evolutionary computation. MIT Press, 2011, 19.1, pp. 45–76. [4] S Bandyopadhyay and A Mukherjee. “An algorithm for many-objective opti- mization with reduced objective computations: A study in differential evolu- tion”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2014, 19.3, pp. 400–413. [5] S Bechikh, M Elarbi, and LB Said. “Many-objective optimization using evo- lutionary algorithms: a survey”. In: Recent Advances in Evolutionary Multi- objective Optimization. Springer, 2017, pp. 105–137. [6] K Bringmann et al. “Approximation-guided evolutionary multi-objective opti- mization”. In: Twenty-Second International Joint Conference on Artificial In- telligence. 2011. [7] D Brockhoff and E Zitzler. “Are all objectives necessary? On dimensionality re- duction in evolutionary multiobjective optimization”. In: Parallel Problem Solv- ing from Nature-PPSN IX. Springer, 2006, pp. 533–542. [8] D Brockhoff and E Zitzler. “Dimensionality reduction in multiobjective opti- mization with (partial) dominance structure preservation: Generalized minimum objective subset problems”. In: TIK Report. 2006, 247. [9] D Brockhoff and E Zitzler. “Objective reduction in evolutionary multiobjec- tive optimization: Theory and applications”. In: Evolutionary computation. MIT Press, 2009, 17.2, pp. 135–166. 114 BIBLIOGRAPHY 115 [10] D Brockhoff and E Zitzler. “Offline and online objective reduction in evolution- ary multiobjective optimization based on objective conflicts”. In: TIK Report. Citeseer, 2007, 269. [11] D Brockhoff and E Zitzler. “On objective conflicts and objective reduction in multiple criteria optimization”. In: TIK Report. 2006, 243. [12] S Chand and M Wagner. “Evolutionary many-objective optimization: A quick- start guide”. In: Surveys in Operations Research and Management Science. El- sevier, 2015, 20.2, pp. 35–42. [13] J Cheng, GG Yen, and G Zhang. “A many-objective evolutionary algorithm with enhanced mating and environmental selections”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2015, 19.4, pp. 592–605. [14] R Cheng et al. “A Reference Vector Guided Evolutionary Algorithm for Many- Objective Optimization.” In: IEEE Trans. Evolutionary Computation. 2016, 20.5, pp. 773–791. [15] Ym Cheung and F Gu. “Online objective reduction for many-objective optimiza- tion problems”. In: Evolutionary Computation (CEC), 2014 IEEE Congress on. IEEE. 2014, pp. 1165–1171. [16] Ym Cheung, F Gu, and HL Liu. “Objective extraction for many-objective op- timization problems: Algorithm and test problems”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2016, 20.5, pp. 755–772. [17] K Chircop and D Zammit-Mangion. “On ε-constraint based methods for the generation of Pareto frontiers”. In: Journal of Mechanics Engineering and Au- tomation. 2013, 3.5, pp. 279–289. [18] EK Chong and SH Zak. An introduction to optimization, Fourth Edition. Vol. 76. John Wiley & Sons, 2013. [19] CAC Coello. “Recent results and open problems in evolutionary multiobjective optimization”. In: International Conference on Theory and Practice of Natural Computing. Springer. 2017, pp. 3–21. [20] CAC Coello and NC Cortés. “Solving multiobjective optimization problems us- ing an artificial immune system”. In: Genetic Programming and Evolvable Ma- chines. Springer, 2005, 6.2, pp. 163–190. [21] CAC Coello, GB Lamont, DA Van Veldhuizen, et al. Evolutionary algorithms for solving multi-objective problems. Vol. 5. Springer, 2007. BIBLIOGRAPHY 116 [22] K Deb. “Multi-objective optimisation using evolutionary algorithms: an intro- duction”. In: Multi-objective evolutionary optimisation for product design and manufacturing. Springer, 2011, pp. 3–34. [23] K Deb and H Jain. “An evolutionary many-objective optimization algorithm us- ing reference-point-based nondominated sorting approach, part I: Solving prob- lems with box constraints.” In: IEEE Trans. Evolutionary Computation. 2014, 18.4, pp. 577–601. [24] K Deb, M Mohan, and S Mishra. “Evaluating the ε-domination based multi- objective evolutionary algorithm for a quick computation of Pareto-optimal so- lutions”. In: Evolutionary computation. MIT Press, 2005, 13.4, pp. 501–525. [25] K Deb and D Saxena. “Searching for Pareto-optimal solutions through dimen- sionality reduction for certain large-dimensional multi-objective optimization problems”. In: Proceedings of the World Congress on Computational Intelligence (WCCI-2006). 2006, pp. 3352–3360. [26] K Deb and DK Saxena. “On finding pareto-optimal solutions through dimen- sionality reduction for certain large-dimensional multi-objective optimization problems”. In: Kangal report. 2005, 2005011. [27] K Deb et al. “A fast and elitist multiobjective genetic algorithm: NSGA-II”. In: IEEE transactions on evolutionary computation. IEEE, 2002, 6.2, pp. 182–197. [28] K Deb et al. “Scalable multi-objective optimization test problems”. In: Proceed- ings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No. 02TH8600). Vol. 1. IEEE. 2002, pp. 825–830. [29] R Ding et al. “An objective reduction method based on advanced clustering for many-objective optimization problems and its human-computer interaction visualization of pareto front”. In: Computers & Electrical Engineering. Elsevier, 2021, 93, p. 107266. [30] N Drechsler, R Drechsler, and B Becker. “Multi-objective optimisation based on relation favour”. In: International conference on evolutionary multi-criterion optimization. Springer. 2001, pp. 154–166. [31] AE Eiben and JE Smith. Introduction to evolutionary computing, 2nd edition. Springer, 2015. [32] M Ester et al. “A density-based algorithm for discovering clusters in large spatial databases with noise.” In: Kdd. Vol. 96. 34. 1996, pp. 226–231. BIBLIOGRAPHY 117 [33] M Farina and P Amato. “On the optimal solution definition for many-criteria optimization problems”. In: 2002 annual meeting of the North American fuzzy in- formation processing society proceedings. NAFIPS-FLINT 2002 (Cat. No. 02TH8622). IEEE. 2002, pp. 233–238. [34] JE Fieldsend. “Dynamic Visualisation of Many-Objective Populations”. In: The Operational Research Society, 2016. [35] T Gal and T Hanne. “Consequences of dropping nonessential objectives for the application of MCDM methods”. In: European Journal of Operational Research. Elsevier, 1999, 119.2, pp. 373–378. [36] M Garza-Fabre, GT Pulido, and CAC Coello. “Ranking methods for many- objective optimization”. In: Mexican international conference on artificial intel- ligence. Springer. 2009, pp. 633–645. [37] RH Gómez and CAC Coello. “MOMBI: A new metaheuristic for many-objective optimization based on the R2 indicator”. In: 2013 IEEE Congress on Evolution- ary Computation. IEEE. 2013, pp. 2488–2495. [38] F Gu, HL Liu, and Ym Cheung. “A Fast Objective Reduction Algorithm Based on Dominance Structure for Many Objective Optimization”. In: Asia-Pacific Conference on Simulated Evolution and Learning. Springer. 2017, pp. 260–271. [39] X Guo and X Wang. “A Novel Objective Grouping Evolutionary Algorithm for Many-Objective Optimization Problems”. In: International Journal of Pattern Recognition and Artificial Intelligence. World Scientific, 2020, 34.06, p. 2059018. [40] X Guo, Y Wang, and X Wang. “An objective reduction algorithm using repre- sentative Pareto solution search for many-objective optimization problems”. In: Soft Computing. Springer, 2016, 20.12, pp. 4881–4895. [41] X Guo, Y Wang, and X Wang. “Using objective clustering for solving many- objective optimization problems”. In: Mathematical Problems in Engineering. Hindawi, 2013, 2013. [42] X Guo et al. “A new non-redundant objective set generation algorithm in many- objective optimization problems”. In: 2015 IEEE Congress on Evolutionary Com- putation (CEC). IEEE. 2015, pp. 2851–2858. [43] X Guo et al. “A new objective reduction algorithm for many-objective problems: employing mutual information and clustering algorithm”. In: Computational In- telligence and Security (CIS), 2012 Eighth International Conference on. IEEE. 2012, pp. 11–16. BIBLIOGRAPHY 118 [44] R Gupta and SJ Nanda. “Objective Reduction in Many-Objective Optimization with Social Spider Algorithm for Cloud Detection in Satellite Images”. In: 2021. [45] Z He and GG Yen. “Many-objective evolutionary algorithm: Objective space reduction and diversity improvement”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2015, 20.1, pp. 145–160. [46] Z He and GG Yen. “Many-objective evolutionary algorithms based on coordi- nated selection strategy”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2016, 21.2, pp. 220–233. [47] S Huband et al. “A review of multiobjective test problems and a scalable test problem toolkit”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2006, 10.5, pp. 477–506. [48] EJ Hughes. “Multiple single objective Pareto sampling”. In: Congress on Evolu- tionary Computation 2003. 2003, pp. 2678–2684. [49] H Ishibuchi, N Akedo, and Y Nojima. “Behavior of multiobjective evolutionary algorithms on many-objective knapsack problems”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2014, 19.2, pp. 264–283. [50] H Ishibuchi and NT and Yusuke Nojima. “Evolutionary many-objective opti- mization: A short review”. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC2008, June 1-6, 2008, Hong Kong. 2008, pp. 2419–2426. [51] AL Jaimes, CAC Coello, and JEU Barrientos. “Online objective reduction to deal with many-objective problems”. In: International Conference on Evolution- ary Multi-Criterion Optimization. Springer. 2009, pp. 423–437. [52] D Kalyanmoy et al. Multi objective optimization using evolutionary algorithms. John Wiley and Sons, 2001. [53] L Kaufman and P Rousseeuw. Clustering by means of medoids. North-Holland, 1987. [54] DJ Ketchen and CL Shook. “The application of cluster analysis in strategic man- agement research: an analysis and critique”. In: Strategic management journal. Wiley Online Library, 1996, 17.6, pp. 441–458. [55] S Kukkonen and J Lampinen. “Ranking-dominance and many-objective opti- mization”. In: 2007 IEEE Congress on Evolutionary Computation. IEEE. 2007, pp. 3983–3990. [56] B Li et al. “Many-objective evolutionary algorithms: A survey”. In: ACM Com- puting Surveys (CSUR). ACM, 2015, 48.1, p. 13. BIBLIOGRAPHY 119 [57] K Li et al. “Evolutionary many-objective optimization: A comparative study of the state-of-the-art”. In: IEEE Access. IEEE, 2018, 6, pp. 26194–26214. [58] M Li, S Yang, and X Liu. “Shift-based density estimation for Pareto-based algo- rithms in many-objective optimization”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2014, 18.3, pp. 348–365. [59] M Li, L Zhen, and X Yao. “How to read many-objective solution sets in parallel coordinates [educational forum]”. In: IEEE Computational Intelligence Maga- zine. IEEE, 2017, 12.4, pp. 88–100. [60] Y Li, HL Liu, and ED Goodman. “Hyperplane-approximation-based method for many-objective optimization problems with redundant objectives”. In: Evo- lutionary computation. MIT Press One Rogers Street, Cambridge, MA 02142- 1209, USA journals-info . . ., 2019, 27.2, pp. 313–344. [61] A López Jaimes, CA Coello Coello, and D Chakraborty. “Objective reduction using a feature selection technique”. In: Proceedings of the 10th annual conference on Genetic and Evolutionary Computation. ACM. 2008, pp. 673–680. [62] N Luo, X Li, and Q Lin. “Objective reduction for many-objective optimization problems using objective subspace extraction”. In: Soft Computing. Springer, 2018, 22.4, pp. 1159–1173. [63] J MacQueen et al. “Some methods for classification and analysis of multivariate observations”. In: Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. 14. Oakland, CA, USA. 1967, pp. 281–297. [64] SU Mane and M Narasinga Rao. “A Non-dominated Sorting based Evolution- ary Algorithm for Many-objective Optimization Problems”. In: Scientia Iranica. Sharif University of Technology, 2021. [65] K Miettinen. Nonlinear Multiobjective Optimization, volume 12 of International Series in Operations Research and Management Science. 1999. [66] L Nguyen, LT Bui, and HA Abbass. “DMEA-II: the direction-based multi- objective evolutionary algorithm-II”. In: Soft Computing. Springer, 2014, 18.11, pp. 2119–2134. [67] S Obayashi and D Sasaki. “Visualization and data mining of Pareto solutions using self-organizing map”. In: International Conference on Evolutionary Multi- Criterion Optimization. Springer. 2003, pp. 796–809. [68] T Okabe, Y Jin, and B Sendhoff. “A critical survey of performance indices for multi-objective optimisation”. In: Evolutionary Computation, 2003. CEC’03. The 2003 Congress on. Vol. 2. IEEE. 2003, pp. 878–885. BIBLIOGRAPHY 120 [69] M Pal, S Saha, and S Bandyopadhyay. “DECOR: differential evolution using clustering based objective reduction for many-objective optimization”. In: In- formation Sciences. Elsevier, 2018, 423, pp. 200–218. [70] A Pryke, S Mostaghim, and A Nazemi. “Heatmap visualization of population based multi objective algorithms”. In: International Conference on Evolutionary Multi-Criterion Optimization. Springer. 2007, pp. 361–375. [71] RC Purshouse and PJ Fleming. “Conflict, harmony, and independence: Relation- ships in evolutionary multi-criterion optimisation”. In: International Conference on Evolutionary Multi-Criterion Optimization. Springer. 2003, pp. 16–30. [72] SS Rao. Engineering Optimization: Theory and Practice, Copyright© 2009 by John Wiley & Sons. 2009. [73] A Ravindran, GV Reklaitis, and KM Ragsdell. Engineering optimization: meth- ods and applications. John Wiley & Sons, 2006. [74] N Riquelme, C Von Lücken, and B Baran. “Performance metrics in multi- objective optimization”. In: Computing Conference (CLEI), 2015 Latin Ameri- can. IEEE. 2015, pp. 1–11. [75] PJ Rousseeuw. “Silhouettes: a graphical aid to the interpretation and valida- tion of cluster analysis”. In: Journal of computational and applied mathematics. Elsevier, 1987, 20, pp. 53–65. [76] DK Saxena and K Deb. “Non-linear dimensionality reduction procedures for cer- tain large-dimensional multi-objective optimization problems: Employing cor- rentropy and a novel maximum variance unfolding”. In: International Conference on Evolutionary Multi-Criterion Optimization. Springer. 2007, pp. 772–787. [77] DK Saxena et al. “Objective reduction in many-objective optimization: Linear and nonlinear algorithms”. In: IEEE Transactions on Evolutionary Computa- tion. IEEE, 2013, 17.1, pp. 77–99. [78] NH Siddique and H Adeli. Nature-Inspired Computing: Physics and Chemistry- Based Algorithms. CRC Press, 2017. [79] HK Singh, A Isaacs, and T Ray. “A Pareto corner search evolutionary algo- rithm and dimensionality reduction in many-objective optimization problems”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2011, 15.4, pp. 539– 556. [80] A Sinha et al. “Using objective reduction and interactive procedure to handle many-objective optimization problems”. In: Applied Soft Computing. Elsevier, 2013, 13.1, pp. 415–427. BIBLIOGRAPHY 121 [81] COS Sorzano, J Vargas, and APMontano. “A survey of dimensionality reduction techniques”. In: arXiv preprint arXiv:1403.2877. 2014. [82] W Sun and J Li. “A strengthened diversity indicator and reference vector-based evolutionary algorithm for many-objective optimization”. In: Soft Computing. Springer, 2021, 25.15, pp. 10257–10273. [83] Y Tian et al. “PlatEMO: A MATLAB platform for evolutionary multi-objective optimization [educational forum]”. In: IEEE Computational Intelligence Maga- zine. IEEE, 2017, 12.4, pp. 73–87. [84] L Van Der Maaten, E Postma, and J Van den Herik. “Dimensionality reduction: a comparative”. In: J Mach Learn Res. 2009, 10.66-71, p. 13. [85] L Van der Maaten. “An introduction to dimensionality reduction using matlab”. In: Report. Citeseer, 2007, 1201.07-07, p. 62. [86] DAV Veldhuizen. “Multiobjective Evolutionary Algorithms: Classifications, Anal- yses, and New Innovations.” In: Jan. 1999. [87] T Wagner, N Beume, and B Naujoks. “Pareto-, aggregation-, and indicator- based methods in many-objective optimization”. In: International conference on evolutionary multi-criterion optimization. Springer. 2007, pp. 742–756. [88] D Walker, J Fieldsend, and R Everson. “Visualising many-objective popula- tions”. In: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation. 2012, pp. 451–458. [89] H Wang, L Jiao, and X Yao. “Two_Arch2: An improved two-archive algorithm for many-objective optimization”. In: IEEE Transactions on Evolutionary Com- putation. IEEE, 2015, 19.4, pp. 524–541. [90] H Wang and X Yao. “Objective reduction based on nonlinear correlation infor- mation entropy”. In: Soft Computing. Springer, 2016, 20.6, pp. 2393–2407. [91] J Wang. Geometric structure of high-dimensional data and dimensionality re- duction. Vol. 5. Springer, 2012. [92] D Xu and Y Tian. “A comprehensive survey of clustering algorithms”. In: Annals of Data Science. Springer, 2015, 2.2, pp. 165–193. [93] S Yang et al. “A grid-based evolutionary algorithm for many-objective optimiza- tion”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2013, 17.5, pp. 721–736. [94] XS Yang. Nature-inspired optimization algorithms. Academic Press, 2020. BIBLIOGRAPHY 122 [95] GG Yen and Z He. “Performance metric ensemble for multiobjective evolution- ary algorithms”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2013, 18.1, pp. 131–144. [96] Y Yuan et al. “A new dominance relation-based evolutionary algorithm for many-objective optimization”. In: IEEE Transactions on Evolutionary Compu- tation. IEEE, 2016, 20.1, pp. 16–37. [97] Y Yuan et al. “Objective reduction in many-objective optimization: evolutionary multiobjective approaches and comprehensive analysis”. In: IEEE Transactions on Evolutionary Computation. IEEE, 2017, 22.2, pp. 189–210. [98] Q Zhang and H Li. “MOEA/D: A multiobjective evolutionary algorithm based on decomposition”. In: IEEE Transactions on evolutionary computation. IEEE, 2007, 11.6, pp. 712–731. [99] X Zhang, Y Tian, and Y Jin. “A knee point-driven evolutionary algorithm for many-objective optimization”. In: IEEE Transactions on Evolutionary Compu- tation. IEEE, 2015, 19.6, pp. 761–776. [100] X Zhang et al. “A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization”. In: IEEE Transactions on Evolution- ary Computation. IEEE, 2016, 22.1, pp. 97–112. [101] E Zitzler and S Künzli. “Indicator-based selection in multiobjective search”. In: International Conference on Parallel Problem Solving from Nature. Springer. 2004, pp. 832–842. [102] E Zitzler, M Laumanns, and L Thiele. “SPEA2: Improving the strength Pareto evolutionary algorithm”. In: TIK-report. Eidgenössische Technische Hochschule Zürich (ETH), Institut für Technische Informatik und Kommunikationsnetze (TIK), 2001, 103. [103] E Zitzler et al. “Performance assessment of multiobjective optimizers: An anal- ysis and review”. In: IEEE Transactions on evolutionary computation. IEEE, 2003, 7.2, pp. 117–132. [104] X Zou et al. “A new evolutionary algorithm for solving many-objective opti- mization problems”. In: IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). IEEE, 2008, 38.5, pp. 1402–1412. Appendix A. Representations of non-dominated solutions In order to represent non-dominated solution set; the star coordinate system, scatter-plot matrix, and parallel coordinates are three ways. While parallel coordinates are presented in section 1.1.2.3 (p. 19), this section shows two other ways. Star coordinate system A star coordinate system [52, 65], which is also called star glyphs to represent multiple non-dominated solutions. For M objective functions, a circle is partitioned into M equal arcs. Each radial line connecting the end of an arc with the center of the circle represents the axis for each objective function. For each line, the center of the circle8 marks the minimum value of each objective and the circumference marks the maximum objective function value9. Since the range of each objec- tive function can be different, it is vital to label both ends of each line. Normalization of objectives is not necessary here. Each solution can be marked on one such a circle. The points marked on each line can be joined with straight lines to form a polygon. Thus, for N solutions, there will be N such circles. Visually, they will convey the convergence and diversity in obtained solutions. Figure A.1 reveals an example of star coordinate system. 8the ideal objective vector for minimize multi- problems 9the nadir objective vector for minimize multi- problems 123 A. Representations of non-dominated solutions 124 0 8 f1 15 17 f2 -0. 1 0.1 5 f3 0 8 f1 15 17 f2 -0.1 0.1 5 f3 0 8 f1 15 17 f2 -0. 1 0.1 5 f3 Figure A.1: Star coordinates for 3 solutions with 3 objectives Scatter-plot matrix The scatter-plot matrix is comprised of panels each representing one objective function pair. The dimension of the square matrix is the number of objective functions. Figure A.2 proves a typical example of such a plot with M = 3 objective functions for the data in Table A.1. Table A.1: An exemplary data for representation (for Figure A.2 and Figure A.3) Solution f1 f2 f3 1 3.90 -1.12 13.0 2 3.70 -1.06 13.0 3 3.50 -1.01 13.0 4 3.30 -0.96 13.0 5 3.10 -0.91 13.0 6 2.75 -0.68 13.0 7 2.40 -0.65 13.0 8 2.05 -0.62 13.0 9 1.65 -0.59 13.2 10 1.30 -0.56 13.7 11 1.05 -0.56 14.6 12 0.80 -0.62 15.5 13 0.65 -0.76 17.0 14 0.55 -0.89 19.0 15 0.50 -1.03 21.5 16 0.45 -1.16 23.5 17 0.40 -1.30 25.5 18 0.35 -1.43 27.5 19 0.30 -1.56 29.5 As can be seen in Figure A.2, each pair is graphed twice with the A. Representations of non-dominated solutions 125 0 1 2 3 4 −1.5 −1 −0.5 0 1 2 3 4 15 20 25 30 −1.5 −1 −0.5 15 20 25 30 f 1 f 2 f 3 f1 f2 f3 Figure A.2: Scatter matrix for data in Table A.1 (p. 124) scales interchanged. This means that either the lower or the upper triangle could be a dropper without losing any information. However, displaying the whole matrix makes it easier to compare the objective function values. One can measure the performance of one objective function against other ones by having a look at one column or one row. Parallel coordinates Parallel coordinate [59], (also called value path [52, 65]) is used to illustrate a set of solutions in an m-dimensional space. Parallel coordinates map that set onto a 2D graph, with m parallel axes being plotted, typically vertical and equally spaced. A solution in an m-dimensional space is represented as a polyline with vertices on these parallel axes, and the position of the vertex on the ith axis corresponds to the value of the point on the ith objective. Parallel coordinates are simple to construct and scale well with the dimensionality of the data. Adding more dimensions only involves adding more axes. Figure A.3 presents an A. Representations of non-dominated solutions 126 example of the parallel coordinates plot for data in Table A.1 (p. 124) as same as Figure A.2 does. 0 1 2 3 4 −1.5 −1 −0.5 15 20 25 30 f1 f2 f3 Figure A.3: Parallel coordinates for data in Table A.1 (p. 124) Appendix B. Several machine learning algorithms used in this study Algorithm B.1: PCA algorithm Input: X, dataset containing n points with number of dimensions d Output: Z, dataset containing n points with number of dimensions k 1 begin 2 Find mean vector x¯ = 1 n ∑n i=1 xi 3 Subtract the mean xˆi = xi − x¯i 4 Compute the covariance matrix S = 1 n XˆXˆ T 5 Compute the eigenvectors and eigenvalues of the covariance matrix S: (λ1,u1), . . . , (λd,ud) 6 Pick k eigenvectors with highest eigenvalues 7 Project data to selected eigenvectors and deriving the new data set Z = UTk Xˆ 8 end 127 B. Several machine learning algorithms 128 Algorithm B.2: k-means algorithm Input: X: A dataset containing n objects; k: the number of clusters; Output: A set of k clusters; 1 begin 2 Choose k random objects as cluster centers called centroids. 3 while true do 4 Calculate the distance between each object and cluster centers. 5 Assign the object x[i] to the cluster whose distance from the cluster center is minimum of all the cluster centers 6 if no object was reassigned then 7 stop 8 end 9 Update the center for each cluster by taking the average of all the data points assigned to that cluster after step 5. 10 end 11 end Algorithm B.3: PAM algorithm Input: D: a dataset containing n objects; k: the number of clusters Output: A set of k clusters 1 begin 2 Arbitrary choose k objects from D as representative objects (seeds) 3 repeat 4 noChange← true; 5 Assign each remaining object to the cluster with the nearest representative object 6 foreach representative object Oj do 7 Randomly select a non representative object Orandom 8 Compute the total swapping cost S of swapping Oj with Orandom 9 if S < 0 then 10 i is replaced by h; 11 noChange← false; 12 end 13 end 14 until noChange; 15 end B. Several machine learning algorithms 129 Algorithm B.4: DBSCAN algorithm Input: Objects, Eps, MinObjs Output: Nc clusters: Cluster[1], Cluster[2],. . . , Cluster[Nc]; 1 begin 2 Nobj ← Objects.size; 3 Cluster[1..Nobj]← 0; 4 Nc← 0 ; // number of cluster 5 Objects[1..Nobj].visit← false ; // to keep track of objects that have been visited. 6 for i = 1 to Nobj do 7 if not Objects[i].visit then 8 Objects[i].visit ← true ; // If not visited yet, then mark as visited 9 neighborObjs ← regionQuery(Objects, i, Eps) ; // find its neighbors (pseudo-code on page 130) 10 if length(neighborObjs) < MinObjs− 1 then 11 objC[i]← 0 ; // Not enough objects to form a cluster, mark object i as a noise 12 else /* Form a cluster */ 13 Nc← Nc+ 1; // Increment No. of clusters and process neighborhood 14 Cluster{Nc} ← i ; // Initialize cluster Nc with object i 15 objC[i]← Nc ; // and mark object i as being a member of cluster Nc. 16 ind← 1 ; // Initialize index into neighborObjs array. /* For each object P’ in neighborObjs */ 17 while ind <= length(neighborObjs) do 18 nb← neighborObjs[ind]; 19 if not Objects[nb].visit then 20 Objects[nb].visit← true ; // If this neighbor has not been visited mark it as visited /* Find the neighbors of this neighbor and if it has enough neighbors add them to the neighborObjs list */ 21 neighborObjsO ← regionQuery(Objects, nb, Eps); // see pseudo-code on page 130 22 if length(neighborObjsO) >= minObjs then 23 neighborsObjs← neighborsObjs ∪ neighborObjsO 24 end 25 end // If this neighbor nb is “free” then add it to this cluster 26 if not objC[nb] then 27 Cluster[Nc]← Cluster[Nc] ∪ {nb}; 28 objC[nb] = Nc; 29 end 30 ind← ind+ 1 ; // increment neighbor object index and process next neighbor 31 end 32 end 33 end 34 end 35 end B. Several machine learning algorithms 130 Algorithm B.5: regionQuery Input: O, n, E Output: neighbors 1 begin 2 E2← E2; 3 Nobj ← O.size; 4 neighbors← ∅; 5 for j = 1 to Nobj do 6 if j 6= n then 7 O[j].visit ← true; // Test if distance < E2 8 dist2← Distance(O[j], O[n]) ; // distance between 2 objects O[j] and O[n] 9 if dist2 < E2 then 10 neighbors← neighbors ∪ {j}; 11 end 12 end 13 end 14 end