A hybrid population-based algorithm for the bi-objective quadratic multiple knapsack problem

Meziane Aider (1) , Oussama Gacem (2) , Mhand Hifi (3)

1 LAROMAD - Laboratoire de Recherche Opérationnelle et de Mathématique de la Décision [Tizi-Ouzou]
2 USTHB - Université des Sciences et de la Technologie Houari Boumediene = University of Sciences and Technology Houari Boumediene [Alger]
3 EPROAD - Eco-Procédés Optimisation et Aide à la Décision - UR UPJV 4669

In this paper, the bi-objective quadratic multiple knapsack problem is tackled with a hybrid population-based method. The proposed method starts by computing two reference solutions, where a specialized powerful mono-objective algorithm is used. From both reference solutions, a starting population is built by using a series of perturbations around the solutions. Next, the so-called non-sorting genetic process is combined with a new drop/rebuild operator for generating a series of populations till converging toward an approximate Pareto front with high density. The performance of the hybrid population based algorithm (namely HBPA) is evaluated on a set of benchmark instances of the literature containing both medium and large-scale instances. Its provided results are compared to those achieved by the best methods available in the literature. Encouraging results have been obtained.

Domaines: Informatique [cs]

Meziane Aider, Oussama Gacem, Mhand Hifi. A hybrid population-based algorithm for the bi-objective quadratic multiple knapsack problem. Expert Systems with Applications, 2022, 191, ⟨10.1016/j.eswa.2021.116238⟩. ⟨hal-03617877⟩