I. Introduction
Bi-level multi-objective optimization problems deal with minimizing (or maximizing) sequentially two interactive decision making levels: (1) the upper level problem (the leader) and (2) the lower level problem (the follower). In this framework, two Decision Makers (DMs. i.e. the leader and the follower) collaborate to ensure the bi-level optimization process. Many real-life applications have inherent hierarchical structure with multiple conflicting objectives can be modeled as bi-level multi-objective problems such as: supply chain [14], program debugging [8], web service [15], etc. However, this research area still lacks methods able to solve efficiently such kind of NP-hard problems. The complexity imposed by a BLOP is explained mainly by the hierarchical decision process between the two involved DMs which may present different difficulties: (1) there is no explicit formulation to evaluate the solution, (2) the solution evaluation depends on the follower’s reaction, (3) the complex interaction between the DMs, and (4) the presence of conflicting objective at one or both levels [19]. This type (MBLOPs) of optimization problems includes three variants: (1) the multiple conflicting objectives are only handled by the upper level, (2) the multiple conflicting objectives are only handled by the lower level, and (3) the multiple conflicting objectives are handled by both levels. We treat through this work MBLOPs with multi-objective optimization task at both upper and lower levels. In this context, the evaluation of one upper level solution depends on the follower’s reaction in which the optimum corresponds to a set of trade-off optimal solutions. This fact complicates the task for the leader which is constrained by the optimal trade-off solutions of the follower. This interlinked interaction increases the computational cost of the evaluation process leading frequently to an NP-hard problem [16]. A number of classical and evolutionary methods have been investigated to solve bi-level multi-objective optimization problems. In the area of classical optimization, we observe extensive research studies solving bi-level problems such as: the Karush-Kuhn-Tucker (KKT) approaches [6], the descent methods [16], the trust region methods [7], etc. However, these methods are still sensitive to a set of regularity properties such as linearity, convexity or smoothness assumptions [6]. This fact makes them inapplicable for complex non-convex, non-linear or large dimensional MBLOPs. Regarding Evolutionary Algorithms (EAs), there exists a panoply of methods. These algorithms have shown their effectiveness to solve such problems, despite, they necessitate a huge number of FEs [18]. For example, if an upper level population is evolved for 50 generations with 50 individuals, and the lower level evolves also 50 individuals for 50 generations, the total number of FEs will be 6.25 million (504). Attempts have been made to address this issue such as: Ankhili [4], Deb and Sinha [9] and have proven their efficiency to reduce the number of FEs. However, these solution methods are applicable only for the continuous research area. Recently, we have proposed a new EA, inspired from CRO algorithm [13], called BMCRO [3] to tackle MBLOPs with single objective lower level task. Our proposal has shown its efficiency in generating good bi-level multi-objective solutions with less number of FEs. Thus, in this paper, we aim to address the most difficult variant of MBLOPs (multi-objective upper and lower problem) exploiting the results reached by our previous work in order to build a robust method. Our proposed algorithm termed BMCROII, uses an approximation technique in order to handle the complex interaction between levels aiming to reach the best lower-level reaction with less number of FEs. This approximation technique is based on our proposed Lower Sub-set Approximation (LSA) [2] which reduces the lower-level Pareto front to a representative subset in the upper level evaluation. It is important to clarify here that the entire Pareto front is saved in an archive Ar and is injected in the new parent upper level population in the environmental replacement step. To this end, a nested evolutionary approach is proposed in this work exploiting the strengths of both the BMCRO approach and the LSA technique to solve combinatorial MBLOPs with multiple conflicting objectives at both levels. We summarize the main contributions of this paper as follows:
Proposing a new extension of BMCRO to solve efficiently MBLOPs with two multi-objective optimization tasks. We note that the use of an approximation technique can reduce the number of FEs and consequently the computational cost, which may increase the scalability of BMCROII in handling large or high dimensional variants of the problems.
Demonstrating the out-performance of BMCROII over other developed extensions of bi-level multi-objective algorithms. We report statistical results with the compared algorithms for solving the multi-objective BMDVRP, which is a well-studied problem in operations research.