Multi-dimensional tree guided efficient global association for decomposition-based evolutionary many-objective optimization. (English) Zbl 1459.90196
Summary: The suitable association between solutions and subproblems or reference vectors (RVs) is very critical to decomposition-based evolutionary algorithms for many-objective optimization problems (MaOPs). However, the original local association approach leads to the mismatch often and the currently existing global ones have to exhaust all subproblems expensively. In this paper, a multi-dimensional tree guided global association (TGA) mechanism is proposed to associate a solution with the nearest RV more efficiently. The TGA mechanism first constructs a nonlinear multi-dimensional tree (MDTree) to organize all RVs of subproblems. It further introduces a direction dissimilarity metric to measure the mismatches of associations between solutions and RVs. More significantly, owing to the compatibility between this metric and the RV MDTree, the TGA mechanism is capable to prune the RV MDTree to find the nearest RV to a solution in a logarithmic time complexity. In addition, an instantiation of a decomposition-based evolutionary algorithm using the TGA mechanism together with an adaptive aggregation approach is further designed to facilitate the empirical validation of the mechanism. The performance of the mechanism is extensively assessed on the normalized and scaled DTLZ benchmark MaOPs, WFG test suite, as well as two engineering problems. A statistical comparison with several existing local and global association approaches demonstrates the superior effectiveness and computational efficiency of the mechanism.
MSC:
| 90C29 | Multi-objective and goal programming |
| 68W50 | Evolutionary algorithms, genetic algorithms (computational aspects) |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
many-objective optimization; evolutionary algorithms; decomposition; global association; multi-dimensional treeReferences:
| [1] | Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point, Proc. ACM SIGEVO workshop on Foundations of genetic algorithms, 87-102 (2009), ACM · Zbl 1369.68293 |
| [2] | Bai, H.; Zheng, J.; Yu, G.; Yang, S.; Zou, J., A Pareto-based many-objective evolutionary algorithm using space partitioning selection and angle-based truncation, Inf. Sci., 478, 186-207 (2019) · Zbl 1443.90307 |
| [3] | Bechikh, S.; Coello, C. A.C., Advances in evolutionary multi-objective optimization, Swarm Evol. Comput., 40, 155-157 (2018) |
| [4] | Bentley, J. L., Multidimensional binary search trees used for associative searching, Commun. ACM, 18, 9, 509-517 (1975) · Zbl 0306.68061 |
| [5] | Beume, N., S-Metric calculation by considering dominated hypervolume as klee’s measure problem, Evol. Comput., 17, 4, 477-492 (2009) |
| [6] | Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: Multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 3, 1653-1669 (2007) · Zbl 1123.90064 |
| [7] | Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E., Time bounds for selection, J. Comput. Syst. Sci., 7, 4, 448-461 (1973) · Zbl 0278.68033 |
| [8] | Chen, Z.; Zhou, Y.; Zhao, X.; Xiang, Y.; Wang, J., A historical solutions based evolution operator for decomposition-based many-objective optimization, Swarm Evol. Comput., 41, 167-189 (2018) |
| [9] | Cheng, R.; Jin, Y.; Olhofer, M.; Sendhoff, B., A reference vector guided evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 5, 773-791 (2016) |
| [10] | Das, I.; Dennis, J. E., Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim., 8, 3, 631-657 (1998) · Zbl 0911.90287 |
| [11] | Das, S. S.; Islam, M. M.; Arafat, N. A., Evolutionary algorithm using adaptive fuzzy dominance and reference point for many-objective optimization, Swarm Evol. Comput., 44, 1092-1107 (2019) |
| [12] | Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints, IEEE Trans. Evol. Comput., 18, 4, 577-601 (2014) |
| [13] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002) |
| [14] | Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable test problems for evolutionary multiobjective optimization, (Abraham, A.; Jain, L.; Goldberg, R., Evolutionary Multiobjective Optimization: Theoretical Advances and Applications (2005), Springer London: Springer London London), 105-145 · Zbl 1078.90567 |
| [15] | Durillo, J. J.; Nebro, A. J., jMetal: a Java framework for multi-objective optimization, Adv. Eng. Softw., 42, 10, 760-771 (2011) |
| [16] | Friedman, J. H.; Bentley, J. L.; Finkel, R. A., An algorithm for finding best matches in logarithmic expected time, ACM Trans. Math. Softw., 3, 3, 209-226 (1977) · Zbl 0364.68037 |
| [17] | Geng, J.; Ying, S.; Jia, X.; Zhang, T.; Liu, X.; Guo, L.; Xuan, J., Supporting many-objective software requirements decision: an exploratory study on the next release problem, IEEE Access, 6, 60547-60558 (2018) |
| [18] | Gong, D.; Ji, X., Optimizing interval higher-dimensional multi-objective problems using set-based evolutionary algorithms incorporated with preferences, Control Theo. Appl., 30, 11, 1369-1383 (2013) · Zbl 1299.90290 |
| [19] | Guerrero-Peña, E.; Araújo, A. F.R., Multi-objective evolutionary algorithm with prediction in the objective space, Inf. Sci., 501, 293-316 (2019) · Zbl 1453.90142 |
| [20] | Ishibuchi, H.; Akedo, N.; Nojima, Y., Behavior of multiobjective evolutionary algorithms on many-objective knapsack problems, IEEE Trans. Evol. Comput., 19, 2, 264-283 (2015) |
| [21] | Ishibuchi, H.; Hitotsuyanagi, Y.; Tsukamoto, N.; Nojima, Y., Many-objective test problems to visually examine the behavior of multiobjective evolution in a decision space, Proc. International Conference on Parallel Problem Solving from Nature, 91-100 (2010), Springer |
| [22] | Ishibuchi, H.; Masuda, H.; Nojima, Y., A study on performance evaluation ability of a modified inverted generational distance indicator, Proc. Annual Conference on Genetic and Evolutionary Computation, 695-702 (2015), ACM |
| [23] | Ishibuchi, H.; Tsukamoto, N.; Nojima, Y., Evolutionary many-objective optimization: a short review, Proc. IEEE congress on evolutionary computation, 2419-2426 (2008) |
| [24] | Lacerda, A. S.; Batista, L. S., KDT-MOEA: a multiobjective optimization framework based on K-D trees, Inf Sci (Ny), 503, 200-218 (2019) |
| [25] | Li, H.; Zhang, Q., Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II, IEEE Trans. Evol. Comput., 13, 2, 284-302 (2009) |
| [26] | Li, K.; Deb, K.; Zhang, Q.; Kwong, S., An evolutionary many-objective optimization algorithm based on dominance and decomposition, IEEE Trans. Evol. Comput., 19, 5, 694-716 (2015) |
| [27] | Li, K.; Wang, R.; Zhang, T.; Ishibuchi, H., Evolutionary many-objective optimization: a comparative study of the state-of-the-art, IEEE Access, 6, 26194-26214 (2018) |
| [28] | Li, L.; Chen, H.; Li, J.; Jing, N.; Emmerich, M., Preference-based evolutionary many-objective optimization for agile satellite mission planning, IEEE Access, 6, 40963-40978 (2018) |
| [29] | Liao, X.; Li, Q.; Yang, X.; Zhang, W.; Li, W., Multiobjective optimization for crash safety design of vehicles using stepwise regression model, Struct. Multidiscip. Optim., 35, 6, 561-569 (2008) |
| [30] | Metiaf, A.; Hong, W. Q.; Aljeroudi, Y., Searching with direction awareness: multi-objective genetic algorithm based on angle quantization and crowding distance MOGA-AQCD, IEEE Access, 7, 10196-10207 (2019) |
| [31] | Ming, M.; Wang, R.; Zha, Y.; Zhang, T., Pareto adaptive penalty-based boundary intersection method for multi-objective optimization, Inf. Sci., 414, 158-174 (2017) · Zbl 1435.90158 |
| [32] | Nebro, A. J.; Durillo, J. J.; Vergne, M., Redesigning the jMetal multi-objective optimization framework, Proc. Annual Conference on Genetic and Evolutionary Computation, 1093-1100 (2015), ACM |
| [33] | Rostami, S.; Neri, F., A fast hypervolume driven selection mechanism for many-objective optimisation problems, Swarm Evol. Comput., 34, 50-67 (2017) |
| [34] | Wang, L.; Zhang, Q.; Zhou, A.; Gong, M.; Jiao, L., Constrained subproblems in a decomposition-based multiobjective evolutionary algorithm, IEEE Trans. Evol. Comput., 20, 3, 475-480 (2016) |
| [35] | Wang, P.; Zhu, W.; Liu, H.; Liao, B.; Cai, L.; Wei, X.; Ren, S.; Yang, J., A new resource allocation strategy based on the relationship between subproblems for MOEA/D, Inf. Sci., 501, 337-362 (2019) · Zbl 1453.90156 |
| [36] | Wang, Z.; Zhang, Q.; Gong, M.; Zhou, A., A replacement strategy for balancing convergence and diversity in MOEA/D, Proc. IEEE Congress on Evolutionary Computation, 2132-2139 (2014) |
| [37] | Wang, Z.; Zhang, Q.; Zhou, A.; Gong, M.; Jiao, L., Adaptive replacement strategies for MOEA/D, IEEE Trans. Cybern., 46, 2, 474-486 (2016) |
| [38] | While, L.; Bradstreet, L.; Barone, L., A fast way of calculating exact hypervolumes, IEEE Trans. Evol. Comput., 16, 1, 86-95 (2012) |
| [39] | While, L.; Hingston, P.; Barone, L.; Huband, S., A faster algorithm for calculating hypervolume, IEEE Trans. Evol. Comput., 10, 1, 29-38 (2006) |
| [40] | Ying, W.; Xie, Y.; Xu, X.; Wu, Y.; Xu, A.; Wang, Z., An efficient and universal conical hypervolume evolutionary algorithm in three or higher dimensional objective space, IEICE Trans. Fundament. Electron. Commun. Comput. Sci., 98, 11, 2330-2335 (2015) |
| [41] | Ying, W.; Xu, X.; Feng, Y.; Wu, Y., An efficient conical area evolutionary algorithm for bi-objective optimization, IEICE Trans. Fundament. Electron. Commun. Comput. Sci., 95, 8, 1420-1425 (2012) |
| [42] | Zapotecas-Martínez, S.; López-Jaimes, A.; García-Nájera, A., LIBEA: a Lebesgue indicator-based evolutionary algorithm for multi-objective optimization, Swarm Evol. Comput., 44, 404-419 (2019) |
| [43] | Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007) |
| [44] | Zhang, X.; Tian, Y.; Jin, Y., Approximate non-dominated sorting for evolutionary many-objective optimization, Inf Sci (Ny), 369, 14-33 (2016) · Zbl 1428.90185 |
| [45] | Zhang, Y.; Gong, D.; Sun, J.; Qu, B., A decomposition-based archiving approach for multi-objective evolutionary optimization, Inf. Sci., 430-431, 397-413 (2018) |
| [46] | Zhao, H.; Zhang, C.; Zhang, B.; Duan, P.; Yang, Y., Decomposition-based sub-problem optimal solution updating direction-guided evolutionary many-objective algorithm, Inf. Sci., 448-449, 91-111 (2018) |
| [47] | Zhou, A.; Qu, B.; Li, H.; Zhao, S.; Suganthan, P. N.; Zhang, Q., Multiobjective evolutionary algorithms: a survey of the state of the art, Swarm Evol. Comput., 1, 1, 32-49 (2011) |
| [48] | Zhou, J.; Yao, X.; Chan, F. T.; Gao, L.; Jing, X.; Li, X.; Lin, Y.; Li, Y., A decomposition based evolutionary algorithm with direction vector adaption and selection enhancement, Inf. Sci., 501, 248-271 (2019) · Zbl 1453.90160 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
