Multi-dimensional tree guided efficient global association for decomposition-based evolutionary many-objective optimization

Abstract 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.