Empirical Linkage Discovery in Bi-Objective Optimization

In complex problems, variable subsets may have a joint non-monotonical influence on function value. Therefore, variation operators in many single-objective (SO) state-of-the-art optimizers leverage such dependent variable sets to improve effectiveness and efficiency. In multi-objective optimization (MO), we optimize multiple objective functions and each may have different dependencies. Thus, choosing relevant dependencies to improve a solution is challenging in MO. To overcome this difficulty, we can transform the MO problem into a set of SO problems (that may be infinite) and discover the dependencies for each SO problem separately. However, dependency discovery is expensive, even for a single problem. Performing it for each SO problem separately seems unacceptable. Moreover, the dependencies of the scalarized problem are neither necessarily a subset nor a superset of the dependencies of all objective functions, making choosing appropriate dependencies impossible. Two variables dependent in all objective functions can be independent in their scalarization, and two variables independent in all objective functions can be dependent in their scalarization. Therefore, we propose the bi-objective non-monotonicity check (BONM). BONM is a linkage learning technique that uses only a single check to discover weight vector ranges for which a given variable pair is dependent concerning the non-monotonicity check. Limiting our proposition only to scalarization using weight vectors may deteriorate its applicability for the MO problems with concave Pareto fronts. Nevertheless, it enables using gray-box-dedicated operators in the black-box setting for MO problems. Finally, the proposed parameter-less optimizer that employs BONM significantly outperforms the competing state-of-the-art MO optimizers.