An Approximation-based Chemical Reaction Algorithm for Combinatorial Multi-Objective Bi-level Optimization Problems

Multi-objective Bi-Level Optimization Problem (MBLOP) is defined as a mathematical program where one multi-objective optimization task is constrained with another one. In this way, the evaluation of a single upper level solution necessitates the evaluation of the whole lower level problem. This fact brings new complexities to the bi-level framework, added to the conflicting objectives and their evaluation which need a large number of Function Evaluations (FEs). Despite the number of works dedicated to solve bi-level optimization problems, the number of methods applied to the multi-objective combinatorial case is much reduced. Motivated by these observations, we propose in this paper an approximation-based version of our recently proposed Bi-level Multi-objective Chemical Reaction Optimization (BMCRO), which we called BMCROII. The approximation technique is adopted here as a surrogate to the lower level leading then to generate efficiently the lower level optimality. Our choice is justified by two main arguments. First, BMCRO applies a Quick Non-Dominated Sorting Algorithm (Q-NDSA) with quasi-linear computational time complexity. Second, the number of FEs savings gained by the approximation technique can hugely improve the whole efficiency of the method. The proposed algorithm is applied to a new multi-objective formulation of the well-known Bi-level Multi Depot Vehicle Routing Problem (BMDVRP). The statistical analysis demonstrates the outperformance of our algorithm compared to prominent baseline algorithms available in literature. Indeed, a large number of savings are detected which confirms the merits of our proposal for solving such type of NP-hard problems.

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 (50⁴). 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 A_r 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: 1)

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.

2)

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.