A HYBRIDIZED MULTI-OBJECTIVE MEMETIC ALGORITHM FOR THE MULTI-OBJECTIVE STOCHASTIC QUADRATIC KNAPSACK PROBLEM
Amina Guerrouma, Méziane Aı̈der · Pesquisa Operacional · 2022
The knapsack problem is basic in combinatorial optimization and possesses several variants and expansions.In this paper, we focus on the multi-objective stochastic quadratic knapsack problem with random weights.We propose a Multi-Objective Memetic Algorithm With Selection Neighborhood Pareto Local Search (MASNPL).At each iteration of this algorithm, crossover, mutation, and local search are applied to a population of solutions to generate new solutions that would constitute an offspring population.Then, we use a selection operator for the best solutions to the combined parent and offspring populations.The principle of the selection operation relies on the termination of the non-domination rank and the crowding distance obtained respectively by the Non-dominated Sort Algorithm and the Crowding-Distance Computation Algorithm.To evaluate the performance of our algorithm, we compare it with both an exact algorithm and the NSGA-II algorithm.Our experimental results show that the MASNPL algorithm leads to significant efficiency.