Solving Combinatorial Multi-Objective Bi-Level Optimization Problems Using Multiple Populations and Migration Schemes

Abstract

Many decision making situations are characterized by a hierarchical structure where a lower-level (follower) optimization problem appears as a constraint of the upper-level (leader) one. Such kind of situations is usually modeled as a BLOP (Bi-Level Optimization Problem). The resolution of the latter usually has a heavy computational cost because the evaluation of a single upper-level solution requires finding its corresponding (near) optimal lower-level one. When several objectives are optimized in each level, the BLOP becomes a multi-objective task and more computationally costly as the optimum corresponds to a whole non-dominated solution set, called the PF (Pareto Front). Despite the considerable number of recent works in multi-objective evolutionary bi-level optimization, the number of methods that could be applied to the combinatorial (discrete) case is much reduced. Motivated by this observation, we propose in this paper an Indicator-Based version of our recently proposed Co-Evolutionary Migration-Based Algorithm (CEMBA), that we name IB-CEMBA, to solve combinatorial multi-objective BLOPs. The indicator-based search choice is justified by two arguments. On the one hand, it allows selecting the solution having the maximal marginal contribution in terms of the performance indicator from the lower-level PF. On the other hand, it encourages both convergence and diversity at the upper-level. The comparative experimental study reveals the outperformance of IB-CEMBA on a multi-objective bi-level production-distribution problem. From the effectiveness viewpoint, the upper-level hyper-volume values and inverted generational distance ones vary in the intervals [0.8500, 0.9710] and [0.0072, 0.2420], respectively. From the efficiency viewpoint, IB-CEMBA has a good reduction rate of the Number of Function Evaluations (NFEs), lying in the interval [30.13%, 54.09%]. To further show the versatility of our algorithm, we have developed a case study in machine learning, and more specifically we have addressed the bi-level multi-objective feature construction problem.

Keywords

• Combinatorial bi-level multi-objective optimization
• computational cost
• indicator-based evolutionary algorithms
• population decomposition
• migration schemes