2021

Conférence

IEEE Congress on Evolutionary Computation, 1627-1634

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.

@inproceedings{abbassi2021approximation,
  title={An approximation-based chemical reaction algorithm for combinatorial multi-objective bi-level optimization problems},
  author={Abbassi, Malek and Chaabani, Abir and Said, Lamjed Ben and Absi, Nabil},
  booktitle={2021 IEEE Congress on Evolutionary Computation (CEC)},
  pages={1627--1634},
  year={2021},
  organization={IEEE}
}